libiberty/hashtab.c

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