From 2d898893815a980f1b821fcec267eb8e7ded678e Mon Sep 17 00:00:00 2001
From: Justus Winter <4winter@informatik.uni-hamburg.de>
Date: Thu, 8 May 2014 15:45:00 +0200
Subject: libihash: use an integer hash function on the keys

Use an integer hash function to derive the index from the key.  This
should reduce the number of collisions.

* libihash/ihash.c (hash_int32): New function.
(find_index): Use hash_int32 on the key to derive the index.
(add_one): Likewise.
---
 libihash/ihash.c | 17 +++++++++++++++--
 1 file changed, 15 insertions(+), 2 deletions(-)

diff --git a/libihash/ihash.c b/libihash/ihash.c
index d670fee2..71ddc26d 100644
--- a/libihash/ihash.c
+++ b/libihash/ihash.c
@@ -80,6 +80,19 @@ static const uint64_t ihash_sizes[] =
 static const unsigned int ihash_nsizes = (sizeof ihash_sizes
 					  / sizeof ihash_sizes[0]);
 
+
+/* This is the integer finalizer from MurmurHash3.  */
+static inline uint32_t
+murmur3_mix32 (uint32_t h, unsigned int bits)
+{
+  h ^= h >> 16;
+  h *= 0x85ebca6b;
+  h ^= h >> 13;
+  h *= 0xc2b2ae35;
+  h ^= h >> 16;
+
+  return h >> (32 - bits);
+}
 
 /* Return 1 if the slot with the index IDX in the hash table HT is
    empty, and 0 otherwise.  */
@@ -111,7 +124,7 @@ find_index (hurd_ihash_t ht, hurd_ihash_key_t key)
   unsigned int up_idx;
   unsigned int down_idx;
 
-  idx = key % ht->size;
+  idx = murmur3_mix32 (key, 32) % ht->size;
 
   if (ht->items[idx].value == _HURD_IHASH_EMPTY || ht->items[idx].key == key)
     return idx;
@@ -264,7 +277,7 @@ add_one (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t value)
   unsigned int idx;
   unsigned int first_free;
 
-  idx = key % ht->size;
+  idx = murmur3_mix32 (key, 32) % ht->size;
   first_free = idx;
 
   if (ht->items[idx].value != _HURD_IHASH_EMPTY && ht->items[idx].key != key)
-- 
cgit v1.2.3