auth/

2003-08-17  Marcus Brinkmann  <marcus@gnu.org>

	* auth.c: Include <stddef.h>.
	(pending_users, pending_server): Change type to struct hurd_ihash,
	initialize with HURD_IHASH_INITIALIZER.
	(struct pending): Change type of member LOCP to hurd_ihash_locp_t.
	(S_auth_user_authenticate): Use hurd_ihash_* functions instead
	ihash_*.
	(S_auth_server_authenticate): Likewise.
	(main): Do not allocate the hash tables.

console-client/
2003-08-17  Marcus Brinkmann  <marcus@gnu.org>

	* vga-dynafont.c: Include <stddef.h>.
	(struct mapped_character): Change type of LOCP to
	hurd_ihash_locp_t.
	(struct dynafont): Change type of CHARMAP to struct hurd_ihash.
	(dynafont_new): Use hurd_ihash_init instead of ihash_create.
	Remove variable ERR.  Call hurd_ihash_add instead of ihash_add.
	(dynafont_free): Call hurd_ihash_destroy, no ihash_free.
	(dynafont_lookup_internal): Use hurd_ihash_find, not ihash_find.
	(dynafont_lookup_internal): Call hurd_ihash_locp_remove instead
	ihash_locp_remove, and hurd_ihash_add instead ihash_add.
	(dynafont_change_font): Likewise.  Clean out LOCP if character is
	unmapped.

ftpfs/
2003-08-17  Marcus Brinkmann  <marcus@gnu.org>

	* ftpfs.h: Include <hurd/ihash.h>.
	(struct ftpfs): Change type of INODE_MAPPINGS to struct
	hurd_ihash.
	(struct ftpfs_dir_entry): Change type of INODE_LOCP to
	hurd_ihash_locp_t.
	* node.c (ftpfs_create_node): Call hurd_ihash_add, not ihash_add.
	(netfs_node_norefs): Call hurd_ihash_locp_remove, not
	ihash_locp_remove.
	* fs.c: Include <stddef.h>.
	(ftpfs_create): Call hurd_ihash_init, not hurd_ihash_create.
	Call hurd_ihash_destroy on error.

libihash/
2003-08-17  Marcus Brinkmann  <marcus@gnu.org>

	* ihash.c: Rewritten.
	* ihash.h: Rewritten.
	* Makefile (SRCS): Remove sizes.c.
	(LCLHDRS): Remove priv.h.
	* primes.c, sizes.c, priv.h: Files removed.

2003-08-17  Marcus Brinkmann  <marcus@gnu.org>

	* ports.h (struct port_bucket): Change type of HTABLE to struct
	hurd_ihash.
	(struct port_info): Change type of HENTRY to hurd_ihash_locp_t.
	* lookup-port.c (ports_lookup_port): Use hurd_ihash_find instead
	ihash_find.
	* bucket-iterate.c (_ports_bucket_class_iterate): Use
	HURD_IHASH_ITERATE instead ihash_iterate.
	* inhibit-all-rpcs.c (ports_inhibit_all_rpcs): Likewise.
	* inhibit-bucket-rpcs.c (ports_inhibit_bucket_rpcs): Likewise.
	* create-internal.c (_ports_create_port_internal): Use
	hurd_ihash_add instead ihash_add.
	* import-port.c (ports_import_port): Likewise.
	* reallocate-from-external.c (ports_reallocate_from_external):
	Likewise.
	* reallocate-port.c (ports_reallocate_port): Likewise.
	* transfer-right.c (ports_transfer_right): Likewise.
	* create-bucket.c: Include <stddef.h>.
	(ports_create_bucket): Use hurd_ihash_init instead hurd_ihash_create.
	* class-iterate.c: Do not include <hurd/ihash.h>.
	* claim-right.c (ports_claim_right): Call hurd_ihash_locp_remove
	instead ihash_locp_remove.
	* complete-deallocate.c (_ports_complete_deallocate): Likewise.
	* destroy-right.c (ports_destroy_right): Likewise.
	* reallocate-from-external.c (ports_reallocate_from_external):
	Likewise.
	* reallocate-port.c (ports_reallocate_port): Likewise.
	* transfer-right.c (ports_transfer_right): Likewise.

