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

From: Jakub Narębski <jnareb@gmail.com>
Date: Aug 2, 2016, 09:50 UTC
Message-ID: <8ec80c21-5ab1-d806-d8d6-e7180be00670@gmail.com>
In-Reply-To: <xmqqtwf4i71l.fsf@gitster.mtv.corp.google.com>

W dniu 01.08.2016 o 22:11, Junio C Hamano pisze:

> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
>> On Fri, 29 Jul 2016, Junio C Hamano wrote:

Show 12 quoted lines

>>> These error returns initially looks slightly iffy in that in general
>>> the caller of any_cmp_fn() wants to know how a/b compares, but by
>>> returning error(), it always says "a is smaller than b".
>>
>> I am to blame, as this is my design.
>>
>> And yes, it is kind of funny that we require a cmpfn that returns <0, ==0
>> and >0 for comparisons, when hashmaps try to avoid any order.
> 
> Perhaps hashmap API needs fixing in the longer term not to call this
> type hashmap_cmp_fn; instead it should lose cmp and say something
> like hashmap_eq_fn or something.

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.

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

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, or splay trees, are worth considering only if the load factor is large, or if the hash distribution is likely to be very non-uniform, or if one must guarantee good performance even in a worst-case scenario. So almost certainly comparing function (which is needed for trees) won't be needed.

Best,

-- 
Jakub Narębski