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