Re: Change set based shallow clone

From: Jeff King <peff@peff.net>
Date: Sep 9, 2006, 20:43 UTC
Message-ID: <20060909204307.GB16906@coredump.intra.peff.net>
In-Reply-To: <Pine.LNX.4.64.0609091256110.27779@g5.osdl.org>

On Sat, Sep 09, 2006 at 01:05:42PM -0700, Linus Torvalds wrote:

Show 17 quoted lines

> The example is
> 
> 		    A		<--- tip of branch
> 		   / \
> 		  B   E
>                 |   |
> 		  |   F
> 		  | /
> 		  C 
> 		  |
> 		  D
> 		...
> 
> where the lettering is in "date order" (ie "A" is more recent than "B" 
> etc). In this situation, we'd start following the branch A->B->C->D->.. 
> before we even start looking at E and F, because they all _look_ more 
> recent.

I'm just coming into this discussion in the middle and know very little about the rev-list code, so please humor me and tell me why my suggestion is completely irrelevant.

The problem you describe seems to come from doing a depth-first display
of each branch. Why not look at the tip of each "active" branch
simultaneously and pick the one with the most recent date? Something
like:
  void show_all(commit_array start)
  {
    commit_array active;

    copy_array(active, start);
    sort_array(active);
    while (active.size > 0) {
      show_commit(active.data[0]);
      push_back(active.data[0].parents);
      pop_front(active);
      sort_array(active);
    }
  }
Obviously you could use a specialized data structure to add nodes into
the right place instead of resorting constantly.

-Peff