diff options
Diffstat (limited to 'libihash')
| -rw-r--r-- | libihash/ChangeLog | 36 | ||||
| -rw-r--r-- | libihash/Makefile | 32 | ||||
| -rw-r--r-- | libihash/ihash.c | 280 | ||||
| -rw-r--r-- | libihash/ihash.h | 97 | ||||
| -rw-r--r-- | libihash/primes.c | 140 | ||||
| -rw-r--r-- | libihash/priv.h | 21 |
6 files changed, 606 insertions, 0 deletions
diff --git a/libihash/ChangeLog b/libihash/ChangeLog new file mode 100644 index 00000000..5137f6cf --- /dev/null +++ b/libihash/ChangeLog @@ -0,0 +1,36 @@ +1999-03-07 Roland McGrath <roland@baalperazim.frob.com> + + * primes.c: Fix last change. + +Fri Mar 5 17:13:04 1999 Thomas Bushnell, BSG <tb@mit.edu> + + * primes.c (_ihash_nextprime): Use a dynamically-sized array for + `seive' instead of alloca, so that if we are looping we won't + allocate more stack than necessary. Suggested by wesommer@mit.edu + (Bill Sommerfeld). + +1997-06-20 Miles Bader <miles@gnu.ai.mit.edu> + + * ihash.c (ihash_create): Initialize CLEANUP & CLEANUP_ARG fields. + +Thu Apr 11 15:26:18 1996 Michael I. Bushnell, p/BSG <mib@gnu.ai.mit.edu> + + * ihash.c: Include "priv.h". + * primes.c: Likewise. + * priv.h: New file. + * Makefile (LCLHDRS): Add priv.h. + * primes.c (_ihash_nextprime): Renamed from nextprime.c. All + callers changed. + +Thu Mar 7 15:01:46 1996 Michael I. Bushnell, p/BSG <mib@gnu.ai.mit.edu> + + * primes.c: Include <spin_lock.h>. + (table_lock): New variable. + (nextprime): Lock table_lock around operation of routine. + +Sun Aug 6 15:23:13 1995 Miles Bader <miles@churchy.gnu.ai.mit.edu> + + * ihash.c (ihash_locp_remove): Get rid of the optimization to use + HASH_EMPTY instead of HASH_DEL when the next position on the chain + is empty -- different hash chains may share this cell, and have + different next positions. diff --git a/libihash/Makefile b/libihash/Makefile new file mode 100644 index 00000000..92078c63 --- /dev/null +++ b/libihash/Makefile @@ -0,0 +1,32 @@ +# +# Copyright (C) 1995, 1996 Free Software Foundation, Inc. +# Written by Michael I. Bushnell. +# +# 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., 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 +installhdrs = ihash.h + +include ../Makeconf + + diff --git a/libihash/ihash.c b/libihash/ihash.c new file mode 100644 index 00000000..635a90c2 --- /dev/null +++ b/libihash/ihash.c @@ -0,0 +1,280 @@ +/* Integer-keyed hash table functions. + + Copyright (C) 1993, 1994, 1995, 1996, 1997 Free Software Foundation, Inc. + + This file is part of the GNU Hurd. + + Written by Michael I. Bushnell; revised by Miles Bader <miles@gnu>. + + 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 the GNU Hurd; see the file COPYING. If not, write to + the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ + +#include <string.h> +#include <stdlib.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) + +/* ---------------------------------------------------------------- */ + +static inline int +index_empty(ihash_t ht, int index) +{ + return ht->tab[index] == HASH_EMPTY || ht->tab[index] == HASH_DEL; +} + +static inline int +index_valid(ihash_t ht, int index, int id) +{ + return !index_empty(ht, index) && ht->ids[index] == id; +} + +/* 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()). */ +static inline int +find_index(ihash_t ht, int id) +{ + int h, firsth = -1; + + 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; + + return h; +} + +/* ---------------------------------------------------------------- */ + +/* 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) +{ + *ht = malloc(sizeof(struct ihash)); + if (*ht == NULL) + return ENOMEM; + (*ht)->size = 0; + (*ht)->cleanup = 0; + (*ht)->cleanup_arg = 0; + return 0; +} + +/* Free HT and all resources it consumes. */ +void +ihash_free(ihash_t ht) +{ + void (*cleanup)(void *value, void *arg) = ht->cleanup; + + if (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); + } + + if (ht->size > 0) + { + free(ht->tab); + free(ht->ids); + free(ht->locps); + } + + 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. */ +void +ihash_set_cleanup(ihash_t ht, + void (*cleanup)(void *value, void *arg), + void *arg) +{ + ht->cleanup = cleanup; + ht->cleanup_arg = 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 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) +{ + if (ht->size) + { + int h, firsth = -1; + + /* 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; + + if (index_empty(ht, h) || ht->ids[h] == id) + { + if (!index_empty(ht, h) && ht->cleanup) + ht->cleanup(ht->tab[h], ht->cleanup_arg); + + ht->tab[h] = item; + ht->ids[h] = id; + ht->locps[h] = locp; + + if (locp) + *locp = &ht->tab[h]; + + return 0; + } + } + + { + int i; + void **entry; + int old_size = ht->size; + void **old_tab = ht->tab; + void ****old_locps = ht->locps; + int *old_ids = ht->ids; + + ht->size = _ihash_nextprime (2 * old_size); + 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); + + ht->size = old_size; + ht->tab = old_tab; + ht->locps = old_locps; + ht->ids = old_ids; + + return ENOMEM; + } + + for (i = ht->size, entry = ht->tab; i > 0; i--, entry++) + *entry = HASH_EMPTY; + + /* 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]); + + /* Finally add the new element! */ + ihash_add(ht, id, item, locp); + + if (old_size > 0) + { + free(old_tab); + free(old_locps); + free(old_ids); + } + + 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) +{ + if (ht->size == 0) + return 0; + else + { + int index = find_index(ht, id); + return index_valid(ht, index, id) ? ht->tab[index] : 0; + } +} + +/* ---------------------------------------------------------------- */ + +/* 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. */ +int +ihash_remove(ihash_t ht, int id) +{ + int index = find_index(ht, id); + if (index_valid(ht, index, id)) + { + ihash_locp_remove(ht, &ht->tab[index]); + return 1; + } + else + return 0; +} diff --git a/libihash/ihash.h b/libihash/ihash.h new file mode 100644 index 00000000..5d01ea1c --- /dev/null +++ b/libihash/ihash.h @@ -0,0 +1,97 @@ +/* Integer-keyed hash table functions. + + Copyright (C) 1995 Free Software Foundation, Inc. + + Written by Miles Bader <miles@gnu.ai.mit.edu> + + 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. */ + +#ifndef __IHASH_H__ +#define __IHASH_H__ + +#include <errno.h> + + +/* ---------------------------------------------------------------- */ + +typedef struct ihash *ihash_t; + +struct ihash +{ + /* An array storing the elements in the hash table (each a void *). */ + void **tab; + + /* An array storing the integer key for each element. */ + int *ids; + + /* 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 */ + + /* The length of all these arrays. */ + int size; + + /* 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; +}; + +/* 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); + +/* 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); + +/* 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 *)); + +/* 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); + +/* 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); + +#endif /* __IHASH_H__ */ diff --git a/libihash/primes.c b/libihash/primes.c new file mode 100644 index 00000000..61b1d7e9 --- /dev/null +++ b/libihash/primes.c @@ -0,0 +1,140 @@ +/* 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 new file mode 100644 index 00000000..5d235700 --- /dev/null +++ b/libihash/priv.h @@ -0,0 +1,21 @@ +/* Private declaration for ihash library + Copyright (C) 1996 Free Software Foundation, Inc. + Written by Michael I. Bushnell, p/BSG. + + 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. */ + +int _ihash_nextprime (unsigned); |