Re: Object hash (was: Re: [ANNOUNCE] git-rev-size: calculate sizes of repository)

From: Johannes Schindelin <johannes.schindelin@gmx.de>
Date: Aug 20, 2006, 16:51 UTC
Message-ID: <Pine.LNX.4.63.0608201846110.28360@wbgn013.biozentrum.uni-wuerzburg.de>
In-Reply-To: <200608201837.33577.Josef.Weidendorfer@gmx.de>

Hi,

On Sun, 20 Aug 2006, Josef Weidendorfer wrote:

Show 9 quoted lines

> On Sunday 20 August 2006 18:09, Johannes Schindelin wrote:
> 
> > +static unsigned int hash_index(struct hash_map *hash, const char *sha1)
> > +{
> > +	unsigned int index = *(unsigned int *)sha1;
> 
> If you have the same SHA1, stored at different addresses, you get different
> indexes for the same SHA1. Index probably should be calculated from the
> SHA1 string.

Actually, it does! "*(unsigned int *)sha1" means that the first 4 bytes of the sha1 are interpreted as a number.

Show 6 quoted lines

> > +void hash_put(struct hash_map *hash, struct object *obj)
> > +{
> > +	if (++hash->nr > hash->alloc / 2)
> > +		grow_hash(hash);
> 
> If you insert the same object multiple times, hash->nr will get too big.

First, you cannot put the same object multiple times. That is not what a hash does (at least in this case): it stores unique objects (identified by their sha1 in this case). If you put another object with the same sha1, the first will be replaced.

Second, since you call hash_put() once per object, hash->nr cannot grow too big, because grow_hash() doubles hash->alloc. And I call grow_hash() once the hash map is half-full; Somebody once told me that would be the optimal growing strategy.

Ciao,
Dscho