Re: [PATCH 09/10] Introduce get_octopus_merge_bases() in commit.c

[Johannes Schindelin <Johannes.Schindelin@gmx.de>]

Hi,

On Thu, 5 Jun 2008, Junio C Hamano wrote:

> Miklos Vajna <vmiklos@frugalware.org> writes:
> 
> > This is like get_merge_bases() but it works for multiple heads, like
> > show-branch --merge-base.
> 
> In what sense is this "like show-branch --merge-base"?
> 
> The only similarlity I can spot is that it can take more than two heads, 
> but what it computes and the way it computes it seem to be different.  
> It certainly looks much less efficient as it does not walk the ancestry 
> chain in one-go like show-branch does.

Ah, you are right.  I thought that in the typical case (where the initial 
commits are independent), it will never traverse any commit twice.  I did 
not really understand your example quickly enough, so I made up my own:

A - B - C - D - E
  \           X
    F - G - H   I
      \   X   \
        J   \   K
             \
              - L 

Now, let's get the merge bases with Miklos' algorithm for E, I, K and L.

First it will find the merge base for E and I, which is D.  Then it 
calculates the merge base between that merge base and the third head, K, 
which leads us all the way back to A.

Now, calculating the merge base between that merge base and L will 
traverse the commits F, G and H _again_.

Ciao,
Dscho