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 void 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.  */
 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   return result;
 146 }
 147
 148 /* This function frees all memory allocated for given hash table.
 149    Naturally the hash table must already exist. */
 150
 151 void
 152 htab_delete (htab)
 153      htab_t htab;
 154 {
 155   int i;
 156
 157   if (htab->del_f)
 158     for (i = htab->size - 1; i >= 0; i--)
 159       if (htab->entries[i] != EMPTY_ENTRY
 160           && htab->entries[i] != DELETED_ENTRY)
 161         (*htab->del_f) (htab->entries[i]);
 162
 163   free (htab->entries);
 164   free (htab);
 165 }
 166
 167 /* This function clears all entries in the given hash table.  */
 168
 169 void
 170 htab_empty (htab)
 171      htab_t htab;
 172 {
 173   int i;
 174
 175   if (htab->del_f)
 176     for (i = htab->size - 1; i >= 0; i--)
 177       if (htab->entries[i] != EMPTY_ENTRY
 178           && htab->entries[i] != DELETED_ENTRY)
 179         (*htab->del_f) (htab->entries[i]);
 180
 181   memset (htab->entries, 0, htab->size * sizeof (PTR));
 182 }
 183
 184 /* Similar to htab_find_slot, but without several unwanted side effects:
 185     - Does not call htab->eq_f when it finds an existing entry.
 186     - Does not change the count of elements/searches/collisions in the
 187       hash table.
 188    This function also assumes there are no deleted entries in the table.
 189    HASH is the hash value for the element to be inserted.  */
 190
 191 static PTR *
 192 find_empty_slot_for_expand (htab, hash)
 193      htab_t htab;
 194      hashval_t hash;
 195 {
 196   size_t size = htab->size;
 197   hashval_t hash2 = 1 + hash % (size - 2);
 198   unsigned int index = hash % size;
 199
 200   for (;;)
 201     {
 202       PTR *slot = htab->entries + index;
 203
 204       if (*slot == EMPTY_ENTRY)
 205         return slot;
 206       else if (*slot == DELETED_ENTRY)
 207         abort ();
 208
 209       index += hash2;
 210       if (index >= size)
 211         index -= size;
 212     }
 213 }
 214
 215 /* The following function changes size of memory allocated for the
 216    entries and repeatedly inserts the table elements.  The occupancy
 217    of the table after the call will be about 50%.  Naturally the hash
 218    table must already exist.  Remember also that the place of the
 219    table entries is changed.  */
 220
 221 static void
 222 htab_expand (htab)
 223      htab_t htab;
 224 {
 225   PTR *oentries;
 226   PTR *olimit;
 227   PTR *p;
 228
 229   oentries = htab->entries;
 230   olimit = oentries + htab->size;
 231
 232   htab->size = higher_prime_number (htab->size * 2);
 233   htab->entries = (PTR *) xcalloc (htab->size, sizeof (PTR *));
 234
 235   htab->n_elements -= htab->n_deleted;
 236   htab->n_deleted = 0;
 237
 238   p = oentries;
 239   do
 240     {
 241       PTR x = *p;
 242
 243       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
 244         {
 245           PTR *q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
 246
 247           *q = x;
 248         }
 249
 250       p++;
 251     }
 252   while (p < olimit);
 253
 254   free (oentries);
 255 }
 256
 257 /* This function searches for a hash table entry equal to the given
 258    element.  It cannot be used to insert or delete an element.  */
 259
 260 PTR
 261 htab_find_with_hash (htab, element, hash)
 262      htab_t htab;
 263      const PTR element;
 264      hashval_t hash;
 265 {
 266   unsigned int index;
 267   hashval_t hash2;
 268   size_t size;
 269   PTR entry;
 270
 271   htab->searches++;
 272   size = htab->size;
 273   index = hash % size;
 274
 275   entry = htab->entries[index];
 276   if (entry == EMPTY_ENTRY
 277       || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
 278     return entry;
 279
 280   hash2 = 1 + hash % (size - 2);
 281
 282   for (;;)
 283     {
 284       htab->collisions++;
 285       index += hash2;
 286       if (index >= size)
 287         index -= size;
 288
 289       entry = htab->entries[index];
 290       if (entry == EMPTY_ENTRY
 291           || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
 292         return entry;
 293     }
 294 }
 295
 296 /* Like htab_find_slot_with_hash, but compute the hash value from the
 297    element.  */
 298
 299 PTR
 300 htab_find (htab, element)
 301      htab_t htab;
 302      const PTR element;
 303 {
 304   return htab_find_with_hash (htab, element, (*htab->hash_f) (element));
 305 }
 306
 307 /* This function searches for a hash table slot containing an entry
 308    equal to the given element.  To delete an entry, call this with
 309    INSERT = 0, then call htab_clear_slot on the slot returned (possibly
 310    after doing some checks).  To insert an entry, call this with
 311    INSERT = 1, then write the value you want into the returned slot.  */
 312
 313 PTR *
 314 htab_find_slot_with_hash (htab, element, hash, insert)
 315      htab_t htab;
 316      const PTR element;
 317      hashval_t hash;
 318      enum insert_option insert;
 319 {
 320   PTR *first_deleted_slot;
 321   unsigned int index;
 322   hashval_t hash2;
 323   size_t size;
 324
 325   if (insert == INSERT && htab->size * 3 <= htab->n_elements * 4)
 326     htab_expand (htab);
 327
 328   size = htab->size;
 329   hash2 = 1 + hash % (size - 2);
 330   index = hash % size;
 331
 332   htab->searches++;
 333   first_deleted_slot = NULL;
 334
 335   for (;;)
 336     {
 337       PTR entry = htab->entries[index];
 338       if (entry == EMPTY_ENTRY)
 339         {
 340           if (insert == NO_INSERT)
 341             return NULL;
 342
 343           htab->n_elements++;
 344
 345           if (first_deleted_slot)
 346             {
 347               *first_deleted_slot = EMPTY_ENTRY;
 348               return first_deleted_slot;
 349             }
 350
 351           return &htab->entries[index];
 352         }
 353
 354       if (entry == DELETED_ENTRY)
 355         {
 356           if (!first_deleted_slot)
 357             first_deleted_slot = &htab->entries[index];
 358         }
 359       else  if ((*htab->eq_f) (entry, element))
 360         return &htab->entries[index];
 361
 362       htab->collisions++;
 363       index += hash2;
 364       if (index >= size)
 365         index -= size;
 366     }
 367 }
 368
 369 /* Like htab_find_slot_with_hash, but compute the hash value from the
 370    element.  */
 371
 372 PTR *
 373 htab_find_slot (htab, element, insert)
 374      htab_t htab;
 375      const PTR element;
 376      enum insert_option insert;
 377 {
 378   return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),
 379                                    insert);
 380 }
 381
 382 /* This function deletes an element with the given value from hash
 383    table.  If there is no matching element in the hash table, this
 384    function does nothing.  */
 385
 386 void
 387 htab_remove_elt (htab, element)
 388      htab_t htab;
 389      PTR element;
 390 {
 391   PTR *slot;
 392
 393   slot = htab_find_slot (htab, element, NO_INSERT);
 394   if (*slot == EMPTY_ENTRY)
 395     return;
 396
 397   if (htab->del_f)
 398     (*htab->del_f) (*slot);
 399
 400   *slot = DELETED_ENTRY;
 401   htab->n_deleted++;
 402 }
 403
 404 /* This function clears a specified slot in a hash table.  It is
 405    useful when you've already done the lookup and don't want to do it
 406    again.  */
 407
 408 void
 409 htab_clear_slot (htab, slot)
 410      htab_t htab;
 411      PTR *slot;
 412 {
 413   if (slot < htab->entries || slot >= htab->entries + htab->size
 414       || *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY)
 415     abort ();
 416
 417   if (htab->del_f)
 418     (*htab->del_f) (*slot);
 419
 420   *slot = DELETED_ENTRY;
 421   htab->n_deleted++;
 422 }
 423
 424 /* This function scans over the entire hash table calling
 425    CALLBACK for each live entry.  If CALLBACK returns false,
 426    the iteration stops.  INFO is passed as CALLBACK's second
 427    argument.  */
 428
 429 void
 430 htab_traverse (htab, callback, info)
 431      htab_t htab;
 432      htab_trav callback;
 433      PTR info;
 434 {
 435   PTR *slot = htab->entries;
 436   PTR *limit = slot + htab->size;
 437
 438   do
 439     {
 440       PTR x = *slot;
 441
 442       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
 443         if (!(*callback) (slot, info))
 444           break;
 445     }
 446   while (++slot < limit);
 447 }
 448
 449 /* Return the current size of given hash table. */
 450
 451 size_t
 452 htab_size (htab)
 453      htab_t htab;
 454 {
 455   return htab->size;
 456 }
 457
 458 /* Return the current number of elements in given hash table. */
 459
 460 size_t
 461 htab_elements (htab)
 462      htab_t htab;
 463 {
 464   return htab->n_elements - htab->n_deleted;
 465 }
 466
 467 /* Return the fraction of fixed collisions during all work with given
 468    hash table. */
 469
 470 double
 471 htab_collisions (htab)
 472      htab_t htab;
 473 {
 474   if (htab->searches == 0)
 475     return 0.0;
 476
 477   return (double) htab->collisions / (double) htab->searches;
 478 }