Re: kernel.org now has gitweb installed

[David Woodhouse <dwmw2@infradead.org>]

On Thu, 2005-04-28 at 09:29 +0100, David Woodhouse wrote:
> Let us assume that C and A were already in Linus' tree (and on our web
> page) yesterday. Thus, they should be last. The newly-pulled stuff
> should be first -- FEDBCA.
> 
> I'd say "depth-first, remote parent first" but that would actually show
> show 'A' (as a parent of D) long before it shows C. Walking of remote
> parents should stop as soon as we hit a commit which was accessible
> through a more local parent, rather than as soon as we hit a commit
> which we've already printed.

Walk the tree once. For each commit, count the number of _children_.
That's not hard -- each new commit you find below HEAD has one child to
start with, then you increment that figure by one each time you find
another path to the same commit.

When printing, you walk the tree depth-first, remote-parent-first. If
you hit a commit with multiple children, decrement its count by one. If
the count is still non-zero, ignore that commit (and its parents) and
continue. If the count _is_ zero, then this is the "most local" path to
the commit in question, so print it and continue to process its
parents...

(Actually I'd probably do it by adding real pointers to the children
instead of using a counter. Operations like convert-cache would be far
better off working that way round, and 'cg comments' is going to need to
do something very similar to convert-cache.)

-- 
dwmw2