Re: kernel.org now has gitweb installed

From: David Woodhouse <dwmw2@infradead.org>
Date: Apr 28, 2005, 09:23 UTC
Message-ID: <1114680199.12012.363.camel@baythorne.infradead.org>
In-Reply-To: <1114676955.12012.346.camel@baythorne.infradead.org>

On Thu, 2005-04-28 at 09:29 +0100, David Woodhouse wrote:

Show 9 quoted lines

> 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