libps/
2003-08-17  Marcus Brinkmann  <marcus@gnu.org>

	* ps.h (struct ps_context): Change type of members procs, ttys,
	ttys_by_cttyid and users to struct hurd_ihash.
	* context.c (ps_context_create): Remove variables err_procs,
	err_ttys, err_ttys_by_cttyid and err_users.  Use hurd_ihash_init
	instead of ihash_create.  Call hurd_ihash_set_cleanup and the
	hurd_ihash_cleanup_t type instead of ihash_set_cleanup.
	(ps_context_free): Call hurd_ihash_destroy instead of ihash_free.
	(lookup): Call hurd_ihash_find instead ihash_find, hurd_ihash_add
	instead ihash_add.
	(ps_context_find_proc_stat): Take pointer of hash object.
	(ps_context_find_tty): Likewise.
	(ps_context_find_tty_by_cttyid): Likewise.
	(ps_context_find_user): Likewise.

libpthread/
2003-08-17  Marcus Brinkmann  <marcus@gnu.org>

	* sysdeps/hurd/pt-key.h (PTHREAD_KEY_MEMBERS): Change type of
	THREAD_SPECIFICS to hurd_ihash_t.
	* sysdeps/hurd/pt-setspecific.c (pthread_setspecific): Call
	hurd_ihash_create instead ihash_create, and hurd_ihash_add instead
	ihash_add.
	* sysdeps/hurd/pt-getspecific.c (pthread_getspecific): Call
	hurd_ihash_find instead of ihash_find.
	* sysdeps/hurd/pt-destroy-specific.c (__pthread_destroy_specific):
	Call hurd_ihash_find instead of ihash_find, hurd_ihash_remove
	instead of ihash_remove, and hurd_ihash_free instead of
	ihash_free.

proc/
2003-08-17  Marcus Brinkmann  <marcus@gnu.org>

	* proc.h: Include <hurd/ihash.h>.
	(struct proc): Change type of members p_pidhashloc and
	p_taskhashloc to hurd_ihash_locp_t.
	(struct pgrp): Likewise for pg_hashloc.
	(struct session): Likewise for s_hashloc.
	* hash.c: Change type of pghash, pidhash, taskhash and sidhash to
	struct hurd_ihash and initialize them with HURD_IHASH_INITIALIZER.
	Include stddef.h.
	(pid_find): Call hurd_ihash_find instead ihash_find.
	(pid_find_allow_zombie): Likewise.
	(task_find): Likewise.
	(task_find_nocreate): Likewise.
	(pgrp_find): Likewise.
	(session_find): Likewise.
	(add_proc_to_hash): Call hurd_ihash_add instead ihash_add.
	(add_pgrp_to_hash): Likewise.
	(add_session_to_hash): Likewise.
	(remove_pgrp_from_hash): Call hurd_ihash_locp_remove instead
	ihash_locp_remove, and provide hash table pointer.
	(remove_proc_from_hash): Likewise.
	(remove_session_from_hash): Likewise.
	(prociterate): Use HURD_IHASH_ITERATE instead ihash_iterate.

trans/
2003-08-17  Marcus Brinkmann  <marcus@gnu.org>

	* fakeroot.c: Include <stddef.h>.
	(struct netnode): Change type of member idport_locp
	to hurd_ihash_locp_t.
	(idport_ihash): Change type to struct hurd_ihash and initialize
	with HURD_IHASH_INITIALIZER.
	(new_node): Call hurd_ihash_add instead of ihash_add.
	(netfs_node_norefs): Call hrd_ihash_locp_remove instead
	ihash_locp_remove.
	(netfs_S_dir_lookup): Call hurd_ihash_find instead ihash_find.

utils/
2003-08-17  Marcus Brinkmann  <marcus@gnu.org>

	* rpctrace.c: Include <stddef.h>.
	(struct traced_info): Change type of LOCP to hurd_ihash_locp_t.
	(msgid_ihash): Change type to struct hurd_ihash, and initialize
	with HURD_IHASH_INITIALIZER, don't set cleanup here.
	(traced_names): Likewise.
	(main): Call hurd_ihash_set_cleanup for msgid_ihash.  Don't create
	traced_names.
	(parse_msgid_list): Call hurd_ihash_add instead ihash_add.
	(new_send_wrapper): Likewise.
	(msgid_info): Likewise.  Call hurd_ihash_find instead ihash_find.
	(rewrite_right): Likewise.
	(traced_dropweak): Call hurd_ihash_locp_remove instead
	ihash_locp_remove.

