hurd-l4/libhurd-ihash ChangeLog ihash.c ihash.h

[Marcus Brinkmann]

CVSROOT:        /cvsroot/hurd
Module name:    hurd-l4
Branch:         
Changes by:     Marcus Brinkmann <address@hidden>       03/08/26 18:47:18

Modified files:
        libhurd-ihash  : ChangeLog ihash.c ihash.h 

Log message:
        2003-08-26  Marcus Brinkmann  <address@hidden>
        
        * ihash.h: Include <limits.h>.
        (HURD_IHASH_NO_LOCP): New macro.
        (HURD_IHASH_INITIALIZER): Take locp offset as argument.
        Initialize HT->nr_items, HT->max_load and HT->locp_offset.
        (HURD_IHASH_MAX_LOAD_DEFAULT): New macro.
        (struct _hurd_ihash_item): New structure.
        (_hurd_ihash_item_t): New type.
        (struct hurd_ihash): New fields NR_ITEMS, ITEMS, LOCP_OFFSET and
        MAX_LOAD.  Remove KEYS, TABLE and LOCPS.
        (hurd_ihash_set_max_load): New function.
        (HURD_IHASH_ITERATE): Rewrite to use ITEMS instead TABLE and KEYS.
        (hurd_ihash_init): Take locp_offs argument in prototype.
        (hurd_ihash_create): Likewise.
        (hurd_ihash_add): Don't take locp argument in prototype.
        (hurd_ihash_set_max_load): New prototype.
        * ihash.c (HASH, REHASH): Macros removed.
        (ihash_sizes): Change table to list prime numbers that are 3
        modulo 4.
        (index_empty): Use HT->items instead HT->table.
        (index_valid): Likewise.
        (find_index): Use quadratic probing.
        (locp_remove): New helper function.
        (hurd_ihash_init): Take locp_offs as argument.  Initialize
        HT->locp_offset, HT->nr_items and HT->max_load.
        (hurd_ihash_destroy): Free HT->items, but not anything else.
        (hurd_ihash_create): Take locp_offs as argument and pass it to
        hurd_ihash_init.
        (hurd_ihash_set_max_load): New function.
        (add_one): Don't take a locp argument anymore.  Use quadratic
        probing.  Call locp_remove instead duplicating the code.
        Increment HT->nr_items.
        (hurd_ihash_add): Don't take a locp argument anymore.  Check
        maximum load factor before adding element.  Use ITEMS and not KEYS
        and TABLE.  Don't allocate memory for locp.  Use calloc instead of
        malloc and initialization.
        (hurd_ihash_remove): Call locp_remove instead hurd_ihash_locp_remove.
        (hurd_ihash_locp_remove): Call locp_remove.

CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/hurd/hurd-l4/libhurd-ihash/ChangeLog.diff?tr1=1.3&tr2=1.4&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/hurd/hurd-l4/libhurd-ihash/ihash.c.diff?tr1=1.4&tr2=1.5&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/hurd/hurd-l4/libhurd-ihash/ihash.h.diff?tr1=1.6&tr2=1.7&r1=text&r2=text

