Re: [PATCH 07/10] rev-list: call new "filter_skip" function

From: Johannes Schindelin <johannes.schindelin@gmx.de>
Date: Mar 31, 2009, 09:23 UTC
Message-ID: <alpine.DEB.1.00.0903311117400.10279@pacific.mpi-cbg.de>
In-Reply-To: <200903310845.23674.chriscool@tuxfamily.org>

Hi,

On Tue, 31 Mar 2009, Christian Couder wrote:

Show 20 quoted lines

> Le lundi 30 mars 2009, Johannes Schindelin a écrit :
>
> > On Mon, 30 Mar 2009, Christian Couder wrote:
> > > Le jeudi 26 mars 2009, Junio C Hamano a écrit :
> > > >
> > > > I've learned to suspect without reading a qsort() callback that 
> > > > does not derefence its arguments.  Is this doing the right thing?
> > >
> > > I think so.
> >
> > I suspect something much worse: you are trying to build a list of 
> > sha1s of commits that need to be skipped, later to look up every 
> > commit via binary search.
> >
> > But it has been proven a lot of times that using a hash set is 
> > superior to that approach, and even better: we already have the 
> > framework in place in the form of struct decorate.
> 
> I had a look, and "struct decorate" can be used to store objects, but I 
> want to store only sha1s.

No, you want to _look up_ sha1s. And struct decorate is not about storing objects, but to attach things to objects. From decorate.h:

	struct object_decoration {
	        const struct object *base;
	        void *decoration;
	};

So, if you just do

	struct decoration all_the_sha1s;

...

		add_decoration(&all_the_sha1s, &commit->object, sha1);

you can look up the sha1 much more efficiently than with binary searches like this:

		unsigned char *sha1 = lookup_decoration(&all_the_sha1s,
			&commit->object);

Ciao, Dscho