]> mj.ucw.cz Git - libucw.git/blob - lib/hashtable.h
Fixed a nasty bug in hash table allocation. HASH_AUTO_POOL must use
[libucw.git] / lib / hashtable.h
1 /*
2  *      UCW Library -- Universal Hash Table
3  *
4  *      (c) 2002--2004 Martin Mares <mj@ucw.cz>
5  *      (c) 2002 Robert Spalek <robert@ucw.cz>
6  *
7  *      This software may be freely distributed and used according to the terms
8  *      of the GNU Lesser General Public License.
9  */
10
11 /*
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
15  *  given.
16  *
17  *  You need to specify:
18  *
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).
22  *
23  *  Then decide on type of keys:
24  *
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
41  *                      are mandatory.
42  *
43  *  Then specify what operations you request (all names are automatically
44  *  prefixed by calling HASH_PREFIX):
45  *
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.
60  *
61  *  You can also supply several functions:
62  *
63  *  HASH_GIVE_HASHFN    unsigned int hash(key) -- calculate hash value of key.
64  *                      We have sensible default hash functions for strings
65  *                      and integers.
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.
81  *
82  *  ... and a couple of extra parameters:
83  *
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) *.
99  *
100  *  You also get a iterator macro at no extra charge:
101  *
102  *  HASH_FOR_ALL(hash_prefix, variable)
103  *    {
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
108  *    }
109  *  HASH_END_FOR;
110  *
111  *  (For dynamic tables, use HASH_FOR_ALL_DYNAMIC(hash_prefix, hash_table, variable) instead.)
112  *
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 :) ).
115  *
116  *  After including this file, all parameter macros are automatically
117  *  undef'd.
118  */
119
120 #ifndef _UCW_HASHFUNC_H
121 #include "lib/hashfunc.h"
122 #endif
123
124 #include <string.h>
125
126 /* Initial setup of parameters */
127
128 #if !defined(HASH_NODE) || !defined(HASH_PREFIX)
129 #error Some of the mandatory configuration macros are missing.
130 #endif
131
132 #if defined(HASH_KEY_ATOMIC) && !defined(HASH_CONSERVE_SPACE)
133 #define HASH_CONSERVE_SPACE
134 #endif
135
136 #define P(x) HASH_PREFIX(x)
137
138 /* Declare buckets and the hash table */
139
140 typedef HASH_NODE P(node);
141
142 typedef struct P(bucket) {
143   struct P(bucket) *next;
144 #ifndef HASH_CONSERVE_SPACE
145   uns hash;
146 #endif
147   P(node) n;
148 } P(bucket);
149
150 struct P(table) {
151   uns hash_size;
152   uns hash_count, hash_max, hash_min, hash_hard_max;
153   P(bucket) **ht;
154 #ifdef HASH_AUTO_POOL
155   struct mempool *pool;
156 #endif
157 };
158
159 #ifdef HASH_TABLE_DYNAMIC
160 #define T (*table)
161 #define TA struct P(table) *table
162 #define TAC TA,
163 #define TAU TA UNUSED
164 #define TAUC TA UNUSED,
165 #define TT table
166 #define TTC table,
167 #else
168 struct P(table) P(table);
169 #define T P(table)
170 #define TA void
171 #define TAC
172 #define TAU void
173 #define TAUC
174 #define TT
175 #define TTC
176 #endif
177
178 /* Preset parameters */
179
180 #if defined(HASH_KEY_ATOMIC)
181
182 #define HASH_KEY(x) x HASH_KEY_ATOMIC
183
184 #ifndef HASH_ATOMIC_TYPE
185 #  define HASH_ATOMIC_TYPE int
186 #endif
187 #define HASH_KEY_DECL HASH_ATOMIC_TYPE HASH_KEY( )
188
189 #ifndef HASH_GIVE_HASHFN
190 #  define HASH_GIVE_HASHFN
191    static inline int P(hash) (TAUC HASH_ATOMIC_TYPE x)
192    { return ((sizeof(x) <= 4) ? hash_u32(x) : hash_u64(x)); }
193 #endif
194
195 #ifndef HASH_GIVE_EQ
196 #  define HASH_GIVE_EQ
197    static inline int P(eq) (TAUC HASH_ATOMIC_TYPE x, HASH_ATOMIC_TYPE y)
198    { return x == y; }
199 #endif
200
201 #ifndef HASH_GIVE_INIT_KEY
202 #  define HASH_GIVE_INIT_KEY
203    static inline void P(init_key) (TAUC P(node) *n, HASH_ATOMIC_TYPE k)
204    { HASH_KEY(n->) = k; }
205 #endif
206
207 #elif defined(HASH_KEY_STRING) || defined(HASH_KEY_ENDSTRING)
208
209 #ifdef HASH_KEY_STRING
210 #  define HASH_KEY(x) x HASH_KEY_STRING
211 #  ifndef HASH_GIVE_INIT_KEY
212 #    define HASH_GIVE_INIT_KEY
213      static inline void P(init_key) (TAUC P(node) *n, char *k)
214      { HASH_KEY(n->) = k; }
215 #  endif
216 #else
217 #  define HASH_KEY(x) x HASH_KEY_ENDSTRING
218 #  define HASH_GIVE_EXTRA_SIZE
219    static inline int P(extra_size) (TAUC char *k)
220    { return strlen(k); }
221 #  ifndef HASH_GIVE_INIT_KEY
222 #    define HASH_GIVE_INIT_KEY
223      static inline void P(init_key) (TAUC P(node) *n, char *k)
224      { strcpy(HASH_KEY(n->), k); }
225 #  endif
226 #endif
227 #define HASH_KEY_DECL char *HASH_KEY( )
228
229 #ifndef HASH_GIVE_HASHFN
230 #define HASH_GIVE_HASHFN
231   static inline uns P(hash) (TAUC char *k)
232    {
233 #    ifdef HASH_NOCASE
234        return hash_string_nocase(k);
235 #    else
236        return hash_string(k);
237 #    endif
238    }
239 #endif
240
241 #ifndef HASH_GIVE_EQ
242 #  define HASH_GIVE_EQ
243    static inline int P(eq) (TAUC char *x, char *y)
244    {
245 #    ifdef HASH_NOCASE
246        return !strcasecmp(x,y);
247 #    else
248        return !strcmp(x,y);
249 #    endif
250    }
251 #endif
252
253 #elif defined(HASH_KEY_COMPLEX)
254
255 #define HASH_KEY(x) HASH_KEY_COMPLEX(x)
256
257 #else
258 #error You forgot to set the hash key type.
259 #endif
260
261 /* Defaults for missing parameters */
262
263 #ifndef HASH_GIVE_HASHFN
264 #error Unable to determine which hash function to use.
265 #endif
266
267 #ifndef HASH_GIVE_EQ
268 #error Unable to determine how to compare two keys.
269 #endif
270
271 #ifdef HASH_GIVE_EXTRA_SIZE
272 /* This trickery is needed to avoid `unused parameter' warnings */
273 #define HASH_EXTRA_SIZE(x) P(extra_size)(TTC x)
274 #else
275 /*
276  *  Beware, C macros are expanded iteratively, not recursively,
277  *  hence we get only a _single_ argument, although the expansion
278  *  of HASH_KEY contains commas.
279  */
280 #define HASH_EXTRA_SIZE(x) 0
281 #endif
282
283 #ifndef HASH_GIVE_INIT_KEY
284 #error Unable to determine how to initialize keys.
285 #endif
286
287 #ifndef HASH_GIVE_INIT_DATA
288 static inline void P(init_data) (TAUC P(node) *n UNUSED)
289 {
290 }
291 #endif
292
293 #include <stdlib.h>
294
295 #ifdef HASH_GIVE_ALLOC
296 /* If the caller has requested to use his own allocation functions, do so */
297 static inline void P(init_alloc) (TAU) { }
298 static inline void P(cleanup_alloc) (TAU) { }
299
300 #elif defined(HASH_USE_POOL)
301 /* If the caller has requested to use his mempool, do so */
302 #include "lib/mempool.h"
303 static inline void * P(alloc) (TAUC unsigned int size) { return mp_alloc_fast(HASH_USE_POOL, size); }
304 static inline void P(free) (TAUC void *x UNUSED) { }
305 static inline void P(init_alloc) (TAU) { }
306 static inline void P(cleanup_alloc) (TAU) { }
307
308 #elif defined(HASH_AUTO_POOL)
309 /* Use our own pools */
310 #include "lib/mempool.h"
311 static inline void * P(alloc) (TAUC unsigned int size) { return mp_alloc_fast(T.pool, size); }
312 static inline void P(free) (TAUC void *x UNUSED) { }
313 static inline void P(init_alloc) (TAU) { T.pool = mp_new(HASH_AUTO_POOL); }
314 static inline void P(cleanup_alloc) (TAU) { mp_delete(T.pool); }
315 #define HASH_USE_POOL
316
317 #else
318 /* The default allocation method */
319 static inline void * P(alloc) (TAUC unsigned int size) { return xmalloc(size); }
320 static inline void P(free) (TAUC void *x) { xfree(x); }
321 static inline void P(init_alloc) (TAU) { }
322 static inline void P(cleanup_alloc) (TAU) { }
323
324 #endif
325
326 #ifdef HASH_TABLE_ALLOC
327 static inline void * P(table_alloc) (TAUC unsigned int size) { return P(alloc)(size); }
328 static inline void P(table_free) (TAUC void *x) { P(free)(x); }
329 #else
330 static inline void * P(table_alloc) (TAUC unsigned int size) { return xmalloc(size); }
331 static inline void P(table_free) (TAUC void *x) { xfree(x); }
332 #endif
333
334 #ifndef HASH_DEFAULT_SIZE
335 #define HASH_DEFAULT_SIZE 32
336 #endif
337
338 #ifndef HASH_FN_BITS
339 #define HASH_FN_BITS 32
340 #endif
341
342 #ifdef HASH_ZERO_FILL
343 static inline void * P(new_bucket)(TAUC uns size)
344 {
345   byte *buck = P(alloc)(TTC size);
346   bzero(buck, size);
347   return buck;
348 }
349 #else
350 static inline void * P(new_bucket)(TAUC uns size) { return P(alloc)(TTC size); }
351 #endif
352
353 /* Now the operations */
354
355 static void P(alloc_table) (TAU)
356 {
357   T.hash_size = nextprime(T.hash_size);
358   T.ht = P(table_alloc)(TTC sizeof(void *) * T.hash_size);
359   bzero(T.ht, sizeof(void *) * T.hash_size);
360   if (2*T.hash_size < T.hash_hard_max)
361     T.hash_max = 2*T.hash_size;
362   else
363     T.hash_max = ~0U;
364   if (T.hash_size/2 > HASH_DEFAULT_SIZE)
365     T.hash_min = T.hash_size/4;
366   else
367     T.hash_min = 0;
368 }
369
370 static void P(init) (TA)
371 {
372   T.hash_count = 0;
373   T.hash_size = HASH_DEFAULT_SIZE;
374 #if HASH_FN_BITS < 28
375   T.hash_hard_max = 1 << HASH_FN_BITS;
376 #else
377   T.hash_hard_max = 1 << 28;
378 #endif
379   P(alloc_table)(TT);
380   P(init_alloc)(TT);
381 }
382
383 #ifdef HASH_WANT_CLEANUP
384 static void P(cleanup) (TA)
385 {
386 #ifndef HASH_USE_POOL
387   uns i;
388   P(bucket) *b, *bb;
389
390   for (i=0; i<T.hash_size; i++)
391     for (b=T.ht[i]; b; b=bb)
392       {
393         bb = b->next;
394         P(free)(TTC b);
395       }
396 #endif
397   P(cleanup_alloc)(TT);
398   P(table_free)(TTC T.ht);
399 }
400 #endif
401
402 static inline uns P(bucket_hash) (TAUC P(bucket) *b)
403 {
404 #ifdef HASH_CONSERVE_SPACE
405   return P(hash)(TTC HASH_KEY(b->n.));
406 #else
407   return b->hash;
408 #endif
409 }
410
411 static void P(rehash) (TAC uns size)
412 {
413   P(bucket) *b, *nb;
414   P(bucket) **oldt = T.ht, **newt;
415   uns oldsize = T.hash_size;
416   uns i, h;
417
418   DBG("Rehashing %d->%d at count %d", oldsize, size, T.hash_count);
419   T.hash_size = size;
420   P(alloc_table)(TT);
421   newt = T.ht;
422   for (i=0; i<oldsize; i++)
423     {
424       b = oldt[i];
425       while (b)
426         {
427           nb = b->next;
428           h = P(bucket_hash)(TTC b) % T.hash_size;
429           b->next = newt[h];
430           newt[h] = b;
431           b = nb;
432         }
433     }
434   P(table_free)(TTC oldt);
435 }
436
437 #ifdef HASH_WANT_FIND
438 static P(node) * P(find) (TAC HASH_KEY_DECL)
439 {
440   uns h0 = P(hash) (TTC HASH_KEY( ));
441   uns h = h0 % T.hash_size;
442   P(bucket) *b;
443
444   for (b=T.ht[h]; b; b=b->next)
445     {
446       if (
447 #ifndef HASH_CONSERVE_SPACE
448           b->hash == h0 &&
449 #endif
450           P(eq)(TTC HASH_KEY( ), HASH_KEY(b->n.)))
451         return &b->n;
452     }
453   return NULL;
454 }
455 #endif
456
457 #ifdef HASH_WANT_FIND_NEXT
458 static P(node) * P(find_next) (TAC P(node) *start)
459 {
460 #ifndef HASH_CONSERVE_SPACE
461   uns h0 = P(hash) (TTC HASH_KEY(start->));
462 #endif
463   P(bucket) *b = SKIP_BACK(P(bucket), n, start);
464
465   for (b=b->next; b; b=b->next)
466     {
467       if (
468 #ifndef HASH_CONSERVE_SPACE
469           b->hash == h0 &&
470 #endif
471           P(eq)(TTC HASH_KEY(start->), HASH_KEY(b->n.)))
472         return &b->n;
473     }
474   return NULL;
475 }
476 #endif
477
478 #ifdef HASH_WANT_NEW
479 static P(node) * P(new) (TAC HASH_KEY_DECL)
480 {
481   uns h0, h;
482   P(bucket) *b;
483
484   h0 = P(hash) (TTC HASH_KEY( ));
485   h = h0 % T.hash_size;
486   b = P(new_bucket) (TTC sizeof(struct P(bucket)) + HASH_EXTRA_SIZE(HASH_KEY( )));
487   b->next = T.ht[h];
488   T.ht[h] = b;
489 #ifndef HASH_CONSERVE_SPACE
490   b->hash = h0;
491 #endif
492   P(init_key)(TTC &b->n, HASH_KEY( ));
493   P(init_data)(TTC &b->n);
494   if (T.hash_count++ >= T.hash_max)
495     P(rehash)(TTC 2*T.hash_size);
496   return &b->n;
497 }
498 #endif
499
500 #ifdef HASH_WANT_LOOKUP
501 static P(node) * P(lookup) (TAC HASH_KEY_DECL)
502 {
503   uns h0 = P(hash) (TTC HASH_KEY( ));
504   uns h = h0 % T.hash_size;
505   P(bucket) *b;
506
507   for (b=T.ht[h]; b; b=b->next)
508     {
509       if (
510 #ifndef HASH_CONSERVE_SPACE
511           b->hash == h0 &&
512 #endif
513           P(eq)(TTC HASH_KEY( ), HASH_KEY(b->n.)))
514         return &b->n;
515     }
516
517   b = P(new_bucket) (TTC sizeof(struct P(bucket)) + HASH_EXTRA_SIZE(HASH_KEY( )));
518   b->next = T.ht[h];
519   T.ht[h] = b;
520 #ifndef HASH_CONSERVE_SPACE
521   b->hash = h0;
522 #endif
523   P(init_key)(TTC &b->n, HASH_KEY( ));
524   P(init_data)(TTC &b->n);
525   if (T.hash_count++ >= T.hash_max)
526     P(rehash)(TTC 2*T.hash_size);
527   return &b->n;
528 }
529 #endif
530
531 #ifdef HASH_WANT_DELETE
532 static int P(delete) (TAC HASH_KEY_DECL)
533 {
534   uns h0 = P(hash) (TTC HASH_KEY( ));
535   uns h = h0 % T.hash_size;
536   P(bucket) *b, **bb;
537
538   for (bb=&T.ht[h]; b=*bb; bb=&b->next)
539     {
540       if (
541 #ifndef HASH_CONSERVE_SPACE
542           b->hash == h0 &&
543 #endif
544           P(eq)(TTC HASH_KEY( ), HASH_KEY(b->n.)))
545         {
546           *bb = b->next;
547           P(free)(TTC b);
548           if (--T.hash_count < T.hash_min)
549             P(rehash)(TTC T.hash_size/2);
550           return 1;
551         }
552     }
553   return 0;
554 }
555 #endif
556
557 #ifdef HASH_WANT_REMOVE
558 static void P(remove) (TAC P(node) *n)
559 {
560   P(bucket) *x = SKIP_BACK(struct P(bucket), n, n);
561   uns h0 = P(bucket_hash)(TTC x);
562   uns h = h0 % T.hash_size;
563   P(bucket) *b, **bb;
564
565   for (bb=&T.ht[h]; (b=*bb) && b != x; bb=&b->next)
566     ;
567   ASSERT(b);
568   *bb = b->next;
569   P(free)(TTC b);
570   if (--T.hash_count < T.hash_min)
571     P(rehash)(TTC T.hash_size/2);
572 }
573 #endif
574
575 /* And the iterator */
576
577 #ifndef HASH_FOR_ALL
578
579 #define HASH_FOR_ALL_DYNAMIC(h_px, h_table, h_var)                                      \
580 do {                                                                                    \
581   uns h_slot;                                                                           \
582   struct GLUE_(h_px,bucket) *h_buck;                                                    \
583   for (h_slot=0; h_slot < (h_table)->hash_size; h_slot++)                               \
584     for (h_buck = (h_table)->ht[h_slot]; h_buck; h_buck = h_buck->next)                 \
585       {                                                                                 \
586         GLUE_(h_px,node) *h_var = &h_buck->n;
587 #define HASH_FOR_ALL(h_px, h_var) HASH_FOR_ALL_DYNAMIC(h_px, &GLUE_(h_px,table), h_var)
588 #define HASH_END_FOR } } while(0)
589 #define HASH_BREAK 
590 #define HASH_CONTINUE continue
591
592 #endif
593
594 /* Finally, undefine all the parameters */
595
596 #undef P
597 #undef T
598 #undef TA
599 #undef TAC
600 #undef TAU
601 #undef TAUC
602 #undef TT
603 #undef TTC
604
605 #undef HASH_ATOMIC_TYPE
606 #undef HASH_CONSERVE_SPACE
607 #undef HASH_DEFAULT_SIZE
608 #undef HASH_EXTRA_SIZE
609 #undef HASH_FN_BITS
610 #undef HASH_GIVE_ALLOC
611 #undef HASH_GIVE_EQ
612 #undef HASH_GIVE_EXTRA_SIZE
613 #undef HASH_GIVE_HASHFN
614 #undef HASH_GIVE_INIT_DATA
615 #undef HASH_GIVE_INIT_KEY
616 #undef HASH_KEY
617 #undef HASH_KEY_ATOMIC
618 #undef HASH_KEY_COMPLEX
619 #undef HASH_KEY_DECL
620 #undef HASH_KEY_ENDSTRING
621 #undef HASH_KEY_STRING
622 #undef HASH_NOCASE
623 #undef HASH_NODE
624 #undef HASH_PREFIX
625 #undef HASH_USE_POOL
626 #undef HASH_AUTO_POOL
627 #undef HASH_WANT_CLEANUP
628 #undef HASH_WANT_DELETE
629 #undef HASH_WANT_FIND
630 #undef HASH_WANT_FIND_NEXT
631 #undef HASH_WANT_LOOKUP
632 #undef HASH_WANT_NEW
633 #undef HASH_WANT_REMOVE
634 #undef HASH_TABLE_ALLOC
635 #undef HASH_TABLE_DYNAMIC
636 #undef HASH_ZERO_FILL