Patches:
Index: hurd-l4/libhurd-ihash/ChangeLog
diff -u hurd-l4/libhurd-ihash/ChangeLog:1.3 hurd-l4/libhurd-ihash/ChangeLog:1.4
--- hurd-l4/libhurd-ihash/ChangeLog:1.3 Sun Aug 17 01:47:32 2003
+++ hurd-l4/libhurd-ihash/ChangeLog     Tue Aug 26 18:47:18 2003
@@ -1,3 +1,43 @@
+2003-08-26  Marcus Brinkmann  <address@hidden>
+
+       * ihash.h: Include <limits.h>.
+       (HURD_IHASH_NO_LOCP): New macro.
+       (HURD_IHASH_INITIALIZER): Take locp offset as argument.
+       Initialize HT->nr_items, HT->max_load and HT->locp_offset.
+       (HURD_IHASH_MAX_LOAD_DEFAULT): New macro.
+       (struct _hurd_ihash_item): New structure.
+       (_hurd_ihash_item_t): New type.
+       (struct hurd_ihash): New fields NR_ITEMS, ITEMS, LOCP_OFFSET and
+       MAX_LOAD.  Remove KEYS, TABLE and LOCPS.
+       (hurd_ihash_set_max_load): New function.
+       (HURD_IHASH_ITERATE): Rewrite to use ITEMS instead TABLE and KEYS.
+       (hurd_ihash_init): Take locp_offs argument in prototype.
+       (hurd_ihash_create): Likewise.
+       (hurd_ihash_add): Don't take locp argument in prototype.
+       (hurd_ihash_set_max_load): New prototype.
+       * ihash.c (HASH, REHASH): Macros removed.
+       (ihash_sizes): Change table to list prime numbers that are 3
+       modulo 4.
+       (index_empty): Use HT->items instead HT->table.
+       (index_valid): Likewise.
+       (find_index): Use quadratic probing.
+       (locp_remove): New helper function.
+       (hurd_ihash_init): Take locp_offs as argument.  Initialize
+       HT->locp_offset, HT->nr_items and HT->max_load.
+       (hurd_ihash_destroy): Free HT->items, but not anything else.
+       (hurd_ihash_create): Take locp_offs as argument and pass it to
+       hurd_ihash_init.
+       (hurd_ihash_set_max_load): New function.
+       (add_one): Don't take a locp argument anymore.  Use quadratic
+       probing.  Call locp_remove instead duplicating the code.
+       Increment HT->nr_items.
+       (hurd_ihash_add): Don't take a locp argument anymore.  Check
+       maximum load factor before adding element.  Use ITEMS and not KEYS
+       and TABLE.  Don't allocate memory for locp.  Use calloc instead of
+       malloc and initialization.
+       (hurd_ihash_remove): Call locp_remove instead hurd_ihash_locp_remove.
+       (hurd_ihash_locp_remove): Call locp_remove.
+       
 2003-08-17  Marcus Brinkmann  <address@hidden>
 
        * ihash.h (HURD_IHASH_INITIALIZER): New macro.
Index: hurd-l4/libhurd-ihash/ihash.c
diff -u hurd-l4/libhurd-ihash/ihash.c:1.4 hurd-l4/libhurd-ihash/ihash.c:1.5
--- hurd-l4/libhurd-ihash/ihash.c:1.4   Sun Aug 17 01:14:48 2003
+++ hurd-l4/libhurd-ihash/ihash.c       Tue Aug 26 18:47:18 2003
@@ -30,48 +30,48 @@
 #include <hurd/ihash.h>
 
 
-/* The odd prime numbers greater than twice the last and less than
-   2^40 (nobody needs more than 640 GB of memory).  */
+/* The prime numbers of the form 4 * i + 3 for some i, all greater
+   than twice the previous one and smaller than 2^40 (for now).  */
 static const uint64_t ihash_sizes[] =
 {
   3,
   7,
-  17,
-  37,
-  79,
-  163,
-  331,
-  673,
-  1361,
-  2729,
-  5471,
-  10949,
-  21911,
-  43853,
-  87719,
-  175447,
-  350899,
-  701819,
-  1403641,
-  2807303,
-  5614657,
-  11229331,
-  22458671,
-  44917381,
-  89834777,
-  179669557,
-  359339171,
-  718678369,
-  1437356741,
-  UINT64_C (2874713497),
-  UINT64_C (5749427029),
-  UINT64_C (11498854069),
-  UINT64_C (22997708177),
-  UINT64_C (45995416409),
-  UINT64_C (91990832831),
-  UINT64_C (183981665689),
-  UINT64_C (367963331389),
-  UINT64_C (735926662813)
+  19,
+  43,
+  103,
+  211,
+  431,
+  863,
+  1747,
+  3499,
+  7019,
+  14051,
+  28111,
+  56239,
+  112507,
+  225023,
+  450067,
+  900139,
+  1800311,
+  3600659,
+  7201351,
+  14402743,
+  28805519,
+  57611039,
+  115222091,
+  230444239,
+  460888499,
+  921777067,
+  1843554151,
+  UINT64_C (3687108307),
+  UINT64_C (7374216631),
+  UINT64_C (14748433279),
+  UINT64_C (29496866579),
+  UINT64_C (58993733159),
+  UINT64_C (117987466379),
+  UINT64_C (235974932759),
+  UINT64_C (471949865531),
+  UINT64_C (943899731087)
 };
 
 
