2 * UCW Library -- Universal Hash Table
4 * (c) 2002--2004 Martin Mares <mj@ucw.cz>
5 * (c) 2002 Robert Spalek <robert@ucw.cz>
7 * This software may be freely distributed and used according to the terms
8 * of the GNU Lesser General Public License.
12 * This is not a normal header file, it's a generator of hash tables.
13 * Each time you include it with parameters set in the corresponding
14 * preprocessor macros, it generates a hash table with the parameters
17 * You need to specify:
19 * HASH_NODE data type where a node dwells (usually a struct).
20 * HASH_PREFIX(x) macro to add a name prefix (used on all global names
21 * defined by the hash table generator).
23 * Then decide on type of keys:
25 * HASH_KEY_ATOMIC=f use node->f as a key of an atomic type (i.e.,
26 * a type which can be compared using `==')
27 * HASH_ATOMIC_TYPE (defaults to int).
28 * | HASH_KEY_STRING=f use node->f as a string key, allocated
29 * separately from the rest of the node.
30 * | HASH_KEY_ENDSTRING=f use node->f as a string key, allocated
31 * automatically at the end of the node struct
32 * (to be declared as "char f[1]" at the end).
33 * | HASH_KEY_COMPLEX use a multi-component key; as the name suggests,
34 * the passing of parameters is a bit complex then.
35 * The HASH_KEY_COMPLEX(x) macro should expand to
36 * `x k1, x k2, ... x kn' and you should also define:
37 * HASH_KEY_DECL declaration of function parameters in which key
38 * should be passed to all hash table operations.
39 * That is, `type1 k1, type2 k2, ... typen kn'.
40 * With complex keys, HASH_GIVE_HASHFN and HASH_GIVE_EQ
43 * Then specify what operations you request (all names are automatically
44 * prefixed by calling HASH_PREFIX):
46 * <always defined> init() -- initialize the hash table.
47 * HASH_WANT_CLEANUP cleanup() -- deallocate the hash table.
48 * HASH_WANT_FIND node *find(key) -- find first node with the specified
49 * key, return NULL if no such node exists.
50 * HASH_WANT_FIND_NEXT node *find(node *start) -- find next node with the
51 * specified key, return NULL if no such node exists.
52 * HASH_WANT_NEW node *new(key) -- create new node with given key.
53 * Doesn't check whether it already exists.
54 * HASH_WANT_LOOKUP node *lookup(key) -- find node with given key,
55 * if it doesn't exist, create it. Defining
56 * HASH_GIVE_INIT_DATA is strongly recommended.
57 * HASH_WANT_DELETE int delete(key) -- delete and deallocate node
58 * with given key. Returns success.
59 * HASH_WANT_REMOVE remove(node *) -- delete and deallocate given node.
61 * You can also supply several functions:
63 * HASH_GIVE_HASHFN unsigned int hash(key) -- calculate hash value of key.
64 * We have sensible default hash functions for strings
66 * HASH_GIVE_EQ int eq(key1, key2) -- return whether keys are equal.
67 * By default, we use == for atomic types and either
68 * strcmp or strcasecmp for strings.
69 * HASH_GIVE_EXTRA_SIZE int extra_size(key) -- returns how many bytes after the
70 * node should be allocated for dynamic data. Default=0
71 * or length of the string with HASH_KEY_ENDSTRING.
72 * HASH_GIVE_INIT_KEY void init_key(node *,key) -- initialize key in a newly
73 * created node. Defaults: assignment for atomic keys
74 * and static strings, strcpy for end-allocated strings.
75 * HASH_GIVE_INIT_DATA void init_data(node *) -- initialize data fields in a
76 * newly created node. Very useful for lookup operations.
77 * HASH_GIVE_ALLOC void *alloc(unsigned int size) -- allocate space for
78 * a node. Default is xmalloc() or pooled allocation, depending
79 * on HASH_USE_POOL and HASH_AUTO_POOL switches.
80 * void free(void *) -- the converse.
82 * ... and a couple of extra parameters:
84 * HASH_NOCASE String comparisons should be case-insensitive.
85 * HASH_DEFAULT_SIZE=n Initially, use hash table of approx. `n' entries.
86 * HASH_CONSERVE_SPACE Use as little space as possible.
87 * HASH_FN_BITS=n The hash function gives only `n' significant bits.
88 * HASH_ATOMIC_TYPE=t Atomic values are of type `t' instead of int.
89 * HASH_USE_POOL=pool Allocate all nodes from given mempool. Note, however, that
90 * deallocation is not supported by mempools, so delete/remove
91 * will leak pool memory.
92 * HASH_AUTO_POOL=size Create a pool of the given block size automatically.
93 * HASH_ZERO_FILL New entries should be initialized to all zeroes.
94 * HASH_TABLE_ALLOC The hash table itself will be allocated and freed using
95 * the same allocation functions as the nodes instead of
96 * the default xmalloc().
97 * HASH_TABLE_DYNAMIC Support multiple hash tables; the first parameter of all
98 * hash table operations is struct HASH_PREFIX(table) *.
100 * You also get a iterator macro at no extra charge:
102 * HASH_FOR_ALL(hash_prefix, variable)
104 * // node *variable gets declared automatically
105 * do_something_with_node(variable);
106 * // use HASH_BREAK and HASH_CONTINUE instead of break and continue
107 * // you must not alter contents of the hash table here
111 * (For dynamic tables, use HASH_FOR_ALL_DYNAMIC(hash_prefix, hash_table, variable) instead.)
113 * Then include "lib/hashtable.h" and voila, you have a hash table
114 * suiting all your needs (at least those which you've revealed :) ).
116 * After including this file, all parameter macros are automatically
120 #ifndef _UCW_HASHFUNC_H
121 #include "lib/hashfunc.h"
126 /* Initial setup of parameters */
128 #if !defined(HASH_NODE) || !defined(HASH_PREFIX)
129 #error Some of the mandatory configuration macros are missing.
132 #if defined(HASH_KEY_ATOMIC) && !defined(HASH_CONSERVE_SPACE)
133 #define HASH_CONSERVE_SPACE
136 #define P(x) HASH_PREFIX(x)
138 /* Declare buckets and the hash table */
140 typedef HASH_NODE P(node);
142 typedef struct P(bucket) {
143 struct P(bucket) *next;
144 #ifndef HASH_CONSERVE_SPACE
152 uns hash_count, hash_max, hash_min, hash_hard_max;
156 #ifdef HASH_TABLE_DYNAMIC
158 #define TA struct P(table) *table
160 #define TAU TA UNUSED
161 #define TAUC TA UNUSED,
165 struct P(table) P(table);
175 /* Preset parameters */
177 #if defined(HASH_KEY_ATOMIC)
179 #define HASH_KEY(x) x HASH_KEY_ATOMIC
181 #ifndef HASH_ATOMIC_TYPE
182 # define HASH_ATOMIC_TYPE int
184 #define HASH_KEY_DECL HASH_ATOMIC_TYPE HASH_KEY( )
186 #ifndef HASH_GIVE_HASHFN
187 # define HASH_GIVE_HASHFN
188 static inline int P(hash) (TAUC HASH_ATOMIC_TYPE x)
189 { return ((sizeof(x) <= 4) ? hash_u32(x) : hash_u64(x)); }
193 # define HASH_GIVE_EQ
194 static inline int P(eq) (TAUC HASH_ATOMIC_TYPE x, HASH_ATOMIC_TYPE y)
198 #ifndef HASH_GIVE_INIT_KEY
199 # define HASH_GIVE_INIT_KEY
200 static inline void P(init_key) (TAUC P(node) *n, HASH_ATOMIC_TYPE k)
201 { HASH_KEY(n->) = k; }
204 #elif defined(HASH_KEY_STRING) || defined(HASH_KEY_ENDSTRING)
206 #ifdef HASH_KEY_STRING
207 # define HASH_KEY(x) x HASH_KEY_STRING
208 # ifndef HASH_GIVE_INIT_KEY
209 # define HASH_GIVE_INIT_KEY
210 static inline void P(init_key) (TAUC P(node) *n, char *k)
211 { HASH_KEY(n->) = k; }
214 # define HASH_KEY(x) x HASH_KEY_ENDSTRING
215 # define HASH_GIVE_EXTRA_SIZE
216 static inline int P(extra_size) (TAUC char *k)
217 { return strlen(k); }
218 # ifndef HASH_GIVE_INIT_KEY
219 # define HASH_GIVE_INIT_KEY
220 static inline void P(init_key) (TAUC P(node) *n, char *k)
221 { strcpy(HASH_KEY(n->), k); }
224 #define HASH_KEY_DECL char *HASH_KEY( )
226 #ifndef HASH_GIVE_HASHFN
227 #define HASH_GIVE_HASHFN
228 static inline uns P(hash) (TAUC char *k)
231 return hash_string_nocase(k);
233 return hash_string(k);
239 # define HASH_GIVE_EQ
240 static inline int P(eq) (TAUC char *x, char *y)
243 return !strcasecmp(x,y);
250 #elif defined(HASH_KEY_COMPLEX)
252 #define HASH_KEY(x) HASH_KEY_COMPLEX(x)
255 #error You forgot to set the hash key type.
258 /* Defaults for missing parameters */
260 #ifndef HASH_GIVE_HASHFN
261 #error Unable to determine which hash function to use.
265 #error Unable to determine how to compare two keys.
268 #ifdef HASH_GIVE_EXTRA_SIZE
269 /* This trickery is needed to avoid `unused parameter' warnings */
270 #define HASH_EXTRA_SIZE(x) P(extra_size)(TTC x)
273 * Beware, C macros are expanded iteratively, not recursively,
274 * hence we get only a _single_ argument, although the expansion
275 * of HASH_KEY contains commas.
277 #define HASH_EXTRA_SIZE(x) 0
280 #ifndef HASH_GIVE_INIT_KEY
281 #error Unable to determine how to initialize keys.
284 #ifndef HASH_GIVE_INIT_DATA
285 static inline void P(init_data) (TAUC P(node) *n UNUSED)
292 #ifdef HASH_GIVE_ALLOC
293 /* If the caller has requested to use his own allocation functions, do so */
294 static inline void P(init_alloc) (TAU) { }
295 static inline void P(cleanup_alloc) (TAU) { }
297 #elif defined(HASH_USE_POOL)
298 /* If the caller has requested to use his mempool, do so */
299 #include "lib/mempool.h"
300 static inline void * P(alloc) (TAUC unsigned int size) { return mp_alloc_fast(HASH_USE_POOL, size); }
301 static inline void P(free) (TAUC void *x UNUSED) { }
302 static inline void P(init_alloc) (TAU) { }
303 static inline void P(cleanup_alloc) (TAU) { }
305 #elif defined(HASH_AUTO_POOL)
306 /* Use our own pools */
307 #include "lib/mempool.h"
308 static struct mempool *P(pool);
309 static inline void * P(alloc) (TAUC unsigned int size) { return mp_alloc_fast(P(pool), size); }
310 static inline void P(free) (TAUC void *x UNUSED) { }
311 static inline void P(init_alloc) (TAU) { P(pool) = mp_new(HASH_AUTO_POOL); }
312 static inline void P(cleanup_alloc) (TAU) { mp_delete(P(pool)); }
315 /* The default allocation method */
316 static inline void * P(alloc) (TAUC unsigned int size) { return xmalloc(size); }
317 static inline void P(free) (TAUC void *x) { xfree(x); }
318 static inline void P(init_alloc) (TAU) { }
319 static inline void P(cleanup_alloc) (TAU) { }
323 #ifdef HASH_TABLE_ALLOC
324 static inline void * P(table_alloc) (TAUC unsigned int size) { return P(alloc)(size); }
325 static inline void P(table_free) (TAUC void *x) { P(free)(x); }
327 static inline void * P(table_alloc) (TAUC unsigned int size) { return xmalloc(size); }
328 static inline void P(table_free) (TAUC void *x) { xfree(x); }
331 #ifndef HASH_DEFAULT_SIZE
332 #define HASH_DEFAULT_SIZE 32
336 #define HASH_FN_BITS 32
339 #ifdef HASH_ZERO_FILL
340 static inline void * P(new_bucket)(TAUC uns size)
342 byte *buck = P(alloc)(TTC size);
347 static inline void * P(new_bucket)(TAUC uns size) { return P(alloc)(TTC size); }
350 /* Now the operations */
352 static void P(alloc_table) (TAU)
354 T.hash_size = nextprime(T.hash_size);
355 T.ht = P(table_alloc)(TTC sizeof(void *) * T.hash_size);
356 bzero(T.ht, sizeof(void *) * T.hash_size);
357 if (2*T.hash_size < T.hash_hard_max)
358 T.hash_max = 2*T.hash_size;
361 if (T.hash_size/2 > HASH_DEFAULT_SIZE)
362 T.hash_min = T.hash_size/4;
367 static void P(init) (TA)
370 T.hash_size = HASH_DEFAULT_SIZE;
371 #if HASH_FN_BITS < 28
372 T.hash_hard_max = 1 << HASH_FN_BITS;
374 T.hash_hard_max = 1 << 28;
380 #ifdef HASH_WANT_CLEANUP
381 static void P(cleanup) (TA)
383 #ifndef HASH_USE_POOL
387 for (i=0; i<T.hash_size; i++)
388 for (b=T.ht[i]; b; b=bb)
394 P(cleanup_alloc)(TT);
395 P(table_free)(TTC T.ht);
399 static inline uns P(bucket_hash) (TAUC P(bucket) *b)
401 #ifdef HASH_CONSERVE_SPACE
402 return P(hash)(TTC HASH_KEY(b->n.));
408 static void P(rehash) (TAC uns size)
411 P(bucket) **oldt = T.ht, **newt;
412 uns oldsize = T.hash_size;
415 DBG("Rehashing %d->%d at count %d", oldsize, size, T.hash_count);
419 for (i=0; i<oldsize; i++)
425 h = P(bucket_hash)(TTC b) % T.hash_size;
431 P(table_free)(TTC oldt);
434 #ifdef HASH_WANT_FIND
435 static P(node) * P(find) (TAC HASH_KEY_DECL)
437 uns h0 = P(hash) (TTC HASH_KEY( ));
438 uns h = h0 % T.hash_size;
441 for (b=T.ht[h]; b; b=b->next)
444 #ifndef HASH_CONSERVE_SPACE
447 P(eq)(TTC HASH_KEY( ), HASH_KEY(b->n.)))
454 #ifdef HASH_WANT_FIND_NEXT
455 static P(node) * P(find_next) (TAC P(node) *start)
457 #ifndef HASH_CONSERVE_SPACE
458 uns h0 = P(hash) (TTC HASH_KEY(start->));
460 P(bucket) *b = SKIP_BACK(P(bucket), n, start);
462 for (b=b->next; b; b=b->next)
465 #ifndef HASH_CONSERVE_SPACE
468 P(eq)(TTC HASH_KEY(start->), HASH_KEY(b->n.)))
476 static P(node) * P(new) (TAC HASH_KEY_DECL)
481 h0 = P(hash) (TTC HASH_KEY( ));
482 h = h0 % T.hash_size;
483 b = P(new_bucket) (TTC sizeof(struct P(bucket)) + HASH_EXTRA_SIZE(HASH_KEY( )));
486 #ifndef HASH_CONSERVE_SPACE
489 P(init_key)(TTC &b->n, HASH_KEY( ));
490 P(init_data)(TTC &b->n);
491 if (T.hash_count++ >= T.hash_max)
492 P(rehash)(TTC 2*T.hash_size);
497 #ifdef HASH_WANT_LOOKUP
498 static P(node) * P(lookup) (TAC HASH_KEY_DECL)
500 uns h0 = P(hash) (TTC HASH_KEY( ));
501 uns h = h0 % T.hash_size;
504 for (b=T.ht[h]; b; b=b->next)
507 #ifndef HASH_CONSERVE_SPACE
510 P(eq)(TTC HASH_KEY( ), HASH_KEY(b->n.)))
514 b = P(new_bucket) (TTC sizeof(struct P(bucket)) + HASH_EXTRA_SIZE(HASH_KEY( )));
517 #ifndef HASH_CONSERVE_SPACE
520 P(init_key)(TTC &b->n, HASH_KEY( ));
521 P(init_data)(TTC &b->n);
522 if (T.hash_count++ >= T.hash_max)
523 P(rehash)(TTC 2*T.hash_size);
528 #ifdef HASH_WANT_DELETE
529 static int P(delete) (TAC HASH_KEY_DECL)
531 uns h0 = P(hash) (TTC HASH_KEY( ));
532 uns h = h0 % T.hash_size;
535 for (bb=&T.ht[h]; b=*bb; bb=&b->next)
538 #ifndef HASH_CONSERVE_SPACE
541 P(eq)(TTC HASH_KEY( ), HASH_KEY(b->n.)))
545 if (--T.hash_count < T.hash_min)
546 P(rehash)(TTC T.hash_size/2);
554 #ifdef HASH_WANT_REMOVE
555 static void P(remove) (TAC P(node) *n)
557 P(bucket) *x = SKIP_BACK(struct P(bucket), n, n);
558 uns h0 = P(bucket_hash)(TTC x);
559 uns h = h0 % T.hash_size;
562 for (bb=&T.ht[h]; (b=*bb) && b != x; bb=&b->next)
567 if (--T.hash_count < T.hash_min)
568 P(rehash)(TTC T.hash_size/2);
572 /* And the iterator */
576 #define HASH_FOR_ALL_DYNAMIC(h_px, h_table, h_var) \
579 struct GLUE_(h_px,bucket) *h_buck; \
580 for (h_slot=0; h_slot < (h_table)->hash_size; h_slot++) \
581 for (h_buck = (h_table)->ht[h_slot]; h_buck; h_buck = h_buck->next) \
583 GLUE_(h_px,node) *h_var = &h_buck->n;
584 #define HASH_FOR_ALL(h_px, h_var) HASH_FOR_ALL_DYNAMIC(h_px, &GLUE_(h_px,table), h_var)
585 #define HASH_END_FOR } } while(0)
587 #define HASH_CONTINUE continue
591 /* Finally, undefine all the parameters */
602 #undef HASH_ATOMIC_TYPE
603 #undef HASH_CONSERVE_SPACE
604 #undef HASH_DEFAULT_SIZE
605 #undef HASH_EXTRA_SIZE
607 #undef HASH_GIVE_ALLOC
609 #undef HASH_GIVE_EXTRA_SIZE
610 #undef HASH_GIVE_HASHFN
611 #undef HASH_GIVE_INIT_DATA
612 #undef HASH_GIVE_INIT_KEY
614 #undef HASH_KEY_ATOMIC
615 #undef HASH_KEY_COMPLEX
617 #undef HASH_KEY_ENDSTRING
618 #undef HASH_KEY_STRING
623 #undef HASH_AUTO_POOL
624 #undef HASH_WANT_CLEANUP
625 #undef HASH_WANT_DELETE
626 #undef HASH_WANT_FIND
627 #undef HASH_WANT_FIND_NEXT
628 #undef HASH_WANT_LOOKUP
630 #undef HASH_WANT_REMOVE
631 #undef HASH_TABLE_ALLOC
632 #undef HASH_TABLE_DYNAMIC
633 #undef HASH_ZERO_FILL