ucw/hashtable.h

   1 /*
   2  *      UCW Library -- Universal Hash Table
   3  *
   4  *      (c) 2002--2004 Martin Mares <mj@ucw.cz>
   5  *      (c) 2002--2005 Robert Spalek <robert@ucw.cz>
   6  *      (c) 2010 Pavel Charvat <pchar@ucw.cz>
   7  *
   8  *      This software may be freely distributed and used according to the terms
   9  *      of the GNU Lesser General Public License.
  10  */
  11
  12 /*
  13  *  This is not a normal header file, it's a generator of hash tables.
  14  *  Each time you include it with parameters set in the corresponding
  15  *  preprocessor macros, it generates a hash table with the parameters
  16  *  given.
  17  *
  18  *  You need to specify:
  19  *
  20  *  HASH_NODE           data type where a node dwells (usually a struct).
  21  *  HASH_PREFIX(x)      macro to add a name prefix (used on all global names
  22  *                      defined by the hash table generator).
  23  *
  24  *  Then decide on type of keys:
  25  *
  26  *  HASH_KEY_ATOMIC=f   use node->f as a key of an atomic type (i.e.,
  27  *                      a type which can be compared using `==')
  28  *                      HASH_ATOMIC_TYPE (defaults to int).
  29  *  | HASH_KEY_STRING=f use node->f as a string key, allocated
  30  *                      separately from the rest of the node.
  31  *  | HASH_KEY_ENDSTRING=f use node->f as a string key, allocated
  32  *                      automatically at the end of the node struct
  33  *                      (to be declared as "char f[1]" at the end).
  34  *  | HASH_KEY_COMPLEX  use a multi-component key; as the name suggests,
  35  *                      the passing of parameters is a bit complex then.
  36  *                      The HASH_KEY_COMPLEX(x) macro should expand to
  37  *                      `x k1, x k2, ... x kn' and you should also define:
  38  *    HASH_KEY_DECL     declaration of function parameters in which key
  39  *                      should be passed to all hash table operations.
  40  *                      That is, `type1 k1, type2 k2, ... typen kn'.
  41  *                      With complex keys, HASH_GIVE_HASHFN and HASH_GIVE_EQ
  42  *                      are mandatory.
  43  *  | HASH_KEY_MEMORY=f use node->f as a raw data key, compared using
  44  *                      memcmp
  45  *    HASH_KEY_SIZE     the length of the key block
  46  *
  47  *  Then specify what operations you request (all names are automatically
  48  *  prefixed by calling HASH_PREFIX):
  49  *
  50  *  <always defined>    init() -- initialize the hash table.
  51  *  HASH_WANT_CLEANUP   cleanup() -- deallocate the hash table.
  52  *  HASH_WANT_FIND      node *find(key) -- find first node with the specified
  53  *                      key, return NULL if no such node exists.
  54  *  HASH_WANT_FIND_NEXT node *find(node *start) -- find next node with the
  55  *                      specified key, return NULL if no such node exists.
  56  *  HASH_WANT_NEW       node *new(key) -- create new node with given key.
  57  *                      Doesn't check whether it already exists.
  58  *  HASH_WANT_LOOKUP    node *lookup(key) -- find node with given key,
  59  *                      if it doesn't exist, create it. Defining
  60  *                      HASH_GIVE_INIT_DATA is strongly recommended.
  61  *  HASH_WANT_DELETE    int delete(key) -- delete and deallocate node
  62  *                      with given key. Returns success.
  63  *  HASH_WANT_REMOVE    remove(node *) -- delete and deallocate given node.
  64  *
  65  *  You can also supply several functions:
  66  *
  67  *  HASH_GIVE_HASHFN    unsigned int hash(key) -- calculate hash value of key.
  68  *                      We have sensible default hash functions for strings
  69  *                      and integers.
  70  *  HASH_GIVE_EQ        int eq(key1, key2) -- return whether keys are equal.
  71  *                      By default, we use == for atomic types and either
  72  *                      strcmp or strcasecmp for strings.
  73  *  HASH_GIVE_EXTRA_SIZE int extra_size(key) -- returns how many bytes after the
  74  *                      node should be allocated for dynamic data. Default=0
  75  *                      or length of the string with HASH_KEY_ENDSTRING.
  76  *  HASH_GIVE_INIT_KEY  void init_key(node *,key) -- initialize key in a newly
  77  *                      created node. Defaults: assignment for atomic keys
  78  *                      and static strings, strcpy for end-allocated strings.
  79  *  HASH_GIVE_INIT_DATA void init_data(node *) -- initialize data fields in a
  80  *                      newly created node. Very useful for lookup operations.
  81  *  HASH_GIVE_ALLOC     void *alloc(unsigned int size) -- allocate space for
  82  *                      a node. Default is xmalloc() or pooled allocation, depending
  83  *                      on HASH_USE_POOL, HASH_AUTO_POOL, HASH_USE_ELTPOOL
  84  *                      and HASH_AUTO_ELTPOOL switches. void free(void *) -- the converse.
  85  * HASH_GIVE_TABLE_ALLOC void *table_alloc(unsigned int size), void *table_free(void *)
  86  *                      Allocate or free space for the table itself. Default is xmalloc()
  87  *                      or the functions defined by HASH_GIVE_ALLOC if HASH_TABLE_ALLOC is set.
  88  *
  89  *  ... and a couple of extra parameters:
  90  *
  91  *  HASH_NOCASE         String comparisons should be case-insensitive.
  92  *  HASH_DEFAULT_SIZE=n Initially, use hash table of approx. `n' entries.
  93  *  HASH_CONSERVE_SPACE Use as little space as possible.
  94  *  HASH_FN_BITS=n      The hash function gives only `n' significant bits.
  95  *  HASH_ATOMIC_TYPE=t  Atomic values are of type `t' instead of int.
  96  *  HASH_USE_POOL=pool  Allocate all nodes from given mempool. Note, however, that
  97  *                      deallocation is not supported by mempools, so delete/remove
  98  *                      will leak pool memory.
  99  *  HASH_AUTO_POOL=size Create a pool of the given block size automatically.
 100  *  HASH_USE_ELTPOOL=pool Allocate all nodes from given eltpool.
 101  *  HASH_AUTO_ELTPOOL=count Create an eltpool of the given number of elements in each chunk.
 102  *  HASH_ZERO_FILL      New entries should be initialized to all zeroes.
 103  *  HASH_TABLE_ALLOC    The hash table itself will be allocated and freed using
 104  *                      the same allocation functions as the nodes instead of
 105  *                      the default xmalloc().
 106  *  HASH_TABLE_GROWING  Never decrease the size of the hash table itself
 107  *  HASH_TABLE_DYNAMIC  Support multiple hash tables; the first parameter of all
 108  *                      hash table operations is struct HASH_PREFIX(table) *.
 109  *  HASH_TABLE_VARS     Extra variables to be defined in table structure
 110  *
 111  *  You also get a iterator macro at no extra charge:
 112  *
 113  *  HASH_FOR_ALL(hash_prefix, variable)
 114  *    {
 115  *      // node *variable gets declared automatically
 116  *      do_something_with_node(variable);
 117  *      // use HASH_BREAK and HASH_CONTINUE instead of break and continue
 118  *      // you must not alter contents of the hash table here
 119  *    }
 120  *  HASH_END_FOR;
 121  *
 122  *  (For dynamic tables, use HASH_FOR_ALL_DYNAMIC(hash_prefix, hash_table, variable) instead.)
 123  *
 124  *  Then include "ucw/hashtable.h" and voila, you have a hash table
 125  *  suiting all your needs (at least those which you've revealed :) ).
 126  *
 127  *  After including this file, all parameter macros are automatically
 128  *  undef'd.
 129  */
 130
 131 #ifndef _UCW_HASHFUNC_H
 132 #include "ucw/hashfunc.h"
 133 #endif
 134
 135 #include "ucw/prime.h"
 136
 137 #include <string.h>
 138
 139 /* Initial setup of parameters */
 140
 141 #if !defined(HASH_NODE) || !defined(HASH_PREFIX)
 142 #error Some of the mandatory configuration macros are missing.
 143 #endif
 144
 145 #if defined(HASH_KEY_ATOMIC) && !defined(HASH_CONSERVE_SPACE)
 146 #define HASH_CONSERVE_SPACE
 147 #endif
 148
 149 #define P(x) HASH_PREFIX(x)
 150
 151 /* Declare buckets and the hash table */
 152
 153 typedef HASH_NODE P(node);
 154
 155 typedef struct P(bucket) {
 156   struct P(bucket) *next;
 157 #ifndef HASH_CONSERVE_SPACE
 158   uns hash;
 159 #endif
 160   P(node) n;
 161 } P(bucket);
 162
 163 struct P(table) {
 164 #ifdef HASH_TABLE_VARS
 165   HASH_TABLE_VARS
 166 #endif
 167   uns hash_size;
 168   uns hash_count, hash_max, hash_min, hash_hard_max;
 169   P(bucket) **ht;
 170 #ifdef HASH_AUTO_POOL
 171   struct mempool *pool;
 172 #endif
 173 #ifdef HASH_AUTO_ELTPOOL
 174   struct eltpool *eltpool;
 175 #endif
 176 };
 177
 178 #ifdef HASH_TABLE_DYNAMIC
 179 #define T (*table)
 180 #define TA struct P(table) *table
 181 #define TAC TA,
 182 #define TAU TA UNUSED
 183 #define TAUC TA UNUSED,
 184 #define TT table
 185 #define TTC table,
 186 #else
 187 struct P(table) P(table);
 188 #define T P(table)
 189 #define TA void
 190 #define TAC
 191 #define TAU void
 192 #define TAUC
 193 #define TT
 194 #define TTC
 195 #endif
 196
 197 /* Preset parameters */
 198
 199 #if defined(HASH_KEY_ATOMIC)
 200
 201 #define HASH_KEY(x) x HASH_KEY_ATOMIC
 202
 203 #ifndef HASH_ATOMIC_TYPE
 204 #  define HASH_ATOMIC_TYPE int
 205 #endif
 206 #define HASH_KEY_DECL HASH_ATOMIC_TYPE HASH_KEY( )
 207
 208 #ifndef HASH_GIVE_HASHFN
 209 #  define HASH_GIVE_HASHFN
 210    static inline int P(hash) (TAUC HASH_ATOMIC_TYPE x)
 211    { return ((sizeof(x) <= 4) ? hash_u32(x) : hash_u64(x)); }
 212 #endif
 213
 214 #ifndef HASH_GIVE_EQ
 215 #  define HASH_GIVE_EQ
 216    static inline int P(eq) (TAUC HASH_ATOMIC_TYPE x, HASH_ATOMIC_TYPE y)
 217    { return x == y; }
 218 #endif
 219
 220 #ifndef HASH_GIVE_INIT_KEY
 221 #  define HASH_GIVE_INIT_KEY
 222    static inline void P(init_key) (TAUC P(node) *n, HASH_ATOMIC_TYPE k)
 223    { HASH_KEY(n->) = k; }
 224 #endif
 225
 226 #elif defined(HASH_KEY_MEMORY)
 227
 228 #define HASH_KEY(x) x HASH_KEY_MEMORY
 229
 230 #define HASH_KEY_DECL byte HASH_KEY( )[HASH_KEY_SIZE]
 231
 232 #ifndef HASH_GIVE_HASHFN
 233 #  define HASH_GIVE_HASHFN
 234    static inline int P(hash) (TAUC byte *x)
 235    { return hash_block(x, HASH_KEY_SIZE); }
 236 #endif
 237
 238 #ifndef HASH_GIVE_EQ
 239 #  define HASH_GIVE_EQ
 240    static inline int P(eq) (TAUC byte *x, byte *y)
 241    { return !memcmp(x, y, HASH_KEY_SIZE); }
 242 #endif
 243
 244 #ifndef HASH_GIVE_INIT_KEY
 245 #  define HASH_GIVE_INIT_KEY
 246    static inline void P(init_key) (TAUC P(node) *n, byte *k)
 247    { memcpy(HASH_KEY(n->), k, HASH_KEY_SIZE); }
 248 #endif
 249
 250 #elif defined(HASH_KEY_STRING) || defined(HASH_KEY_ENDSTRING)
 251
 252 #ifdef HASH_KEY_STRING
 253 #  define HASH_KEY(x) x HASH_KEY_STRING
 254 #  ifndef HASH_GIVE_INIT_KEY
 255 #    define HASH_GIVE_INIT_KEY
 256      static inline void P(init_key) (TAUC P(node) *n, char *k)
 257      { HASH_KEY(n->) = k; }
 258 #  endif
 259 #else
 260 #  define HASH_KEY(x) x HASH_KEY_ENDSTRING
 261 #  define HASH_GIVE_EXTRA_SIZE
 262    static inline int P(extra_size) (TAUC char *k)
 263    { return strlen(k); }
 264 #  ifndef HASH_GIVE_INIT_KEY
 265 #    define HASH_GIVE_INIT_KEY
 266      static inline void P(init_key) (TAUC P(node) *n, char *k)
 267      { strcpy(HASH_KEY(n->), k); }
 268 #  endif
 269 #endif
 270 #define HASH_KEY_DECL char *HASH_KEY( )
 271
 272 #ifndef HASH_GIVE_HASHFN
 273 #define HASH_GIVE_HASHFN
 274   static inline uns P(hash) (TAUC char *k)
 275    {
 276 #    ifdef HASH_NOCASE
 277        return hash_string_nocase(k);
 278 #    else
 279        return hash_string(k);
 280 #    endif
 281    }
 282 #endif
 283
 284 #ifndef HASH_GIVE_EQ
 285 #  define HASH_GIVE_EQ
 286    static inline int P(eq) (TAUC char *x, char *y)
 287    {
 288 #    ifdef HASH_NOCASE
 289        return !strcasecmp(x,y);
 290 #    else
 291        return !strcmp(x,y);
 292 #    endif
 293    }
 294 #endif
 295
 296 #elif defined(HASH_KEY_COMPLEX)
 297
 298 #define HASH_KEY(x) HASH_KEY_COMPLEX(x)
 299
 300 #else
 301 #error You forgot to set the hash key type.
 302 #endif
 303
 304 /* Defaults for missing parameters */
 305
 306 #ifndef HASH_GIVE_HASHFN
 307 #error Unable to determine which hash function to use.
 308 #endif
 309
 310 #ifndef HASH_GIVE_EQ
 311 #error Unable to determine how to compare two keys.
 312 #endif
 313
 314 #ifdef HASH_GIVE_EXTRA_SIZE
 315 /* This trickery is needed to avoid `unused parameter' warnings */
 316 #define HASH_EXTRA_SIZE(x) P(extra_size)(TTC x)
 317 #else
 318 /*
 319  *  Beware, C macros are expanded iteratively, not recursively,
 320  *  hence we get only a _single_ argument, although the expansion
 321  *  of HASH_KEY contains commas.
 322  */
 323 #define HASH_EXTRA_SIZE(x) 0
 324 #endif
 325
 326 #ifndef HASH_GIVE_INIT_KEY
 327 #error Unable to determine how to initialize keys.
 328 #endif
 329
 330 #ifndef HASH_GIVE_INIT_DATA
 331 static inline void P(init_data) (TAUC P(node) *n UNUSED)
 332 {
 333 }
 334 #endif
 335
 336 #ifdef HASH_GIVE_ALLOC
 337 /* If the caller has requested to use his own allocation functions, do so */
 338 static inline void P(init_alloc) (TAU) { }
 339 static inline void P(cleanup_alloc) (TAU) { }
 340
 341 #elif defined(HASH_USE_POOL)
 342 /* If the caller has requested to use his mempool, do so */
 343 #include "ucw/mempool.h"
 344 static inline void * P(alloc) (TAUC unsigned int size) { return mp_alloc_fast(HASH_USE_POOL, size); }
 345 static inline void P(free) (TAUC void *x UNUSED) { }
 346 static inline void P(init_alloc) (TAU) { }
 347 static inline void P(cleanup_alloc) (TAU) { }
 348
 349 #elif defined(HASH_AUTO_POOL)
 350 /* Use our own pools */
 351 #include "ucw/mempool.h"
 352 static inline void * P(alloc) (TAUC unsigned int size) { return mp_alloc_fast(T.pool, size); }
 353 static inline void P(free) (TAUC void *x UNUSED) { }
 354 static inline void P(init_alloc) (TAU) { T.pool = mp_new(HASH_AUTO_POOL); }
 355 static inline void P(cleanup_alloc) (TAU) { mp_delete(T.pool); }
 356 #define HASH_USE_POOL
 357
 358 #elif defined(HASH_USE_ELTPOOL)
 359 /* If the caller has requested to use his eltpool, do so */
 360 #include "ucw/eltpool.h"
 361 static inline void * P(alloc) (TAUC unsigned int size UNUSED) { ASSERT(size <= (HASH_USE_ELTPOOL)->elt_size); return ep_alloc(HASH_USE_ELTPOOL); }
 362 static inline void P(free) (TAUC void *x) { ep_free(HASH_USE_ELTPOOL, x); }
 363 static inline void P(init_alloc) (TAU) { }
 364 static inline void P(cleanup_alloc) (TAU) { }
 365
 366 #elif defined(HASH_AUTO_ELTPOOL)
 367 /* Use our own eltpools */
 368 #include "ucw/eltpool.h"
 369 static inline void * P(alloc) (TAUC unsigned int size UNUSED) { return ep_alloc(T.eltpool); }
 370 static inline void P(free) (TAUC void *x) { ep_free(T.eltpool, x); }
 371 static inline void P(init_alloc) (TAU) { T.eltpool = ep_new(sizeof(P(bucket)), HASH_AUTO_ELTPOOL); }
 372 static inline void P(cleanup_alloc) (TAU) { ep_delete(T.eltpool); }
 373 #define HASH_USE_ELTPOOL
 374
 375 #else
 376 /* The default allocation method */
 377 static inline void * P(alloc) (TAUC unsigned int size) { return xmalloc(size); }
 378 static inline void P(free) (TAUC void *x) { xfree(x); }
 379 static inline void P(init_alloc) (TAU) { }
 380 static inline void P(cleanup_alloc) (TAU) { }
 381
 382 #endif
 383
 384 #if defined(HASH_USE_ELTPOOL) && defined(HASH_GIVE_EXTRA_SIZE)
 385 #error Eltpools not supported in combination with variable-sized nodes
 386 #endif
 387
 388 #ifdef HASH_GIVE_TABLE_ALLOC
 389 /* If the caller has requested to use his own allocation functions, do so */
 390 #elif defined(HASH_TABLE_ALLOC)
 391 #ifdef HASH_USE_ELTPOOL
 392 #error HASH_TABLE_ALLOC not supported in combination with eltpools
 393 #endif
 394 static inline void * P(table_alloc) (TAUC unsigned int size) { return P(alloc)(TTC size); }
 395 static inline void P(table_free) (TAUC void *x) { P(free)(TTC x); }
 396 #else
 397 static inline void * P(table_alloc) (TAUC unsigned int size) { return xmalloc(size); }
 398 static inline void P(table_free) (TAUC void *x) { xfree(x); }
 399 #endif
 400
 401 #if defined(HASH_USE_POOL) && defined(HASH_TABLE_ALLOC) && !defined(HASH_TABLE_GROWING)
 402 #define HASH_TABLE_GROWING
 403 #endif
 404
 405 #ifndef HASH_DEFAULT_SIZE
 406 #define HASH_DEFAULT_SIZE 32
 407 #endif
 408
 409 #ifndef HASH_FN_BITS
 410 #define HASH_FN_BITS 32
 411 #endif
 412
 413 #ifdef HASH_ZERO_FILL
 414 static inline void * P(new_bucket)(TAUC uns size)
 415 {
 416   byte *buck = P(alloc)(TTC size);
 417   bzero(buck, size);
 418   return buck;
 419 }
 420 #else
 421 static inline void * P(new_bucket)(TAUC uns size) { return P(alloc)(TTC size); }
 422 #endif
 423
 424 /* Now the operations */
 425
 426 static void P(alloc_table) (TAU)
 427 {
 428   T.hash_size = next_table_prime(T.hash_size);
 429   T.ht = P(table_alloc)(TTC sizeof(void *) * T.hash_size);
 430   bzero(T.ht, sizeof(void *) * T.hash_size);
 431   if (2*T.hash_size < T.hash_hard_max)
 432     T.hash_max = 2*T.hash_size;
 433   else
 434     T.hash_max = ~0U;
 435 #ifndef HASH_TABLE_GROWING
 436   if (T.hash_size/2 > HASH_DEFAULT_SIZE)
 437     T.hash_min = T.hash_size/4;
 438   else
 439 #endif
 440     T.hash_min = 0;
 441 }
 442
 443 /**
 444  * Initializes the hash table.
 445  * This one is available no matter what `HASH_WANT_` macros you defined or not.
 446  **/
 447 static void HASH_PREFIX(init)(TA)
 448 {
 449   T.hash_count = 0;
 450   T.hash_size = HASH_DEFAULT_SIZE;
 451 #if HASH_FN_BITS < 28
 452   T.hash_hard_max = 1 << HASH_FN_BITS;
 453 #else
 454   T.hash_hard_max = 1 << 28;
 455 #endif
 456   P(init_alloc)(TT);
 457   P(alloc_table)(TT);
 458 }
 459
 460 #ifdef HASH_WANT_CLEANUP
 461 /**
 462  * Deallocates the hash table, including the nodes.
 463  * It is available if you defined <<want_cleanup,`HASH_WANT_CLEANUP`>>.
 464  **/
 465 static void HASH_PREFIX(cleanup)(TA)
 466 {
 467 #ifndef HASH_USE_POOL
 468   uns i;
 469   P(bucket) *b, *bb;
 470
 471   for (i=0; i<T.hash_size; i++)
 472     for (b=T.ht[i]; b; b=bb)
 473       {
 474         bb = b->next;
 475         P(free)(TTC b);
 476       }
 477 #endif
 478   P(cleanup_alloc)(TT);
 479   P(table_free)(TTC T.ht);
 480 }
 481 #endif
 482
 483 static inline uns P(bucket_hash) (TAUC P(bucket) *b)
 484 {
 485 #ifdef HASH_CONSERVE_SPACE
 486   return P(hash)(TTC HASH_KEY(b->n.));
 487 #else
 488   return b->hash;
 489 #endif
 490 }
 491
 492 static void P(rehash) (TAC uns size)
 493 {
 494   P(bucket) *b, *nb;
 495   P(bucket) **oldt = T.ht, **newt;
 496   uns oldsize = T.hash_size;
 497   uns i, h;
 498
 499   DBG("Rehashing %d->%d at count %d", oldsize, size, T.hash_count);
 500   T.hash_size = size;
 501   P(alloc_table)(TT);
 502   newt = T.ht;
 503   for (i=0; i<oldsize; i++)
 504     {
 505       b = oldt[i];
 506       while (b)
 507         {
 508           nb = b->next;
 509           h = P(bucket_hash)(TTC b) % T.hash_size;
 510           b->next = newt[h];
 511           newt[h] = b;
 512           b = nb;
 513         }
 514     }
 515   P(table_free)(TTC oldt);
 516 }
 517
 518 #ifdef HASH_WANT_FIND
 519 /**
 520  * Finds a node with given key (specified in the @HAS_KEY_DECL parameter).
 521  * If it does not exist, NULL is returned.
 522  *
 523  * Enabled by the <<want_find,`HASH_WANT_FIND`>> macro.
 524  **/
 525 static HASH_NODE* HASH_PREFIX(find)(TAC HASH_KEY_DECL)
 526 {
 527   uns h0 = P(hash) (TTC HASH_KEY( ));
 528   uns h = h0 % T.hash_size;
 529   P(bucket) *b;
 530
 531   for (b=T.ht[h]; b; b=b->next)
 532     {
 533       if (
 534 #ifndef HASH_CONSERVE_SPACE
 535           b->hash == h0 &&
 536 #endif
 537           P(eq)(TTC HASH_KEY( ), HASH_KEY(b->n.)))
 538         return &b->n;
 539     }
 540   return NULL;
 541 }
 542 #endif
 543
 544 #ifdef HASH_WANT_FIND_NEXT
 545 /**
 546  * Finds next node with the same key. Returns NULL if it does not exist.
 547  *
 548  * Enabled by the <<want_find_next,`HASH_WANT_FIND_NEXT`>> macro.
 549  **/
 550 static HASH_NODE* HASH_PREFIX(find_next)(TAC P(node) *start)
 551 {
 552 #ifndef HASH_CONSERVE_SPACE
 553   uns h0 = P(hash) (TTC HASH_KEY(start->));
 554 #endif
 555   P(bucket) *b = SKIP_BACK(P(bucket), n, start);
 556
 557   for (b=b->next; b; b=b->next)
 558     {
 559       if (
 560 #ifndef HASH_CONSERVE_SPACE
 561           b->hash == h0 &&
 562 #endif
 563           P(eq)(TTC HASH_KEY(start->), HASH_KEY(b->n.)))
 564         return &b->n;
 565     }
 566   return NULL;
 567 }
 568 #endif
 569
 570 #ifdef HASH_WANT_NEW
 571 /**
 572  * Generates a new node with a given key.
 573  *
 574  * Enabled by the <<want_new,`HASH_WANT_NEW`>> macro.
 575  **/
 576 static HASH_NODE * HASH_PREFIX(new)(TAC HASH_KEY_DECL)
 577 {
 578   uns h0, h;
 579   P(bucket) *b;
 580
 581   h0 = P(hash) (TTC HASH_KEY( ));
 582   h = h0 % T.hash_size;
 583   b = P(new_bucket) (TTC sizeof(struct P(bucket)) + HASH_EXTRA_SIZE(HASH_KEY( )));
 584   b->next = T.ht[h];
 585   T.ht[h] = b;
 586 #ifndef HASH_CONSERVE_SPACE
 587   b->hash = h0;
 588 #endif
 589   P(init_key)(TTC &b->n, HASH_KEY( ));
 590   P(init_data)(TTC &b->n);
 591   if (T.hash_count++ >= T.hash_max)
 592     P(rehash)(TTC 2*T.hash_size);
 593   return &b->n;
 594 }
 595 #endif
 596
 597 #ifdef HASH_WANT_LOOKUP
 598 /**
 599  * Finds a node with a given key. If it does not exist, a new one is created.
 600  * It is strongly recommended to use <<give_init_data,`HASH_GIVE_INIT_DATA`>>.
 601  *
 602  * This one is enabled by the <<want_lookup,`HASH_WANT_LOOKUP`>> macro.
 603  **/
 604 static HASH_NODE* HASH_PREFIX(lookup)(TAC HASH_KEY_DECL)
 605 {
 606   uns h0 = P(hash) (TTC HASH_KEY( ));
 607   uns h = h0 % T.hash_size;
 608   P(bucket) *b;
 609
 610   for (b=T.ht[h]; b; b=b->next)
 611     {
 612       if (
 613 #ifndef HASH_CONSERVE_SPACE
 614           b->hash == h0 &&
 615 #endif
 616           P(eq)(TTC HASH_KEY( ), HASH_KEY(b->n.)))
 617         return &b->n;
 618     }
 619
 620   b = P(new_bucket) (TTC sizeof(struct P(bucket)) + HASH_EXTRA_SIZE(HASH_KEY( )));
 621   b->next = T.ht[h];
 622   T.ht[h] = b;
 623 #ifndef HASH_CONSERVE_SPACE
 624   b->hash = h0;
 625 #endif
 626   P(init_key)(TTC &b->n, HASH_KEY( ));
 627   P(init_data)(TTC &b->n);
 628   if (T.hash_count++ >= T.hash_max)
 629     P(rehash)(TTC 2*T.hash_size);
 630   return &b->n;
 631 }
 632 #endif
 633
 634 #ifdef HASH_WANT_DELETE
 635 /**
 636  * Removes a node with the given key from hash table and deallocates it.
 637  *
 638  * Success is returned.
 639  *
 640  * This one is enabled by <<want_delete,`HASH_WANT_DELETE`>> macro.
 641  **/
 642 static int HASH_PREFIX(delete)(TAC HASH_KEY_DECL)
 643 {
 644   uns h0 = P(hash) (TTC HASH_KEY( ));
 645   uns h = h0 % T.hash_size;
 646   P(bucket) *b, **bb;
 647
 648   for (bb=&T.ht[h]; b=*bb; bb=&b->next)
 649     {
 650       if (
 651 #ifndef HASH_CONSERVE_SPACE
 652           b->hash == h0 &&
 653 #endif
 654           P(eq)(TTC HASH_KEY( ), HASH_KEY(b->n.)))
 655         {
 656           *bb = b->next;
 657           P(free)(TTC b);
 658           T.hash_count--;
 659 #ifndef HASH_TABLE_GROWING
 660           if (T.hash_count < T.hash_min)
 661             P(rehash)(TTC T.hash_size/2);
 662 #endif
 663           return 1;
 664         }
 665     }
 666   return 0;
 667 }
 668 #endif
 669
 670 #ifdef HASH_WANT_REMOVE
 671 /**
 672  * Removes a given node and deallocates it.
 673  * It differs from <<fun__GENERIC_LINK|HASH_PREFIX|delete,`HASH_PREFIX(delete)()`>>
 674  * in its type of parameter -- this one deletes a specific node, that one looks for it by a key.
 675  *
 676  * Enabled by <<want_remove,`HASH_WANT_REMOVE`>> macro.
 677  **/
 678 static void HASH_PREFIX(remove)(TAC HASH_NODE *n)
 679 {
 680   P(bucket) *x = SKIP_BACK(struct P(bucket), n, n);
 681   uns h0 = P(bucket_hash)(TTC x);
 682   uns h = h0 % T.hash_size;
 683   P(bucket) *b, **bb;
 684
 685   for (bb=&T.ht[h]; (b=*bb) && b != x; bb=&b->next)
 686     ;
 687   ASSERT(b);
 688   *bb = b->next;
 689   P(free)(TTC b);
 690   T.hash_count--;
 691 #ifndef HASH_TABLE_GROWING
 692   if (T.hash_count < T.hash_min)
 693     P(rehash)(TTC T.hash_size/2);
 694 #endif
 695 }
 696 #endif
 697
 698 /* And the iterator */
 699
 700 #ifndef HASH_FOR_ALL
 701
 702 #define HASH_FOR_ALL_DYNAMIC(h_px, h_table, h_var)                                      \
 703 do {                                                                                    \
 704   uns h_slot;                                                                           \
 705   struct GLUE_(h_px,bucket) *h_buck;                                                    \
 706   for (h_slot=0; h_slot < (h_table)->hash_size; h_slot++)                               \
 707     for (h_buck = (h_table)->ht[h_slot]; h_buck; h_buck = h_buck->next)                 \
 708       {                                                                                 \
 709         GLUE_(h_px,node) *h_var = &h_buck->n;
 710 #define HASH_FOR_ALL(h_px, h_var) HASH_FOR_ALL_DYNAMIC(h_px, &GLUE_(h_px,table), h_var)
 711 #define HASH_END_FOR } } while(0)
 712 #define HASH_BREAK
 713 #define HASH_CONTINUE continue
 714
 715 #endif
 716
 717 /* Finally, undefine all the parameters */
 718
 719 #undef P
 720 #undef T
 721 #undef TA
 722 #undef TAC
 723 #undef TAU
 724 #undef TAUC
 725 #undef TT
 726 #undef TTC
 727
 728 #undef HASH_ATOMIC_TYPE
 729 #undef HASH_CONSERVE_SPACE
 730 #undef HASH_DEFAULT_SIZE
 731 #undef HASH_EXTRA_SIZE
 732 #undef HASH_FN_BITS
 733 #undef HASH_GIVE_ALLOC
 734 #undef HASH_GIVE_TABLE_ALLOC
 735 #undef HASH_GIVE_EQ
 736 #undef HASH_GIVE_EXTRA_SIZE
 737 #undef HASH_GIVE_HASHFN
 738 #undef HASH_GIVE_INIT_DATA
 739 #undef HASH_GIVE_INIT_KEY
 740 #undef HASH_KEY
 741 #undef HASH_KEY_ATOMIC
 742 #undef HASH_KEY_COMPLEX
 743 #undef HASH_KEY_DECL
 744 #undef HASH_KEY_ENDSTRING
 745 #undef HASH_KEY_STRING
 746 #undef HASH_KEY_MEMORY
 747 #undef HASH_KEY_SIZE
 748 #undef HASH_NOCASE
 749 #undef HASH_NODE
 750 #undef HASH_PREFIX
 751 #undef HASH_USE_POOL
 752 #undef HASH_AUTO_POOL
 753 #undef HASH_USE_ELTPOOL
 754 #undef HASH_AUTO_ELTPOOL
 755 #undef HASH_WANT_CLEANUP
 756 #undef HASH_WANT_DELETE
 757 #undef HASH_WANT_FIND
 758 #undef HASH_WANT_FIND_NEXT
 759 #undef HASH_WANT_LOOKUP
 760 #undef HASH_WANT_NEW
 761 #undef HASH_WANT_REMOVE
 762 #undef HASH_TABLE_ALLOC
 763 #undef HASH_TABLE_GROWING
 764 #undef HASH_TABLE_DYNAMIC
 765 #undef HASH_TABLE_VARS
 766 #undef HASH_ZERO_FILL