@@ -79,23 +79,13 @@
                                          / sizeof ihash_sizes[0]);
 
 
-/* Return an initial index in the hash table HT for the key KEY, to
-   search for an entry.  */
-#define HASH(ht, key)          ((key) % (ht)->size)
-
-
-/* Return the next possible index in the hash table HT for the key
-   KEY, given the previous one.  */
-#define REHASH(ht, key, idx)   (((idx) + (key)) % (ht)->size)
-
-
 /* Return 1 if the slot with the index IDX in the hash table HT is
    empty, and 0 otherwise.  */
 static inline int
 index_empty (hurd_ihash_t ht, unsigned int idx)
 {
-  return ht->table[idx] == _HURD_IHASH_EMPTY
-    || ht->table[idx] == _HURD_IHASH_DELETED;
+  return ht->items[idx].value == _HURD_IHASH_EMPTY
+    || ht->items[idx].value == _HURD_IHASH_DELETED;
 }
 
 
@@ -104,7 +94,7 @@
 static inline int
 index_valid (hurd_ihash_t ht, unsigned int idx, hurd_ihash_key_t key)
 {
-  return !index_empty (ht, idx) && ht->keys[idx] == key;
+  return !index_empty (ht, idx) && ht->items[idx].key == key;
 }
 
 
@@ -115,29 +105,70 @@
 find_index (hurd_ihash_t ht, hurd_ihash_key_t key)
 {
   unsigned int idx;
-  unsigned int first_idx;
-
-  first_idx = HASH (ht, key);
-  idx = first_idx;
+  unsigned int i;
+  unsigned int up_idx;
+  unsigned int down_idx;
+
+  idx = key % ht->size;
+
+  if (ht->items[idx].value == _HURD_IHASH_EMPTY || ht->items[idx].key == key)
+    return idx;
+
+  /* Instead of calculating idx + 1, idx + 4, idx + 9, ..., idx + i^2,
+     we add 1, 3, 5, 7, etc to the previous index.  We do this in both
+     directions separately.  */
+  i = 1;
+  up_idx = idx;
+  down_idx = idx;
 
-  while (ht->table[idx] != _HURD_IHASH_EMPTY && ht->keys[idx] != key)
+  do
     {
-      idx = REHASH (ht, key, idx);
-      if (idx == first_idx)
-       break;
+      up_idx = (up_idx + i) % ht->size;
+      if (ht->items[up_idx].value == _HURD_IHASH_EMPTY
+         || ht->items[up_idx].key == key)
+       return up_idx;
+
+      if (down_idx < i)
+       down_idx += ht->size;
+      down_idx = (down_idx - i) % ht->size;
+      if (ht->items[down_idx].value == _HURD_IHASH_EMPTY
+         || ht->items[down_idx].key == key)
+       return down_idx;
+
+      /* After (ht->size - 1) / 2 iterations, this will be 0.  */
+      i = (i + 2) % ht->size;
     }
+  while (i);
 
+  /* If we end up here, the item could not be found.  Return any
+     invalid index.  */
   return idx;
 }
 
+
+/* Remove the entry pointed to by the location pointer LOCP from the
+   hashtable HT.  LOCP is the location pointer of which the address
+   was provided to hurd_ihash_add().  */
+static inline void
+locp_remove (hurd_ihash_t ht, hurd_ihash_locp_t locp)
+{
+  if (ht->cleanup)
+    (*ht->cleanup) (*locp, ht->cleanup_data);
+  *locp = _HURD_IHASH_DELETED;
+  ht->nr_items--;
+}
+
 
 /* Construction and destruction of hash tables.  */
 
 /* Initialize the hash table at address HT.  */
 void
-hurd_ihash_init (hurd_ihash_t ht)
+hurd_ihash_init (hurd_ihash_t ht, off_t locp_offs)
 {
+  ht->nr_items = 0;
   ht->size = 0;
+  ht->locp_offset = locp_offs;
+  ht->max_load = HURD_IHASH_MAX_LOAD_DEFAULT;
   ht->cleanup = 0;
 }
 
@@ -158,24 +189,20 @@
     }
 
   if (ht->size > 0)
