Re: Consistency question

From: David Kastrup <dak@gnu.org>
Date: Jan 15, 2014, 13:00 UTC
Message-ID: <87ppnt7635.fsf@fencepost.gnu.org>
In-Reply-To: <20140115124434.GA27030@inner.h.apk.li>

Andreas Krey <a.krey@gmx.de> writes:

Show 10 quoted lines

> On Wed, 15 Jan 2014 12:40:29 +0000, David Kastrup wrote:
> ...
>> With a single root, "depth" helps a lot.  When looking for a common
>> parent of a number of commits, you first shorten all ancestries to the
>> same size and then you can look for the point of convergence in
>> lockstep.
>
> Hmm, how about traversing from all the start commits downwards
> simultaneously, noting which start you say each commit from, and stopping
> when you have a commit carrying all start labels?

It means that when the start commits are at considerably different depth, you'll traverse much more material than necessary.

Also you need labels.

> I don't quite see how the same size plus lockstep works out (but the
> 'same size' part is possibly the same as my 'concurrent traversal').

It just equalizes the depth before starting, so you don't need labels: any common ancestor is reached at the same time by its descendants.

Of course, I conveniently forgot merge commits. This scheme works out of the box only with single parenting. And it works fine without a common ancestor, too: you just run into a NULL pointer at the same time when there isn't one.

So, uh, this solution does not really seem to match the problem...

-- 
David Kastrup