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

From: Junio C Hamano <gitster@pobox.com>
Date: Aug 2, 2016, 17:06 UTC
Message-ID: <xmqqoa5bf6d0.fsf@gitster.mtv.corp.google.com>
In-Reply-To: <8ec80c21-5ab1-d806-d8d6-e7180be00670@gmail.com>

Jakub Narębski <jnareb@gmail.com> 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?"