-    {
-      free (ht->table);
-      free (ht->keys);
-      free (ht->locps);
-    }
+    free (ht->items);
 }
 
 
 /* Create a hash table, initialize it and return it in HT.  If a
    memory allocation error occurs, ENOMEM is returned, otherwise 0.  */
 error_t
-hurd_ihash_create (hurd_ihash_t *ht)
+hurd_ihash_create (hurd_ihash_t *ht, off_t locp_offs)
 {
   *ht = malloc (sizeof (struct hurd_ihash));
   if (*ht == NULL)
     return ENOMEM;
 
-  hurd_ihash_init (*ht);
+  hurd_ihash_init (*ht, locp_offs);
 
   return 0;
 }
@@ -203,42 +230,91 @@
 }
 
 
+/* Set the maximum load factor in percent to MAX_LOAD, which
+   should be between 1 and 100.  The default is
+   HURD_IHASH_MAX_LOAD_DEFAULT.  New elements are only added to the
+   hash table while the number of hashed elements is that much percent
+   of the total size of the hash table.  If more elements are added,
+   the hash table is first expanded and reorganized.  A MAX_LOAD of
+   100 will always fill the whole table before enlarging it, but note
+   that this will increase the cost of operations significantly when
+   the table is almost full.
+
+   If the value is set to a smaller value than the current load
+   factor, the next reorganization will happen when a new item is
+   added to the hash table.  */
+void
+hurd_ihash_set_max_load (hurd_ihash_t ht, unsigned int max_load)
+{
+  ht->max_load = max_load;
+}
+
+
 /* Helper function for hurd_ihash_add.  Return 1 if the item was
    added, and 0 if it could not be added because no empty slot was
-   found.  The arguments are identical to hurd_ihash_add.  */
+   found.  The arguments are identical to hurd_ihash_add.
+
+   We are using open address hashing.  As the hash function we use the
+   division method with quadratic probe.  This is guaranteed to try
+   all slots in the hash table if the prime number is 3 mod 4.  */
 static inline int
-add_one (hurd_ihash_t ht, hurd_ihash_key_t key,
-        hurd_ihash_value_t item, hurd_ihash_locp_t *locp)
+add_one (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t value)
 {
   unsigned int idx;
-  unsigned int first_idx;
   unsigned int first_free;
 
-  first_idx = HASH (ht, key);
-  idx = first_idx;
-  first_free = first_idx;
-
-  /* Search for for an empty or deleted space.  Even if a deleted
-     space is found, keep going until we know if the same key
-     already exists.  */
-  while (ht->table[idx] != _HURD_IHASH_EMPTY
-        && ht->keys[idx] != key)
-    {
-      if (ht->table[idx] == _HURD_IHASH_DELETED)
-       first_free = idx;
-      
-      idx = REHASH (ht, key, idx);
-      if (idx == first_idx)
-       break;
-    }
+  idx = key % ht->size;
+  first_free = idx;
 
-  if (ht->keys[idx] == key)
+  if (ht->items[idx].value != _HURD_IHASH_EMPTY && ht->items[idx].key != key)
     {
-      if (ht->cleanup)
-       ht->cleanup (ht->table[idx], ht->cleanup_data);
-      ht->table[idx] = _HURD_IHASH_DELETED;
+      /* Instead of calculating idx + 1, idx + 4, idx + 9, ..., idx +
+         i^2, we add 1, 3, 5, 7, ... 2 * i - 1 to the previous index.
+         We do this in both directions separately.  */
+      unsigned int i = 1;
+      unsigned int up_idx = idx;
+      unsigned int down_idx = idx;
+ 
+      do
+       {
+         up_idx = (up_idx + i) % ht->size;
+         if (ht->items[up_idx].value == _HURD_IHASH_EMPTY
+             || ht->items[up_idx].key == key)
+           {
+             idx = up_idx;
+             break;
+           }
+         if (first_free == idx
+             && ht->items[up_idx].value == _HURD_IHASH_DELETED)
+           first_free = up_idx;
+
+         if (down_idx < i)
+           down_idx += ht->size;
+         down_idx = (down_idx - i) % ht->size;
+         if (down_idx < 0)
+           down_idx += ht->size;
+         else
+           down_idx %= ht->size;
+         if (ht->items[down_idx].value == _HURD_IHASH_EMPTY
+             || ht->items[down_idx].key == key)
+           {
+             idx = down_idx;
+             break;
+           }
+         if (first_free == idx
+             && ht->items[down_idx].value == _HURD_IHASH_DELETED)
+           first_free = down_idx;
+
+         /* After (ht->size - 1) / 2 iterations, this will be 0.  */
+         i = (i + 2) % ht->size;
+       }
+      while (i);
     }
 
+  /* Remove the old entry for this key if necessary.  */
+  if (index_valid (ht, idx, key))
+    locp_remove (ht, &ht->items[idx].value);
+
   /* If we have not found an empty slot, maybe the last one we
      looked at was empty (or just got deleted).  */
   if (!index_empty (ht, first_free))
@@ -246,13 +322,14 @@
  
   if (index_empty (ht, first_free))
     {
-      ht->table[first_free] = item;
-      ht->keys[first_free] = key;
-      ht->locps[first_free] = locp;
-      
-      if (locp)
-       *locp = &ht->table[first_free];
-      
+      ht->nr_items++;
+      ht->items[first_free].value = value;
+      ht->items[first_free].key = key;
+
+      if (ht->locp_offset != HURD_IHASH_NO_LOCP)
+       *((hurd_ihash_locp_t) (((char *) value) + ht->locp_offset))
+         = &ht->items[first_free].value;
+
       return 1;
     }
 
@@ -260,75 +337,61 @@
 }
 
   
