Subject: Re: [[PATCH v2] 4/4] rebase: avoid computing unnecessary patch IDs

From: Junio C Hamano <[email-masked]>
Date: Tue, 02 Aug 2016 10:06:19 -0700

Jakub Narębski <[email-masked]> writes:

> The problem is that one expects hashmap_cmp_fn() to return ==0 on equality,
> while one would expect for hashmap_eq_fn() to return true (==1) on equality.
> So we would have to rewrite all calling sites.

Yes, and I do not think it is a "problem".  There only are about a
dozen callsites of hashmap_init().

> It would be nice to have a comment about how hashmap uses cmpfn in
> hashmap.h.  

That is the absolute minimum but I think that is already done in the
Documentation/technical/api-hashmap.txt.

> Though... currently our hashmap implementation uses linked
> list (separate chaining) for handling hash collisions (for collision
> resolution). More sophisticated data structures, such as balanced search
> trees,...

But that requires total ordering of the elements registered in a
hashmap.  So far, because cmp_fn that was misnamed was only about
equality, you can safely use a hashmap to store things that do not
have inherent order among them.  Besides, if your hashmap has to
optimize the hash collision resolution part with complex strucure,
your hash function is bad or your hash bucket growing strategy is
suboptimal, or both, which is the first thing you should look at,
not the "now how would we find it in the bucket with too many
things?"