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.

7 files changed, 566 insertions, 469 deletions

diff --git a/libihash/ChangeLog b/libihash/ChangeLog
index 093bfe06..5e662950 100644
--- a/libihash/ChangeLog
+++ b/libihash/ChangeLog
@@ -1,3 +1,11 @@
+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.
+
 2001-08-15  Roland McGrath  <roland@frob.com>
 
 	* sizes.c: New file, a list of prime numbers useful for table sizes.
diff --git a/libihash/Makefile b/libihash/Makefile
index 902ff6d3..e0258241 100644
--- a/libihash/Makefile
+++ b/libihash/Makefile
@@ -1,5 +1,5 @@
 #
-#   Copyright (C) 1995,96,2001 Free Software Foundation, Inc.
+#   Copyright (C) 1995, 1996, 2001, 2003 Free Software Foundation, Inc.
 #
 #   This file is part of the GNU Hurd.
 #
@@ -21,9 +21,9 @@ dir := libihash
 makemode := library
 
 libname := libihash
-SRCS = ihash.c sizes.c
+SRCS = ihash.c
 installhdrs = ihash.h
-LCLHDRS = $(installhdrs) priv.h
+LCLHDRS = $(installhdrs)
 
 OBJS = $(SRCS:.c=.o)
 
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);
+}
diff --git a/libihash/ihash.h b/libihash/ihash.h
index 5d01ea1c..11092532 100644
--- a/libihash/ihash.h
+++ b/libihash/ihash.h
@@ -1,97 +1,231 @@
-/* Integer-keyed hash table functions.
+/* ihash.h - Integer keyed hash table interface.
+   Copyright (C) 1995, 2003 Free Software Foundation, Inc.
+   Written by Miles Bader <miles@gnu.org>.
+   Revised by Marcus Brinkmann <marcus@gnu.org>.
 
-   Copyright (C) 1995 Free Software Foundation, Inc.
+   This file is part of the GNU Hurd.
 
-   Written by Miles Bader <miles@gnu.ai.mit.edu>
-
-   This program is free software; you can redistribute it and/or
+   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) any later version.
 
-   This program is distributed in the hope that it will be useful, but
+   The GNU Hurd is distributed in the hope that it will be useful, but
    WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    General Public License for more details.
 
    You should have received a copy of the GNU General Public License
-   along with this program; if not, write to the Free Software
-   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */
+   along with the GNU Hurd; if not, write to the Free Software
+   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
 
-#ifndef __IHASH_H__
-#define __IHASH_H__
+#ifndef _HURD_IHASH_H
+#define _HURD_IHASH_H	1
 
 #include <errno.h>
+#include <sys/types.h>
+#include <limits.h>
+#include <stdint.h>
 
 
-/* ---------------------------------------------------------------- */
+/* The type of the values corresponding to the keys.  Must be a
+   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 value entry in the hash table is _HURD_IHASH_EMPTY or
+   _HURD_IHASH_DELETED, then the location is available, and none of
+   the other members of the item 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)
+
+/* The type of integer we want to use for the keys.  */
+typedef uintptr_t hurd_ihash_key_t;
+
+/* The type of a location pointer, which is a pointer to the hash
+   value stored in the hash table.  */
+typedef hurd_ihash_value_t *hurd_ihash_locp_t;
 
-typedef struct ihash *ihash_t;
+
+/* The type of the cleanup function, which is called for every value
+   removed from the hash table.  */
+typedef void (*hurd_ihash_cleanup_t) (hurd_ihash_value_t value, void *arg);
 
-struct ihash
+
+struct _hurd_ihash_item
 {
-  /* An array storing the elements in the hash table (each a void *).  */
-  void **tab;
+  /* 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;
 
-  /* An array storing the integer key for each element.  */
-  int *ids;
+  /* The integer key of this hash item.  */
+  hurd_ihash_key_t key;
+};
+typedef struct _hurd_ihash_item *_hurd_ihash_item_t;
 
-  /* An array storing pointers to the `location pointers' for each element.
-     These are used as cookies for quick 'n' easy removal.  */
-  void ****locps;		/* four, count them, four stars */
+struct hurd_ihash
+{
+  /* The number of hashed elements.  */
+  size_t nr_items;
 
-  /* The length of all these arrays.  */
-  int size;
+  /* An array of (key, value) pairs.  */
+  _hurd_ihash_item_t items;
 
-  /* When freeing or overwriting an element, this function, if non-NULL, is
-     called with the value as the first argument, and CLEANUP_ARG as the
-     second argument.  */
-  void (*cleanup)(void *element, void *arg);
-  void *cleanup_arg;
-};
+  /* The length of the array ITEMS.  */
+  size_t size;
 
