Andreas Krey <a.krey@xxxxxx> writes: > 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 -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html