1 files changed, 353 insertions, 196 deletions

diff --git a/libihash/ihash.c b/libihash/ihash.c
index dfc36b01..51cca82b 100644
--- a/libihash/ihash.c
+++ b/libihash/ihash.c
@@ -1,11 +1,11 @@
-/* Integer-keyed hash table functions.
-
-   Copyright (C) 1993,94,95,96,97,2001 Free Software Foundation, Inc.
-
+/* ihash.c - Integer-keyed hash table functions.
+   Copyright (C) 1993-1997, 2001, 2003 Free Software Foundation, Inc.
+   Written by Michael I. Bushnell.
+   Revised by Miles Bader <miles@gnu.org>.
+   Revised by Marcus Brinkmann <marcus@gnu.org>.
+   
    This file is part of the GNU Hurd.
 
-   Written by Michael I. Bushnell; revised by Miles Bader <miles@gnu.org>.
-
    The GNU Hurd is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2, or (at your option)
@@ -20,266 +20,423 @@
    along with the GNU Hurd; see the file COPYING.  If not, write to
    the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
 
+#if HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include <errno.h>
 #include <string.h>
 #include <stdlib.h>
+#include <limits.h>
+#include <stdint.h>
+#include <assert.h>
+
+#include <hurd/ihash.h>
 
-#include "ihash.h"
-#include "priv.h"
-
-/* ---------------------------------------------------------------- */
-
-/* When an entry in a hashtable's TAB array is HASH_EMPTY, that location is
-   available, and none of the other arrays are valid at that index.  */
-#define HASH_EMPTY 0
-
-/* When an entry in a hashtable's TAB array is HASH_DEL, that location is
-   available, and none of the other arrays are valid at that index.  The
-   difference from HASH_EMPTY is that searches continue though HASH_DEL and
-   stop at HASH_EMPTY.  */
-#define HASH_DEL ((void *) -1)
-
-/* Returns an initial index in HT for the key ID, for search for an entry.  */
-#define HASH(ht, id) ((id) % (ht)->size)
-/* Returns subsequent indices in HT for the key ID, given the previous one.  */
-#define REHASH(ht, id, h) (((id) + (h)) % (ht)->size)
 
-/* ---------------------------------------------------------------- */
+/* 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,
+  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)
+};
+
+static const unsigned int ihash_nsizes = (sizeof ihash_sizes
+					  / sizeof ihash_sizes[0]);
 
+
+/* Return 1 if the slot with the index IDX in the hash table HT is
+   empty, and 0 otherwise.  */
 static inline int
-index_empty(ihash_t ht, int index)
+index_empty (hurd_ihash_t ht, unsigned int idx)
 {
-  return ht->tab[index] == HASH_EMPTY || ht->tab[index] == HASH_DEL;
+  return ht->items[idx].value == _HURD_IHASH_EMPTY
+    || ht->items[idx].value == _HURD_IHASH_DELETED;
 }
 
+
+/* Return 1 if the index IDX in the hash table HT is occupied by the
+   element with the key KEY.  */
 static inline int
-index_valid(ihash_t ht, int index, int id)
+index_valid (hurd_ihash_t ht, unsigned int idx, hurd_ihash_key_t key)
 {
-  return !index_empty(ht, index) && ht->ids[index] == id;
+  return !index_empty (ht, idx) && ht->items[idx].key == key;
 }
 
-/* Given a hash table HT, and a key ID, finds the index in the table of that
-   key.  You must subsequently check to see whether the given index is valid
-   (with index_valid() or index_empty()).  */
+
+/* Given a hash table HT, and a key KEY, find the index in the table
+   of that key.  You must subsequently check with index_valid() if the
+   returned index is valid.  */
 static inline int