-/* 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);
-
-/* Free HT and all resources it consumes.  */
-void ihash_free(ihash_t 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.  */
-void ihash_set_cleanup(ihash_t ht,
-		       void (*cleanup)(void *value, void *arg),
-		       void *arg);
-
-/* 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 call 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);
+  /* The offset of the location pointer from the hash value.  */
+  off_t locp_offset;
 
-/* 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);
+  /* The maximum load factor in percent.  */
+  int max_load;
 
-/* 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 *));
+  /* 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.  */
+  hurd_ihash_cleanup_t cleanup;
+  void *cleanup_data;
+};
+typedef struct hurd_ihash *hurd_ihash_t;
 
-/* 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.  */
-int ihash_remove(ihash_t ht, int id);
+
+/* Construction and destruction of hash tables.  */
+
+/* The default value for the maximum load factor in percent.  */
+#define HURD_IHASH_MAX_LOAD_DEFAULT 80
+
+/* The LOCP_OFFS to use if no location pointer is available.  */
+#define HURD_IHASH_NO_LOCP	INT_MIN
+
+/* The static initializer for a struct hurd_ihash.  */
+#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
+   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);
+
+/* 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
+   by hurd_ihash_create().  */
+void hurd_ihash_free (hurd_ihash_t ht);
 