-/* Add ITEM to the hash table HT under the key KEY.  LOCP is the
-   address of a location pointer in ITEM; If non-NULL, it will be
-   filled with a pointer that may be used as an argument to
-   hurd_ihash_locp_remove().  (The variable pointed to by LOCP may be
-   written to subsequently between this call and when the element is
-   deleted).  If there already is an item under this key, call the
-   cleanup function (if any) for it before overriding the value.  If a
-   memory allocation error occurs, ENOMEM is returned, otherwise 0.  */
+/* Add ITEM to the hash table HT under the key KEY.  If there already
+   is an item under this key, call the cleanup function (if any) for
+   it before overriding the value.  If a memory allocation error
+   occurs, ENOMEM is returned, otherwise 0.  */
 error_t
-hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key,
-               hurd_ihash_value_t item, hurd_ihash_locp_t *locp)
+hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t item)
 {
   struct hurd_ihash old_ht = *ht;
   int was_added;
   int i;
 
-  if (ht->size && add_one (ht, key, item, locp))
-    return 0;
+  if (ht->size)
+    {
+      /* Only fill the hash table up to its maximum load factor.  */
+      if (ht->nr_items * 100 / ht->size <= ht->max_load)
+       if (add_one (ht, key, item))
+         return 0;
+    }
 
   /* The hash table is too small, and we have to increase it.  */
   for (i = 0; i < ihash_nsizes; i++)
     if (ihash_sizes[i] > old_ht.size)
       break;
   if (i == ihash_nsizes
-      || ihash_sizes[i] > SIZE_MAX / sizeof (hurd_ihash_value_t)
-      || ihash_sizes[i] > SIZE_MAX / sizeof (hurd_ihash_key_t)
-      || ihash_sizes[i] > SIZE_MAX / sizeof (hurd_ihash_locp_t *))
+      || ihash_sizes[i] > SIZE_MAX / sizeof (struct _hurd_ihash_item))
     return ENOMEM;             /* Surely will be true momentarily.  */
-    
+
+  ht->nr_items = 0;
   ht->size = ihash_sizes[i];
-  ht->table = malloc (ht->size * sizeof (hurd_ihash_value_t));
-  ht->keys = malloc (ht->size * sizeof (hurd_ihash_key_t));
-  ht->locps = malloc (ht->size * sizeof (hurd_ihash_locp_t *));
+  /* calloc() will initialize all values to _HURD_IHASH_EMPTY implicitely.  */
+  ht->items = calloc (ht->size, sizeof (struct _hurd_ihash_item));
 
-  if (ht->table == NULL || ht->locps == NULL || ht->keys == NULL)
+  if (ht->items == NULL)
     {
-      if (ht->table)
-       free (ht->table);
-      if (ht->keys)
-       free(ht->keys);
-      if (ht->locps)
-       free (ht->locps);
+      if (ht->items)
+       free(ht->items);
 
       *ht = old_ht;
       return ENOMEM;
     }
 
