Re: [PATCH/RFC 1/5] add a hashtable implementation that supports O(1) removal

From: Junio C Hamano <gitster@pobox.com>
Date: Sep 11, 2013, 23:56 UTC
Message-ID: <xmqqtxhqrjzf.fsf@gitster.dls.corp.google.com>
In-Reply-To: <522FAB19.3080704@gmail.com>

Karsten Blees <karsten.blees@gmail.com> writes:

Show 7 quoted lines

> +#define FNV32_BASE ((unsigned int) 0x811c9dc5)
> +#define FNV32_PRIME ((unsigned int) 0x01000193)
> + ...
> +static inline unsigned int bucket(const hashmap *map, const hashmap_entry *key)
> +{
> +	return key->hash & (map->tablesize - 1);
> +}

As tablesize would hopefully be reasonably small, not worrying about platforms' "unsigned int" being 64-bit (in which case it would be more appropriate to compute with FNV64_PRIME) should be fine.

Show 8 quoted lines

> +static inline hashmap_entry **find_entry(const hashmap *map,
> +		const hashmap_entry *key)
> +{
> +	hashmap_entry **e = &map->table[bucket(map, key)];
> +	while (*e && !entry_equals(map, *e, key))
> +		e = &(*e)->next;
> +	return e;
> +}

(mental note) This finds the location the pointer to the entry is stored, not the entry itself.

> +void *hashmap_get(const hashmap *map, const void *key)
> +{
> +	return *find_entry(map, key);
> +}

... which is consistent with this, and more importantly, it is crucial for hashmap_remove()'s implementation, because...

Show 10 quoted lines

> +void *hashmap_remove(hashmap *map, const void *key)
> +{
> +	hashmap_entry *old;
> +	hashmap_entry **e = find_entry(map, key);
> +	if (!*e)
> +		return NULL;
> +
> +	/* remove existing entry */
> +	old = *e;
> +	*e = old->next;

... this wants to update the linked list in place.

Looking good.

I however wonder if the singly linked linear chain is a really good alternative for the access pattern of the hashes we use, though. Do we really want to trigger growth on the bucket load factor, not the length of the longest chain, for example?

Show 7 quoted lines

> +	old->next = NULL;
> +
> +	/* fix size and rehash if appropriate */
> +	map->size--;
> +	if (map->tablesize > HASHMAP_INITIAL_SIZE &&
> +		map->size * HASHMAP_SHRINK_AT < map->tablesize)
> +		rehash(map, map->tablesize >> HASHMAP_GROW);

Please align the first two lines so that the first non-whitespace on the second line of the condition part of the "if" statement (i.e. 'm') aligns with the first non-whitespace inside the '(' open parenthesis (i.e. 'm').