get_merge_bases_many(): walk from many tips in parallel
authorJunio C Hamano <gitster@pobox.com>
Thu, 30 Aug 2012 22:35:39 +0000 (15:35 -0700)
committerJunio C Hamano <gitster@pobox.com>
Fri, 31 Aug 2012 00:25:57 +0000 (17:25 -0700)
commit94f0ced0d08c8f835992b82224231b9353490e0c
tree8a35b4a73d042fb2f762d2a112f86d6212210632
parent6440fdbab430bc10fdac37e86ae25607c93d3903
get_merge_bases_many(): walk from many tips in parallel

The get_merge_bases_many() function reduces the result returned by
the merge_bases_many() function, which is a set of possible merge
bases, by excluding commits that can be reached from other commits.
We used to do N*(N-1) traversals for this, but we can check if one
commit reaches which other (N-1) commits by a single traversal, and
repeat it for all the candidates to find the answer.

Introduce remove_redundant() helper function to do this painting; we
should be able to use it to reimplement reduce_heads() as well.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
commit.c