libiberty/hashtab.c

   1 /* An expandable hash tables datatype.
   2    Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2009, 2010
   3    Free Software Foundation, Inc.
   4    Contributed by Vladimir Makarov (vmakarov@cygnus.com).
   5
   6 This file is part of the libiberty library.
   7 Libiberty is free software; you can redistribute it and/or
   8 modify it under the terms of the GNU Library General Public
   9 License as published by the Free Software Foundation; either
  10 version 2 of the License, or (at your option) any later version.
  11
  12 Libiberty is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 Library General Public License for more details.
  16
  17 You should have received a copy of the GNU Library General Public
  18 License along with libiberty; see the file COPYING.LIB.  If
  19 not, write to the Free Software Foundation, Inc., 51 Franklin Street - Fifth Floor,
  20 Boston, MA 02110-1301, USA.  */
  21
  22 /* This package implements basic hash table functionality.  It is possible
  23    to search for an entry, create an entry and destroy an entry.
  24
  25    Elements in the table are generic pointers.
  26
  27    The size of the table is not fixed; if the occupancy of the table
  28    grows too high the hash table will be expanded.
  29
  30    The abstract data implementation is based on generalized Algorithm D
  31    from Knuth's book "The art of computer programming".  Hash table is
  32    expanded by creation of new hash table and transferring elements from
  33    the old table to the new table. */
  34
  35 #ifdef HAVE_CONFIG_H
  36 #include "config.h"
  37 #endif
  38
  39 #include <sys/types.h>
  40
  41 #ifdef HAVE_STDLIB_H
  42 #include <stdlib.h>
  43 #endif
  44 #ifdef HAVE_STRING_H
  45 #include <string.h>
  46 #endif
  47 #ifdef HAVE_MALLOC_H
  48 #include <malloc.h>
  49 #endif
  50 #ifdef HAVE_LIMITS_H
  51 #include <limits.h>
  52 #endif
  53 #ifdef HAVE_INTTYPES_H
  54 #include <inttypes.h>
  55 #endif
  56 #ifdef HAVE_STDINT_H
  57 #include <stdint.h>
  58 #endif
  59
  60 #include <stdio.h>
  61
  62 #include "libiberty.h"
  63 #include "ansidecl.h"
  64 #include "hashtab.h"
  65
  66 #ifndef CHAR_BIT
  67 #define CHAR_BIT 8
  68 #endif
  69
  70 static unsigned int higher_prime_index (unsigned long);
  71 static hashval_t htab_mod_1 (hashval_t, hashval_t, hashval_t, int);
  72 static hashval_t htab_mod (hashval_t, htab_t);
  73 static hashval_t htab_mod_m2 (hashval_t, htab_t);
  74 static hashval_t hash_pointer (const void *);
  75 static int eq_pointer (const void *, const void *);
  76 static int htab_expand (htab_t);
  77 static PTR *find_empty_slot_for_expand (htab_t, hashval_t);
  78
  79 /* At some point, we could make these be NULL, and modify the
  80    hash-table routines to handle NULL specially; that would avoid
  81    function-call overhead for the common case of hashing pointers.  */
  82 htab_hash htab_hash_pointer = hash_pointer;
  83 htab_eq htab_eq_pointer = eq_pointer;
  84
  85 /* Table of primes and multiplicative inverses.
  86
  87    Note that these are not minimally reduced inverses.  Unlike when generating
  88    code to divide by a constant, we want to be able to use the same algorithm
  89    all the time.  All of these inverses (are implied to) have bit 32 set.
  90
  91    For the record, here's the function that computed the table; it's a
  92    vastly simplified version of the function of the same name from gcc.  */
  93
  94 #if 0
  95 unsigned int
  96 ceil_log2 (unsigned int x)
  97 {
  98   int i;
  99   for (i = 31; i >= 0 ; --i)
 100     if (x > (1u << i))
 101       return i+1;
 102   abort ();
 103 }
 104
 105 unsigned int
 106 choose_multiplier (unsigned int d, unsigned int *mlp, unsigned char *shiftp)
 107 {
 108   unsigned long long mhigh;
 109   double nx;
 110   int lgup, post_shift;
 111   int pow, pow2;
 112   int n = 32, precision = 32;
 113
 114   lgup = ceil_log2 (d);
 115   pow = n + lgup;
 116   pow2 = n + lgup - precision;
 117
 118   nx = ldexp (1.0, pow) + ldexp (1.0, pow2);
 119   mhigh = nx / d;
 120
 121   *shiftp = lgup - 1;
 122   *mlp = mhigh;
 123   return mhigh >> 32;
 124 }
 125 #endif
 126
 127 struct prime_ent
 128 {
 129   hashval_t prime;
 130   hashval_t inv;
 131   hashval_t inv_m2;     /* inverse of prime-2 */
 132   hashval_t shift;
 133 };
 134
 135 static struct prime_ent const prime_tab[] = {
 136   {          7, 0x24924925, 0x9999999b, 2 },
 137   {         13, 0x3b13b13c, 0x745d1747, 3 },
 138   {         31, 0x08421085, 0x1a7b9612, 4 },
 139   {         61, 0x0c9714fc, 0x15b1e5f8, 5 },
 140   {        127, 0x02040811, 0x0624dd30, 6 },
 141   {        251, 0x05197f7e, 0x073260a5, 7 },
 142   {        509, 0x01824366, 0x02864fc8, 8 },
 143   {       1021, 0x00c0906d, 0x014191f7, 9 },
 144   {       2039, 0x0121456f, 0x0161e69e, 10 },
 145   {       4093, 0x00300902, 0x00501908, 11 },
 146   {       8191, 0x00080041, 0x00180241, 12 },
 147   {      16381, 0x000c0091, 0x00140191, 13 },
 148   {      32749, 0x002605a5, 0x002a06e6, 14 },
 149   {      65521, 0x000f00e2, 0x00110122, 15 },
 150   {     131071, 0x00008001, 0x00018003, 16 },
 151   {     262139, 0x00014002, 0x0001c004, 17 },
 152   {     524287, 0x00002001, 0x00006001, 18 },
 153   {    1048573, 0x00003001, 0x00005001, 19 },
 154   {    2097143, 0x00004801, 0x00005801, 20 },
 155   {    4194301, 0x00000c01, 0x00001401, 21 },
 156   {    8388593, 0x00001e01, 0x00002201, 22 },
 157   {   16777213, 0x00000301, 0x00000501, 23 },
 158   {   33554393, 0x00001381, 0x00001481, 24 },
 159   {   67108859, 0x00000141, 0x000001c1, 25 },
 160   {  134217689, 0x000004e1, 0x00000521, 26 },
 161   {  268435399, 0x00000391, 0x000003b1, 27 },
 162   {  536870909, 0x00000019, 0x00000029, 28 },
 163   { 1073741789, 0x0000008d, 0x00000095, 29 },
 164   { 2147483647, 0x00000003, 0x00000007, 30 },
 165   /* Avoid "decimal constant so large it is unsigned" for 4294967291.  */
 166   { 0xfffffffb, 0x00000006, 0x00000008, 31 }
 167 };
 168
 169 /* The following function returns an index into the above table of the
 170    nearest prime number which is greater than N, and near a power of two. */
 171
 172 static unsigned int
 173 higher_prime_index (unsigned long n)
 174 {
 175   unsigned int low = 0;
 176   unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]);
 177
 178   while (low != high)
 179     {
 180       unsigned int mid = low + (high - low) / 2;
 181       if (n > prime_tab[mid].prime)
 182         low = mid + 1;
 183       else
 184         high = mid;
 185     }
 186
 187   /* If we've run out of primes, abort.  */
 188   if (n > prime_tab[low].prime)
 189     {
 190       fprintf (stderr, "Cannot find prime bigger than %lu\n", n);
 191       abort ();
 192     }
 193
 194   return low;
 195 }
 196
 197 /* Returns a hash code for P.  */
 198
 199 static hashval_t
 200 hash_pointer (const PTR p)
 201 {
 202   return (hashval_t) ((intptr_t)p >> 3);
 203 }
 204
 205 /* Returns non-zero if P1 and P2 are equal.  */
 206
 207 static int
 208 eq_pointer (const PTR p1, const PTR p2)
 209 {
 210   return p1 == p2;
 211 }
 212
 213
 214 /* The parens around the function names in the next two definitions
 215    are essential in order to prevent macro expansions of the name.
 216    The bodies, however, are expanded as expected, so they are not
 217    recursive definitions.  */
 218
 219 /* Return the current size of given hash table.  */
 220
 221 #define htab_size(htab)  ((htab)->size)
 222
 223 size_t
 224 (htab_size) (htab_t htab)
 225 {
 226   return htab_size (htab);
 227 }
 228
 229 /* Return the current number of elements in given hash table. */
 230
 231 #define htab_elements(htab)  ((htab)->n_elements - (htab)->n_deleted)
 232
 233 size_t
 234 (htab_elements) (htab_t htab)
 235 {
 236   return htab_elements (htab);
 237 }
 238
 239 /* Return X % Y.  */
 240
 241 static inline hashval_t
 242 htab_mod_1 (hashval_t x, hashval_t y, hashval_t inv, int shift)
 243 {
 244   /* The multiplicative inverses computed above are for 32-bit types, and
 245      requires that we be able to compute a highpart multiply.  */
 246 #ifdef UNSIGNED_64BIT_TYPE
 247   __extension__ typedef UNSIGNED_64BIT_TYPE ull;
 248   if (sizeof (hashval_t) * CHAR_BIT <= 32)
 249     {
 250       hashval_t t1, t2, t3, t4, q, r;
 251
 252       t1 = ((ull)x * inv) >> 32;
 253       t2 = x - t1;
 254       t3 = t2 >> 1;
 255       t4 = t1 + t3;
 256       q  = t4 >> shift;
 257       r  = x - (q * y);
 258
 259       return r;
 260     }
 261 #endif
 262
 263   /* Otherwise just use the native division routines.  */
 264   return x % y;
 265 }
 266
 267 /* Compute the primary hash for HASH given HTAB's current size.  */
 268
 269 static inline hashval_t
 270 htab_mod (hashval_t hash, htab_t htab)
 271 {
 272   const struct prime_ent *p = &prime_tab[htab->size_prime_index];
 273   return htab_mod_1 (hash, p->prime, p->inv, p->shift);
 274 }
 275
 276 /* Compute the secondary hash for HASH given HTAB's current size.  */
 277
 278 static inline hashval_t
 279 htab_mod_m2 (hashval_t hash, htab_t htab)
 280 {
 281   const struct prime_ent *p = &prime_tab[htab->size_prime_index];
 282   return 1 + htab_mod_1 (hash, p->prime - 2, p->inv_m2, p->shift);
 283 }
 284
 285 /* This function creates table with length slightly longer than given
 286    source length.  Created hash table is initiated as empty (all the
 287    hash table entries are HTAB_EMPTY_ENTRY).  The function returns the
 288    created hash table, or NULL if memory allocation fails.  */
 289
 290 htab_t
 291 htab_create_alloc (size_t size, htab_hash hash_f, htab_eq eq_f,
 292                    htab_del del_f, htab_alloc alloc_f, htab_free free_f)
 293 {
 294   return htab_create_typed_alloc (size, hash_f, eq_f, del_f, alloc_f, alloc_f,
 295                                   free_f);
 296 }
 297
 298 /* As above, but uses the variants of ALLOC_F and FREE_F which accept
 299    an extra argument.  */
 300
 301 htab_t
 302 htab_create_alloc_ex (size_t size, htab_hash hash_f, htab_eq eq_f,
 303                       htab_del del_f, void *alloc_arg,
 304                       htab_alloc_with_arg alloc_f,
 305                       htab_free_with_arg free_f)
 306 {
 307   htab_t result;
 308   unsigned int size_prime_index;
 309
 310   size_prime_index = higher_prime_index (size);
 311   size = prime_tab[size_prime_index].prime;
 312
 313   result = (htab_t) (*alloc_f) (alloc_arg, 1, sizeof (struct htab));
 314   if (result == NULL)
 315     return NULL;
 316   result->entries = (PTR *) (*alloc_f) (alloc_arg, size, sizeof (PTR));
 317   if (result->entries == NULL)
 318     {
 319       if (free_f != NULL)
 320         (*free_f) (alloc_arg, result);
 321       return NULL;
 322     }
 323   result->size = size;
 324   result->size_prime_index = size_prime_index;
 325   result->hash_f = hash_f;
 326   result->eq_f = eq_f;
 327   result->del_f = del_f;
 328   result->alloc_arg = alloc_arg;
 329   result->alloc_with_arg_f = alloc_f;
 330   result->free_with_arg_f = free_f;
 331   return result;
 332 }
 333
 334 /*
 335
 336 @deftypefn Supplemental htab_t htab_create_typed_alloc (size_t @var{size},
 337 htab_hash @var{hash_f}, htab_eq @var{eq_f}, htab_del @var{del_f},
 338 htab_alloc @var{alloc_tab_f}, htab_alloc @var{alloc_f},
 339 htab_free @var{free_f})
 340
 341 This function creates a hash table that uses two different allocators
 342 @var{alloc_tab_f} and @var{alloc_f} to use for allocating the table itself
 343 and its entries respectively.  This is useful when variables of different
 344 types need to be allocated with different allocators.
 345
 346 The created hash table is slightly larger than @var{size} and it is
 347 initially empty (all the hash table entries are @code{HTAB_EMPTY_ENTRY}).
 348 The function returns the created hash table, or @code{NULL} if memory
 349 allocation fails.
 350
 351 @end deftypefn
 352
 353 */
 354
 355 htab_t
 356 htab_create_typed_alloc (size_t size, htab_hash hash_f, htab_eq eq_f,
 357                          htab_del del_f, htab_alloc alloc_tab_f,
 358                          htab_alloc alloc_f, htab_free free_f)
 359 {
 360   htab_t result;
 361   unsigned int size_prime_index;
 362
 363   size_prime_index = higher_prime_index (size);
 364   size = prime_tab[size_prime_index].prime;
 365
 366   result = (htab_t) (*alloc_tab_f) (1, sizeof (struct htab));
 367   if (result == NULL)
 368     return NULL;
 369   result->entries = (PTR *) (*alloc_f) (size, sizeof (PTR));
 370   if (result->entries == NULL)
 371     {
 372       if (free_f != NULL)
 373         (*free_f) (result);
 374       return NULL;
 375     }
 376   result->size = size;
 377   result->size_prime_index = size_prime_index;
 378   result->hash_f = hash_f;
 379   result->eq_f = eq_f;
 380   result->del_f = del_f;
 381   result->alloc_f = alloc_f;
 382   result->free_f = free_f;
 383   return result;
 384 }
 385
 386
 387 /* Update the function pointers and allocation parameter in the htab_t.  */
 388
 389 void
 390 htab_set_functions_ex (htab_t htab, htab_hash hash_f, htab_eq eq_f,
 391                        htab_del del_f, PTR alloc_arg,
 392                        htab_alloc_with_arg alloc_f, htab_free_with_arg free_f)
 393 {
 394   htab->hash_f = hash_f;
 395   htab->eq_f = eq_f;
 396   htab->del_f = del_f;
 397   htab->alloc_arg = alloc_arg;
 398   htab->alloc_with_arg_f = alloc_f;
 399   htab->free_with_arg_f = free_f;
 400 }
 401
 402 /* These functions exist solely for backward compatibility.  */
 403
 404 #undef htab_create
 405 htab_t
 406 htab_create (size_t size, htab_hash hash_f, htab_eq eq_f, htab_del del_f)
 407 {
 408   return htab_create_alloc (size, hash_f, eq_f, del_f, xcalloc, free);
 409 }
 410
 411 htab_t
 412 htab_try_create (size_t size, htab_hash hash_f, htab_eq eq_f, htab_del del_f)
 413 {
 414   return htab_create_alloc (size, hash_f, eq_f, del_f, calloc, free);
 415 }
 416
 417 /* This function frees all memory allocated for given hash table.
 418    Naturally the hash table must already exist. */
 419
 420 void
 421 htab_delete (htab_t htab)
 422 {
 423   size_t size = htab_size (htab);
 424   PTR *entries = htab->entries;
 425   int i;
 426
 427   if (htab->del_f)
 428     for (i = size - 1; i >= 0; i--)
 429       if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
 430         (*htab->del_f) (entries[i]);
 431
 432   if (htab->free_f != NULL)
 433     {
 434       (*htab->free_f) (entries);
 435       (*htab->free_f) (htab);
 436     }
 437   else if (htab->free_with_arg_f != NULL)
 438     {
 439       (*htab->free_with_arg_f) (htab->alloc_arg, entries);
 440       (*htab->free_with_arg_f) (htab->alloc_arg, htab);
 441     }
 442 }
 443
 444 /* This function clears all entries in the given hash table.  */
 445
 446 void
 447 htab_empty (htab_t htab)
 448 {
 449   size_t size = htab_size (htab);
 450   PTR *entries = htab->entries;
 451   int i;
 452
 453   if (htab->del_f)
 454     for (i = size - 1; i >= 0; i--)
 455       if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
 456         (*htab->del_f) (entries[i]);
 457
 458   /* Instead of clearing megabyte, downsize the table.  */
 459   if (size > 1024*1024 / sizeof (PTR))
 460     {
 461       int nindex = higher_prime_index (1024 / sizeof (PTR));
 462       int nsize = prime_tab[nindex].prime;
 463
 464       if (htab->free_f != NULL)
 465         (*htab->free_f) (htab->entries);
 466       else if (htab->free_with_arg_f != NULL)
 467         (*htab->free_with_arg_f) (htab->alloc_arg, htab->entries);
 468       if (htab->alloc_with_arg_f != NULL)
 469         htab->entries = (PTR *) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize,
 470                                                            sizeof (PTR *));
 471       else
 472         htab->entries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR *));
 473      htab->size = nsize;
 474      htab->size_prime_index = nindex;
 475     }
 476   else
 477     memset (entries, 0, size * sizeof (PTR));
 478   htab->n_deleted = 0;
 479   htab->n_elements = 0;
 480 }
 481
 482 /* Similar to htab_find_slot, but without several unwanted side effects:
 483     - Does not call htab->eq_f when it finds an existing entry.
 484     - Does not change the count of elements/searches/collisions in the
 485       hash table.
 486    This function also assumes there are no deleted entries in the table.
 487    HASH is the hash value for the element to be inserted.  */
 488
 489 static PTR *
 490 find_empty_slot_for_expand (htab_t htab, hashval_t hash)
 491 {
 492   hashval_t index = htab_mod (hash, htab);
 493   size_t size = htab_size (htab);
 494   PTR *slot = htab->entries + index;
 495   hashval_t hash2;
 496
 497   if (*slot == HTAB_EMPTY_ENTRY)
 498     return slot;
 499   else if (*slot == HTAB_DELETED_ENTRY)
 500     abort ();
 501
 502   hash2 = htab_mod_m2 (hash, htab);
 503   for (;;)
 504     {
 505       index += hash2;
 506       if (index >= size)
 507         index -= size;
 508
 509       slot = htab->entries + index;
 510       if (*slot == HTAB_EMPTY_ENTRY)
 511         return slot;
 512       else if (*slot == HTAB_DELETED_ENTRY)
 513         abort ();
 514     }
 515 }
 516
 517 /* The following function changes size of memory allocated for the
 518    entries and repeatedly inserts the table elements.  The occupancy
 519    of the table after the call will be about 50%.  Naturally the hash
 520    table must already exist.  Remember also that the place of the
 521    table entries is changed.  If memory allocation failures are allowed,
 522    this function will return zero, indicating that the table could not be
 523    expanded.  If all goes well, it will return a non-zero value.  */
 524
 525 static int
 526 htab_expand (htab_t htab)
 527 {
 528   PTR *oentries;
 529   PTR *olimit;
 530   PTR *p;
 531   PTR *nentries;
 532   size_t nsize, osize, elts;
 533   unsigned int oindex, nindex;
 534
 535   oentries = htab->entries;
 536   oindex = htab->size_prime_index;
 537   osize = htab->size;
 538   olimit = oentries + osize;
 539   elts = htab_elements (htab);
 540
 541   /* Resize only when table after removal of unused elements is either
 542      too full or too empty.  */
 543   if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
 544     {
 545       nindex = higher_prime_index (elts * 2);
 546       nsize = prime_tab[nindex].prime;
 547     }
 548   else
 549     {
 550       nindex = oindex;
 551       nsize = osize;
 552     }
 553
 554   if (htab->alloc_with_arg_f != NULL)
 555     nentries = (PTR *) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize,
 556                                                   sizeof (PTR *));
 557   else
 558     nentries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR *));
 559   if (nentries == NULL)
 560     return 0;
 561   htab->entries = nentries;
 562   htab->size = nsize;
 563   htab->size_prime_index = nindex;
 564   htab->n_elements -= htab->n_deleted;
 565   htab->n_deleted = 0;
 566
 567   p = oentries;
 568   do
 569     {
 570       PTR x = *p;
 571
 572       if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
 573         {
 574           PTR *q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
 575
 576           *q = x;
 577         }
 578
 579       p++;
 580     }
 581   while (p < olimit);
 582
 583   if (htab->free_f != NULL)
 584     (*htab->free_f) (oentries);
 585   else if (htab->free_with_arg_f != NULL)
 586     (*htab->free_with_arg_f) (htab->alloc_arg, oentries);
 587   return 1;
 588 }
 589
 590 /* This function searches for a hash table entry equal to the given
 591    element.  It cannot be used to insert or delete an element.  */
 592
 593 PTR
 594 htab_find_with_hash (htab_t htab, const PTR element, hashval_t hash)
 595 {
 596   hashval_t index, hash2;
 597   size_t size;
 598   PTR entry;
 599
 600   htab->searches++;
 601   size = htab_size (htab);
 602   index = htab_mod (hash, htab);
 603
 604   entry = htab->entries[index];
 605   if (entry == HTAB_EMPTY_ENTRY
 606       || (entry != HTAB_DELETED_ENTRY && (*htab->eq_f) (entry, element)))
 607     return entry;
 608
 609   hash2 = htab_mod_m2 (hash, htab);
 610   for (;;)
 611     {
 612       htab->collisions++;
 613       index += hash2;
 614       if (index >= size)
 615         index -= size;
 616
 617       entry = htab->entries[index];
 618       if (entry == HTAB_EMPTY_ENTRY
 619           || (entry != HTAB_DELETED_ENTRY && (*htab->eq_f) (entry, element)))
 620         return entry;
 621     }
 622 }
 623
 624 /* Like htab_find_slot_with_hash, but compute the hash value from the
 625    element.  */
 626
 627 PTR
 628 htab_find (htab_t htab, const PTR element)
 629 {
 630   return htab_find_with_hash (htab, element, (*htab->hash_f) (element));
 631 }
 632
 633 /* This function searches for a hash table slot containing an entry
 634    equal to the given element.  To delete an entry, call this with
 635    insert=NO_INSERT, then call htab_clear_slot on the slot returned
 636    (possibly after doing some checks).  To insert an entry, call this
 637    with insert=INSERT, then write the value you want into the returned
 638    slot.  When inserting an entry, NULL may be returned if memory
 639    allocation fails.  */
 640
 641 PTR *
 642 htab_find_slot_with_hash (htab_t htab, const PTR element,
 643                           hashval_t hash, enum insert_option insert)
 644 {
 645   PTR *first_deleted_slot;
 646   hashval_t index, hash2;
 647   size_t size;
 648   PTR entry;
 649
 650   size = htab_size (htab);
 651   if (insert == INSERT && size * 3 <= htab->n_elements * 4)
 652     {
 653       if (htab_expand (htab) == 0)
 654         return NULL;
 655       size = htab_size (htab);
 656     }
 657
 658   index = htab_mod (hash, htab);
 659
 660   htab->searches++;
 661   first_deleted_slot = NULL;
 662
 663   entry = htab->entries[index];
 664   if (entry == HTAB_EMPTY_ENTRY)
 665     goto empty_entry;
 666   else if (entry == HTAB_DELETED_ENTRY)
 667     first_deleted_slot = &htab->entries[index];
 668   else if ((*htab->eq_f) (entry, element))
 669     return &htab->entries[index];
 670
 671   hash2 = htab_mod_m2 (hash, htab);
 672   for (;;)
 673     {
 674       htab->collisions++;
 675       index += hash2;
 676       if (index >= size)
 677         index -= size;
 678
 679       entry = htab->entries[index];
 680       if (entry == HTAB_EMPTY_ENTRY)
 681         goto empty_entry;
 682       else if (entry == HTAB_DELETED_ENTRY)
 683         {
 684           if (!first_deleted_slot)
 685             first_deleted_slot = &htab->entries[index];
 686         }
 687       else if ((*htab->eq_f) (entry, element))
 688         return &htab->entries[index];
 689     }
 690
 691  empty_entry:
 692   if (insert == NO_INSERT)
 693     return NULL;
 694
 695   if (first_deleted_slot)
 696     {
 697       htab->n_deleted--;
 698       *first_deleted_slot = HTAB_EMPTY_ENTRY;
 699       return first_deleted_slot;
 700     }
 701
 702   htab->n_elements++;
 703   return &htab->entries[index];
 704 }
 705
 706 /* Like htab_find_slot_with_hash, but compute the hash value from the
 707    element.  */
 708
 709 PTR *
 710 htab_find_slot (htab_t htab, const PTR element, enum insert_option insert)
 711 {
 712   return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),
 713                                    insert);
 714 }
 715
 716 /* This function deletes an element with the given value from hash
 717    table (the hash is computed from the element).  If there is no matching
 718    element in the hash table, this function does nothing.  */
 719
 720 void
 721 htab_remove_elt (htab_t htab, PTR element)
 722 {
 723   htab_remove_elt_with_hash (htab, element, (*htab->hash_f) (element));
 724 }
 725
 726
 727 /* This function deletes an element with the given value from hash
 728    table.  If there is no matching element in the hash table, this
 729    function does nothing.  */
 730
 731 void
 732 htab_remove_elt_with_hash (htab_t htab, PTR element, hashval_t hash)
 733 {
 734   PTR *slot;
 735
 736   slot = htab_find_slot_with_hash (htab, element, hash, NO_INSERT);
 737   if (*slot == HTAB_EMPTY_ENTRY)
 738     return;
 739
 740   if (htab->del_f)
 741     (*htab->del_f) (*slot);
 742
 743   *slot = HTAB_DELETED_ENTRY;
 744   htab->n_deleted++;
 745 }
 746
 747 /* This function clears a specified slot in a hash table.  It is
 748    useful when you've already done the lookup and don't want to do it
 749    again.  */
 750
 751 void
 752 htab_clear_slot (htab_t htab, PTR *slot)
 753 {
 754   if (slot < htab->entries || slot >= htab->entries + htab_size (htab)
 755       || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)
 756     abort ();
 757
 758   if (htab->del_f)
 759     (*htab->del_f) (*slot);
 760
 761   *slot = HTAB_DELETED_ENTRY;
 762   htab->n_deleted++;
 763 }
 764
 765 /* This function scans over the entire hash table calling
 766    CALLBACK for each live entry.  If CALLBACK returns false,
 767    the iteration stops.  INFO is passed as CALLBACK's second
 768    argument.  */
 769
 770 void
 771 htab_traverse_noresize (htab_t htab, htab_trav callback, PTR info)
 772 {
 773   PTR *slot;
 774   PTR *limit;
 775
 776   slot = htab->entries;
 777   limit = slot + htab_size (htab);
 778
 779   do
 780     {
 781       PTR x = *slot;
 782
 783       if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
 784         if (!(*callback) (slot, info))
 785           break;
 786     }
 787   while (++slot < limit);
 788 }
 789
 790 /* Like htab_traverse_noresize, but does resize the table when it is
 791    too empty to improve effectivity of subsequent calls.  */
 792
 793 void
 794 htab_traverse (htab_t htab, htab_trav callback, PTR info)
 795 {
 796   size_t size = htab_size (htab);
 797   if (htab_elements (htab) * 8 < size && size > 32)
 798     htab_expand (htab);
 799
 800   htab_traverse_noresize (htab, callback, info);
 801 }
 802
 803 /* Return the fraction of fixed collisions during all work with given
 804    hash table. */
 805
 806 double
 807 htab_collisions (htab_t htab)
 808 {
 809   if (htab->searches == 0)
 810     return 0.0;
 811
 812   return (double) htab->collisions / (double) htab->searches;
 813 }
 814
 815 /* Hash P as a null-terminated string.
 816
 817    Copied from gcc/hashtable.c.  Zack had the following to say with respect
 818    to applicability, though note that unlike hashtable.c, this hash table
 819    implementation re-hashes rather than chain buckets.
 820
 821    http://gcc.gnu.org/ml/gcc-patches/2001-08/msg01021.html
 822    From: Zack Weinberg <zackw@panix.com>
 823    Date: Fri, 17 Aug 2001 02:15:56 -0400
 824
 825    I got it by extracting all the identifiers from all the source code
 826    I had lying around in mid-1999, and testing many recurrences of
 827    the form "H_n = H_{n-1} * K + c_n * L + M" where K, L, M were either
 828    prime numbers or the appropriate identity.  This was the best one.
 829    I don't remember exactly what constituted "best", except I was
 830    looking at bucket-length distributions mostly.
 831
 832    So it should be very good at hashing identifiers, but might not be
 833    as good at arbitrary strings.
 834
 835    I'll add that it thoroughly trounces the hash functions recommended
 836    for this use at http://burtleburtle.net/bob/hash/index.html, both
 837    on speed and bucket distribution.  I haven't tried it against the
 838    function they just started using for Perl's hashes.  */
 839
 840 hashval_t
 841 htab_hash_string (const PTR p)
 842 {
 843   const unsigned char *str = (const unsigned char *) p;
 844   hashval_t r = 0;
 845   unsigned char c;
 846
 847   while ((c = *str++) != 0)
 848     r = r * 67 + c - 113;
 849
 850   return r;
 851 }
 852
 853 /* DERIVED FROM:
 854 --------------------------------------------------------------------
 855 lookup2.c, by Bob Jenkins, December 1996, Public Domain.
 856 hash(), hash2(), hash3, and mix() are externally useful functions.
 857 Routines to test the hash are included if SELF_TEST is defined.
 858 You can use this free for any purpose.  It has no warranty.
 859 --------------------------------------------------------------------
 860 */
 861
 862 /*
 863 --------------------------------------------------------------------
 864 mix -- mix 3 32-bit values reversibly.
 865 For every delta with one or two bit set, and the deltas of all three
 866   high bits or all three low bits, whether the original value of a,b,c
 867   is almost all zero or is uniformly distributed,
 868 * If mix() is run forward or backward, at least 32 bits in a,b,c
 869   have at least 1/4 probability of changing.
 870 * If mix() is run forward, every bit of c will change between 1/3 and
 871   2/3 of the time.  (Well, 22/100 and 78/100 for some 2-bit deltas.)
 872 mix() was built out of 36 single-cycle latency instructions in a
 873   structure that could supported 2x parallelism, like so:
 874       a -= b;
 875       a -= c; x = (c>>13);
 876       b -= c; a ^= x;
 877       b -= a; x = (a<<8);
 878       c -= a; b ^= x;
 879       c -= b; x = (b>>13);
 880       ...
 881   Unfortunately, superscalar Pentiums and Sparcs can't take advantage
 882   of that parallelism.  They've also turned some of those single-cycle
 883   latency instructions into multi-cycle latency instructions.  Still,
 884   this is the fastest good hash I could find.  There were about 2^^68
 885   to choose from.  I only looked at a billion or so.
 886 --------------------------------------------------------------------
 887 */
 888 /* same, but slower, works on systems that might have 8 byte hashval_t's */
 889 #define mix(a,b,c) \
 890 { \
 891   a -= b; a -= c; a ^= (c>>13); \
 892   b -= c; b -= a; b ^= (a<< 8); \
 893   c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
 894   a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
 895   b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
 896   c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
 897   a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
 898   b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
 899   c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
 900 }
 901
 902 /*
 903 --------------------------------------------------------------------
 904 hash() -- hash a variable-length key into a 32-bit value
 905   k     : the key (the unaligned variable-length array of bytes)
 906   len   : the length of the key, counting by bytes
 907   level : can be any 4-byte value
 908 Returns a 32-bit value.  Every bit of the key affects every bit of
 909 the return value.  Every 1-bit and 2-bit delta achieves avalanche.
 910 About 36+6len instructions.
 911
 912 The best hash table sizes are powers of 2.  There is no need to do
 913 mod a prime (mod is sooo slow!).  If you need less than 32 bits,
 914 use a bitmask.  For example, if you need only 10 bits, do
 915   h = (h & hashmask(10));
 916 In which case, the hash table should have hashsize(10) elements.
 917
 918 If you are hashing n strings (ub1 **)k, do it like this:
 919   for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h);
 920
 921 By Bob Jenkins, 1996.  bob_jenkins@burtleburtle.net.  You may use this
 922 code any way you wish, private, educational, or commercial.  It's free.
 923
 924 See http://burtleburtle.net/bob/hash/evahash.html
 925 Use for hash table lookup, or anything where one collision in 2^32 is
 926 acceptable.  Do NOT use for cryptographic purposes.
 927 --------------------------------------------------------------------
 928 */
 929
 930 hashval_t
 931 iterative_hash (const PTR k_in /* the key */,
 932                 register size_t  length /* the length of the key */,
 933                 register hashval_t initval /* the previous hash, or
 934                                               an arbitrary value */)
 935 {
 936   register const unsigned char *k = (const unsigned char *)k_in;
 937   register hashval_t a,b,c,len;
 938
 939   /* Set up the internal state */
 940   len = length;
 941   a = b = 0x9e3779b9;  /* the golden ratio; an arbitrary value */
 942   c = initval;           /* the previous hash value */
 943
 944   /*---------------------------------------- handle most of the key */
 945 #ifndef WORDS_BIGENDIAN
 946   /* On a little-endian machine, if the data is 4-byte aligned we can hash
 947      by word for better speed.  This gives nondeterministic results on
 948      big-endian machines.  */
 949   if (sizeof (hashval_t) == 4 && (((size_t)k)&3) == 0)
 950     while (len >= 12)    /* aligned */
 951       {
 952         a += *(hashval_t *)(k+0);
 953         b += *(hashval_t *)(k+4);
 954         c += *(hashval_t *)(k+8);
 955         mix(a,b,c);
 956         k += 12; len -= 12;
 957       }
 958   else /* unaligned */
 959 #endif
 960     while (len >= 12)
 961       {
 962         a += (k[0] +((hashval_t)k[1]<<8) +((hashval_t)k[2]<<16) +((hashval_t)k[3]<<24));
 963         b += (k[4] +((hashval_t)k[5]<<8) +((hashval_t)k[6]<<16) +((hashval_t)k[7]<<24));
 964         c += (k[8] +((hashval_t)k[9]<<8) +((hashval_t)k[10]<<16)+((hashval_t)k[11]<<24));
 965         mix(a,b,c);
 966         k += 12; len -= 12;
 967       }
 968
 969   /*------------------------------------- handle the last 11 bytes */
 970   c += length;
 971   switch(len)              /* all the case statements fall through */
 972     {
 973     case 11: c+=((hashval_t)k[10]<<24);
 974     case 10: c+=((hashval_t)k[9]<<16);
 975     case 9 : c+=((hashval_t)k[8]<<8);
 976       /* the first byte of c is reserved for the length */
 977     case 8 : b+=((hashval_t)k[7]<<24);
 978     case 7 : b+=((hashval_t)k[6]<<16);
 979     case 6 : b+=((hashval_t)k[5]<<8);
 980     case 5 : b+=k[4];
 981     case 4 : a+=((hashval_t)k[3]<<24);
 982     case 3 : a+=((hashval_t)k[2]<<16);
 983     case 2 : a+=((hashval_t)k[1]<<8);
 984     case 1 : a+=k[0];
 985       /* case 0: nothing left to add */
 986     }
 987   mix(a,b,c);
 988   /*-------------------------------------------- report the result */
 989   return c;
 990 }