libiberty/hashtab.c

   1 /* An expandable hash tables datatype.
   2    Copyright (C) 1999, 2000, 2001, 2002, 2003 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 /* As above, but use the variants of alloc_f and free_f which accept
 195    an extra argument.  */
 196
 197 htab_t
 198 htab_create_alloc_ex (size, hash_f, eq_f, del_f, alloc_arg, alloc_f,
 199                       free_f)
 200      size_t size;
 201      htab_hash hash_f;
 202      htab_eq eq_f;
 203      htab_del del_f;
 204      PTR alloc_arg;
 205      htab_alloc_with_arg alloc_f;
 206      htab_free_with_arg free_f;
 207 {
 208   htab_t result;
 209
 210   size = higher_prime_number (size);
 211   result = (htab_t) (*alloc_f) (alloc_arg, 1, sizeof (struct htab));
 212   if (result == NULL)
 213     return NULL;
 214   result->entries = (PTR *) (*alloc_f) (alloc_arg, size, sizeof (PTR));
 215   if (result->entries == NULL)
 216     {
 217       if (free_f != NULL)
 218         (*free_f) (alloc_arg, result);
 219       return NULL;
 220     }
 221   result->size = size;
 222   result->hash_f = hash_f;
 223   result->eq_f = eq_f;
 224   result->del_f = del_f;
 225   result->alloc_arg = alloc_arg;
 226   result->alloc_with_arg_f = alloc_f;
 227   result->free_with_arg_f = free_f;
 228   return result;
 229 }
 230
 231 /* Update the function pointers and allocation parameter in the htab_t.  */
 232
 233 void
 234 htab_set_functions_ex (htab, hash_f, eq_f, del_f, alloc_arg, alloc_f, free_f)
 235      htab_t htab;
 236      htab_hash hash_f;
 237      htab_eq eq_f;
 238      htab_del del_f;
 239      PTR alloc_arg;
 240      htab_alloc_with_arg alloc_f;
 241      htab_free_with_arg free_f;
 242 {
 243   htab->hash_f = hash_f;
 244   htab->eq_f = eq_f;
 245   htab->del_f = del_f;
 246   htab->alloc_arg = alloc_arg;
 247   htab->alloc_with_arg_f = alloc_f;
 248   htab->free_with_arg_f = free_f;
 249 }
 250
 251 /* These functions exist solely for backward compatibility.  */
 252
 253 #undef htab_create
 254 htab_t
 255 htab_create (size, hash_f, eq_f, del_f)
 256      size_t size;
 257      htab_hash hash_f;
 258      htab_eq eq_f;
 259      htab_del del_f;
 260 {
 261   return htab_create_alloc (size, hash_f, eq_f, del_f, xcalloc, free);
 262 }
 263
 264 htab_t
 265 htab_try_create (size, hash_f, eq_f, del_f)
 266      size_t size;
 267      htab_hash hash_f;
 268      htab_eq eq_f;
 269      htab_del del_f;
 270 {
 271   return htab_create_alloc (size, hash_f, eq_f, del_f, calloc, free);
 272 }
 273
 274 /* This function frees all memory allocated for given hash table.
 275    Naturally the hash table must already exist. */
 276
 277 void
 278 htab_delete (htab)
 279      htab_t htab;
 280 {
 281   int i;
 282
 283   if (htab->del_f)
 284     for (i = htab->size - 1; i >= 0; i--)
 285       if (htab->entries[i] != EMPTY_ENTRY
 286           && htab->entries[i] != DELETED_ENTRY)
 287         (*htab->del_f) (htab->entries[i]);
 288
 289   if (htab->free_f != NULL)
 290     {
 291       (*htab->free_f) (htab->entries);
 292       (*htab->free_f) (htab);
 293     }
 294   else if (htab->free_with_arg_f != NULL)
 295     {
 296       (*htab->free_with_arg_f) (htab->alloc_arg, htab->entries);
 297       (*htab->free_with_arg_f) (htab->alloc_arg, htab);
 298     }
 299 }
 300
 301 /* This function clears all entries in the given hash table.  */
 302
 303 void
 304 htab_empty (htab)
 305      htab_t htab;
 306 {
 307   int i;
 308
 309   if (htab->del_f)
 310     for (i = htab->size - 1; i >= 0; i--)
 311       if (htab->entries[i] != EMPTY_ENTRY
 312           && htab->entries[i] != DELETED_ENTRY)
 313         (*htab->del_f) (htab->entries[i]);
 314
 315   memset (htab->entries, 0, htab->size * sizeof (PTR));
 316 }
 317
 318 /* Similar to htab_find_slot, but without several unwanted side effects:
 319     - Does not call htab->eq_f when it finds an existing entry.
 320     - Does not change the count of elements/searches/collisions in the
 321       hash table.
 322    This function also assumes there are no deleted entries in the table.
 323    HASH is the hash value for the element to be inserted.  */
 324
 325 static PTR *
 326 find_empty_slot_for_expand (htab, hash)
 327      htab_t htab;
 328      hashval_t hash;
 329 {
 330   size_t size = htab->size;
 331   unsigned int index = hash % size;
 332   PTR *slot = htab->entries + index;
 333   hashval_t hash2;
 334
 335   if (*slot == EMPTY_ENTRY)
 336     return slot;
 337   else if (*slot == DELETED_ENTRY)
 338     abort ();
 339
 340   hash2 = 1 + hash % (size - 2);
 341   for (;;)
 342     {
 343       index += hash2;
 344       if (index >= size)
 345         index -= size;
 346
 347       slot = htab->entries + index;
 348       if (*slot == EMPTY_ENTRY)
 349         return slot;
 350       else if (*slot == DELETED_ENTRY)
 351         abort ();
 352     }
 353 }
 354
 355 /* The following function changes size of memory allocated for the
 356    entries and repeatedly inserts the table elements.  The occupancy
 357    of the table after the call will be about 50%.  Naturally the hash
 358    table must already exist.  Remember also that the place of the
 359    table entries is changed.  If memory allocation failures are allowed,
 360    this function will return zero, indicating that the table could not be
 361    expanded.  If all goes well, it will return a non-zero value.  */
 362
 363 static int
 364 htab_expand (htab)
 365      htab_t htab;
 366 {
 367   PTR *oentries;
 368   PTR *olimit;
 369   PTR *p;
 370   PTR *nentries;
 371   size_t nsize;
 372
 373   oentries = htab->entries;
 374   olimit = oentries + htab->size;
 375
 376   nsize = higher_prime_number (htab->size * 2);
 377
 378   if (htab->alloc_with_arg_f != NULL)
 379     nentries = (PTR *) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize,
 380                                                   sizeof (PTR *));
 381   else
 382     nentries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR *));
 383   if (nentries == NULL)
 384     return 0;
 385   htab->entries = nentries;
 386   htab->size = nsize;
 387
 388   htab->n_elements -= htab->n_deleted;
 389   htab->n_deleted = 0;
 390
 391   p = oentries;
 392   do
 393     {
 394       PTR x = *p;
 395
 396       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
 397         {
 398           PTR *q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
 399
 400           *q = x;
 401         }
 402
 403       p++;
 404     }
 405   while (p < olimit);
 406
 407   if (htab->free_f != NULL)
 408     (*htab->free_f) (oentries);
 409   else if (htab->free_with_arg_f != NULL)
 410     (*htab->free_with_arg_f) (htab->alloc_arg, oentries);
 411   return 1;
 412 }
 413
 414 /* This function searches for a hash table entry equal to the given
 415    element.  It cannot be used to insert or delete an element.  */
 416
 417 PTR
 418 htab_find_with_hash (htab, element, hash)
 419      htab_t htab;
 420      const PTR element;
 421      hashval_t hash;
 422 {
 423   unsigned int index;
 424   hashval_t hash2;
 425   size_t size;
 426   PTR entry;
 427
 428   htab->searches++;
 429   size = htab->size;
 430   index = hash % size;
 431
 432   entry = htab->entries[index];
 433   if (entry == EMPTY_ENTRY
 434       || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
 435     return entry;
 436
 437   hash2 = 1 + hash % (size - 2);
 438
 439   for (;;)
 440     {
 441       htab->collisions++;
 442       index += hash2;
 443       if (index >= size)
 444         index -= size;
 445
 446       entry = htab->entries[index];
 447       if (entry == EMPTY_ENTRY
 448           || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
 449         return entry;
 450     }
 451 }
 452
 453 /* Like htab_find_slot_with_hash, but compute the hash value from the
 454    element.  */
 455
 456 PTR
 457 htab_find (htab, element)
 458      htab_t htab;
 459      const PTR element;
 460 {
 461   return htab_find_with_hash (htab, element, (*htab->hash_f) (element));
 462 }
 463
 464 /* This function searches for a hash table slot containing an entry
 465    equal to the given element.  To delete an entry, call this with
 466    INSERT = 0, then call htab_clear_slot on the slot returned (possibly
 467    after doing some checks).  To insert an entry, call this with
 468    INSERT = 1, then write the value you want into the returned slot.
 469    When inserting an entry, NULL may be returned if memory allocation
 470    fails.  */
 471
 472 PTR *
 473 htab_find_slot_with_hash (htab, element, hash, insert)
 474      htab_t htab;
 475      const PTR element;
 476      hashval_t hash;
 477      enum insert_option insert;
 478 {
 479   PTR *first_deleted_slot;
 480   unsigned int index;
 481   hashval_t hash2;
 482   size_t size;
 483   PTR entry;
 484
 485   if (insert == INSERT && htab->size * 3 <= htab->n_elements * 4
 486       && htab_expand (htab) == 0)
 487     return NULL;
 488
 489   size = htab->size;
 490   index = hash % size;
 491
 492   htab->searches++;
 493   first_deleted_slot = NULL;
 494
 495   entry = htab->entries[index];
 496   if (entry == EMPTY_ENTRY)
 497     goto empty_entry;
 498   else if (entry == DELETED_ENTRY)
 499     first_deleted_slot = &htab->entries[index];
 500   else if ((*htab->eq_f) (entry, element))
 501     return &htab->entries[index];
 502
 503   hash2 = 1 + hash % (size - 2);
 504   for (;;)
 505     {
 506       htab->collisions++;
 507       index += hash2;
 508       if (index >= size)
 509         index -= size;
 510
 511       entry = htab->entries[index];
 512       if (entry == EMPTY_ENTRY)
 513         goto empty_entry;
 514       else if (entry == DELETED_ENTRY)
 515         {
 516           if (!first_deleted_slot)
 517             first_deleted_slot = &htab->entries[index];
 518         }
 519       else if ((*htab->eq_f) (entry, element))
 520         return &htab->entries[index];
 521     }
 522
 523  empty_entry:
 524   if (insert == NO_INSERT)
 525     return NULL;
 526
 527   htab->n_elements++;
 528
 529   if (first_deleted_slot)
 530     {
 531       *first_deleted_slot = EMPTY_ENTRY;
 532       return first_deleted_slot;
 533     }
 534
 535   return &htab->entries[index];
 536 }
 537
 538 /* Like htab_find_slot_with_hash, but compute the hash value from the
 539    element.  */
 540
 541 PTR *
 542 htab_find_slot (htab, element, insert)
 543      htab_t htab;
 544      const PTR element;
 545      enum insert_option insert;
 546 {
 547   return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),
 548                                    insert);
 549 }
 550
 551 /* This function deletes an element with the given value from hash
 552    table.  If there is no matching element in the hash table, this
 553    function does nothing.  */
 554
 555 void
 556 htab_remove_elt (htab, element)
 557      htab_t htab;
 558      PTR element;
 559 {
 560   PTR *slot;
 561
 562   slot = htab_find_slot (htab, element, NO_INSERT);
 563   if (*slot == EMPTY_ENTRY)
 564     return;
 565
 566   if (htab->del_f)
 567     (*htab->del_f) (*slot);
 568
 569   *slot = DELETED_ENTRY;
 570   htab->n_deleted++;
 571 }
 572
 573 /* This function clears a specified slot in a hash table.  It is
 574    useful when you've already done the lookup and don't want to do it
 575    again.  */
 576
 577 void
 578 htab_clear_slot (htab, slot)
 579      htab_t htab;
 580      PTR *slot;
 581 {
 582   if (slot < htab->entries || slot >= htab->entries + htab->size
 583       || *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY)
 584     abort ();
 585
 586   if (htab->del_f)
 587     (*htab->del_f) (*slot);
 588
 589   *slot = DELETED_ENTRY;
 590   htab->n_deleted++;
 591 }
 592
 593 /* This function scans over the entire hash table calling
 594    CALLBACK for each live entry.  If CALLBACK returns false,
 595    the iteration stops.  INFO is passed as CALLBACK's second
 596    argument.  */
 597
 598 void
 599 htab_traverse (htab, callback, info)
 600      htab_t htab;
 601      htab_trav callback;
 602      PTR info;
 603 {
 604   PTR *slot = htab->entries;
 605   PTR *limit = slot + htab->size;
 606
 607   do
 608     {
 609       PTR x = *slot;
 610
 611       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
 612         if (!(*callback) (slot, info))
 613           break;
 614     }
 615   while (++slot < limit);
 616 }
 617
 618 /* Return the current size of given hash table. */
 619
 620 size_t
 621 htab_size (htab)
 622      htab_t htab;
 623 {
 624   return htab->size;
 625 }
 626
 627 /* Return the current number of elements in given hash table. */
 628
 629 size_t
 630 htab_elements (htab)
 631      htab_t htab;
 632 {
 633   return htab->n_elements - htab->n_deleted;
 634 }
 635
 636 /* Return the fraction of fixed collisions during all work with given
 637    hash table. */
 638
 639 double
 640 htab_collisions (htab)
 641      htab_t htab;
 642 {
 643   if (htab->searches == 0)
 644     return 0.0;
 645
 646   return (double) htab->collisions / (double) htab->searches;
 647 }
 648
 649 /* Hash P as a null-terminated string.
 650
 651    Copied from gcc/hashtable.c.  Zack had the following to say with respect
 652    to applicability, though note that unlike hashtable.c, this hash table
 653    implementation re-hashes rather than chain buckets.
 654
 655    http://gcc.gnu.org/ml/gcc-patches/2001-08/msg01021.html
 656    From: Zack Weinberg <zackw@panix.com>
 657    Date: Fri, 17 Aug 2001 02:15:56 -0400
 658
 659    I got it by extracting all the identifiers from all the source code
 660    I had lying around in mid-1999, and testing many recurrences of
 661    the form "H_n = H_{n-1} * K + c_n * L + M" where K, L, M were either
 662    prime numbers or the appropriate identity.  This was the best one.
 663    I don't remember exactly what constituted "best", except I was
 664    looking at bucket-length distributions mostly.
 665
 666    So it should be very good at hashing identifiers, but might not be
 667    as good at arbitrary strings.
 668
 669    I'll add that it thoroughly trounces the hash functions recommended
 670    for this use at http://burtleburtle.net/bob/hash/index.html, both
 671    on speed and bucket distribution.  I haven't tried it against the
 672    function they just started using for Perl's hashes.  */
 673
 674 hashval_t
 675 htab_hash_string (p)
 676      const PTR p;
 677 {
 678   const unsigned char *str = (const unsigned char *) p;
 679   hashval_t r = 0;
 680   unsigned char c;
 681
 682   while ((c = *str++) != 0)
 683     r = r * 67 + c - 113;
 684
 685   return r;
 686 }