From 57341e5be12f79ee1916369679bb6507a10fcac9 Mon Sep 17 00:00:00 2001
From: Justus Winter <4winter@informatik.uni-hamburg.de>
Date: Thu, 8 May 2014 18:33:57 +0200
Subject: 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.
---
 libihash/ihash.h | 4 ++++
 1 file changed, 4 insertions(+)

(limited to 'libihash/ihash.h')

diff --git a/libihash/ihash.h b/libihash/ihash.h
index a24f384d..8829e51e 100644
--- a/libihash/ihash.h
+++ b/libihash/ihash.h
@@ -93,6 +93,10 @@ typedef struct hurd_ihash *hurd_ihash_t;
 
 /* Construction and destruction of hash tables.  */
 
+/* The size of the initial allocation in number of items.  This must
+   be a power of two.  */
+#define HURD_IHASH_MIN_SIZE	32
+
 /* The default value for the maximum load factor in percent.  */
 #define HURD_IHASH_MAX_LOAD_DEFAULT 75
 
-- 
cgit v1.2.3