-  for (i = 0; i < ht->size; i++)
-    ht->table[i] = _HURD_IHASH_EMPTY;
-
   /* We have to rehash the old entries.  */
   for (i = 0; i < old_ht.size; i++)
     if (!index_empty (&old_ht, i))
       {
-       was_added = add_one (ht, old_ht.keys[i], old_ht.table[i],
-                            old_ht.locps[i]);
+       was_added = add_one (ht, old_ht.items[i].key, old_ht.items[i].value);
        assert (was_added);
       }
 
   /* Finally add the new element!  */
-  was_added = add_one (ht, key, item, locp);
+  was_added = add_one (ht, key, item);
   assert (was_added);
 
   if (old_ht.size > 0)
-    {
-      free (old_ht.table);
-      free (old_ht.keys);
-      free (old_ht.locps);
-    }
+    free (old_ht.items);
 
   return 0;
 }
@@ -344,7 +407,7 @@
   else
     {
       int idx = find_index (ht, key);
-      return index_valid (ht, idx, key) ? ht->table[idx] : NULL;
+      return index_valid (ht, idx, key) ? ht->items[idx].value : NULL;
     }
 }
 
@@ -358,7 +421,7 @@
 
   if (index_valid (ht, idx, key))
     {
-      hurd_ihash_locp_remove (ht, &ht->table[idx]);
+      locp_remove (ht, &ht->items[idx].value);
       return 1;
     }
   else
@@ -369,13 +432,9 @@
 /* Remove the entry pointed to by the location pointer LOCP from the
    hashtable HT.  LOCP is the location pointer of which the address
    was provided to hurd_ihash_add().  This call is faster than
-   hurd_ihash_remove().  HT can be NULL, in which case the call still
-   succeeds, but the cleanup function (if any) will not be invoked in
-   this case.  */
+   hurd_ihash_remove().  */
 void
 hurd_ihash_locp_remove (hurd_ihash_t ht, hurd_ihash_locp_t locp)
 {
-  if (ht && ht->cleanup)
-    (*ht->cleanup) (*locp, ht->cleanup_data);
-  *locp = _HURD_IHASH_DELETED;
+  locp_remove (ht, locp);
 }
Index: hurd-l4/libhurd-ihash/ihash.h
diff -u hurd-l4/libhurd-ihash/ihash.h:1.6 hurd-l4/libhurd-ihash/ihash.h:1.7
--- hurd-l4/libhurd-ihash/ihash.h:1.6   Sun Aug 17 01:47:32 2003
+++ hurd-l4/libhurd-ihash/ihash.h       Tue Aug 26 18:47:18 2003
@@ -24,17 +24,19 @@
 
 #include <errno.h>
 #include <sys/types.h>
+#include <limits.h>
 
 
 /* The type of the values corresponding to the keys.  Must be a
-   pointer type.  */
+   pointer type.  The values (hurd_ihash_value_t) 0 and
+   (hurd_ihash_value_t) ~0 are reserved for the implementation.  */
 typedef void *hurd_ihash_value_t;
 
-/* When an entry in the table TABLE of a hash table is
-   _HURD_IHASH_EMPTY or _HURD_IHASH_DELETED, then the location is
-   available, and none of the other arrays are valid at that index.
-   The difference is that searches continue though HASH_DEL, but stop
-   at _HURD_IHASH_EMPTY.  */
+/* When an entry in the hash table is _HURD_IHASH_EMPTY or
+   _HURD_IHASH_DELETED, then the location is available, and none of
+   the other arrays are valid at that index.  The difference is that
+   searches continue though _HURD_IHASH_DELETED, but stop at
+   _HURD_IHASH_EMPTY.  */
 #define _HURD_IHASH_EMPTY      ((hurd_ihash_value_t) 0)
 #define _HURD_IHASH_DELETED    ((hurd_ihash_value_t) -1)
 
@@ -53,21 +55,35 @@
 typedef void (*hurd_ihash_cleanup_t) (hurd_ihash_value_t value, void *arg);
 
 
