2 * Sherlock Library -- Universal Hash Table
4 * (c) 2002 Martin Mares <mj@ucw.cz>
8 * This is not a normal header file, it's a generator of hash tables.
9 * Each time you include it with parameters set in the corresponding
10 * preprocessor macros, it generates a hash table with the parameters
13 * You need to specify:
15 * HASH_NODE data type where a node dwells (usually a struct).
16 * HASH_PREFIX(x) macro to add a name prefix (used on all global names
17 * defined by the hash table generator).
19 * Then decide on type of keys:
21 * HASH_KEY_ATOMIC=f use node->f as a key of an atomic type (i.e.,
22 * a type which can be compared using `==')
23 * HASH_ATOMIC_TYPE (defaults to int).
24 * | HASH_KEY_STRING=f use node->f as a string key, allocated
25 * separately from the rest of the node.
26 * | HASH_KEY_ENDSTRING=f use node->f as a string key, allocated
27 * automatically at the end of the node struct
28 * (to be declared as "char f[1]" at the end).
29 * | HASH_KEY_COMPLEX use a multi-component key; as the name suggests,
30 * the passing of parameters is a bit complex then.
31 * The HASH_KEY_COMPLEX(x) macro should expand to
32 * `x k1, x k2, ... x kn' and you should also define:
33 * HASH_KEY_DECL declaration of function parameters in which key
34 * should be passed to all hash table operations.
35 * That is, `type1 k1, type2 k2, ... typen kn'.
36 * With complex keys, HASH_GIVE_HASHFN and HASH_GIVE_EQ
39 * Then specify what operations you request (all names are automatically
40 * prefixed by calling HASH_PREFIX):
42 * <always defined> init() -- initialize the hash table.
43 * HASH_WANT_CLEANUP cleanup() -- deallocate the hash table.
44 * HASH_WANT_FIND node *find(key) -- find node with the specified
45 * key, return NULL if no such node exists.
46 * HASH_WANT_NEW node *new(key) -- create new node with given key.
47 * Doesn't check whether it already exists.
48 * HASH_WANT_LOOKUP node *lookup(key) -- find node with given key,
49 * if it doesn't exist, create it. Defining
50 * HASH_GIVE_INIT_DATA is strongly recommended.
51 * HASH_WANT_DELETE int delete(key) -- delete and deallocate node
52 * with given key. Returns success.
53 * HASH_WANT_REMOVE remove(node *) -- delete and deallocate given node.
55 * You can also supply several functions:
57 * HASH_GIVE_HASHFN unsigned int hash(key) -- calculate hash value of key.
58 * We have sensible default hash functions for strings
60 * HASH_GIVE_EQ int eq(key1, key2) -- return whether keys are equal.
61 * By default, we use == for atomic types and either
62 * strcmp or strcasecmp for strings.
63 * HASH_GIVE_EXTRA_SIZE int extra_size(key) -- returns how many bytes after the
64 * node should be allocated for dynamic data. Default=0
65 * or length of the string with HASH_KEY_ENDSTRING.
66 * HASH_GIVE_INIT_KEY void init_key(node *,key) -- initialize key in a newly
67 * created node. Defaults: assignment for atomic keys
68 * and static strings, strcpy for end-allocated strings.
69 * HASH_GIVE_INIT_DATA void init_data(node *) -- initialize data fields in a
70 * newly created node. Very useful for lookup operations.
71 * HASH_GIVE_ALLOC void *alloc(unsigned int size) -- allocate space for
72 * a node. Default is either normal or pooled allocation
73 * depending on whether we want deletions.
74 * void free(void *) -- the converse.
76 * ... and a couple of extra parameters:
78 * HASH_NOCASE string comparisons should be case-insensitive.
79 * HASH_DEFAULT_SIZE=n initially, use hash table of `n' entries.
80 * The `n' has to be a power of two.
81 * HASH_CONSERVE_SPACE use as little space as possible.
82 * HASH_FN_BITS=n The hash function gives only `n' significant bits.
83 * HASH_ATOMIC_TYPE=t Atomic values are of type `t' instead of int.
84 * HASH_USE_POOL=pool Allocate all nodes from given mempool.
85 * Collides with delete/remove functions.
87 * You also get a iterator macro at no extra charge:
89 * HASH_FOR_ALL(hash_prefix, variable)
91 * // node *variable gets declared automatically
92 * do_something_with_node(variable);
93 * // use HASH_BREAK and HASH_CONTINUE instead of break and continue
94 * // you must not alter contents of the hash table here
98 * Then include <lib/hashtable.h> and voila, you have a hash table
99 * suiting all your needs (at least those which you've revealed :) ).
101 * After including this file, all parameter macros are automatically
105 #ifndef _SHERLOCK_HASHFUNC_H
106 #include "lib/hashfunc.h"
111 #if !defined(HASH_NODE) || !defined(HASH_PREFIX)
112 #error Some of the mandatory configuration macros are missing.
115 #define P(x) HASH_PREFIX(x)
117 /* Declare buckets and the hash table */
119 typedef HASH_NODE P(node);
121 typedef struct P(bucket) {
122 struct P(bucket) *next;
123 #ifndef HASH_CONSERVE_SPACE
131 uns hash_count, hash_max, hash_min, hash_hard_max, hash_mask;
137 /* Preset parameters */
139 #if defined(HASH_KEY_ATOMIC)
141 #define HASH_KEY(x) x HASH_KEY_ATOMIC
143 #ifndef HASH_ATOMIC_TYPE
144 # define HASH_ATOMIC_TYPE int
146 #define HASH_KEY_DECL HASH_ATOMIC_TYPE HASH_KEY( )
148 #ifndef HASH_GIVE_HASHFN
149 # define HASH_GIVE_HASHFN
150 static inline int P(hash) (HASH_ATOMIC_TYPE x)
151 { return hash_int(x); }
155 # define HASH_GIVE_EQ
156 static inline int P(eq) (HASH_ATOMIC_TYPE x, HASH_ATOMIC_TYPE y)
160 #ifndef HASH_GIVE_INIT_KEY
161 # define HASH_GIVE_INIT_KEY
162 static inline void P(init_key) (P(node) *n, HASH_ATOMIC_TYPE k)
163 { HASH_KEY(n->) = k; }
166 #ifndef HASH_CONSERVE_SPACE
167 #define HASH_CONSERVE_SPACE
170 #elif defined(HASH_KEY_STRING) || defined(HASH_KEY_ENDSTRING)
172 #ifdef HASH_KEY_STRING
173 # define HASH_KEY(x) x HASH_KEY_STRING
174 # ifndef HASH_GIVE_INIT_KEY
175 # define HASH_GIVE_INIT_KEY
176 static inline void P(init_key) (P(node) *n, char *k)
177 { HASH_KEY(n->) = k; }
180 # define HASH_KEY(x) x HASH_KEY_ENDSTRING
181 # define HASH_GIVE_EXTRA_SIZE
182 static inline int P(extra_size) (char *k)
183 { return strlen(k); }
184 # ifndef HASH_GIVE_INIT_KEY
185 # define HASH_GIVE_INIT_KEY
186 static inline void P(init_key) (P(node) *n, char *k)
187 { strcpy(HASH_KEY(n->), k); }
190 #define HASH_KEY_DECL char *HASH_KEY( )
192 #ifndef HASH_GIVE_HASHFN
193 #define HASH_GIVE_HASHFN
194 static inline uns P(hash) (char *k)
197 return hash_string_nocase(k);
199 return hash_string(k);
205 # define HASH_GIVE_EQ
206 static inline int P(eq) (char *x, char *y)
209 return !strcasecmp(x,y);
216 #elif defined(HASH_KEY_COMPLEX)
218 #define HASH_KEY(x) HASH_KEY_COMPLEX(x)
221 #error You forgot to set the hash key type.
224 /* Defaults for missing parameters */
226 #ifndef HASH_GIVE_HASHFN
227 #error Unable to determine which hash function to use.
231 #error Unable to determine how to compare two keys.
234 #ifdef HASH_GIVE_EXTRA_SIZE
235 /* This trickery is needed to avoid `unused parameter' warnings */
236 #define HASH_EXTRA_SIZE P(extra_size)
239 * Beware, C macros are expanded iteratively, not recursively,
240 * hence we get only a _single_ argument, although the expansion
241 * of HASH_KEY contains commas.
243 #define HASH_EXTRA_SIZE(x) 0
246 #ifndef HASH_GIVE_INIT_KEY
247 #error Unable to determine how to initialize keys.
250 #ifndef HASH_GIVE_INIT_DATA
251 static inline void P(init_data) (P(node) *n UNUSED)
258 #ifndef HASH_GIVE_ALLOC
261 static inline void * P(alloc) (unsigned int size)
262 { return mp_alloc_fast(HASH_USE_POOL, size); }
266 static inline void * P(alloc) (unsigned int size)
267 { return xmalloc(size); }
269 static inline void P(free) (void *x)
275 #ifndef HASH_DEFAULT_SIZE
276 #define HASH_DEFAULT_SIZE 32
280 #define HASH_FN_BITS 32
283 /* Now the operations */
285 static void P(alloc_table) (void)
287 T.ht = xmalloc(sizeof(void *) * T.hash_size);
288 bzero(T.ht, sizeof(void *) * T.hash_size);
289 T.hash_max = T.hash_size * 2;
290 if (T.hash_max > T.hash_hard_max)
291 T.hash_max = T.hash_hard_max;
292 T.hash_min = T.hash_size / 4;
293 T.hash_mask = T.hash_size - 1;
296 static void P(init) (void)
299 T.hash_size = HASH_DEFAULT_SIZE;
300 #if HASH_FN_BITS < 28
301 T.hash_hard_max = 1 << HASH_FN_BITS;
303 T.hash_hard_max = 1 << 28;
308 #ifdef HASH_WANT_CLEANUP
309 static void P(cleanup) (void)
311 #ifndef HASH_USE_POOL
315 for (i=0; i<T.hash_size; i++)
316 for (b=T.ht[i]; b; b=bb)
326 static inline uns P(bucket_hash) (P(bucket) *b)
328 #ifdef HASH_CONSERVE_SPACE
329 return P(hash)(HASH_KEY(b->n.));
335 static void P(rehash) (uns size)
338 P(bucket) **oldt = T.ht, **newt;
339 uns oldsize = T.hash_size;
342 // log(L_DEBUG, "Rehashing %d->%d at count %d", oldsize, size, T.hash_count);
346 for (i=0; i<oldsize; i++)
352 h = P(bucket_hash)(b) & T.hash_mask;
361 #ifdef HASH_WANT_FIND
362 static P(node) * P(find) (HASH_KEY_DECL)
364 uns h0 = P(hash) (HASH_KEY( ));
365 uns h = h0 & T.hash_mask;
368 for (b=T.ht[h]; b; b=b->next)
371 #ifndef HASH_CONSERVE_SPACE
374 P(eq)(HASH_KEY( ), HASH_KEY(b->n.)))
382 static P(node) * P(new) (HASH_KEY_DECL)
387 h0 = P(hash) (HASH_KEY( ));
388 h = h0 & T.hash_mask;
389 b = P(alloc) (sizeof(struct P(bucket)) + HASH_EXTRA_SIZE(HASH_KEY( )));
392 #ifndef HASH_CONSERVE_SPACE
395 P(init_key)(&b->n, HASH_KEY( ));
397 if (T.hash_count++ >= T.hash_max)
398 P(rehash)(2*T.hash_size);
403 #ifdef HASH_WANT_LOOKUP
404 static P(node) * P(lookup) (HASH_KEY_DECL)
406 uns h0 = P(hash) (HASH_KEY( ));
407 uns h = h0 & T.hash_mask;
410 for (b=T.ht[h]; b; b=b->next)
413 #ifndef HASH_CONSERVE_SPACE
416 P(eq)(HASH_KEY( ), HASH_KEY(b->n.)))
420 b = P(alloc) (sizeof(struct P(bucket)) + HASH_EXTRA_SIZE(HASH_KEY( )));
423 #ifndef HASH_CONSERVE_SPACE
426 P(init_key)(&b->n, HASH_KEY( ));
428 if (T.hash_count++ >= T.hash_max)
429 P(rehash)(2*T.hash_size);
434 #ifdef HASH_WANT_DELETE
435 static int P(delete) (HASH_KEY_DECL)
437 uns h0 = P(hash) (HASH_KEY( ));
438 uns h = h0 & T.hash_mask;
441 for (bb=&T.ht[h]; b=*bb; bb=&b->next)
444 #ifndef HASH_CONSERVE_SPACE
447 P(eq)(HASH_KEY( ), HASH_KEY(b->n.)))
451 if (--T.hash_count < T.hash_min)
452 P(rehash)(T.hash_size/2);
460 #ifdef HASH_WANT_REMOVE
461 static void P(remove) (P(node) *n)
463 P(bucket) *x = SKIP_BACK(struct P(bucket), n, n);
464 uns h0 = P(bucket_hash)(x);
465 uns h = h0 & T.hash_mask;
468 for (bb=&T.ht[h]; (b=*bb) && b != x; bb=&b->next)
473 if (--T.hash_count < T.hash_min)
474 P(rehash)(T.hash_size/2);
478 /* And the iterator */
482 #define HASH_FOR_ALL(h_px, h_var) \
485 struct HASH_GLUE(h_px,bucket) *h_buck; \
486 for (h_slot=0; h_slot < HASH_GLUE(h_px,table).hash_size; h_slot++) \
487 for (h_buck = HASH_GLUE(h_px,table).ht[h_slot]; h_buck; h_buck = h_buck->next) \
489 HASH_GLUE(h_px,node) *h_var = &h_buck->n;
490 #define HASH_END_FOR } } while(0)
492 #define HASH_CONTINUE continue
493 #define HASH_GLUE(x,y) x##_##y
497 /* Finally, undefine all the parameters */
502 #undef HASH_ATOMIC_TYPE
503 #undef HASH_CONSERVE_SPACE
504 #undef HASH_DEFAULT_SIZE
505 #undef HASH_EXTRA_SIZE
507 #undef HASH_GIVE_ALLOC
509 #undef HASH_GIVE_EXTRA_SIZE
510 #undef HASH_GIVE_HASHFN
511 #undef HASH_GIVE_INIT_DATA
512 #undef HASH_GIVE_INIT_KEY
514 #undef HASH_KEY_ATOMIC
515 #undef HASH_KEY_COMPLEX
517 #undef HASH_KEY_ENDSTRING
518 #undef HASH_KEY_STRING
523 #undef HASH_WANT_CLEANUP
524 #undef HASH_WANT_DELETE
525 #undef HASH_WANT_FIND
526 #undef HASH_WANT_LOOKUP
528 #undef HASH_WANT_REMOVE