contrib/gdb-7/libiberty/hashtab.c

   1 /* An expandable hash tables datatype.
   2    Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2009
   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   htab_t result;
 295   unsigned int size_prime_index;
 296
 297   size_prime_index = higher_prime_index (size);
 298   size = prime_tab[size_prime_index].prime;
 299
 300   result = (htab_t) (*alloc_f) (1, sizeof (struct htab));
 301   if (result == NULL)
 302     return NULL;
 303   result->entries = (PTR *) (*alloc_f) (size, sizeof (PTR));
 304   if (result->entries == NULL)
 305     {
 306       if (free_f != NULL)
 307         (*free_f) (result);
 308       return NULL;
 309     }
 310   result->size = size;
 311   result->size_prime_index = size_prime_index;
 312   result->hash_f = hash_f;
 313   result->eq_f = eq_f;
 314   result->del_f = del_f;
 315   result->alloc_f = alloc_f;
 316   result->free_f = free_f;
 317   return result;
 318 }
 319
 320 /* As above, but use the variants of alloc_f and free_f which accept
 321    an extra argument.  */
 322
 323 htab_t
 324 htab_create_alloc_ex (size_t size, htab_hash hash_f, htab_eq eq_f,
 325                       htab_del del_f, void *alloc_arg,
 326                       htab_alloc_with_arg alloc_f,
 327                       htab_free_with_arg free_f)
 328 {
 329   htab_t result;
 330   unsigned int size_prime_index;
 331
 332   size_prime_index = higher_prime_index (size);
 333   size = prime_tab[size_prime_index].prime;
 334
 335   result = (htab_t) (*alloc_f) (alloc_arg, 1, sizeof (struct htab));
 336   if (result == NULL)
 337     return NULL;
 338   result->entries = (PTR *) (*alloc_f) (alloc_arg, size, sizeof (PTR));
 339   if (result->entries == NULL)
 340     {
 341       if (free_f != NULL)
 342         (*free_f) (alloc_arg, result);
 343       return NULL;
 344     }
 345   result->size = size;
 346   result->size_prime_index = size_prime_index;
 347   result->hash_f = hash_f;
 348   result->eq_f = eq_f;
 349   result->del_f = del_f;
 350   result->alloc_arg = alloc_arg;
 351   result->alloc_with_arg_f = alloc_f;
 352   result->free_with_arg_f = free_f;
 353   return result;
 354 }
 355
 356 /* Update the function pointers and allocation parameter in the htab_t.  */
 357
 358 void
 359 htab_set_functions_ex (htab_t htab, htab_hash hash_f, htab_eq eq_f,
 360                        htab_del del_f, PTR alloc_arg,
 361                        htab_alloc_with_arg alloc_f, htab_free_with_arg free_f)
 362 {
 363   htab->hash_f = hash_f;
 364   htab->eq_f = eq_f;
 365   htab->del_f = del_f;
 366   htab->alloc_arg = alloc_arg;
 367   htab->alloc_with_arg_f = alloc_f;
 368   htab->free_with_arg_f = free_f;
 369 }
 370
 371 /* These functions exist solely for backward compatibility.  */
 372
 373 #undef htab_create
 374 htab_t
 375 htab_create (size_t size, htab_hash hash_f, htab_eq eq_f, htab_del del_f)
 376 {
 377   return htab_create_alloc (size, hash_f, eq_f, del_f, xcalloc, free);
 378 }
 379
 380 htab_t
 381 htab_try_create (size_t size, htab_hash hash_f, htab_eq eq_f, htab_del del_f)
 382 {
 383   return htab_create_alloc (size, hash_f, eq_f, del_f, calloc, free);
 384 }
 385
 386 /* This function frees all memory allocated for given hash table.
 387    Naturally the hash table must already exist. */
 388
 389 void
 390 htab_delete (htab_t htab)
 391 {
 392   size_t size = htab_size (htab);
 393   PTR *entries = htab->entries;
 394   int i;
 395
 396   if (htab->del_f)
 397     for (i = size - 1; i >= 0; i--)
 398       if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
 399         (*htab->del_f) (entries[i]);
 400
 401   if (htab->free_f != NULL)
 402     {
 403       (*htab->free_f) (entries);
 404       (*htab->free_f) (htab);
 405     }
 406   else if (htab->free_with_arg_f != NULL)
 407     {
 408       (*htab->free_with_arg_f) (htab->alloc_arg, entries);
 409       (*htab->free_with_arg_f) (htab->alloc_arg, htab);
 410     }
 411 }
 412
 413 /* This function clears all entries in the given hash table.  */
 414
 415 void
 416 htab_empty (htab_t htab)
 417 {
 418   size_t size = htab_size (htab);
 419   PTR *entries = htab->entries;
 420   int i;
 421
 422   if (htab->del_f)
 423     for (i = size - 1; i >= 0; i--)
 424       if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
 425         (*htab->del_f) (entries[i]);
 426
 427   /* Instead of clearing megabyte, downsize the table.  */
 428   if (size > 1024*1024 / sizeof (PTR))
 429     {
 430       int nindex = higher_prime_index (1024 / sizeof (PTR));
 431       int nsize = prime_tab[nindex].prime;
 432
 433       if (htab->free_f != NULL)
 434         (*htab->free_f) (htab->entries);
 435       else if (htab->free_with_arg_f != NULL)
 436         (*htab->free_with_arg_f) (htab->alloc_arg, htab->entries);
 437       if (htab->alloc_with_arg_f != NULL)
 438         htab->entries = (PTR *) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize,
 439                                                            sizeof (PTR *));
 440       else
 441         htab->entries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR *));
 442      htab->size = nsize;
 443      htab->size_prime_index = nindex;
 444     }
 445   else
 446     memset (entries, 0, size * sizeof (PTR));
 447   htab->n_deleted = 0;
 448   htab->n_elements = 0;
 449 }
 450
 451 /* Similar to htab_find_slot, but without several unwanted side effects:
 452     - Does not call htab->eq_f when it finds an existing entry.
 453     - Does not change the count of elements/searches/collisions in the
 454       hash table.
 455    This function also assumes there are no deleted entries in the table.
 456    HASH is the hash value for the element to be inserted.  */
 457
 458 static PTR *
 459 find_empty_slot_for_expand (htab_t htab, hashval_t hash)
 460 {
 461   hashval_t index = htab_mod (hash, htab);
 462   size_t size = htab_size (htab);
 463   PTR *slot = htab->entries + index;
 464   hashval_t hash2;
 465
 466   if (*slot == HTAB_EMPTY_ENTRY)
 467     return slot;
 468   else if (*slot == HTAB_DELETED_ENTRY)
 469     abort ();
 470
 471   hash2 = htab_mod_m2 (hash, htab);
 472   for (;;)
 473     {
 474       index += hash2;
 475       if (index >= size)
 476         index -= size;
 477
 478       slot = htab->entries + index;
 479       if (*slot == HTAB_EMPTY_ENTRY)
 480         return slot;
 481       else if (*slot == HTAB_DELETED_ENTRY)
 482         abort ();
 483     }
 484 }
 485
 486 /* The following function changes size of memory allocated for the
 487    entries and repeatedly inserts the table elements.  The occupancy
 488    of the table after the call will be about 50%.  Naturally the hash
 489    table must already exist.  Remember also that the place of the
 490    table entries is changed.  If memory allocation failures are allowed,
 491    this function will return zero, indicating that the table could not be
 492    expanded.  If all goes well, it will return a non-zero value.  */
 493
 494 static int
 495 htab_expand (htab_t htab)
 496 {
 497   PTR *oentries;
 498   PTR *olimit;
 499   PTR *p;
 500   PTR *nentries;
 501   size_t nsize, osize, elts;
 502   unsigned int oindex, nindex;
 503
 504   oentries = htab->entries;
 505   oindex = htab->size_prime_index;
 506   osize = htab->size;
 507   olimit = oentries + osize;
 508   elts = htab_elements (htab);
 509
 510   /* Resize only when table after removal of unused elements is either
 511      too full or too empty.  */
 512   if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
 513     {
 514       nindex = higher_prime_index (elts * 2);
 515       nsize = prime_tab[nindex].prime;
 516     }
 517   else
 518     {
 519       nindex = oindex;
 520       nsize = osize;
 521     }
 522
 523   if (htab->alloc_with_arg_f != NULL)
 524     nentries = (PTR *) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize,
 525                                                   sizeof (PTR *));
 526   else
 527     nentries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR *));
 528   if (nentries == NULL)
 529     return 0;
 530   htab->entries = nentries;
 531   htab->size = nsize;
 532   htab->size_prime_index = nindex;
 533   htab->n_elements -= htab->n_deleted;
 534   htab->n_deleted = 0;
 535
 536   p = oentries;
 537   do
 538     {
 539       PTR x = *p;
 540
 541       if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
 542         {
 543           PTR *q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
 544
 545           *q = x;
 546         }
 547
 548       p++;
 549     }
 550   while (p < olimit);
 551
 552   if (htab->free_f != NULL)
 553     (*htab->free_f) (oentries);
 554   else if (htab->free_with_arg_f != NULL)
 555     (*htab->free_with_arg_f) (htab->alloc_arg, oentries);
 556   return 1;
 557 }
 558
 559 /* This function searches for a hash table entry equal to the given
 560    element.  It cannot be used to insert or delete an element.  */
 561
 562 PTR
 563 htab_find_with_hash (htab_t htab, const PTR element, hashval_t hash)
 564 {
 565   hashval_t index, hash2;
 566   size_t size;
 567   PTR entry;
 568
 569   htab->searches++;
 570   size = htab_size (htab);
 571   index = htab_mod (hash, htab);
 572
 573   entry = htab->entries[index];
 574   if (entry == HTAB_EMPTY_ENTRY
 575       || (entry != HTAB_DELETED_ENTRY && (*htab->eq_f) (entry, element)))
 576     return entry;
 577
 578   hash2 = htab_mod_m2 (hash, htab);
 579   for (;;)
 580     {
 581       htab->collisions++;
 582       index += hash2;
 583       if (index >= size)
 584         index -= size;
 585
 586       entry = htab->entries[index];
 587       if (entry == HTAB_EMPTY_ENTRY
 588           || (entry != HTAB_DELETED_ENTRY && (*htab->eq_f) (entry, element)))
 589         return entry;
 590     }
 591 }
 592
 593 /* Like htab_find_slot_with_hash, but compute the hash value from the
 594    element.  */
 595
 596 PTR
 597 htab_find (htab_t htab, const PTR element)
 598 {
 599   return htab_find_with_hash (htab, element, (*htab->hash_f) (element));
 600 }
 601
 602 /* This function searches for a hash table slot containing an entry
 603    equal to the given element.  To delete an entry, call this with
 604    insert=NO_INSERT, then call htab_clear_slot on the slot returned
 605    (possibly after doing some checks).  To insert an entry, call this
 606    with insert=INSERT, then write the value you want into the returned
 607    slot.  When inserting an entry, NULL may be returned if memory
 608    allocation fails.  */
 609
 610 PTR *
 611 htab_find_slot_with_hash (htab_t htab, const PTR element,
 612                           hashval_t hash, enum insert_option insert)
 613 {
 614   PTR *first_deleted_slot;
 615   hashval_t index, hash2;
 616   size_t size;
 617   PTR entry;
 618
 619   size = htab_size (htab);
 620   if (insert == INSERT && size * 3 <= htab->n_elements * 4)
 621     {
 622       if (htab_expand (htab) == 0)
 623         return NULL;
 624       size = htab_size (htab);
 625     }
 626
 627   index = htab_mod (hash, htab);
 628
 629   htab->searches++;
 630   first_deleted_slot = NULL;
 631
 632   entry = htab->entries[index];
 633   if (entry == HTAB_EMPTY_ENTRY)
 634     goto empty_entry;
 635   else if (entry == HTAB_DELETED_ENTRY)
 636     first_deleted_slot = &htab->entries[index];
 637   else if ((*htab->eq_f) (entry, element))
 638     return &htab->entries[index];
 639
 640   hash2 = htab_mod_m2 (hash, htab);
 641   for (;;)
 642     {
 643       htab->collisions++;
 644       index += hash2;
 645       if (index >= size)
 646         index -= size;
 647
 648       entry = htab->entries[index];
 649       if (entry == HTAB_EMPTY_ENTRY)
 650         goto empty_entry;
 651       else if (entry == HTAB_DELETED_ENTRY)
 652         {
 653           if (!first_deleted_slot)
 654             first_deleted_slot = &htab->entries[index];
 655         }
 656       else if ((*htab->eq_f) (entry, element))
 657         return &htab->entries[index];
 658     }
 659
 660  empty_entry:
 661   if (insert == NO_INSERT)
 662     return NULL;
 663
 664   if (first_deleted_slot)
 665     {
 666       htab->n_deleted--;
 667       *first_deleted_slot = HTAB_EMPTY_ENTRY;
 668       return first_deleted_slot;
 669     }
 670
 671   htab->n_elements++;
 672   return &htab->entries[index];
 673 }
 674
 675 /* Like htab_find_slot_with_hash, but compute the hash value from the
 676    element.  */
 677
 678 PTR *
 679 htab_find_slot (htab_t htab, const PTR element, enum insert_option insert)
 680 {
 681   return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),
 682                                    insert);
 683 }
 684
 685 /* This function deletes an element with the given value from hash
 686    table (the hash is computed from the element).  If there is no matching
 687    element in the hash table, this function does nothing.  */
 688
 689 void
 690 htab_remove_elt (htab_t htab, PTR element)
 691 {
 692   htab_remove_elt_with_hash (htab, element, (*htab->hash_f) (element));
 693 }
 694
 695
 696 /* This function deletes an element with the given value from hash
 697    table.  If there is no matching element in the hash table, this
 698    function does nothing.  */
 699
 700 void
 701 htab_remove_elt_with_hash (htab_t htab, PTR element, hashval_t hash)
 702 {
 703   PTR *slot;
 704
 705   slot = htab_find_slot_with_hash (htab, element, hash, NO_INSERT);
 706   if (*slot == HTAB_EMPTY_ENTRY)
 707     return;
 708
 709   if (htab->del_f)
 710     (*htab->del_f) (*slot);
 711
 712   *slot = HTAB_DELETED_ENTRY;
 713   htab->n_deleted++;
 714 }
 715
 716 /* This function clears a specified slot in a hash table.  It is
 717    useful when you've already done the lookup and don't want to do it
 718    again.  */
 719
 720 void
 721 htab_clear_slot (htab_t htab, PTR *slot)
 722 {
 723   if (slot < htab->entries || slot >= htab->entries + htab_size (htab)
 724       || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)
 725     abort ();
 726
 727   if (htab->del_f)
 728     (*htab->del_f) (*slot);
 729
 730   *slot = HTAB_DELETED_ENTRY;
 731   htab->n_deleted++;
 732 }
 733
 734 /* This function scans over the entire hash table calling
 735    CALLBACK for each live entry.  If CALLBACK returns false,
 736    the iteration stops.  INFO is passed as CALLBACK's second
 737    argument.  */
 738
 739 void
 740 htab_traverse_noresize (htab_t htab, htab_trav callback, PTR info)
 741 {
 742   PTR *slot;
 743   PTR *limit;
 744
 745   slot = htab->entries;
 746   limit = slot + htab_size (htab);
 747
 748   do
 749     {
 750       PTR x = *slot;
 751
 752       if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
 753         if (!(*callback) (slot, info))
 754           break;
 755     }
 756   while (++slot < limit);
 757 }
 758
 759 /* Like htab_traverse_noresize, but does resize the table when it is
 760    too empty to improve effectivity of subsequent calls.  */
 761
 762 void
 763 htab_traverse (htab_t htab, htab_trav callback, PTR info)
 764 {
 765   size_t size = htab_size (htab);
 766   if (htab_elements (htab) * 8 < size && size > 32)
 767     htab_expand (htab);
 768
 769   htab_traverse_noresize (htab, callback, info);
 770 }
 771
 772 /* Return the fraction of fixed collisions during all work with given
 773    hash table. */
 774
 775 double
 776 htab_collisions (htab_t htab)
 777 {
 778   if (htab->searches == 0)
 779     return 0.0;
 780
 781   return (double) htab->collisions / (double) htab->searches;
 782 }
 783
 784 /* Hash P as a null-terminated string.
 785
 786    Copied from gcc/hashtable.c.  Zack had the following to say with respect
 787    to applicability, though note that unlike hashtable.c, this hash table
 788    implementation re-hashes rather than chain buckets.
 789
 790    http://gcc.gnu.org/ml/gcc-patches/2001-08/msg01021.html
 791    From: Zack Weinberg <zackw@panix.com>
 792    Date: Fri, 17 Aug 2001 02:15:56 -0400
 793
 794    I got it by extracting all the identifiers from all the source code
 795    I had lying around in mid-1999, and testing many recurrences of
 796    the form "H_n = H_{n-1} * K + c_n * L + M" where K, L, M were either
 797    prime numbers or the appropriate identity.  This was the best one.
 798    I don't remember exactly what constituted "best", except I was
 799    looking at bucket-length distributions mostly.
 800
 801    So it should be very good at hashing identifiers, but might not be
 802    as good at arbitrary strings.
 803
 804    I'll add that it thoroughly trounces the hash functions recommended
 805    for this use at http://burtleburtle.net/bob/hash/index.html, both
 806    on speed and bucket distribution.  I haven't tried it against the
 807    function they just started using for Perl's hashes.  */
 808
 809 hashval_t
 810 htab_hash_string (const PTR p)
 811 {
 812   const unsigned char *str = (const unsigned char *) p;
 813   hashval_t r = 0;
 814   unsigned char c;
 815
 816   while ((c = *str++) != 0)
 817     r = r * 67 + c - 113;
 818
 819   return r;
 820 }
 821
 822 /* DERIVED FROM:
 823 --------------------------------------------------------------------
 824 lookup2.c, by Bob Jenkins, December 1996, Public Domain.
 825 hash(), hash2(), hash3, and mix() are externally useful functions.
 826 Routines to test the hash are included if SELF_TEST is defined.
 827 You can use this free for any purpose.  It has no warranty.
 828 --------------------------------------------------------------------
 829 */
 830
 831 /*
 832 --------------------------------------------------------------------
 833 mix -- mix 3 32-bit values reversibly.
 834 For every delta with one or two bit set, and the deltas of all three
 835   high bits or all three low bits, whether the original value of a,b,c
 836   is almost all zero or is uniformly distributed,
 837 * If mix() is run forward or backward, at least 32 bits in a,b,c
 838   have at least 1/4 probability of changing.
 839 * If mix() is run forward, every bit of c will change between 1/3 and
 840   2/3 of the time.  (Well, 22/100 and 78/100 for some 2-bit deltas.)
 841 mix() was built out of 36 single-cycle latency instructions in a
 842   structure that could supported 2x parallelism, like so:
 843       a -= b;
 844       a -= c; x = (c>>13);
 845       b -= c; a ^= x;
 846       b -= a; x = (a<<8);
 847       c -= a; b ^= x;
 848       c -= b; x = (b>>13);
 849       ...
 850   Unfortunately, superscalar Pentiums and Sparcs can't take advantage
 851   of that parallelism.  They've also turned some of those single-cycle
 852   latency instructions into multi-cycle latency instructions.  Still,
 853   this is the fastest good hash I could find.  There were about 2^^68
 854   to choose from.  I only looked at a billion or so.
 855 --------------------------------------------------------------------
 856 */
 857 /* same, but slower, works on systems that might have 8 byte hashval_t's */
 858 #define mix(a,b,c) \
 859 { \
 860   a -= b; a -= c; a ^= (c>>13); \
 861   b -= c; b -= a; b ^= (a<< 8); \
 862   c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
 863   a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
 864   b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
 865   c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
 866   a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
 867   b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
 868   c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
 869 }
 870
 871 /*
 872 --------------------------------------------------------------------
 873 hash() -- hash a variable-length key into a 32-bit value
 874   k     : the key (the unaligned variable-length array of bytes)
 875   len   : the length of the key, counting by bytes
 876   level : can be any 4-byte value
 877 Returns a 32-bit value.  Every bit of the key affects every bit of
 878 the return value.  Every 1-bit and 2-bit delta achieves avalanche.
 879 About 36+6len instructions.
 880
 881 The best hash table sizes are powers of 2.  There is no need to do
 882 mod a prime (mod is sooo slow!).  If you need less than 32 bits,
 883 use a bitmask.  For example, if you need only 10 bits, do
 884   h = (h & hashmask(10));
 885 In which case, the hash table should have hashsize(10) elements.
 886
 887 If you are hashing n strings (ub1 **)k, do it like this:
 888   for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h);
 889
 890 By Bob Jenkins, 1996.  bob_jenkins@burtleburtle.net.  You may use this
 891 code any way you wish, private, educational, or commercial.  It's free.
 892
 893 See http://burtleburtle.net/bob/hash/evahash.html
 894 Use for hash table lookup, or anything where one collision in 2^32 is
 895 acceptable.  Do NOT use for cryptographic purposes.
 896 --------------------------------------------------------------------
 897 */
 898
 899 hashval_t
 900 iterative_hash (const PTR k_in /* the key */,
 901                 register size_t  length /* the length of the key */,
 902                 register hashval_t initval /* the previous hash, or
 903                                               an arbitrary value */)
 904 {
 905   register const unsigned char *k = (const unsigned char *)k_in;
 906   register hashval_t a,b,c,len;
 907
 908   /* Set up the internal state */
 909   len = length;
 910   a = b = 0x9e3779b9;  /* the golden ratio; an arbitrary value */
 911   c = initval;           /* the previous hash value */
 912
 913   /*---------------------------------------- handle most of the key */
 914 #ifndef WORDS_BIGENDIAN
 915   /* On a little-endian machine, if the data is 4-byte aligned we can hash
 916      by word for better speed.  This gives nondeterministic results on
 917      big-endian machines.  */
 918   if (sizeof (hashval_t) == 4 && (((size_t)k)&3) == 0)
 919     while (len >= 12)    /* aligned */
 920       {
 921         a += *(hashval_t *)(k+0);
 922         b += *(hashval_t *)(k+4);
 923         c += *(hashval_t *)(k+8);
 924         mix(a,b,c);
 925         k += 12; len -= 12;
 926       }
 927   else /* unaligned */
 928 #endif
 929     while (len >= 12)
 930       {
 931         a += (k[0] +((hashval_t)k[1]<<8) +((hashval_t)k[2]<<16) +((hashval_t)k[3]<<24));
 932         b += (k[4] +((hashval_t)k[5]<<8) +((hashval_t)k[6]<<16) +((hashval_t)k[7]<<24));
 933         c += (k[8] +((hashval_t)k[9]<<8) +((hashval_t)k[10]<<16)+((hashval_t)k[11]<<24));
 934         mix(a,b,c);
 935         k += 12; len -= 12;
 936       }
 937
 938   /*------------------------------------- handle the last 11 bytes */
 939   c += length;
 940   switch(len)              /* all the case statements fall through */
 941     {
 942     case 11: c+=((hashval_t)k[10]<<24);
 943     case 10: c+=((hashval_t)k[9]<<16);
 944     case 9 : c+=((hashval_t)k[8]<<8);
 945       /* the first byte of c is reserved for the length */
 946     case 8 : b+=((hashval_t)k[7]<<24);
 947     case 7 : b+=((hashval_t)k[6]<<16);
 948     case 6 : b+=((hashval_t)k[5]<<8);
 949     case 5 : b+=k[4];
 950     case 4 : a+=((hashval_t)k[3]<<24);
 951     case 3 : a+=((hashval_t)k[2]<<16);
 952     case 2 : a+=((hashval_t)k[1]<<8);
 953     case 1 : a+=k[0];
 954       /* case 0: nothing left to add */
 955     }
 956   mix(a,b,c);
 957   /*-------------------------------------------- report the result */
 958   return c;
 959 }