Re: Consistency question

Andreas Krey [off-list ref] writes:

On Wed, 15 Jan 2014 12:40:29 +0000, David Kastrup wrote:
...

quoted

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