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 the nearest prime number which is
  75    greater than a given source number, N. */
  76
  77 static unsigned long
  78 higher_prime_number (n)
  79      unsigned long n;
  80 {
  81   unsigned long i;
  82
  83   /* Ensure we have a larger number and then force to odd.  */
  84   n++;
  85   n |= 0x01;
  86
  87   /* All odd numbers < 9 are prime.  */
  88   if (n < 9)
  89     return n;
  90
  91   /* Otherwise find the next prime using a sieve.  */
  92
  93  next:
  94
  95   for (i = 3; i * i <= n; i += 2)
  96     if (n % i == 0)
  97       {
  98          n += 2;
  99          goto next;
 100        }
 101
 102   return n;
 103 }
 104
 105 /* Returns a hash code for P.  */
 106
 107 static hashval_t
 108 hash_pointer (p)
 109      const PTR p;
 110 {
 111   return (hashval_t) ((long)p >> 3);
 112 }
 113
 114 /* Returns non-zero if P1 and P2 are equal.  */
 115
 116 static int
 117 eq_pointer (p1, p2)
 118      const PTR p1;
 119      const PTR p2;
 120 {
 121   return p1 == p2;
 122 }
 123
 124 /* This function creates table with length slightly longer than given
 125    source length.  Created hash table is initiated as empty (all the
 126    hash table entries are EMPTY_ENTRY).  The function returns the
 127    created hash table.  Memory allocation must not fail.  */
 128
 129 htab_t
 130 htab_create (size, hash_f, eq_f, del_f)
 131      size_t size;
 132      htab_hash hash_f;
 133      htab_eq eq_f;
 134      htab_del del_f;
 135 {
 136   htab_t result;
 137
 138   size = higher_prime_number (size);
 139   result = (htab_t) xcalloc (1, sizeof (struct htab));
 140   result->entries = (PTR *) xcalloc (size, sizeof (PTR));
 141   result->size = size;
 142   result->hash_f = hash_f;
 143   result->eq_f = eq_f;
 144   result->del_f = del_f;
 145   result->return_allocation_failure = 0;
 146   return result;
 147 }
 148
 149 /* This function creates table with length slightly longer than given
 150    source length.  The created hash table is initiated as empty (all the
 151    hash table entries are EMPTY_ENTRY).  The function returns the created
 152    hash table.  Memory allocation may fail; it may return NULL.  */
 153
 154 htab_t
 155 htab_try_create (size, hash_f, eq_f, del_f)
 156      size_t size;
 157      htab_hash hash_f;
 158      htab_eq eq_f;
 159      htab_del del_f;
 160 {
 161   htab_t result;
 162
 163   size = higher_prime_number (size);
 164   result = (htab_t) calloc (1, sizeof (struct htab));
 165   if (result == NULL)
 166     return NULL;
 167
 168   result->entries = (PTR *) calloc (size, sizeof (PTR));
 169   if (result->entries == NULL)
 170     {
 171       free (result);
 172       return NULL;
 173     }
 174
 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 = 1;
 180   return result;
 181 }
 182
 183 /* This function frees all memory allocated for given hash table.
 184    Naturally the hash table must already exist. */
 185
 186 void
 187 htab_delete (htab)
 188      htab_t htab;
 189 {
 190   int i;
 191
 192   if (htab->del_f)
 193     for (i = htab->size - 1; i >= 0; i--)
 194       if (htab->entries[i] != EMPTY_ENTRY
 195           && htab->entries[i] != DELETED_ENTRY)
 196         (*htab->del_f) (htab->entries[i]);
 197
 198   free (htab->entries);
 199   free (htab);
 200 }
 201
 202 /* This function clears all entries in the given hash table.  */
 203
 204 void
 205 htab_empty (htab)
 206      htab_t htab;
 207 {
 208   int i;
 209
 210   if (htab->del_f)
 211     for (i = htab->size - 1; i >= 0; i--)
 212       if (htab->entries[i] != EMPTY_ENTRY
 213           && htab->entries[i] != DELETED_ENTRY)
 214         (*htab->del_f) (htab->entries[i]);
 215
 216   memset (htab->entries, 0, htab->size * sizeof (PTR));
 217 }
 218
 219 /* Similar to htab_find_slot, but without several unwanted side effects:
 220     - Does not call htab->eq_f when it finds an existing entry.
 221     - Does not change the count of elements/searches/collisions in the
 222       hash table.
 223    This function also assumes there are no deleted entries in the table.
 224    HASH is the hash value for the element to be inserted.  */
 225
 226 static PTR *
 227 find_empty_slot_for_expand (htab, hash)
 228      htab_t htab;
 229      hashval_t hash;
 230 {
 231   size_t size = htab->size;
 232   hashval_t hash2 = 1 + hash % (size - 2);
 233   unsigned int index = hash % size;
 234
 235   for (;;)
 236     {
 237       PTR *slot = htab->entries + index;
 238
 239       if (*slot == EMPTY_ENTRY)
 240         return slot;
 241       else if (*slot == DELETED_ENTRY)
 242         abort ();
 243
 244       index += hash2;
 245       if (index >= size)
 246         index -= size;
 247     }
 248 }
 249
 250 /* The following function changes size of memory allocated for the
 251    entries and repeatedly inserts the table elements.  The occupancy
 252    of the table after the call will be about 50%.  Naturally the hash
 253    table must already exist.  Remember also that the place of the
 254    table entries is changed.  If memory allocation failures are allowed,
 255    this function will return zero, indicating that the table could not be
 256    expanded.  If all goes well, it will return a non-zero value.  */
 257
 258 static int
 259 htab_expand (htab)
 260      htab_t htab;
 261 {
 262   PTR *oentries;
 263   PTR *olimit;
 264   PTR *p;
 265
 266   oentries = htab->entries;
 267   olimit = oentries + htab->size;
 268
 269   htab->size = higher_prime_number (htab->size * 2);
 270
 271   if (htab->return_allocation_failure)
 272     {
 273       PTR *nentries = (PTR *) calloc (htab->size, sizeof (PTR *));
 274       if (nentries == NULL)
 275         return 0;
 276       htab->entries = nentries;
 277     }
 278   else
 279     htab->entries = (PTR *) xcalloc (htab->size, sizeof (PTR *));
 280
 281   htab->n_elements -= htab->n_deleted;
 282   htab->n_deleted = 0;
 283
 284   p = oentries;
 285   do
 286     {
 287       PTR x = *p;
 288
 289       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
 290         {
 291           PTR *q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
 292
 293           *q = x;
 294         }
 295
 296       p++;
 297     }
 298   while (p < olimit);
 299
 300   free (oentries);
 301   return 1;
 302 }
 303
 304 /* This function searches for a hash table entry equal to the given
 305    element.  It cannot be used to insert or delete an element.  */
 306
 307 PTR
 308 htab_find_with_hash (htab, element, hash)
 309      htab_t htab;
 310      const PTR element;
 311      hashval_t hash;
 312 {
 313   unsigned int index;
 314   hashval_t hash2;
 315   size_t size;
 316   PTR entry;
 317
 318   htab->searches++;
 319   size = htab->size;
 320   index = hash % size;
 321
 322   entry = htab->entries[index];
 323   if (entry == EMPTY_ENTRY
 324       || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
 325     return entry;
 326
 327   hash2 = 1 + hash % (size - 2);
 328
 329   for (;;)
 330     {
 331       htab->collisions++;
 332       index += hash2;
 333       if (index >= size)
 334         index -= size;
 335
 336       entry = htab->entries[index];
 337       if (entry == EMPTY_ENTRY
 338           || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
 339         return entry;
 340     }
 341 }
 342
 343 /* Like htab_find_slot_with_hash, but compute the hash value from the
 344    element.  */
 345
 346 PTR
 347 htab_find (htab, element)
 348      htab_t htab;
 349      const PTR element;
 350 {
 351   return htab_find_with_hash (htab, element, (*htab->hash_f) (element));
 352 }
 353
 354 /* This function searches for a hash table slot containing an entry
 355    equal to the given element.  To delete an entry, call this with
 356    INSERT = 0, then call htab_clear_slot on the slot returned (possibly
 357    after doing some checks).  To insert an entry, call this with
 358    INSERT = 1, then write the value you want into the returned slot.
 359    When inserting an entry, NULL may be returned if memory allocation
 360    fails.  */
 361
 362 PTR *
 363 htab_find_slot_with_hash (htab, element, hash, insert)
 364      htab_t htab;
 365      const PTR element;
 366      hashval_t hash;
 367      enum insert_option insert;
 368 {
 369   PTR *first_deleted_slot;
 370   unsigned int index;
 371   hashval_t hash2;
 372   size_t size;
 373
 374   if (insert == INSERT && htab->size * 3 <= htab->n_elements * 4
 375       && htab_expand (htab) == 0)
 376     return NULL;
 377
 378   size = htab->size;
 379   hash2 = 1 + hash % (size - 2);
 380   index = hash % size;
 381
 382   htab->searches++;
 383   first_deleted_slot = NULL;
 384
 385   for (;;)
 386     {
 387       PTR entry = htab->entries[index];
 388       if (entry == EMPTY_ENTRY)
 389         {
 390           if (insert == NO_INSERT)
 391             return NULL;
 392
 393           htab->n_elements++;
 394
 395           if (first_deleted_slot)
 396             {
 397               *first_deleted_slot = EMPTY_ENTRY;
 398               return first_deleted_slot;
 399             }
 400
 401           return &htab->entries[index];
 402         }
 403
 404       if (entry == DELETED_ENTRY)
 405         {
 406           if (!first_deleted_slot)
 407             first_deleted_slot = &htab->entries[index];
 408         }
 409       else  if ((*htab->eq_f) (entry, element))
 410         return &htab->entries[index];
 411
 412       htab->collisions++;
 413       index += hash2;
 414       if (index >= size)
 415         index -= size;
 416     }
 417 }
 418
 419 /* Like htab_find_slot_with_hash, but compute the hash value from the
 420    element.  */
 421
 422 PTR *
 423 htab_find_slot (htab, element, insert)
 424      htab_t htab;
 425      const PTR element;
 426      enum insert_option insert;
 427 {
 428   return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),
 429                                    insert);
 430 }
 431
 432 /* This function deletes an element with the given value from hash
 433    table.  If there is no matching element in the hash table, this
 434    function does nothing.  */
 435
 436 void
 437 htab_remove_elt (htab, element)
 438      htab_t htab;
 439      PTR element;
 440 {
 441   PTR *slot;
 442
 443   slot = htab_find_slot (htab, element, NO_INSERT);
 444   if (*slot == EMPTY_ENTRY)
 445     return;
 446
 447   if (htab->del_f)
 448     (*htab->del_f) (*slot);
 449
 450   *slot = DELETED_ENTRY;
 451   htab->n_deleted++;
 452 }
 453
 454 /* This function clears a specified slot in a hash table.  It is
 455    useful when you've already done the lookup and don't want to do it
 456    again.  */
 457
 458 void
 459 htab_clear_slot (htab, slot)
 460      htab_t htab;
 461      PTR *slot;
 462 {
 463   if (slot < htab->entries || slot >= htab->entries + htab->size
 464       || *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY)
 465     abort ();
 466
 467   if (htab->del_f)
 468     (*htab->del_f) (*slot);
 469
 470   *slot = DELETED_ENTRY;
 471   htab->n_deleted++;
 472 }
 473
 474 /* This function scans over the entire hash table calling
 475    CALLBACK for each live entry.  If CALLBACK returns false,
 476    the iteration stops.  INFO is passed as CALLBACK's second
 477    argument.  */
 478
 479 void
 480 htab_traverse (htab, callback, info)
 481      htab_t htab;
 482      htab_trav callback;
 483      PTR info;
 484 {
 485   PTR *slot = htab->entries;
 486   PTR *limit = slot + htab->size;
 487
 488   do
 489     {
 490       PTR x = *slot;
 491
 492       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
 493         if (!(*callback) (slot, info))
 494           break;
 495     }
 496   while (++slot < limit);
 497 }
 498
 499 /* Return the current size of given hash table. */
 500
 501 size_t
 502 htab_size (htab)
 503      htab_t htab;
 504 {
 505   return htab->size;
 506 }
 507
 508 /* Return the current number of elements in given hash table. */
 509
 510 size_t
 511 htab_elements (htab)
 512      htab_t htab;
 513 {
 514   return htab->n_elements - htab->n_deleted;
 515 }
 516
 517 /* Return the fraction of fixed collisions during all work with given
 518    hash table. */
 519
 520 double
 521 htab_collisions (htab)
 522      htab_t htab;
 523 {
 524   if (htab->searches == 0)
 525     return 0.0;
 526
 527   return (double) htab->collisions / (double) htab->searches;
 528 }