Change de API of the hash table to allow arbitrary key length

• Provide a new set of functions to the hash table:

  • key_hash takes a key, and provides a hash between 0 and 2<<nbits-1

  • key_print provides a human-readable version of the key (used for debugging purposes)

  • key_equal compares two keys (returns 1 iff they are equal)

• Use nbits instead of size to define the number of buckets

  • This introduces a restriction on the hash tables, but the dynamic strategy doubles every time anyway, and this enables fast hash functions that use shifts and masks instead of modulo

The hash table is as before: we start with a small one, and create larger ones as the current one fills up; we never add elements in old tables, but search them in those, and when they become empty we skip the old tables for searching (we only free them when the main table is destroyed, to avoid ABA race conditions).

To avoid calling key_equal too often (this is costly), we use a 64-bits (largest possible) hash for each element, and first compare to this key before calling equal (only if the 64 bits hash are equal). We also create lower number of bits hashs to split the elements between the buckets.

Performance comparison using the tests/units/hash.c benchmark show that performance degradation compared to the previous version of the hash tables is negligible.

Here is a comparison on a00 (2x Haswell E5-2650 v3) using hash benchmark tests/units/hash.c. The benchmark compares inserting a fixed number of elements (300 x 30000) and removing them with a parameterized number of threads. Threads are de-synchronized so some removing happens in concurrence with some insertion. The benchmark returns the overall completion time. It shows that the use of the new API (AKL) does not degrade performance significantly (except for the 1 thread case).