2001-08-15 Roland McGrath <roland@frob.com>

	* sizes.c: New file, a list of prime numbers useful for table sizes.
	* priv.h (_ihash_sizes, _ihash_nsizes): Declare.
	(_ihash_nextprime): Don't.
	* ihash.c (ihash_add): Select sizes from the _ihash_sizes array
	instead of using _ihash_nextprime.
	* Makefile: Clean up whitespace, reorder all the variable definitions.
	(SRCS): Remove primes.c, add sizes.c instead.
	(OBJS): Define dynamically.

4 files changed, 70 insertions, 26 deletions

diff --git a/libihash/Makefile b/libihash/Makefile
index 92078c63..902ff6d3 100644
--- a/libihash/Makefile
+++ b/libihash/Makefile
@@ -1,6 +1,5 @@
-# 
-#   Copyright (C) 1995, 1996 Free Software Foundation, Inc.
-#   Written by Michael I. Bushnell.
+#
+#   Copyright (C) 1995,96,2001 Free Software Foundation, Inc.
 #
 #   This file is part of the GNU Hurd.
 #
@@ -17,16 +16,15 @@
 #   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.
- 
+
 dir := libihash
 makemode := library
 
-SRCS=ihash.c primes.c
-LCLHDRS=ihash.h priv.h
-OBJS=ihash.o primes.o
 libname := libihash
+SRCS = ihash.c sizes.c
 installhdrs = ihash.h
+LCLHDRS = $(installhdrs) priv.h
 
-include ../Makeconf
-
+OBJS = $(SRCS:.c=.o)
 
+include ../Makeconf
diff --git a/libihash/ihash.c b/libihash/ihash.c
index 635a90c2..dfc36b01 100644
--- a/libihash/ihash.c
+++ b/libihash/ihash.c
@@ -1,21 +1,21 @@
 /* Integer-keyed hash table functions.
 
-   Copyright (C) 1993, 1994, 1995, 1996, 1997 Free Software Foundation, Inc.
-   
+   Copyright (C) 1993,94,95,96,97,2001 Free Software Foundation, Inc.
+
    This file is part of the GNU Hurd.
 
-   Written by Michael I. Bushnell; revised by Miles Bader <miles@gnu>.
-   
+   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)
    any later version.
-   
-   The GNU Hurd is distributed in the hope that it will be useful, 
+
+   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 the GNU Hurd; see the file COPYING.  If not, write to
    the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
@@ -65,7 +65,7 @@ find_index(ihash_t ht, int id)
 {
   int h, firsth = -1;
 
-  for (h = HASH(ht, id); 
+  for (h = HASH(ht, id);
        ht->tab[h] != HASH_EMPTY && ht->ids[h] != id && h != firsth;
        h = REHASH(ht, id, h))
     if (firsth == -1)
@@ -91,7 +91,7 @@ ihash_create(ihash_t *ht)
 }
 
 /* Free HT and all resources it consumes.  */
-void 
+void
 ihash_free(ihash_t ht)
 {
   void (*cleanup)(void *value, void *arg) = ht->cleanup;
@@ -145,7 +145,7 @@ ihash_add(ihash_t ht, int id, void *item, void ***locp)
       int h, firsth = -1;
 
       /* Search for for an empty or deleted space.  */
-      for (h = HASH(ht, id); 
+      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)
@@ -175,11 +175,16 @@ ihash_add(ihash_t ht, int id, void *item, void ***locp)
     void ****old_locps = ht->locps;
     int *old_ids = ht->ids;
 
-    ht->size = _ihash_nextprime (2 * old_size);
+    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...  */
       {
@@ -206,7 +211,7 @@ ihash_add(ihash_t ht, int id, void *item, void ***locp)
 
     /* Finally add the new element!  */
     ihash_add(ht, id, item, locp);
-  
+
     if (old_size > 0)
       {
 	free(old_tab);
diff --git a/libihash/priv.h b/libihash/priv.h
index 5d235700..f31bf6c6 100644
--- a/libihash/priv.h
+++ b/libihash/priv.h
@@ -1,6 +1,5 @@
-/* Private declaration for ihash library
-   Copyright (C) 1996 Free Software Foundation, Inc.
-   Written by Michael I. Bushnell, p/BSG.
+/* Private declarations for ihash library
+   Copyright (C) 1996,2001 Free Software Foundation, Inc.
 
    This file is part of the GNU Hurd.
 
@@ -18,4 +17,5 @@
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111, USA. */
 
-int _ihash_nextprime (unsigned);
+extern const unsigned int _ihash_sizes[];
+const unsigned int _ihash_nsizes;
diff --git a/libihash/sizes.c b/libihash/sizes.c
new file mode 100644
index 00000000..17f3fb1f
--- /dev/null
+++ b/libihash/sizes.c
@@ -0,0 +1,41 @@
+/* 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]);