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