-/* 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 **ht_locp);
+
+/* 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.  */
+void hurd_ihash_set_cleanup (hurd_ihash_t ht, hurd_ihash_cleanup_t cleanup,
+			     void *cleanup_data);
+
+/* 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);
 
-#endif /* __IHASH_H__ */
+
+/* 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);
+
+/* 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);
+
+/* Iterate over all elements in the hash table.  You use this macro
+   with a block, for example like this:
+
+     error_t err;
+     HURD_IHASH_ITERATE (ht, value)
+       {
+         err = foo (value);
+         if (err)
+           break;
+       }
+     if (err)
+       cleanup_and_return ();
+
+   Or even like this:
+
+     hurd_ihash_iterate (ht, value)
+       foo (value);
+
+   The block will be run for every element in the hash table HT.  The
+   value of the current element is available in the variable VALUE
+   (which is declared for you and local to the block).  */
+
+/* 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 (or both) 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, val)					\
+  for (hurd_ihash_value_t val,						\
+         *_hurd_ihash_valuep = (ht)->size ? &(ht)->items[0].value : 0;	\
+       (ht)->size							\
+         && ((_hurd_ihash_item_t) _hurd_ihash_valuep) - &(ht)->items[0]	\
+            < (ht)->size						\
+         && (val = *_hurd_ihash_valuep, 1);				\
+       _hurd_ihash_valuep = (hurd_ihash_value_t *)			\
+	 (((_hurd_ihash_item_t) _hurd_ihash_valuep)++))			\
+    if (val != _HURD_IHASH_EMPTY && val != _HURD_IHASH_DELETED)
+
+/* 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 hurd_ihash_remove (hurd_ihash_t ht, hurd_ihash_key_t key);
+
+/* Remove the entry pointed to by the location pointer LOCP from the
+   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().  */
+void hurd_ihash_locp_remove (hurd_ihash_t ht, hurd_ihash_locp_t locp);
+
+#endif	/* _HURD_IHASH_H */
diff --git a/libihash/primes.c b/libihash/primes.c
deleted file mode 100644
index 61b1d7e9..00000000
--- a/libihash/primes.c
+++ /dev/null
@@ -1,140 +0,0 @@
-/* Prime number generation
-   Copyright (C) 1994, 1996, 1999 Free Software Foundation
-
-   This program 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) any later version.
-
-   This program is distributed in the hope that it will be useful, but
-   WITHOUT ANY WARRANTY; without even the implied warranty of
-   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
-   General Public License for more details.
-
-   You should have received a copy of the GNU General Public License
-   along with this program; if not, write to the Free Software
-   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */
-
-#include <stdlib.h>
-#include <limits.h>
-#include <string.h>
-#include <assert.h>
-#include <spin-lock.h>
-#include "priv.h"
-
-#define BITS_PER_UNSIGNED (8 * sizeof (unsigned))
-#define SQRT_INT_MAX (1 << (BITS_PER_UNSIGNED / 2))
-
-static spin_lock_t table_lock = SPIN_LOCK_INITIALIZER;
-
-/* Return the next prime greater than or equal to N. */
-int
-_ihash_nextprime (unsigned n)
-{
-  /* Among other things, We guarantee that, for all i (0 <= i < primes_len),
-     primes[i] is a prime,
-     next_multiple[i] is a multiple of primes[i],
-     next_multiple[i] > primes[primes_len - 1],
-     next_multiple[i] is not a multiple of two unless primes[i] == 2, and
-     next_multiple[i] is the smallest such value.  */
-  static unsigned *primes, *next_multiple;
-  static int primes_len;
-  static int primes_size;
-  static unsigned next_sieve;	/* always even */
-  unsigned max_prime;
-
-  spin_lock (&table_lock);
-
-  if (! primes)
-    {
-      primes_size = 128;
-      primes        = (unsigned *) malloc (primes_size * sizeof (*primes));
-      next_multiple = (unsigned *) malloc (primes_size
-					   * sizeof (*next_multiple));
-
-      primes[0] = 2;		next_multiple[0] = 6;
-      primes[1] = 3;		next_multiple[1] = 9;
-      primes[2] = 5;		next_multiple[2] = 15;
-      primes_len = 3;
-
-      next_sieve = primes[primes_len - 1] + 1;
-    }
-
-  if (n <= primes[0])
-    {
-      spin_unlock (&table_lock);
-      return primes[0];
-    }
-
-  while (n > (max_prime = primes[primes_len - 1]))
-    {
-      /* primes doesn't contain any prime large enough.  Sieve from
-         max_prime + 1 to 2 * max_prime, looking for more primes.  */
-      unsigned start = next_sieve;
-      unsigned end   = start + max_prime + 1;
-      char sieve[end - start];
-      int i;
-
-      bzero (sieve, (end - start) * sizeof (*sieve));
-
-      /* Make the sieve indexed by prime number, rather than
-	 distance-from-start-to-the-prime-number.  When we're done,
-	 sieve[P] will be zero iff P is prime.  */
-#define sieve (sieve - start)
-
-      /* Set sieve[i] for all composites i, start <= i < end.
-	 Ignore multiples of 2.  */
-      for (i = 1; i < primes_len; i++)
-	{
-	  unsigned twice_prime = 2 * primes[i];
-	  unsigned multiple;
-
-	  for (multiple = next_multiple[i];
-	       multiple < end;
-	       multiple += twice_prime)
-	    sieve[multiple] = 1;
-	  next_multiple[i] = multiple;
-	}
-
-      for (i = start + 1; i < end; i += 2)
-	if (! sieve[i])
-	  {
-	    if (primes_len >= primes_size)
-	      {
-		primes_size *= 2;
-		primes = (int *) realloc (primes,
-					  primes_size * sizeof (*primes));
-		next_multiple
-		  = (int *) realloc (next_multiple,
-				     primes_size * sizeof (*next_multiple));
-	      }
-	    primes[primes_len] = i;
-	    if (i >= SQRT_INT_MAX)
-	      next_multiple[primes_len] = INT_MAX;
-	    else
-	      next_multiple[primes_len] = i * i;
-	    primes_len++;
-	  }
-
-      next_sieve = end;
-    }
-
-  /* Now we have at least one prime >= n.  Find the smallest such.  */
-  {
-    int bottom = 0;
-    int top = primes_len;
-
-    while (bottom < top)
-      {
-	int mid = (bottom + top) / 2;
-
-	if (primes[mid] < n)
-	  bottom = mid + 1;
-	else
-	  top = mid;
-      }
-
-    spin_unlock (&table_lock);
-    return primes[top];
-  }
-}
diff --git a/libihash/priv.h b/libihash/priv.h
deleted file mode 100644
index f31bf6c6..00000000
--- a/libihash/priv.h
+++ /dev/null
@@ -1,21 +0,0 @@
-/* Private declarations for ihash library
-   Copyright (C) 1996,2001 Free Software Foundation, Inc.
-
-   This file is part of the GNU Hurd.
-
-   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) any later version.
-
-   The GNU Hurd is distributed in the hope that it will be useful, but
-   WITHOUT ANY WARRANTY; without even the implied warranty of
-   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
-   General Public License for more details.
-
-   You should have received a copy of the GNU General Public License
-   along with this program; if not, write to the Free Software
-   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111, USA. */
-
-extern const unsigned int _ihash_sizes[];
-const unsigned int _ihash_nsizes;
diff --git a/libihash/sizes.c b/libihash/sizes.c
deleted file mode 100644
index 17f3fb1f..00000000
--- a/libihash/sizes.c
+++ /dev/null
@@ -1,41 +0,0 @@
-/* Some prime numbers for the ihash library.
-   I cannot bring myself to assert copyright over a list of prime numbers.
-   This file is in the public domain.  */
-
-#include "priv.h"
-
-/* The prime numbers greater than twice the last and less than 2^32.  */
-const unsigned int _ihash_sizes[] =
-{
-  2,
-  5,
-  11,
-  23,
-  47,
-  97,
-  197,
-  397,
-  797,
-  1597,
-  3203,
-  6421,
-  12853,
-  25717,
-  51437,
-  102877,
-  205759,
-  411527,
-  823117,
-  1646237,
-  3292489,
-  6584983,
-  13169977,
-  26339969,
-  52679969,
-  105359939,
-  210719881,
-  421439783,
-};
-
-const unsigned int _ihash_nsizes = (sizeof _ihash_sizes
-				    / sizeof _ihash_sizes[0]);