libiberty/hashtab.c

   1 /* An expandable hash tables datatype.
   2    Copyright (C) 1999, 2000 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 unsigned long primes[] = {
  84     2,
  85     7,
  86     13,
  87     31,
  88     61,
  89     127,
  90     251,
  91     509,
  92     1021,
  93     2039,
  94     4093,
  95     8191,
  96     16381,
  97     32749,
  98     65521,
  99     131071,
 100     262139,
 101     524287,
 102     1048573,
 103     2097143,
 104     4194301,
 105     8388593,
 106     16777213,
 107     33554393,
 108     67108859,
 109     134217689,
 110     268435399,
 111     536870909,
 112     1073741789,
 113     2147483647,
 114     4294967291
 115   };
 116
 117   unsigned long* low = &primes[0];
 118   unsigned long* high = &primes[sizeof(primes) / sizeof(primes[0])];
 119
 120   while (low != high)
 121     {
 122       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   hashval_t hash2 = 1 + hash % (size - 2);
 267   unsigned int index = hash % size;
 268
 269   for (;;)
 270     {
 271       PTR *slot = htab->entries + index;
 272
 273       if (*slot == EMPTY_ENTRY)
 274         return slot;
 275       else if (*slot == DELETED_ENTRY)
 276         abort ();
 277
 278       index += hash2;
 279       if (index >= size)
 280         index -= size;
 281     }
 282 }
 283
 284 /* The following function changes size of memory allocated for the
 285    entries and repeatedly inserts the table elements.  The occupancy
 286    of the table after the call will be about 50%.  Naturally the hash
 287    table must already exist.  Remember also that the place of the
 288    table entries is changed.  If memory allocation failures are allowed,
 289    this function will return zero, indicating that the table could not be
 290    expanded.  If all goes well, it will return a non-zero value.  */
 291
 292 static int
 293 htab_expand (htab)
 294      htab_t htab;
 295 {
 296   PTR *oentries;
 297   PTR *olimit;
 298   PTR *p;
 299
 300   oentries = htab->entries;
 301   olimit = oentries + htab->size;
 302
 303   htab->size = higher_prime_number (htab->size * 2);
 304
 305   if (htab->return_allocation_failure)
 306     {
 307       PTR *nentries = (PTR *) calloc (htab->size, sizeof (PTR *));
 308       if (nentries == NULL)
 309         return 0;
 310       htab->entries = nentries;
 311     }
 312   else
 313     htab->entries = (PTR *) xcalloc (htab->size, sizeof (PTR *));
 314
 315   htab->n_elements -= htab->n_deleted;
 316   htab->n_deleted = 0;
 317
 318   p = oentries;
 319   do
 320     {
 321       PTR x = *p;
 322
 323       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
 324         {
 325           PTR *q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
 326
 327           *q = x;
 328         }
 329
 330       p++;
 331     }
 332   while (p < olimit);
 333
 334   free (oentries);
 335   return 1;
 336 }
 337
 338 /* This function searches for a hash table entry equal to the given
 339    element.  It cannot be used to insert or delete an element.  */
 340
 341 PTR
 342 htab_find_with_hash (htab, element, hash)
 343      htab_t htab;
 344      const PTR element;
 345      hashval_t hash;
 346 {
 347   unsigned int index;
 348   hashval_t hash2;
 349   size_t size;
 350   PTR entry;
 351
 352   htab->searches++;
 353   size = htab->size;
 354   index = hash % size;
 355
 356   entry = htab->entries[index];
 357   if (entry == EMPTY_ENTRY
 358       || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
 359     return entry;
 360
 361   hash2 = 1 + hash % (size - 2);
 362
 363   for (;;)
 364     {
 365       htab->collisions++;
 366       index += hash2;
 367       if (index >= size)
 368         index -= size;
 369
 370       entry = htab->entries[index];
 371       if (entry == EMPTY_ENTRY
 372           || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
 373         return entry;
 374     }
 375 }
 376
 377 /* Like htab_find_slot_with_hash, but compute the hash value from the
 378    element.  */
 379
 380 PTR
 381 htab_find (htab, element)
 382      htab_t htab;
 383      const PTR element;
 384 {
 385   return htab_find_with_hash (htab, element, (*htab->hash_f) (element));
 386 }
 387
 388 /* This function searches for a hash table slot containing an entry
 389    equal to the given element.  To delete an entry, call this with
 390    INSERT = 0, then call htab_clear_slot on the slot returned (possibly
 391    after doing some checks).  To insert an entry, call this with
 392    INSERT = 1, then write the value you want into the returned slot.
 393    When inserting an entry, NULL may be returned if memory allocation
 394    fails.  */
 395
 396 PTR *
 397 htab_find_slot_with_hash (htab, element, hash, insert)
 398      htab_t htab;
 399      const PTR element;
 400      hashval_t hash;
 401      enum insert_option insert;
 402 {
 403   PTR *first_deleted_slot;
 404   unsigned int index;
 405   hashval_t hash2;
 406   size_t size;
 407
 408   if (insert == INSERT && htab->size * 3 <= htab->n_elements * 4
 409       && htab_expand (htab) == 0)
 410     return NULL;
 411
 412   size = htab->size;
 413   hash2 = 1 + hash % (size - 2);
 414   index = hash % size;
 415
 416   htab->searches++;
 417   first_deleted_slot = NULL;
 418
 419   for (;;)
 420     {
 421       PTR entry = htab->entries[index];
 422       if (entry == EMPTY_ENTRY)
 423         {
 424           if (insert == NO_INSERT)
 425             return NULL;
 426
 427           htab->n_elements++;
 428
 429           if (first_deleted_slot)
 430             {
 431               *first_deleted_slot = EMPTY_ENTRY;
 432               return first_deleted_slot;
 433             }
 434
 435           return &htab->entries[index];
 436         }
 437
 438       if (entry == DELETED_ENTRY)
 439         {
 440           if (!first_deleted_slot)
 441             first_deleted_slot = &htab->entries[index];
 442         }
 443       else  if ((*htab->eq_f) (entry, element))
 444         return &htab->entries[index];
 445
 446       htab->collisions++;
 447       index += hash2;
 448       if (index >= size)
 449         index -= size;
 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_slot (htab, element, insert)
 458      htab_t htab;
 459      const PTR element;
 460      enum insert_option insert;
 461 {
 462   return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),
 463                                    insert);
 464 }
 465
 466 /* This function deletes an element with the given value from hash
 467    table.  If there is no matching element in the hash table, this
 468    function does nothing.  */
 469
 470 void
 471 htab_remove_elt (htab, element)
 472      htab_t htab;
 473      PTR element;
 474 {
 475   PTR *slot;
 476
 477   slot = htab_find_slot (htab, element, NO_INSERT);
 478   if (*slot == EMPTY_ENTRY)
 479     return;
 480
 481   if (htab->del_f)
 482     (*htab->del_f) (*slot);
 483
 484   *slot = DELETED_ENTRY;
 485   htab->n_deleted++;
 486 }
 487
 488 /* This function clears a specified slot in a hash table.  It is
 489    useful when you've already done the lookup and don't want to do it
 490    again.  */
 491
 492 void
 493 htab_clear_slot (htab, slot)
 494      htab_t htab;
 495      PTR *slot;
 496 {
 497   if (slot < htab->entries || slot >= htab->entries + htab->size
 498       || *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY)
 499     abort ();
 500
 501   if (htab->del_f)
 502     (*htab->del_f) (*slot);
 503
 504   *slot = DELETED_ENTRY;
 505   htab->n_deleted++;
 506 }
 507
 508 /* This function scans over the entire hash table calling
 509    CALLBACK for each live entry.  If CALLBACK returns false,
 510    the iteration stops.  INFO is passed as CALLBACK's second
 511    argument.  */
 512
 513 void
 514 htab_traverse (htab, callback, info)
 515      htab_t htab;
 516      htab_trav callback;
 517      PTR info;
 518 {
 519   PTR *slot = htab->entries;
 520   PTR *limit = slot + htab->size;
 521
 522   do
 523     {
 524       PTR x = *slot;
 525
 526       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
 527         if (!(*callback) (slot, info))
 528           break;
 529     }
 530   while (++slot < limit);
 531 }
 532
 533 /* Return the current size of given hash table. */
 534
 535 size_t
 536 htab_size (htab)
 537      htab_t htab;
 538 {
 539   return htab->size;
 540 }
 541
 542 /* Return the current number of elements in given hash table. */
 543
 544 size_t
 545 htab_elements (htab)
 546      htab_t htab;
 547 {
 548   return htab->n_elements - htab->n_deleted;
 549 }
 550
 551 /* Return the fraction of fixed collisions during all work with given
 552    hash table. */
 553
 554 double
 555 htab_collisions (htab)
 556      htab_t htab;
 557 {
 558   if (htab->searches == 0)
 559     return 0.0;
 560
 561   return (double) htab->collisions / (double) htab->searches;
 562 }