libiberty/hashtab.c

   1 /* An expandable hash tables datatype.
   2    Copyright (C) 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
   3    Contributed by Vladimir Makarov (vmakarov@cygnus.com).
   4
   5 This file is part of the libiberty library.
   6 Libiberty is free software; you can redistribute it and/or
   7 modify it under the terms of the GNU Library General Public
   8 License as published by the Free Software Foundation; either
   9 version 2 of the License, or (at your option) any later version.
  10
  11 Libiberty is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 Library General Public License for more details.
  15
  16 You should have received a copy of the GNU Library General Public
  17 License along with libiberty; see the file COPYING.LIB.  If
  18 not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, USA.  */
  20
  21 /* This package implements basic hash table functionality.  It is possible
  22    to search for an entry, create an entry and destroy an entry.
  23
  24    Elements in the table are generic pointers.
  25
  26    The size of the table is not fixed; if the occupancy of the table
  27    grows too high the hash table will be expanded.
  28
  29    The abstract data implementation is based on generalized Algorithm D
  30    from Knuth's book "The art of computer programming".  Hash table is
  31    expanded by creation of new hash table and transferring elements from
  32    the old table to the new table. */
  33
  34 #ifdef HAVE_CONFIG_H
  35 #include "config.h"
  36 #endif
  37
  38 #include <sys/types.h>
  39
  40 #ifdef HAVE_STDLIB_H
  41 #include <stdlib.h>
  42 #endif
  43
  44 #ifdef HAVE_STRING_H
  45 #include <string.h>
  46 #endif
  47
  48 #include <stdio.h>
  49
  50 #include "libiberty.h"
  51 #include "hashtab.h"
  52
  53 /* This macro defines reserved value for empty table entry. */
  54
  55 #define EMPTY_ENTRY    ((PTR) 0)
  56
  57 /* This macro defines reserved value for table entry which contained
  58    a deleted element. */
  59
  60 #define DELETED_ENTRY  ((PTR) 1)
  61
  62 static unsigned long higher_prime_number PARAMS ((unsigned long));
  63 static hashval_t hash_pointer PARAMS ((const void *));
  64 static int eq_pointer PARAMS ((const void *, const void *));
  65 static int htab_expand PARAMS ((htab_t));
  66 static PTR *find_empty_slot_for_expand  PARAMS ((htab_t, hashval_t));
  67
  68 /* At some point, we could make these be NULL, and modify the
  69    hash-table routines to handle NULL specially; that would avoid
  70    function-call overhead for the common case of hashing pointers.  */
  71 htab_hash htab_hash_pointer = hash_pointer;
  72 htab_eq htab_eq_pointer = eq_pointer;
  73
  74 /* The following function returns a nearest prime number which is
  75    greater than N, and near a power of two. */
  76
  77 static unsigned long
  78 higher_prime_number (n)
  79      unsigned long n;
  80 {
  81   /* These are primes that are near, but slightly smaller than, a
  82      power of two.  */
  83   static const unsigned long primes[] = {
  84     (unsigned long) 7,
  85     (unsigned long) 13,
  86     (unsigned long) 31,
  87     (unsigned long) 61,
  88     (unsigned long) 127,
  89     (unsigned long) 251,
  90     (unsigned long) 509,
  91     (unsigned long) 1021,
  92     (unsigned long) 2039,
  93     (unsigned long) 4093,
  94     (unsigned long) 8191,
  95     (unsigned long) 16381,
  96     (unsigned long) 32749,
  97     (unsigned long) 65521,
  98     (unsigned long) 131071,
  99     (unsigned long) 262139,
 100     (unsigned long) 524287,
 101     (unsigned long) 1048573,
 102     (unsigned long) 2097143,
 103     (unsigned long) 4194301,
 104     (unsigned long) 8388593,
 105     (unsigned long) 16777213,
 106     (unsigned long) 33554393,
 107     (unsigned long) 67108859,
 108     (unsigned long) 134217689,
 109     (unsigned long) 268435399,
 110     (unsigned long) 536870909,
 111     (unsigned long) 1073741789,
 112     (unsigned long) 2147483647,
 113                                         /* 4294967291L */
 114     ((unsigned long) 2147483647) + ((unsigned long) 2147483644),
 115   };
 116
 117   const unsigned long *low = &primes[0];
 118   const unsigned long *high = &primes[sizeof(primes) / sizeof(primes[0])];
 119
 120   while (low != high)
 121     {
 122       const unsigned long *mid = low + (high - low) / 2;
 123       if (n > *mid)
 124         low = mid + 1;
 125       else
 126         high = mid;
 127     }
 128
 129   /* If we've run out of primes, abort.  */
 130   if (n > *low)
 131     {
 132       fprintf (stderr, "Cannot find prime bigger than %lu\n", n);
 133       abort ();
 134     }
 135
 136   return *low;
 137 }
 138
 139 /* Returns a hash code for P.  */
 140
 141 static hashval_t
 142 hash_pointer (p)
 143      const PTR p;
 144 {
 145   return (hashval_t) ((long)p >> 3);
 146 }
 147
 148 /* Returns non-zero if P1 and P2 are equal.  */
 149
 150 static int
 151 eq_pointer (p1, p2)
 152      const PTR p1;
 153      const PTR p2;
 154 {
 155   return p1 == p2;
 156 }
 157
 158 /* This function creates table with length slightly longer than given
 159    source length.  Created hash table is initiated as empty (all the
 160    hash table entries are EMPTY_ENTRY).  The function returns the
 161    created hash table, or NULL if memory allocation fails.  */
 162
 163 htab_t
 164 htab_create_alloc (size, hash_f, eq_f, del_f, alloc_f, free_f)
 165      size_t size;
 166      htab_hash hash_f;
 167      htab_eq eq_f;
 168      htab_del del_f;
 169      htab_alloc alloc_f;
 170      htab_free free_f;
 171 {
 172   htab_t result;
 173
 174   size = higher_prime_number (size);
 175   result = (htab_t) (*alloc_f) (1, sizeof (struct htab));
 176   if (result == NULL)
 177     return NULL;
 178   result->entries = (PTR *) (*alloc_f) (size, sizeof (PTR));
 179   if (result->entries == NULL)
 180     {
 181       if (free_f != NULL)
 182         (*free_f) (result);
 183       return NULL;
 184     }
 185   result->size = size;
 186   result->hash_f = hash_f;
 187   result->eq_f = eq_f;
 188   result->del_f = del_f;
 189   result->alloc_f = alloc_f;
 190   result->free_f = free_f;
 191   return result;
 192 }
 193
 194 /* This function frees all memory allocated for given hash table.
 195    Naturally the hash table must already exist. */
 196
 197 void
 198 htab_delete (htab)
 199      htab_t htab;
 200 {
 201   int i;
 202
 203   if (htab->del_f)
 204     for (i = htab->size - 1; i >= 0; i--)
 205       if (htab->entries[i] != EMPTY_ENTRY
 206           && htab->entries[i] != DELETED_ENTRY)
 207         (*htab->del_f) (htab->entries[i]);
 208
 209   if (htab->free_f != NULL)
 210     {
 211       (*htab->free_f) (htab->entries);
 212       (*htab->free_f) (htab);
 213     }
 214 }
 215
 216 /* This function clears all entries in the given hash table.  */
 217
 218 void
 219 htab_empty (htab)
 220      htab_t htab;
 221 {
 222   int i;
 223
 224   if (htab->del_f)
 225     for (i = htab->size - 1; i >= 0; i--)
 226       if (htab->entries[i] != EMPTY_ENTRY
 227           && htab->entries[i] != DELETED_ENTRY)
 228         (*htab->del_f) (htab->entries[i]);
 229
 230   memset (htab->entries, 0, htab->size * sizeof (PTR));
 231 }
 232
 233 /* Similar to htab_find_slot, but without several unwanted side effects:
 234     - Does not call htab->eq_f when it finds an existing entry.
 235     - Does not change the count of elements/searches/collisions in the
 236       hash table.
 237    This function also assumes there are no deleted entries in the table.
 238    HASH is the hash value for the element to be inserted.  */
 239
 240 static PTR *
 241 find_empty_slot_for_expand (htab, hash)
 242      htab_t htab;
 243      hashval_t hash;
 244 {
 245   size_t size = htab->size;
 246   unsigned int index = hash % size;
 247   PTR *slot = htab->entries + index;
 248   hashval_t hash2;
 249
 250   if (*slot == EMPTY_ENTRY)
 251     return slot;
 252   else if (*slot == DELETED_ENTRY)
 253     abort ();
 254
 255   hash2 = 1 + hash % (size - 2);
 256   for (;;)
 257     {
 258       index += hash2;
 259       if (index >= size)
 260         index -= size;
 261
 262       slot = htab->entries + index;
 263       if (*slot == EMPTY_ENTRY)
 264         return slot;
 265       else if (*slot == DELETED_ENTRY)
 266         abort ();
 267     }
 268 }
 269
 270 /* The following function changes size of memory allocated for the
 271    entries and repeatedly inserts the table elements.  The occupancy
 272    of the table after the call will be about 50%.  Naturally the hash
 273    table must already exist.  Remember also that the place of the
 274    table entries is changed.  If memory allocation failures are allowed,
 275    this function will return zero, indicating that the table could not be
 276    expanded.  If all goes well, it will return a non-zero value.  */
 277
 278 static int
 279 htab_expand (htab)
 280      htab_t htab;
 281 {
 282   PTR *oentries;
 283   PTR *olimit;
 284   PTR *p;
 285   PTR *nentries;
 286
 287   oentries = htab->entries;
 288   olimit = oentries + htab->size;
 289
 290   htab->size = higher_prime_number (htab->size * 2);
 291
 292   nentries = (PTR *) (*htab->alloc_f) (htab->size, sizeof (PTR *));
 293   if (nentries == NULL)
 294     return 0;
 295   htab->entries = nentries;
 296
 297   htab->n_elements -= htab->n_deleted;
 298   htab->n_deleted = 0;
 299
 300   p = oentries;
 301   do
 302     {
 303       PTR x = *p;
 304
 305       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
 306         {
 307           PTR *q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
 308
 309           *q = x;
 310         }
 311
 312       p++;
 313     }
 314   while (p < olimit);
 315
 316   if (htab->free_f != NULL)
 317     (*htab->free_f) (oentries);
 318   return 1;
 319 }
 320
 321 /* This function searches for a hash table entry equal to the given
 322    element.  It cannot be used to insert or delete an element.  */
 323
 324 PTR
 325 htab_find_with_hash (htab, element, hash)
 326      htab_t htab;
 327      const PTR element;
 328      hashval_t hash;
 329 {
 330   unsigned int index;
 331   hashval_t hash2;
 332   size_t size;
 333   PTR entry;
 334
 335   htab->searches++;
 336   size = htab->size;
 337   index = hash % size;
 338
 339   entry = htab->entries[index];
 340   if (entry == EMPTY_ENTRY
 341       || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
 342     return entry;
 343
 344   hash2 = 1 + hash % (size - 2);
 345
 346   for (;;)
 347     {
 348       htab->collisions++;
 349       index += hash2;
 350       if (index >= size)
 351         index -= size;
 352
 353       entry = htab->entries[index];
 354       if (entry == EMPTY_ENTRY
 355           || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
 356         return entry;
 357     }
 358 }
 359
 360 /* Like htab_find_slot_with_hash, but compute the hash value from the
 361    element.  */
 362
 363 PTR
 364 htab_find (htab, element)
 365      htab_t htab;
 366      const PTR element;
 367 {
 368   return htab_find_with_hash (htab, element, (*htab->hash_f) (element));
 369 }
 370
 371 /* This function searches for a hash table slot containing an entry
 372    equal to the given element.  To delete an entry, call this with
 373    INSERT = 0, then call htab_clear_slot on the slot returned (possibly
 374    after doing some checks).  To insert an entry, call this with
 375    INSERT = 1, then write the value you want into the returned slot.
 376    When inserting an entry, NULL may be returned if memory allocation
 377    fails.  */
 378
 379 PTR *
 380 htab_find_slot_with_hash (htab, element, hash, insert)
 381      htab_t htab;
 382      const PTR element;
 383      hashval_t hash;
 384      enum insert_option insert;
 385 {
 386   PTR *first_deleted_slot;
 387   unsigned int index;
 388   hashval_t hash2;
 389   size_t size;
 390   PTR entry;
 391
 392   if (insert == INSERT && htab->size * 3 <= htab->n_elements * 4
 393       && htab_expand (htab) == 0)
 394     return NULL;
 395
 396   size = htab->size;
 397   index = hash % size;
 398
 399   htab->searches++;
 400   first_deleted_slot = NULL;
 401
 402   entry = htab->entries[index];
 403   if (entry == EMPTY_ENTRY)
 404     goto empty_entry;
 405   else if (entry == DELETED_ENTRY)
 406     first_deleted_slot = &htab->entries[index];
 407   else if ((*htab->eq_f) (entry, element))
 408     return &htab->entries[index];
 409
 410   hash2 = 1 + hash % (size - 2);
 411   for (;;)
 412     {
 413       htab->collisions++;
 414       index += hash2;
 415       if (index >= size)
 416         index -= size;
 417
 418       entry = htab->entries[index];
 419       if (entry == EMPTY_ENTRY)
 420         goto empty_entry;
 421       else if (entry == DELETED_ENTRY)
 422         {
 423           if (!first_deleted_slot)
 424             first_deleted_slot = &htab->entries[index];
 425         }
 426       else if ((*htab->eq_f) (entry, element))
 427         return &htab->entries[index];
 428     }
 429
 430  empty_entry:
 431   if (insert == NO_INSERT)
 432     return NULL;
 433
 434   htab->n_elements++;
 435
 436   if (first_deleted_slot)
 437     {
 438       *first_deleted_slot = EMPTY_ENTRY;
 439       return first_deleted_slot;
 440     }
 441
 442   return &htab->entries[index];
 443 }
 444
 445 /* Like htab_find_slot_with_hash, but compute the hash value from the
 446    element.  */
 447
 448 PTR *
 449 htab_find_slot (htab, element, insert)
 450      htab_t htab;
 451      const PTR element;
 452      enum insert_option insert;
 453 {
 454   return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),
 455                                    insert);
 456 }
 457
 458 /* This function deletes an element with the given value from hash
 459    table.  If there is no matching element in the hash table, this
 460    function does nothing.  */
 461
 462 void
 463 htab_remove_elt (htab, element)
 464      htab_t htab;
 465      PTR element;
 466 {
 467   PTR *slot;
 468
 469   slot = htab_find_slot (htab, element, NO_INSERT);
 470   if (*slot == EMPTY_ENTRY)
 471     return;
 472
 473   if (htab->del_f)
 474     (*htab->del_f) (*slot);
 475
 476   *slot = DELETED_ENTRY;
 477   htab->n_deleted++;
 478 }
 479
 480 /* This function clears a specified slot in a hash table.  It is
 481    useful when you've already done the lookup and don't want to do it
 482    again.  */
 483
 484 void
 485 htab_clear_slot (htab, slot)
 486      htab_t htab;
 487      PTR *slot;
 488 {
 489   if (slot < htab->entries || slot >= htab->entries + htab->size
 490       || *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY)
 491     abort ();
 492
 493   if (htab->del_f)
 494     (*htab->del_f) (*slot);
 495
 496   *slot = DELETED_ENTRY;
 497   htab->n_deleted++;
 498 }
 499
 500 /* This function scans over the entire hash table calling
 501    CALLBACK for each live entry.  If CALLBACK returns false,
 502    the iteration stops.  INFO is passed as CALLBACK's second
 503    argument.  */
 504
 505 void
 506 htab_traverse (htab, callback, info)
 507      htab_t htab;
 508      htab_trav callback;
 509      PTR info;
 510 {
 511   PTR *slot = htab->entries;
 512   PTR *limit = slot + htab->size;
 513
 514   do
 515     {
 516       PTR x = *slot;
 517
 518       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
 519         if (!(*callback) (slot, info))
 520           break;
 521     }
 522   while (++slot < limit);
 523 }
 524
 525 /* Return the current size of given hash table. */
 526
 527 size_t
 528 htab_size (htab)
 529      htab_t htab;
 530 {
 531   return htab->size;
 532 }
 533
 534 /* Return the current number of elements in given hash table. */
 535
 536 size_t
 537 htab_elements (htab)
 538      htab_t htab;
 539 {
 540   return htab->n_elements - htab->n_deleted;
 541 }
 542
 543 /* Return the fraction of fixed collisions during all work with given
 544    hash table. */
 545
 546 double
 547 htab_collisions (htab)
 548      htab_t htab;
 549 {
 550   if (htab->searches == 0)
 551     return 0.0;
 552
 553   return (double) htab->collisions / (double) htab->searches;
 554 }
 555
 556 /* Hash P as a null-terminated string.
 557
 558    Copied from gcc/hashtable.c.  Zack had the following to say with respect
 559    to applicability, though note that unlike hashtable.c, this hash table
 560    implementation re-hashes rather than chain buckets.
 561
 562    http://gcc.gnu.org/ml/gcc-patches/2001-08/msg01021.html
 563    From: Zack Weinberg <zackw@panix.com>
 564    Date: Fri, 17 Aug 2001 02:15:56 -0400
 565
 566    I got it by extracting all the identifiers from all the source code
 567    I had lying around in mid-1999, and testing many recurrences of
 568    the form "H_n = H_{n-1} * K + c_n * L + M" where K, L, M were either
 569    prime numbers or the appropriate identity.  This was the best one.
 570    I don't remember exactly what constituted "best", except I was
 571    looking at bucket-length distributions mostly.
 572
 573    So it should be very good at hashing identifiers, but might not be
 574    as good at arbitrary strings.
 575
 576    I'll add that it thoroughly trounces the hash functions recommended
 577    for this use at http://burtleburtle.net/bob/hash/index.html, both
 578    on speed and bucket distribution.  I haven't tried it against the
 579    function they just started using for Perl's hashes.  */
 580
 581 hashval_t
 582 htab_hash_string (p)
 583      const PTR p;
 584 {
 585   const unsigned char *str = (const unsigned char *) p;
 586   hashval_t r = 0;
 587   unsigned char c;
 588
 589   while ((c = *str++) != 0)
 590     r = r * 67 + c - 113;
 591
 592   return r;
 593 }