-struct hurd_ihash
+struct _hurd_ihash_item
 {
-  /* An array storing the elements in the hash table.  */
-  hurd_ihash_value_t *table;
+  /* The value of this hash item.  Must be the first element of
+     the struct for the HURD_IHASH_ITERATE macro.  */
+  hurd_ihash_value_t value;
+
+  /* The integer key of this hash item.  */
+  hurd_ihash_key_t key;
+};
+typedef struct _hurd_ihash_item *_hurd_ihash_item_t;
 
-  /* An array storing the integer key for each element.  */
-  hurd_ihash_key_t *keys;
 
-  /* An array storing pointers to the location pointers for each
-     element.  These are used as cookies for quick'n'easy removal.  */
-  hurd_ihash_locp_t **locps;
+struct hurd_ihash
+{
+  /* The number of hashed elements.  */
+  size_t nr_items;
 
-  /* The length of the three arrays TABLE, KEYS and LOCPS.  */
+  /* An array of (key, value) pairs.  */
+  _hurd_ihash_item_t items;
+
+  /* The length of the array ITEMS.  */
   size_t size;
 
+  /* The offset of the location pointer from the hash value.  */
+  off_t locp_offset;
+
+  /* The maximum load factor in percent.  */
+  int max_load;
+
   /* When freeing or overwriting an element, this function is called
      with the value as the first argument, and CLEANUP_DATA as the
      second argument.  This does not happen if CLEANUP is NULL.  */
@@ -79,11 +95,25 @@
 
 /* Construction and destruction of hash tables.  */
 
-#define HURD_IHASH_INITIALIZER \
-  { .size = 0, .cleanup = (hurd_ihash_cleanup_t) 0 }
+/* The default value for the maximum load factor in percent.  */
+#define HURD_IHASH_MAX_LOAD_DEFAULT 80
+
 
-/* Initialize the hash table at address HT.  */
-void hurd_ihash_init (hurd_ihash_t ht);
+#define HURD_IHASH_NO_LOCP     INT_MIN
+
+
+#define HURD_IHASH_INITIALIZER(locp_offs)                      \
+  { .nr_items = 0, .size = 0, .cleanup = (hurd_ihash_cleanup_t) 0,     \
+    .max_load = HURD_IHASH_MAX_LOAD_DEFAULT,                           \
+    .locp_offset = (locp_offs)}
+
+
+/* Initialize the hash table at address HT.  If LOCP_OFFSET is not
+   HURD_IHASH_NO_LOCP, then this is an offset (in bytes) from the
+   address of a hash value where a location pointer can be found.  The
+   location pointer must be of type hurd_ihash_locp_t and can be used
+   for fast removal with hurd_ihash_locp_remove().  */
+void hurd_ihash_init (hurd_ihash_t ht, off_t locp_offs);
 
 
 /* Destroy the hash table at address HT.  This first removes all
@@ -92,9 +122,14 @@
 void hurd_ihash_destroy (hurd_ihash_t ht);
 
 
-/* Create a hash table, initialize it and return it in HT.  If a
-   memory allocation error occurs, ENOMEM is returned, otherwise 0.  */
-error_t hurd_ihash_create (hurd_ihash_t *ht);
+/* Create a hash table, initialize it and return it in HT.  If
+   LOCP_OFFSET is not HURD_IHASH_NO_LOCP, then this is an offset (in
+   bytes) from the address of a hash value where a location pointer
+   can be found.  The location pointer must be of type
+   hurd_ihash_locp_t and can be used for fast removal with
+   hurd_ihash_locp_remove().  If a memory allocation error occurs,
+   ENOMEM is returned, otherwise 0.  */
+error_t hurd_ihash_create (hurd_ihash_t *ht, off_t locp_offs);
 
 
 /* Destroy the hash table HT and release the memory allocated for it
@@ -102,6 +137,8 @@
 void hurd_ihash_free (hurd_ihash_t ht);
 
 
+/* Configuration of the hash table.  */
+
 /* Set the cleanup function for the hash table HT to CLEANUP.  The
    second argument to CLEANUP will be CLEANUP_DATA on every
    invocation.  */
@@ -109,16 +146,28 @@
                             void *cleanup_data);
 
 
