Mercurial > hg > octave-kai > gnulib-hg
changeset 1033:f4f00c32582a
use malloc, not xmalloc in obstack #define
use Uli's prime code, not near-prime
(hash_initialize): don't require prime table size as input
(hash_insert_if_absent): When rehashing, choose new size that is 2N+1, not 2N.
| author | Jim Meyering <jim@meyering.net> |
|---|---|
| date | Wed, 17 Sep 1997 17:06:26 +0000 |
| parents | 0b6b7e10fe5f |
| children | eed1d91067c8 |
| files | lib/hash.c |
| diffstat | 1 files changed, 38 insertions(+), 4 deletions(-) [+] |
line wrap: on
line diff
--- a/lib/hash.c +++ b/lib/hash.c @@ -12,7 +12,6 @@ #include <stdlib.h> #include <assert.h> -#include "near-prime.h" #include "hash.h" #ifdef USE_OBSTACK @@ -27,6 +26,39 @@ static void hash_free_0 (HT *, int); +static int +is_prime (candidate) + unsigned long candidate; +{ + /* No even number and none less than 10 will be passed here. */ + unsigned long divn = 3; + unsigned long sq = divn * divn; + + while (sq < candidate && (candidate % divn)) + { + divn++; + sq += 4 * divn; + divn++; + } + + return (candidate % divn); +} + +/* Round a given number up to the nearest prime. */ + +static unsigned long +next_prime (candidate) + unsigned long candidate; +{ + /* Make it definitely odd. */ + candidate |= 1; + + while (!is_prime (candidate)) + candidate += 2; + + return candidate; +} + static void hash_free_entry (HT *ht, HASH_ENT *e) { @@ -156,15 +188,16 @@ function is called (e.g. a second time). */ HT * -hash_initialize (unsigned int table_size, +hash_initialize (unsigned int candidate_table_size, Hash_key_freer_type key_freer, unsigned int (*hash) (const void *, unsigned int), int (*key_comparator) (const void *, const void *)) { HT *ht; unsigned int i; + unsigned int table_size; - if (table_size <= 0) + if (candidate_table_size <= 0) return NULL; if (hash == NULL || key_comparator == NULL) @@ -174,6 +207,7 @@ if (ht == NULL) return NULL; + table_size = next_prime (candidate_table_size); ht->hash_table = (HASH_ENT **) malloc (table_size * sizeof (HASH_ENT *)); if (ht->hash_table == NULL) return NULL; @@ -336,7 +370,7 @@ if ((double) ht->hash_n_keys / ht->hash_table_size > 0.80) { unsigned int new_size; - new_size = near_prime (2 * ht->hash_table_size); + new_size = next_prime (2 * ht->hash_table_size + 1); *failed = hash_rehash (ht, new_size); }