From: Daniel Barkalow <barkalow@iabervon.org>
Date: Thu, 25 Oct 2007 20:23:37 GMT
Subject: Re: [PATCH 5/6] Do linear-time/space rename logic for exact renames
Message-ID: <Pine.LNX.4.64.0710251606280.7345@iabervon.org>
In-Reply-To: <20071025194859.GB27745@coredump.intra.peff.net>

On Thu, 25 Oct 2007, Jeff King wrote:

> On Thu, Oct 25, 2007 at 03:43:46PM -0400, Daniel Barkalow wrote:
> 
> > Creating a list of the pointers doesn't work correctly with the grow 
> > implementation, because growing the hash may turn a collision into a 
> > non-collision, at which point items other than the first cannot be found 
> > (since they're listed inside a bucket that's now wrong for them). AFAIK, 
> > resizing a hash table requires being able to figure out what happened with 
> > collisions.
> 
> I thought this at first, too, but there are two types of collisions in
> this hash implementation: those that come from having the actual 32-bit
> hash collide, and those that come from not having enough buckets.
> 
> The client code gets a pointer kicked back to it when there is a
> collision on the actual hash value (i.e., two things had the exact same
> hash value). The number of buckets grows when you simply have more
> buckets filled than you like. Two different hashes that would be in the
> same bucket don't actually occupy the same bucket -- the second one to
> arrive gets shoved into the next available bucket.

Ah, right, nevermind. The comment might be a bit misleading in that case, 
if we both missed this at first.

	-Daniel
*This .sig left intentionally blank*