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

From: Johannes Schindelin <johannes.schindelin@gmx.de>
Date: Jun 6, 2008, 12:30 UTC
Message-ID: <alpine.DEB.1.00.0806061305490.1783@racer>
In-Reply-To: <7vk5h3xlt9.fsf@gitster.siamese.dyndns.org>

Hi,

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

Show 11 quoted lines

> 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