diffcore-order: export generic ordering interface

diffcore_order() interface only accepts a queue of `struct
diff_filepair`.

In the next patches, we'll want to order `struct combine_diff_path`
by path, so let's first rework diffcore-order to also provide
generic low-level interface for ordering arbitrary objects, provided
they have path accessors.

The new interface is:

    - `struct obj_order`    for describing objects to ordering routine, and
    - order_objects()       for actually doing the ordering work.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
diff test: add tests for combine-diff with orderfile

In the next patch combine-diff will have special code-path for taking
orderfile into account. Prepare for making changes by introducing
coverage tests for that case.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
combine-diff: optimize combine_diff_path sets intersection

When generating combined diff, for each commit, we intersect diff
paths from diff(parent_0,commit) to diff(parent_i,commit) comparing
all paths pairs, i.e. doing it the quadratic way. That is correct,
but could be optimized.

Paths come from trees in sorted (= tree) order, and so does diff_tree()
emits resulting paths in that order too. Now if we look at diffcore
transformations, all of them, except diffcore_order, preserve resulting
path ordering:

    - skip_stat_unmatch, grep, pickaxe, filter
                            -- just skip elements -> order stays preserved

    - break                 -- just breaks diff for a path, adding path
                               dup after the path -> order stays preserved

    - detect rename/copy    -- resulting paths are emitted sorted
                               (verified empirically)

So only diffcore_order changes diff paths ordering.

But diffcore_order meaning affects only presentation - i.e. only how to
show the diff, so we could do all the internal computations without
paths reordering, and order only resultant paths set. This is faster,
since, if we know two paths sets are all ordered, their intersection
could be done in linear time.

This patch does just that.

Timings for `git log --raw --no-abbrev --no-renames` without `-c` ("git log")
and with `-c` ("git log -c") before and after the patch are as follows:

                linux.git v3.10..v3.11

            log     log -c

    before  1.9s    20.4s
    after   1.9s    16.6s

                navy.git    (private repo)

            log     log -c

    before  0.83s   15.6s
    after   0.83s    2.1s

P.S.

I think linux.git case is sped up not so much as the second one, since
in navy.git, there are more exotic (subtree, etc) merges.

P.P.S.

My tracing showed that the rest of the time (16.6s vs 1.9s) is usually
spent in computing huge diffs from commit to second parent. Will try to
deal with it, if I'll have time.

P.P.P.S.

For combine_diff_path, ->len is not needed anymore - will remove it in
the next noisy cleanup path, to maintain good signal/noise ratio here.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
combine-diff: combine_diff_path.len is not needed anymore

The field was used in order to speed-up name comparison and also to
mark removed paths by setting it to 0.

Because the updated code does significantly less strcmp and also
just removes paths from the list and free right after we know a path
will not be needed, it is not needed anymore.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
combine-diff: simplify intersect_paths() further

Linus once said:

    I actually wish more people understood the really core low-level
    kind of coding. Not big, complex stuff like the lockless name
    lookup, but simply good use of pointers-to-pointers etc. For
    example, I've seen too many people who delete a singly-linked
    list entry by keeping track of the "prev" entry, and then to
    delete the entry, doing something like

	if (prev)
	    prev->next = entry->next;
	else
	    list_head = entry->next;

    and whenever I see code like that, I just go "This person
    doesn't understand pointers". And it's sadly quite common.

    People who understand pointers just use a "pointer to the entry
    pointer", and initialize that with the address of the
    list_head. And then as they traverse the list, they can remove
    the entry without using any conditionals, by just doing a "*pp =
    entry->next".

Applying that simplification lets us lose 7 lines from this function
even while adding 2 lines of comment.

I was tempted to squash this into the original commit, but because
the benchmarking described in the commit log is without this
simplification, I decided to keep it a separate follow-up patch.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
Merge branch 'ks/diff-c-with-diff-order' into next

Teach combine-diff to honour the path-output-order imposed by
diffcore-order.

* ks/diff-c-with-diff-order:
  combine-diff: simplify intersect_paths() further
  combine-diff: combine_diff_path.len is not needed anymore
  combine-diff: optimize combine_diff_path sets intersection
  diff test: add tests for combine-diff with orderfile
  diffcore-order: export generic ordering interface