move patience data out of struct diff_atom Now allocating patience specific data only when patience is going to be used. This may allow using forward-Myers more often, since the state size per line is significantly smaller. Patience instead allocates an array, puts it in the current diff_data, and also place a pointer of the current diff_data in the root diff_data (since each atom points to the root diff_data).

patience: use qsort to optimize finding unique lines

rename diff_atom->d to diff_atom->root, because it always is The idea was that for each diff box within the files, the atoms would have a backpointer to the current layer of diff_data (indicating the current section), but it is not actually needed to update the backpointer in each atom to the current diff_data. That is why the current code always points atom->d to the root diff_data for the entire file. Clarify by proper name. Constructs like atom->d->root->foo are redundant, just use atom->root->foo.

add results_test.c

optionally provide information about the generated diff to the API user

move some definitions from the public diff_main.h to an internal header file