lib/hashtable.h

   1 /*
   2  *      Sherlock 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 either normal or pooled allocation
  79  *                      depending on whether we want deletions.
  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.
  90  *                      Collides with delete/remove functions.
  91  *  HASH_AUTO_POOL=size Create a pool of the given block size automatically.
  92  *
  93  *  You also get a iterator macro at no extra charge:
  94  *
  95  *  HASH_FOR_ALL(hash_prefix, variable)
  96  *    {
  97  *      // node *variable gets declared automatically
  98  *      do_something_with_node(variable);
  99  *      // use HASH_BREAK and HASH_CONTINUE instead of break and continue
 100  *      // you must not alter contents of the hash table here
 101  *    }
 102  *  HASH_END_FOR;
 103  *
 104  *  Then include "lib/hashtable.h" and voila, you have a hash table
 105  *  suiting all your needs (at least those which you've revealed :) ).
 106  *
 107  *  After including this file, all parameter macros are automatically
 108  *  undef'd.
 109  */
 110
 111 #ifndef _SHERLOCK_HASHFUNC_H
 112 #include "lib/hashfunc.h"
 113 #endif
 114
 115 #include <string.h>
 116
 117 #if !defined(HASH_NODE) || !defined(HASH_PREFIX)
 118 #error Some of the mandatory configuration macros are missing.
 119 #endif
 120
 121 #define P(x) HASH_PREFIX(x)
 122
 123 /* Declare buckets and the hash table */
 124
 125 typedef HASH_NODE P(node);
 126
 127 typedef struct P(bucket) {
 128   struct P(bucket) *next;
 129 #ifndef HASH_CONSERVE_SPACE
 130   uns hash;
 131 #endif
 132   P(node) n;
 133 } P(bucket);
 134
 135 struct P(table) {
 136   uns hash_size;
 137   uns hash_count, hash_max, hash_min, hash_hard_max;
 138   P(bucket) **ht;
 139 } P(table);
 140
 141 #define T P(table)
 142
 143 /* Preset parameters */
 144
 145 #if defined(HASH_KEY_ATOMIC)
 146
 147 #define HASH_KEY(x) x HASH_KEY_ATOMIC
 148
 149 #ifndef HASH_ATOMIC_TYPE
 150 #  define HASH_ATOMIC_TYPE int
 151 #endif
 152 #define HASH_KEY_DECL HASH_ATOMIC_TYPE HASH_KEY( )
 153
 154 #ifndef HASH_GIVE_HASHFN
 155 #  define HASH_GIVE_HASHFN
 156    static inline int P(hash) (HASH_ATOMIC_TYPE x)
 157    { return hash_int(x); }
 158 #endif
 159
 160 #ifndef HASH_GIVE_EQ
 161 #  define HASH_GIVE_EQ
 162    static inline int P(eq) (HASH_ATOMIC_TYPE x, HASH_ATOMIC_TYPE y)
 163    { return x == y; }
 164 #endif
 165
 166 #ifndef HASH_GIVE_INIT_KEY
 167 #  define HASH_GIVE_INIT_KEY
 168    static inline void P(init_key) (P(node) *n, HASH_ATOMIC_TYPE k)
 169    { HASH_KEY(n->) = k; }
 170 #endif
 171
 172 #ifndef HASH_CONSERVE_SPACE
 173 #define HASH_CONSERVE_SPACE
 174 #endif
 175
 176 #elif defined(HASH_KEY_STRING) || defined(HASH_KEY_ENDSTRING)
 177
 178 #ifdef HASH_KEY_STRING
 179 #  define HASH_KEY(x) x HASH_KEY_STRING
 180 #  ifndef HASH_GIVE_INIT_KEY
 181 #    define HASH_GIVE_INIT_KEY
 182      static inline void P(init_key) (P(node) *n, char *k)
 183      { HASH_KEY(n->) = k; }
 184 #  endif
 185 #else
 186 #  define HASH_KEY(x) x HASH_KEY_ENDSTRING
 187 #  define HASH_GIVE_EXTRA_SIZE
 188    static inline int P(extra_size) (char *k)
 189    { return strlen(k); }
 190 #  ifndef HASH_GIVE_INIT_KEY
 191 #    define HASH_GIVE_INIT_KEY
 192      static inline void P(init_key) (P(node) *n, char *k)
 193      { strcpy(HASH_KEY(n->), k); }
 194 #  endif
 195 #endif
 196 #define HASH_KEY_DECL char *HASH_KEY( )
 197
 198 #ifndef HASH_GIVE_HASHFN
 199 #define HASH_GIVE_HASHFN
 200   static inline uns P(hash) (char *k)
 201    {
 202 #    ifdef HASH_NOCASE
 203        return hash_string_nocase(k);
 204 #    else
 205        return hash_string(k);
 206 #    endif
 207    }
 208 #endif
 209
 210 #ifndef HASH_GIVE_EQ
 211 #  define HASH_GIVE_EQ
 212    static inline int P(eq) (char *x, char *y)
 213    {
 214 #    ifdef HASH_NOCASE
 215        return !strcasecmp(x,y);
 216 #    else
 217        return !strcmp(x,y);
 218 #    endif
 219    }
 220 #endif
 221
 222 #elif defined(HASH_KEY_COMPLEX)
 223
 224 #define HASH_KEY(x) HASH_KEY_COMPLEX(x)
 225
 226 #else
 227 #error You forgot to set the hash key type.
 228 #endif
 229
 230 /* Defaults for missing parameters */
 231
 232 #ifndef HASH_GIVE_HASHFN
 233 #error Unable to determine which hash function to use.
 234 #endif
 235
 236 #ifndef HASH_GIVE_EQ
 237 #error Unable to determine how to compare two keys.
 238 #endif
 239
 240 #ifdef HASH_GIVE_EXTRA_SIZE
 241 /* This trickery is needed to avoid `unused parameter' warnings */
 242 #define HASH_EXTRA_SIZE P(extra_size)
 243 #else
 244 /*
 245  *  Beware, C macros are expanded iteratively, not recursively,
 246  *  hence we get only a _single_ argument, although the expansion
 247  *  of HASH_KEY contains commas.
 248  */
 249 #define HASH_EXTRA_SIZE(x) 0
 250 #endif
 251
 252 #ifndef HASH_GIVE_INIT_KEY
 253 #error Unable to determine how to initialize keys.
 254 #endif
 255
 256 #ifndef HASH_GIVE_INIT_DATA
 257 static inline void P(init_data) (P(node) *n UNUSED)
 258 {
 259 }
 260 #endif
 261
 262 #include <stdlib.h>
 263
 264 #ifdef HASH_GIVE_ALLOC
 265 /* If the caller has requested to use his own allocation functions, do so */
 266 static inline void P(init_alloc) (void) { }
 267 static inline void P(cleanup_alloc) (void) { }
 268
 269 #elif defined(HASH_USE_POOL)
 270 /* If the caller has requested to use his mempool, do so */
 271 #include "lib/pools.h"
 272 static inline void * P(alloc) (unsigned int size) { return mp_alloc_fast(HASH_USE_POOL, size); }
 273 static inline void P(init_alloc) (void) { }
 274 static inline void P(cleanup_alloc) (void) { }
 275
 276 #elif defined(HASH_AUTO_POOL)
 277 /* Use our own pools */
 278 #include "lib/pools.h"
 279 static struct mempool *P(pool);
 280 static inline void * P(alloc) (unsigned int size) { return mp_alloc_fast(P(pool), size); }
 281 static inline void P(init_alloc) (void) { P(pool) = mp_new(HASH_AUTO_POOL); }
 282 static inline void P(cleanup_alloc) (void) { mp_delete(P(pool)); }
 283
 284 #else
 285 /* The default allocation method */
 286 static inline void * P(alloc) (unsigned int size) { return xmalloc(size); }
 287 static inline void P(free) (void *x) { xfree(x); }
 288 static inline void P(init_alloc) (void) { }
 289 static inline void P(cleanup_alloc) (void) { }
 290
 291 #endif
 292
 293 #ifndef HASH_DEFAULT_SIZE
 294 #define HASH_DEFAULT_SIZE 32
 295 #endif
 296
 297 #ifndef HASH_FN_BITS
 298 #define HASH_FN_BITS 32
 299 #endif
 300
 301 /* Now the operations */
 302
 303 static void P(alloc_table) (void)
 304 {
 305   T.hash_size = nextprime(T.hash_size);
 306   T.ht = xmalloc(sizeof(void *) * T.hash_size);
 307   bzero(T.ht, sizeof(void *) * T.hash_size);
 308   if (2*T.hash_size < T.hash_hard_max)
 309     T.hash_max = 2*T.hash_size;
 310   else
 311     T.hash_max = ~0U;
 312   if (T.hash_size/2 > HASH_DEFAULT_SIZE)
 313     T.hash_min = T.hash_size/4;
 314   else
 315     T.hash_min = 0;
 316 }
 317
 318 static void P(init) (void)
 319 {
 320   T.hash_count = 0;
 321   T.hash_size = HASH_DEFAULT_SIZE;
 322 #if HASH_FN_BITS < 28
 323   T.hash_hard_max = 1 << HASH_FN_BITS;
 324 #else
 325   T.hash_hard_max = 1 << 28;
 326 #endif
 327   P(alloc_table)();
 328   P(init_alloc)();
 329 }
 330
 331 #ifdef HASH_WANT_CLEANUP
 332 static void P(cleanup) (void)
 333 {
 334 #ifndef HASH_USE_POOL
 335   uns i;
 336   P(bucket) *b, *bb;
 337
 338   for (i=0; i<T.hash_size; i++)
 339     for (b=T.ht[i]; b; b=bb)
 340       {
 341         bb = b->next;
 342         P(free)(b);
 343       }
 344 #endif
 345   P(cleanup_alloc)();
 346   xfree(T.ht);
 347 }
 348 #endif
 349
 350 static inline uns P(bucket_hash) (P(bucket) *b)
 351 {
 352 #ifdef HASH_CONSERVE_SPACE
 353   return P(hash)(HASH_KEY(b->n.));
 354 #else
 355   return b->hash;
 356 #endif
 357 }
 358
 359 static void P(rehash) (uns size)
 360 {
 361   P(bucket) *b, *nb;
 362   P(bucket) **oldt = T.ht, **newt;
 363   uns oldsize = T.hash_size;
 364   uns i, h;
 365
 366   // log(L_DEBUG, "Rehashing %d->%d at count %d", oldsize, size, T.hash_count);
 367   T.hash_size = size;
 368   P(alloc_table)();
 369   newt = T.ht;
 370   for (i=0; i<oldsize; i++)
 371     {
 372       b = oldt[i];
 373       while (b)
 374         {
 375           nb = b->next;
 376           h = P(bucket_hash)(b) % T.hash_size;
 377           b->next = newt[h];
 378           newt[h] = b;
 379           b = nb;
 380         }
 381     }
 382   xfree(oldt);
 383 }
 384
 385 #ifdef HASH_WANT_FIND
 386 static P(node) * P(find) (HASH_KEY_DECL)
 387 {
 388   uns h0 = P(hash) (HASH_KEY( ));
 389   uns h = h0 % T.hash_size;
 390   P(bucket) *b;
 391
 392   for (b=T.ht[h]; b; b=b->next)
 393     {
 394       if (
 395 #ifndef HASH_CONSERVE_SPACE
 396           b->hash == h0 &&
 397 #endif
 398           P(eq)(HASH_KEY( ), HASH_KEY(b->n.)))
 399         return &b->n;
 400     }
 401   return NULL;
 402 }
 403 #endif
 404
 405 #ifdef HASH_WANT_FIND_NEXT
 406 static P(node) * P(find_next) (P(node) *start)
 407 {
 408 #ifndef HASH_CONSERVE_SPACE
 409   uns h0 = P(hash) (HASH_KEY(start->));
 410 #endif
 411   P(bucket) *b = SKIP_BACK(P(bucket), n, start);
 412
 413   for (b=b->next; b; b=b->next)
 414     {
 415       if (
 416 #ifndef HASH_CONSERVE_SPACE
 417           b->hash == h0 &&
 418 #endif
 419           P(eq)(HASH_KEY(start->), HASH_KEY(b->n.)))
 420         return &b->n;
 421     }
 422   return NULL;
 423 }
 424 #endif
 425
 426 #ifdef HASH_WANT_NEW
 427 static P(node) * P(new) (HASH_KEY_DECL)
 428 {
 429   uns h0, h;
 430   P(bucket) *b;
 431
 432   h0 = P(hash) (HASH_KEY( ));
 433   h = h0 % T.hash_size;
 434   b = P(alloc) (sizeof(struct P(bucket)) + HASH_EXTRA_SIZE(HASH_KEY( )));
 435   b->next = T.ht[h];
 436   T.ht[h] = b;
 437 #ifndef HASH_CONSERVE_SPACE
 438   b->hash = h0;
 439 #endif
 440   P(init_key)(&b->n, HASH_KEY( ));
 441   P(init_data)(&b->n);
 442   if (T.hash_count++ >= T.hash_max)
 443     P(rehash)(2*T.hash_size);
 444   return &b->n;
 445 }
 446 #endif
 447
 448 #ifdef HASH_WANT_LOOKUP
 449 static P(node) * P(lookup) (HASH_KEY_DECL)
 450 {
 451   uns h0 = P(hash) (HASH_KEY( ));
 452   uns h = h0 % T.hash_size;
 453   P(bucket) *b;
 454
 455   for (b=T.ht[h]; b; b=b->next)
 456     {
 457       if (
 458 #ifndef HASH_CONSERVE_SPACE
 459           b->hash == h0 &&
 460 #endif
 461           P(eq)(HASH_KEY( ), HASH_KEY(b->n.)))
 462         return &b->n;
 463     }
 464
 465   b = P(alloc) (sizeof(struct P(bucket)) + HASH_EXTRA_SIZE(HASH_KEY( )));
 466   b->next = T.ht[h];
 467   T.ht[h] = b;
 468 #ifndef HASH_CONSERVE_SPACE
 469   b->hash = h0;
 470 #endif
 471   P(init_key)(&b->n, HASH_KEY( ));
 472   P(init_data)(&b->n);
 473   if (T.hash_count++ >= T.hash_max)
 474     P(rehash)(2*T.hash_size);
 475   return &b->n;
 476 }
 477 #endif
 478
 479 #ifdef HASH_WANT_DELETE
 480 static int P(delete) (HASH_KEY_DECL)
 481 {
 482   uns h0 = P(hash) (HASH_KEY( ));
 483   uns h = h0 % T.hash_size;
 484   P(bucket) *b, **bb;
 485
 486   for (bb=&T.ht[h]; b=*bb; bb=&b->next)
 487     {
 488       if (
 489 #ifndef HASH_CONSERVE_SPACE
 490           b->hash == h0 &&
 491 #endif
 492           P(eq)(HASH_KEY( ), HASH_KEY(b->n.)))
 493         {
 494           *bb = b->next;
 495           P(free)(b);
 496           if (--T.hash_count < T.hash_min)
 497             P(rehash)(T.hash_size/2);
 498           return 1;
 499         }
 500     }
 501   return 0;
 502 }
 503 #endif
 504
 505 #ifdef HASH_WANT_REMOVE
 506 static void P(remove) (P(node) *n)
 507 {
 508   P(bucket) *x = SKIP_BACK(struct P(bucket), n, n);
 509   uns h0 = P(bucket_hash)(x);
 510   uns h = h0 % T.hash_size;
 511   P(bucket) *b, **bb;
 512
 513   for (bb=&T.ht[h]; (b=*bb) && b != x; bb=&b->next)
 514     ;
 515   ASSERT(b);
 516   *bb = b->next;
 517   P(free)(b);
 518   if (--T.hash_count < T.hash_min)
 519     P(rehash)(T.hash_size/2);
 520 }
 521 #endif
 522
 523 /* And the iterator */
 524
 525 #ifndef HASH_FOR_ALL
 526
 527 #define HASH_FOR_ALL(h_px, h_var)                                                       \
 528 do {                                                                                    \
 529   uns h_slot;                                                                           \
 530   struct GLUE_(h_px,bucket) *h_buck;                                                    \
 531   for (h_slot=0; h_slot < GLUE_(h_px,table).hash_size; h_slot++)                        \
 532     for (h_buck = GLUE_(h_px,table).ht[h_slot]; h_buck; h_buck = h_buck->next)  \
 533       {                                                                                 \
 534         GLUE_(h_px,node) *h_var = &h_buck->n;
 535 #define HASH_END_FOR } } while(0)
 536 #define HASH_BREAK
 537 #define HASH_CONTINUE continue
 538
 539 #endif
 540
 541 /* Finally, undefine all the parameters */
 542
 543 #undef P
 544 #undef T
 545
 546 #undef HASH_ATOMIC_TYPE
 547 #undef HASH_CONSERVE_SPACE
 548 #undef HASH_DEFAULT_SIZE
 549 #undef HASH_EXTRA_SIZE
 550 #undef HASH_FN_BITS
 551 #undef HASH_GIVE_ALLOC
 552 #undef HASH_GIVE_EQ
 553 #undef HASH_GIVE_EXTRA_SIZE
 554 #undef HASH_GIVE_HASHFN
 555 #undef HASH_GIVE_INIT_DATA
 556 #undef HASH_GIVE_INIT_KEY
 557 #undef HASH_KEY
 558 #undef HASH_KEY_ATOMIC
 559 #undef HASH_KEY_COMPLEX
 560 #undef HASH_KEY_DECL
 561 #undef HASH_KEY_ENDSTRING
 562 #undef HASH_KEY_STRING
 563 #undef HASH_NOCASE
 564 #undef HASH_NODE
 565 #undef HASH_PREFIX
 566 #undef HASH_USE_POOL
 567 #undef HASH_AUTO_POOL
 568 #undef HASH_WANT_CLEANUP
 569 #undef HASH_WANT_DELETE
 570 #undef HASH_WANT_FIND
 571 #undef HASH_WANT_FIND_NEXT
 572 #undef HASH_WANT_LOOKUP
 573 #undef HASH_WANT_NEW
 574 #undef HASH_WANT_REMOVE