From 4a220521e7b46263b156a6c784856a996997df76 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 8 Jun 2002 13:17:39 +0000 Subject: [PATCH] The universal hash table generator now uses prime table sizes instead of powers of two. This slows down all operations a little as we now need to perform division instead of just AND-ing with a mask, but it allows us to use the new hash functions in hashfunc.h which are significantly faster than the original ones (at the expense of having bad distribution modulo non-primes). Also changed the limit logic to avoid rehashing when the table is already too small or too large. --- lib/hash-test.c | 8 ++++---- lib/hashtable.h | 31 +++++++++++++++++-------------- 2 files changed, 21 insertions(+), 18 deletions(-) diff --git a/lib/hash-test.c b/lib/hash-test.c index c03d9fa4..2f835613 100644 --- a/lib/hash-test.c +++ b/lib/hash-test.c @@ -5,7 +5,7 @@ #include #include -#if 1 +#if 0 /* TEST 1: integers */ @@ -111,7 +111,7 @@ static void test(void) log(L_INFO, "OK"); } -#elif 0 +#elif 1 /* TEST 3: internal strings + pools */ @@ -141,13 +141,13 @@ static void test(void) pool = mp_new(16384); test_init(); - for (i=0; i<1024; i+=2) + for (i=0; i<1048576; i+=2) { char x[32]; sprintf(x, "abc%d", i); test_new(x); } - for (i=0; i<1024; i++) + for (i=0; i<1048576; i++) { char x[32]; struct node *n; diff --git a/lib/hashtable.h b/lib/hashtable.h index f96a07fd..17b6d08e 100644 --- a/lib/hashtable.h +++ b/lib/hashtable.h @@ -76,8 +76,7 @@ * ... and a couple of extra parameters: * * HASH_NOCASE string comparisons should be case-insensitive. - * HASH_DEFAULT_SIZE=n initially, use hash table of `n' entries. - * The `n' has to be a power of two. + * HASH_DEFAULT_SIZE=n initially, use hash table of approx. `n' entries. * HASH_CONSERVE_SPACE use as little space as possible. * HASH_FN_BITS=n The hash function gives only `n' significant bits. * HASH_ATOMIC_TYPE=t Atomic values are of type `t' instead of int. @@ -128,7 +127,7 @@ typedef struct P(bucket) { struct P(table) { uns hash_size; - uns hash_count, hash_max, hash_min, hash_hard_max, hash_mask; + uns hash_count, hash_max, hash_min, hash_hard_max; P(bucket) **ht; } P(table); @@ -284,13 +283,17 @@ static inline void P(free) (void *x) static void P(alloc_table) (void) { + T.hash_size = nextprime(T.hash_size); T.ht = xmalloc(sizeof(void *) * T.hash_size); bzero(T.ht, sizeof(void *) * T.hash_size); - T.hash_max = T.hash_size * 2; - if (T.hash_max > T.hash_hard_max) - T.hash_max = T.hash_hard_max; - T.hash_min = T.hash_size / 4; - T.hash_mask = T.hash_size - 1; + if (2*T.hash_size < T.hash_hard_max) + T.hash_max = 2*T.hash_size; + else + T.hash_max = ~0U; + if (T.hash_size/2 > HASH_DEFAULT_SIZE) + T.hash_min = T.hash_size/4; + else + T.hash_min = 0; } static void P(init) (void) @@ -349,7 +352,7 @@ static void P(rehash) (uns size) while (b) { nb = b->next; - h = P(bucket_hash)(b) & T.hash_mask; + h = P(bucket_hash)(b) % T.hash_size; b->next = newt[h]; newt[h] = b; b = nb; @@ -362,7 +365,7 @@ static void P(rehash) (uns size) static P(node) * P(find) (HASH_KEY_DECL) { uns h0 = P(hash) (HASH_KEY( )); - uns h = h0 & T.hash_mask; + uns h = h0 % T.hash_size; P(bucket) *b; for (b=T.ht[h]; b; b=b->next) @@ -385,7 +388,7 @@ static P(node) * P(new) (HASH_KEY_DECL) P(bucket) *b; h0 = P(hash) (HASH_KEY( )); - h = h0 & T.hash_mask; + h = h0 % T.hash_size; b = P(alloc) (sizeof(struct P(bucket)) + HASH_EXTRA_SIZE(HASH_KEY( ))); b->next = T.ht[h]; T.ht[h] = b; @@ -404,7 +407,7 @@ static P(node) * P(new) (HASH_KEY_DECL) static P(node) * P(lookup) (HASH_KEY_DECL) { uns h0 = P(hash) (HASH_KEY( )); - uns h = h0 & T.hash_mask; + uns h = h0 % T.hash_size; P(bucket) *b; for (b=T.ht[h]; b; b=b->next) @@ -435,7 +438,7 @@ static P(node) * P(lookup) (HASH_KEY_DECL) static int P(delete) (HASH_KEY_DECL) { uns h0 = P(hash) (HASH_KEY( )); - uns h = h0 & T.hash_mask; + uns h = h0 % T.hash_size; P(bucket) *b, **bb; for (bb=&T.ht[h]; b=*bb; bb=&b->next) @@ -462,7 +465,7 @@ static void P(remove) (P(node) *n) { P(bucket) *x = SKIP_BACK(struct P(bucket), n, n); uns h0 = P(bucket_hash)(x); - uns h = h0 & T.hash_mask; + uns h = h0 % T.hash_size; P(bucket) *b, **bb; for (bb=&T.ht[h]; (b=*bb) && b != x; bb=&b->next) -- 2.39.2