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

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

>>> 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