add 0006-libihash-use-an-integer-hash-function-on-the-keys.patch

2 files changed, 67 insertions, 0 deletions

diff --git a/debian/patches/0006-libihash-use-an-integer-hash-function-on-the-keys.patch b/debian/patches/0006-libihash-use-an-integer-hash-function-on-the-keys.patch
new file mode 100644
index 00000000..1fcd7a31
--- /dev/null
+++ b/debian/patches/0006-libihash-use-an-integer-hash-function-on-the-keys.patch
@@ -0,0 +1,66 @@
+From 7849d265ce00e936df1a186647253cd2231d1c90 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: [PATCH 6/6] 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 | 23 +++++++++++++++++++++--
+ 1 file changed, 21 insertions(+), 2 deletions(-)
+
+diff --git a/libihash/ihash.c b/libihash/ihash.c
+index d670fee..1de4c35 100644
+--- a/libihash/ihash.c
++++ b/libihash/ihash.c
+@@ -81,6 +81,25 @@ static const unsigned int ihash_nsizes = (sizeof ihash_sizes
+ 					  / sizeof ihash_sizes[0]);
+ 
+ 
++/* Integer hashing follows Thomas Wang's paper about his 32/64-bits
++   mix functions :
++   -  http://www.concentric.net/~Ttwang/tech/inthash.htm  */
++static inline uint32_t
++hash_int32(uint32_t n, unsigned int bits)
++{
++  uint32_t hash;
++
++  hash = n;
++  hash = ~hash + (hash << 15);
++  hash ^= (hash >> 12);
++  hash += (hash << 2);
++  hash ^= (hash >> 4);
++  hash += (hash << 3) + (hash << 11);
++  hash ^= (hash >> 16);
++
++  return hash >> (32 - bits);
++}
++
+ /* Return 1 if the slot with the index IDX in the hash table HT is
+    empty, and 0 otherwise.  */
+ static inline int
+@@ -111,7 +130,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 = hash_int32 (key, 32) % ht->size;
+ 
+   if (ht->items[idx].value == _HURD_IHASH_EMPTY || ht->items[idx].key == key)
+     return idx;
+@@ -264,7 +283,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 = hash_int32 (key, 32) % ht->size;
+   first_free = idx;
+ 
+   if (ht->items[idx].value != _HURD_IHASH_EMPTY && ht->items[idx].key != key)
+-- 
+2.0.0.rc0
+
diff --git a/debian/patches/series b/debian/patches/series
index 5913ebff..bb1a6043 100644
--- a/debian/patches/series
+++ b/debian/patches/series
@@ -46,3 +46,4 @@ mach-defpager-protected-payload.patch
 0003-libports-lock-less-reference-counting-for-port_info-.patch
 0004-libdiskfs-lock-less-reference-counting-for-peropen-o.patch
 0005-libtrivfs-lock-less-reference-counting-for-trivfs_pr.patch
+0006-libihash-use-an-integer-hash-function-on-the-keys.patch