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