From 175fa7701ded3785c31e82581f74e2fd32db7330 Mon Sep 17 00:00:00 2001
From: Roland McGrath <roland@gnu.org>
Date: Wed, 15 Aug 2001 09:29:26 +0000
Subject: 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.
---
libihash/Makefile | 16 +++++++---------
libihash/ihash.c | 31 ++++++++++++++++++-------------
libihash/priv.h | 8 ++++----
libihash/sizes.c | 41 +++++++++++++++++++++++++++++++++++++++++
4 files changed, 70 insertions(+), 26 deletions(-)
create mode 100644 libihash/sizes.c
(limited to 'libihash')
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]);
--
cgit v1.2.3