-find_index(ihash_t ht, int id)
+find_index (hurd_ihash_t ht, hurd_ihash_key_t key)
 {
-  int h, firsth = -1;
+  unsigned int idx;
+  unsigned int i;
+  unsigned int up_idx;
+  unsigned int down_idx;
+
+  idx = key % ht->size;
 
-  for (h = HASH(ht, id);
-       ht->tab[h] != HASH_EMPTY && ht->ids[h] != id && h != firsth;
-       h = REHASH(ht, id, h))
-    if (firsth == -1)
-      firsth = h;
+  if (ht->items[idx].value == _HURD_IHASH_EMPTY || ht->items[idx].key == key)
+    return idx;
 
-  return h;
+  /* 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;
+
+  do
+    {
+      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;
 }
-
-/* ---------------------------------------------------------------- */
 
-/* Create an integer hash table and return it in HT.  If a memory allocation
-   error occurs, ENOMEM is returned, otherwise 0.  */
-error_t
-ihash_create(ihash_t *ht)
+
+/* 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)
 {
-  *ht = malloc(sizeof(struct ihash));
-  if (*ht == NULL)
-    return ENOMEM;
-  (*ht)->size = 0;
-  (*ht)->cleanup = 0;
-  (*ht)->cleanup_arg = 0;
-  return 0;
+  if (ht->cleanup)
+    (*ht->cleanup) (*locp, ht->cleanup_data);
+  *locp = _HURD_IHASH_DELETED;
+  ht->nr_items--;
 }
 
-/* Free HT and all resources it consumes.  */
+
+/* Construction and destruction of hash tables.  */
+
+/* Initialize the hash table at address HT.  */
 void
-ihash_free(ihash_t ht)
+hurd_ihash_init (hurd_ihash_t ht, off_t locp_offs)
 {
-  void (*cleanup)(void *value, void *arg) = ht->cleanup;
+  ht->nr_items = 0;
+  ht->size = 0;
+  ht->locp_offset = locp_offs;
+  ht->max_load = HURD_IHASH_MAX_LOAD_DEFAULT;
+  ht->cleanup = 0;
+}
 
-  if (cleanup)
+
+/* Destroy the hash table at address HT.  This first removes all
+   elements which are still in the hash table, and calling the cleanup
+   function for them (if any).  */
+void
+hurd_ihash_destroy (hurd_ihash_t ht)
+{
+  if (ht->cleanup)
     {
-      int i;
-      void *arg = ht->cleanup_arg;
-      for (i = 0; i < ht->size; i++)
-	if (!index_empty(ht, i))
-	  (*cleanup)(ht->tab[i], arg);
+      hurd_ihash_cleanup_t cleanup = ht->cleanup;
+      void *cleanup_data = ht->cleanup_data;
+
+      HURD_IHASH_ITERATE (ht, value)
+	(*cleanup) (value, cleanup_data);
     }
 
   if (ht->size > 0)
-    {
-      free(ht->tab);
-      free(ht->ids);
-      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, off_t locp_offs)
+{
+  *ht = malloc (sizeof (struct hurd_ihash));
+  if (*ht == NULL)
+    return ENOMEM;
+
+  hurd_ihash_init (*ht, locp_offs);
+
+  return 0;
+}
+
 
-  free(ht);
+/* Destroy the hash table HT and release the memory allocated for it
+   by hurd_ihash_create().  */
+void
+hurd_ihash_free (hurd_ihash_t ht)
+{
+  hurd_ihash_destroy (ht);
+  free (ht);
 }
 
-/* Sets HT's element cleanup function to CLEANUP, and its second argument to
-   ARG.  CLEANUP will be called on the value of any element to be
-   subsequently overwritten or deleted, with ARG as the second argument.  */
+
+/* Set the cleanup function for the hash table HT to CLEANUP.  The
+   second argument to CLEANUP will be CLEANUP_DATA on every
+   invocation.  */
 void
-ihash_set_cleanup(ihash_t ht,
-		  void (*cleanup)(void *value, void *arg),
-		  void *arg)
+hurd_ihash_set_cleanup (hurd_ihash_t ht, hurd_ihash_cleanup_t cleanup,
+			void *cleanup_data)
 {
   ht->cleanup = cleanup;
-  ht->cleanup_arg = arg;
+  ht->cleanup_data = cleanup_data;
 }
+
+
+/* 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;
+}
+
 
-/* ---------------------------------------------------------------- */
-
-/* Add ITEM to the hash table HT under the key ID.  LOCP is the address of a
-   pointer located in ITEM; If non-NULL, LOCP should point to a variable of
-   type void **, and will be filled with a pointer that may be used as an
-   argument to ihash_locp_remove().  The variable pointed to by LOCP may be
-   written to subsequently between this called and when the element is
-   deleted, so you can't stash its value elsewhere and hope to use the
-   stashed value with ihash_locp_remove().  If a memory allocation error
-   occurs, ENOMEM is returned, otherwise 0.  */
-error_t
-ihash_add(ihash_t ht, int id, void *item, void ***locp)
+/* 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.
+
+   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 value)
 {
-  if (ht->size)
-    {
-      int h, firsth = -1;
+  unsigned int idx;
+  unsigned int first_free;
 
-      /* Search for for an empty or deleted space.  */
-      for (h = HASH(ht, id);
-	   ht->tab[h] != HASH_EMPTY && ht->tab[h] != HASH_DEL && h != firsth;
-	   h = REHASH(ht, id, h))
-	if (firsth == -1)
-	  firsth = h;
+  idx = key % ht->size;
+  first_free = idx;
 
-      if (index_empty(ht, h) || ht->ids[h] == id)
+  if (ht->items[idx].value != _HURD_IHASH_EMPTY && ht->items[idx].key != key)
+    {
+      /* 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
 	{
-	  if (!index_empty(ht, h) && ht->cleanup)
-	    ht->cleanup(ht->tab[h], ht->cleanup_arg);
+	  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);
+    }
 
-	  ht->tab[h] = item;
-	  ht->ids[h] = id;
-	  ht->locps[h] = locp;
+  /* Remove the old entry for this key if necessary.  */
+  if (index_valid (ht, idx, key))
+    locp_remove (ht, &ht->items[idx].value);
 
-	  if (locp)
-	    *locp = &ht->tab[h];
+  /* 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))
+    first_free = idx;
+ 
+  if (index_empty (ht, first_free))
+    {
+      ht->nr_items++;
+      ht->items[first_free].value = value;
+      ht->items[first_free].key = key;
 
-	  return 0;
-	}
+      if (ht->locp_offset != HURD_IHASH_NO_LOCP)
+	*((hurd_ihash_locp_t) (((char *) value) + ht->locp_offset))
+	  = &ht->items[first_free].value;
+
+      return 1;
     }
 
-  {
-    int i;
-    void **entry;
-    int old_size = ht->size;
-    void **old_tab = ht->tab;
-    void ****old_locps = ht->locps;
-    int *old_ids = ht->ids;
-
-    i = 0;
-    while (_ihash_sizes[i] <= old_size)
-      if (++i == _ihash_nsizes)
-	return ENOMEM;		/* Surely will be true momentarily.  */
-
-    ht->size = _ihash_sizes[i];
-    ht->tab = malloc(ht->size * sizeof (void *));
-    ht->locps = malloc (ht->size * sizeof (void ***));
-    ht->ids = malloc (ht->size * sizeof (int));
-
-    if (ht->tab == NULL || ht->locps == NULL || ht->ids == NULL)
-      /* Memory allocation error; back out our changes and fail...  */
-      {
-	if (ht->tab) free(ht->tab);
-	if (ht->locps) free(ht->locps);
-	if (ht->ids) free(ht->ids);
+  return 0;
+}
 
-	ht->size = old_size;
-	ht->tab = old_tab;
-	ht->locps = old_locps;
-	ht->ids = old_ids;
+  
+/* 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)
+{
+  struct hurd_ihash old_ht = *ht;
+  int was_added;
+  int i;
 
-	return ENOMEM;
-      }
+  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 (struct _hurd_ihash_item))
+    return ENOMEM;		/* Surely will be true momentarily.  */
 
-    for (i = ht->size, entry = ht->tab; i > 0; i--, entry++)
-      *entry = HASH_EMPTY;
+  ht->nr_items = 0;
+  ht->size = ihash_sizes[i];
+  /* calloc() will initialize all values to _HURD_IHASH_EMPTY implicitely.  */
+  ht->items = calloc (ht->size, sizeof (struct _hurd_ihash_item));
 
-    /* We have to rehash this again?  */
-    if (old_size > 0)
-      for (i = 0; i < old_size; i++)
-	if (old_tab[i] != HASH_EMPTY && old_tab[i] != HASH_DEL)
-	  ihash_add(ht, old_ids[i], old_tab[i], old_locps[i]);
+  if (ht->items == NULL)
+    {
+      if (ht->items)
+	free(ht->items);
 
-    /* Finally add the new element!  */
-    ihash_add(ht, id, item, locp);
+      *ht = old_ht;
+      return ENOMEM;
+    }
 
-    if (old_size > 0)
+  /* We have to rehash the old entries.  */
+  for (i = 0; i < old_ht.size; i++)
+    if (!index_empty (&old_ht, i))
       {
-	free(old_tab);
-	free(old_locps);
-	free(old_ids);
+	was_added = add_one (ht, old_ht.items[i].key, old_ht.items[i].value);
+	assert (was_added);
       }
 
-    return 0;
-  }
+  /* Finally add the new element!  */
+  was_added = add_one (ht, key, item);
+  assert (was_added);
+
+  if (old_ht.size > 0)
+    free (old_ht.items);
+
+  return 0;
 }
 
-/* Find and return the item in hash table HT with key ID, or NULL if it
-   doesn't exist.  */
-void *
-ihash_find (ihash_t ht, int id)
+
+/* Find and return the item in the hash table HT with key KEY, or NULL
+   if it doesn't exist.  */
+hurd_ihash_value_t
+hurd_ihash_find (hurd_ihash_t ht, hurd_ihash_key_t key)
 {
   if (ht->size == 0)
-    return 0;
+    return NULL;
   else
     {
-      int index = find_index(ht, id);
-      return index_valid(ht, index, id) ? ht->tab[index] : 0;
+      int idx = find_index (ht, key);
+      return index_valid (ht, idx, key) ? ht->items[idx].value : NULL;
     }
 }
-
-/* ---------------------------------------------------------------- */
-
-/* Call function FUN of one arg for each element of HT.  FUN's only arg is a
-   pointer to the value stored in the hash table.  If FUN ever returns
-   non-zero, then iteration stops and ihash_iterate returns that value,
-   otherwise it (eventually) returns 0.  */
-error_t
-ihash_iterate(ihash_t ht, error_t (*fun)(void *))
-{
-  int i;
-  for (i = 0; i < ht->size; i++)
-    if (!index_empty(ht, i))
-      {
-	error_t err = fun(ht->tab[i]);
-	if (err)
-	  return err;
-      }
-  return 0;
-}
 
-/* Remove the entry at LOCP from the hashtable HT.  LOCP is as returned from
-   an earlier call to ihash_add().  This call should be faster than
-   ihash_remove().  HT can be NULL, in which case the call still succeeds,
-   but no cleanup can be done.  */
-void
-ihash_locp_remove(ihash_t ht, void **locp)
-{
-  if (ht && ht->cleanup)
-    ht->cleanup(*locp, ht->cleanup_arg);
-  *locp = HASH_DEL;
-}
 
-/* Remove the entry with a key of ID from HT.  If anything was actually
-   removed, 1 is returned, otherwise (if there was no such element), 0.  */
+/* Remove the entry with the key KEY from the hash table HT.  If such
+   an entry was found and removed, 1 is returned, otherwise 0.  */
 int
-ihash_remove(ihash_t ht, int id)
+hurd_ihash_remove (hurd_ihash_t ht, hurd_ihash_key_t key)
 {
-  int index = find_index(ht, id);
-  if (index_valid(ht, index, id))
+  int idx = find_index (ht, key);
+
+  if (index_valid (ht, idx, key))
     {
-      ihash_locp_remove(ht, &ht->tab[index]);
+      locp_remove (ht, &ht->items[idx].value);
       return 1;
     }
   else
     return 0;
 }
+
+
+/* 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().  */
+void
+hurd_ihash_locp_remove (hurd_ihash_t ht, hurd_ihash_locp_t locp)
+{
+  locp_remove (ht, locp);
+}