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