-/* Add ITEM to the hash table HT under the key KEY.  LOCP is the
-   address of a location pointer in ITEM; If non-NULL, it will be
-   filled with a pointer that may be used as an argument to
-   hurd_ihash_locp_remove().  (The variable pointed to by LOCP may be
-   written to subsequently between this call and when the element is
-   deleted).  If there already is an item under this key, call the
-   cleanup function (if any) for it before overriding the value.  If a
-   memory allocation error occurs, ENOMEM is returned, otherwise 0.  */
+/* Set the maximum load factor in percent to MAX_LOAD, which
+   should be between 50 and 100.  The default is
+   HURD_IHASH_MAX_LOAD_DEFAULT.  New elements are only added to the
+   hash table while the number of hashed elements is that much percent
+   of the total size of the hash table.  If more elements are added,
+   the hash table is first expanded and reorganized.  A MAX_LOAD of
+   100 will always fill the whole table before enlarging it, but note
+   that this will increase the cost of operations significantly when
+   the table is almost full.
+
+   If the value is set to a smaller value than the current load
+   factor, the next reorganization will happen when a new item is
+   added to the hash table.  */
+void hurd_ihash_set_max_load (hurd_ihash_t ht, unsigned int max_load);
+
+
+/* Add ITEM to the hash table HT under the key KEY.  If there already
+   is an item under this key, call the cleanup function (if any) for
+   it before overriding the value.  If a memory allocation error
+   occurs, ENOMEM is returned, otherwise 0.  */
 error_t hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key,
-                       hurd_ihash_value_t item, hurd_ihash_locp_t *locp);
+                       hurd_ihash_value_t item);
 
 
 /* Find and return the item in the hash table HT with key KEY, or NULL
@@ -147,12 +196,35 @@
    The block will be run for every element in the hash table HT.  The
    value of the current element is available via the macro
    HURD_IHASH_ITERATOR_VALUE.  */
+
+/* The implementation of this macro is peculiar.  We want the macro to
+   execute a block following its invocation, so we can only prepend
+   code.  This excludes creating an outer block.  However, we must
+   define two variables: The hash value variable VALUE, and the loop
+   variable.
+
+   We can define variables inside the for-loop initializer (C99), but
+   we can only use one basic type to do that.  We can not use two
+   for-loops, because we want a break statement inside the iterator
+   block to terminate the operation.  So we must have both variables
+   of the same basic type, but we can make one of them a pointer type.
+
+   The pointer to the value can be used as the loop variable.  This is
+   also the first element of the hash item, so we can cast the pointer
+   freely between these two types.  The pointer is only dereferenced
+   after the loop condition is checked (but of course the value the
+   pointer pointed to must not have an influence on the condition
+   result, so the comma operator is used to make sure this
+   subexpression is always true).  */
 #define HURD_IHASH_ITERATE(ht, value)                                  \
-  for (hurd_ihash_value_t value = (ht)->size ? (ht)->table[0] : 0,     \
-         *_hurd_ihash_valuep = (ht)->size ? &(ht)->table[0] : 0;       \
-       (ht)->size && _hurd_ihash_valuep - &(ht)->table[0] < (ht)->size \
+  for (hurd_ihash_value_t value,                                       \
+         *_hurd_ihash_valuep = (ht)->size ? &(ht)->items[0].value : 0; \
+       (ht)->size                                                      \
+         && ((_hurd_ihash_item_t) _hurd_ihash_valuep) - &(ht)->items[0]        
\
+            < (ht)->size                                               \
          && (value = *_hurd_ihash_valuep, 1);                          \
-       _hurd_ihash_valuep++)                                           \
+       _hurd_ihash_valuep = (hurd_ihash_value_t *)                     \
+        (((_hurd_ihash_item_t) _hurd_ihash_valuep)++))                 \
     if (value != _HURD_IHASH_EMPTY && value != _HURD_IHASH_DELETED)
 
 
@@ -162,11 +234,9 @@
 
 
 /* Remove the entry pointed to by the location pointer LOCP from the
-   hashtable HT.  LOCP is the location pointer of which the address
+   hash table HT.  LOCP is the location pointer of which the address
    was provided to hurd_ihash_add().  This call is faster than
-   hurd_ihash_remove().  HT can be NULL, in which case the call still
-   succeeds, but the cleanup function (if any) will not be invoked in
-   this case.  */
+   hurd_ihash_remove().  */
 void hurd_ihash_locp_remove (hurd_ihash_t ht, hurd_ihash_locp_t locp);
 
 #endif /* _HURD_IHASH_H */