libihash: use linear probing and fast modulo operation

libihash uses open addressing.  Previously, quadratic probing in both
directions was used to resolve collisions.  Quadratic probing might
result in a less efficient use of caches.

Also, prime numbers of the form 4 * i + 3 were used as array sizes.
This was used in combination with the integer modulo operation for
hashing.  It has been known for some time that libihash suffers from
collisions, so a integer hash function is now applied to the keys to
derive the index.

Use linear probing instead.  Also, use powers of two for the array
sizes, so a bit mask can be used for the modulo operation.

* libihash/ihash.c (ihash_sizes, ihash_nsizes): Remove.
(find_index): Use linear probing and fast modulo operation.
(add_one): Likewise.
* libihash/ihash.h (HURD_IHASH_MIN_SIZE): New macro.

0 files changed, 0 insertions, 0 deletions