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