X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;ds=sidebyside;f=lib%2Fhashtable.h;h=1c40ea9d6729f3f7b61a75838fd9015d5e5852f1;hb=e828732528e0ed88973dd18f2dee97a42c0b4e59;hp=f96a07fd1f9aa61f685ed260619e36a1044e63ed;hpb=b23db618057b5aa8905c41df963d6fa865d82c8c;p=libucw.git diff --git a/lib/hashtable.h b/lib/hashtable.h index f96a07fd..1c40ea9d 100644 --- a/lib/hashtable.h +++ b/lib/hashtable.h @@ -1,7 +1,11 @@ /* * Sherlock Library -- Universal Hash Table * - * (c) 2002 Martin Mares + * (c) 2002--2004 Martin Mares + * (c) 2002 Robert Spalek + * + * This software may be freely distributed and used according to the terms + * of the GNU Lesser General Public License. */ /* @@ -41,8 +45,10 @@ * * init() -- initialize the hash table. * HASH_WANT_CLEANUP cleanup() -- deallocate the hash table. - * HASH_WANT_FIND node *find(key) -- find node with the specified + * HASH_WANT_FIND node *find(key) -- find first node with the specified * key, return NULL if no such node exists. + * HASH_WANT_FIND_NEXT node *find(node *start) -- find next node with the + * specified key, return NULL if no such node exists. * HASH_WANT_NEW node *new(key) -- create new node with given key. * Doesn't check whether it already exists. * HASH_WANT_LOOKUP node *lookup(key) -- find node with given key, @@ -76,13 +82,13 @@ * ... 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. * HASH_USE_POOL=pool Allocate all nodes from given mempool. * Collides with delete/remove functions. + * HASH_AUTO_POOL=size Create a pool of the given block size automatically. * * You also get a iterator macro at no extra charge: * @@ -95,7 +101,7 @@ * } * HASH_END_FOR; * - * Then include and voila, you have a hash table + * Then include "lib/hashtable.h" and voila, you have a hash table * suiting all your needs (at least those which you've revealed :) ). * * After including this file, all parameter macros are automatically @@ -128,7 +134,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); @@ -255,21 +261,33 @@ static inline void P(init_data) (P(node) *n UNUSED) #include -#ifndef HASH_GIVE_ALLOC -#ifdef HASH_USE_POOL - -static inline void * P(alloc) (unsigned int size) -{ return mp_alloc_fast(HASH_USE_POOL, size); } +#ifdef HASH_GIVE_ALLOC +/* If the caller has requested to use his own allocation functions, do so */ +static inline void P(init_alloc) (void) { } +static inline void P(cleanup_alloc) (void) { } + +#elif defined(HASH_USE_POOL) +/* If the caller has requested to use his mempool, do so */ +#include "lib/mempool.h" +static inline void * P(alloc) (unsigned int size) { return mp_alloc_fast(HASH_USE_POOL, size); } +static inline void P(init_alloc) (void) { } +static inline void P(cleanup_alloc) (void) { } + +#elif defined(HASH_AUTO_POOL) +/* Use our own pools */ +#include "lib/mempool.h" +static struct mempool *P(pool); +static inline void * P(alloc) (unsigned int size) { return mp_alloc_fast(P(pool), size); } +static inline void P(init_alloc) (void) { P(pool) = mp_new(HASH_AUTO_POOL); } +static inline void P(cleanup_alloc) (void) { mp_delete(P(pool)); } #else +/* The default allocation method */ +static inline void * P(alloc) (unsigned int size) { return xmalloc(size); } +static inline void P(free) (void *x) { xfree(x); } +static inline void P(init_alloc) (void) { } +static inline void P(cleanup_alloc) (void) { } -static inline void * P(alloc) (unsigned int size) -{ return xmalloc(size); } - -static inline void P(free) (void *x) -{ xfree(x); } - -#endif #endif #ifndef HASH_DEFAULT_SIZE @@ -284,13 +302,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) @@ -303,6 +325,7 @@ static void P(init) (void) T.hash_hard_max = 1 << 28; #endif P(alloc_table)(); + P(init_alloc)(); } #ifdef HASH_WANT_CLEANUP @@ -319,6 +342,7 @@ static void P(cleanup) (void) P(free)(b); } #endif + P(cleanup_alloc)(); xfree(T.ht); } #endif @@ -349,7 +373,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 +386,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) @@ -378,6 +402,27 @@ static P(node) * P(find) (HASH_KEY_DECL) } #endif +#ifdef HASH_WANT_FIND_NEXT +static P(node) * P(find_next) (P(node) *start) +{ +#ifndef HASH_CONSERVE_SPACE + uns h0 = P(hash) (HASH_KEY(start->)); +#endif + P(bucket) *b = SKIP_BACK(P(bucket), n, start); + + for (b=b->next; b; b=b->next) + { + if ( +#ifndef HASH_CONSERVE_SPACE + b->hash == h0 && +#endif + P(eq)(HASH_KEY(start->), HASH_KEY(b->n.))) + return &b->n; + } + return NULL; +} +#endif + #ifdef HASH_WANT_NEW static P(node) * P(new) (HASH_KEY_DECL) { @@ -385,7 +430,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 +449,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 +480,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 +507,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) @@ -482,15 +527,14 @@ static void P(remove) (P(node) *n) #define HASH_FOR_ALL(h_px, h_var) \ do { \ uns h_slot; \ - struct HASH_GLUE(h_px,bucket) *h_buck; \ - for (h_slot=0; h_slot < HASH_GLUE(h_px,table).hash_size; h_slot++) \ - for (h_buck = HASH_GLUE(h_px,table).ht[h_slot]; h_buck; h_buck = h_buck->next) \ + struct GLUE_(h_px,bucket) *h_buck; \ + for (h_slot=0; h_slot < GLUE_(h_px,table).hash_size; h_slot++) \ + for (h_buck = GLUE_(h_px,table).ht[h_slot]; h_buck; h_buck = h_buck->next) \ { \ - HASH_GLUE(h_px,node) *h_var = &h_buck->n; + GLUE_(h_px,node) *h_var = &h_buck->n; #define HASH_END_FOR } } while(0) #define HASH_BREAK #define HASH_CONTINUE continue -#define HASH_GLUE(x,y) x##_##y #endif @@ -520,9 +564,11 @@ do { \ #undef HASH_NODE #undef HASH_PREFIX #undef HASH_USE_POOL +#undef HASH_AUTO_POOL #undef HASH_WANT_CLEANUP #undef HASH_WANT_DELETE #undef HASH_WANT_FIND +#undef HASH_WANT_FIND_NEXT #undef HASH_WANT_LOOKUP #undef HASH_WANT_NEW #undef HASH_WANT_REMOVE