libiberty/hashtab.c

   1 /* An expandable hash tables datatype.
   2    Copyright (C) 1999 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 #ifdef HAVE_STDLIB_H
  39 #include <stdlib.h>
  40 #endif
  41
  42 #include "libiberty.h"
  43 #include "hashtab.h"
  44
  45 /* The following variable is used for debugging. Its value is number
  46    of all calls of `find_hash_table_entry' for all hash tables. */
  47
  48 static int all_searches = 0;
  49
  50 /* The following variable is used for debugging. Its value is number
  51    of collisions fixed for time of work with all hash tables. */
  52
  53 static int all_collisions = 0;
  54
  55 /* The following variable is used for debugging. Its value is number
  56    of all table expansions fixed for time of work with all hash
  57    tables. */
  58
  59 static int all_expansions = 0;
  60
  61 /* This macro defines reserved value for empty table entry. */
  62
  63 #define EMPTY_ENTRY    NULL
  64
  65 /* This macro defines reserved value for table entry which contained
  66    a deleted element. */
  67
  68 #define DELETED_ENTRY  ((void *) 1)
  69
  70 /* The following function returns the nearest prime number which is
  71    greater than given source number. */
  72
  73 static unsigned long
  74 higher_prime_number (number)
  75      unsigned long number;
  76 {
  77   unsigned long i;
  78
  79   for (number = (number / 2) * 2 + 3;; number += 2)
  80     {
  81       for (i = 3; i * i <= number; i += 2)
  82         if (number % i == 0)
  83           break;
  84       if (i * i > number)
  85         return number;
  86     }
  87 }
  88
  89 /* This function creates table with length slightly longer than given
  90    source length.  Created hash table is initiated as empty (all the
  91    hash table entries are EMPTY_ENTRY).  The function returns the
  92    created hash table. */
  93
  94 hash_table_t
  95 create_hash_table (size, hash_function, eq_function)
  96      size_t size;
  97      unsigned (*hash_function) PARAMS ((hash_table_entry_t));
  98      int (*eq_function) PARAMS ((hash_table_entry_t, hash_table_entry_t));
  99 {
 100   hash_table_t result;
 101
 102   size = higher_prime_number (size);
 103   result = (hash_table_t) xmalloc (sizeof (*result));
 104   result->entries
 105     = (hash_table_entry_t *) xmalloc (size * sizeof (hash_table_entry_t));
 106   result->size = size;
 107   result->hash_function = hash_function;
 108   result->eq_function = eq_function;
 109   result->number_of_elements = 0;
 110   result->number_of_deleted_elements = 0;
 111   result->searches = 0;
 112   result->collisions = 0;
 113   memset (result->entries, 0, size * sizeof (hash_table_entry_t));
 114   return result;
 115 }
 116
 117 /* This function frees all memory allocated for given hash table.
 118    Naturally the hash table must already exist. */
 119
 120 void
 121 delete_hash_table (htab)
 122      hash_table_t htab;
 123 {
 124   free (htab->entries);
 125   free (htab);
 126 }
 127
 128 /* This function clears all entries in the given hash table.  */
 129
 130 void
 131 empty_hash_table (htab)
 132      hash_table_t htab;
 133 {
 134   memset (htab->entries, 0, htab->size * sizeof (hash_table_entry_t));
 135 }
 136
 137 /* The following function changes size of memory allocated for the
 138    entries and repeatedly inserts the table elements.  The occupancy
 139    of the table after the call will be about 50%.  Naturally the hash
 140    table must already exist.  Remember also that the place of the
 141    table entries is changed. */
 142
 143 static void
 144 expand_hash_table (htab)
 145      hash_table_t htab;
 146 {
 147   hash_table_t new_htab;
 148   hash_table_entry_t *entry_ptr;
 149   hash_table_entry_t *new_entry_ptr;
 150
 151   new_htab = create_hash_table (htab->number_of_elements * 2,
 152                                 htab->hash_function, htab->eq_function);
 153   for (entry_ptr = htab->entries; entry_ptr < htab->entries + htab->size;
 154        entry_ptr++)
 155     if (*entry_ptr != EMPTY_ENTRY && *entry_ptr != DELETED_ENTRY)
 156       {
 157         new_entry_ptr = find_hash_table_entry (new_htab, *entry_ptr, 1);
 158         *new_entry_ptr = (*entry_ptr);
 159       }
 160   free (htab->entries);
 161   *htab = (*new_htab);
 162   free (new_htab);
 163 }
 164
 165 /* This function searches for hash table entry which contains element
 166    equal to given value or empty entry in which given value can be
 167    placed (if the element with given value does not exist in the
 168    table).  The function works in two regimes.  The first regime is
 169    used only for search.  The second is used for search and
 170    reservation empty entry for given value.  The table is expanded if
 171    occupancy (taking into accout also deleted elements) is more than
 172    75%.  Naturally the hash table must already exist.  If reservation
 173    flag is TRUE then the element with given value should be inserted
 174    into the table entry before another call of
 175    `find_hash_table_entry'. */
 176
 177 hash_table_entry_t *
 178 find_hash_table_entry (htab, element, reserve)
 179      hash_table_t htab;
 180      hash_table_entry_t element;
 181      int reserve;
 182 {
 183   hash_table_entry_t *entry_ptr;
 184   hash_table_entry_t *first_deleted_entry_ptr;
 185   unsigned index, hash_value, secondary_hash_value;
 186
 187   if (htab->size * 3 <= htab->number_of_elements * 4)
 188     {
 189       all_expansions++;
 190       expand_hash_table (htab);
 191     }
 192   hash_value = (*htab->hash_function) (element);
 193   secondary_hash_value = 1 + hash_value % (htab->size - 2);
 194   index = hash_value % htab->size;
 195   htab->searches++;
 196   all_searches++;
 197   first_deleted_entry_ptr = NULL;
 198   for (;;htab->collisions++, all_collisions++)
 199     {
 200       entry_ptr = htab->entries + index;
 201       if (*entry_ptr == EMPTY_ENTRY)
 202         {
 203           if (reserve)
 204             {
 205               htab->number_of_elements++;
 206               if (first_deleted_entry_ptr != NULL)
 207                 {
 208                   entry_ptr = first_deleted_entry_ptr;
 209                   *entry_ptr = EMPTY_ENTRY;
 210                 }
 211             }
 212           break;
 213         }
 214       else if (*entry_ptr != DELETED_ENTRY)
 215         {
 216           if ((*htab->eq_function) (*entry_ptr, element))
 217             break;
 218         }
 219       else if (first_deleted_entry_ptr == NULL)
 220         first_deleted_entry_ptr = entry_ptr;
 221       index += secondary_hash_value;
 222       if (index >= htab->size)
 223         index -= htab->size;
 224     }
 225   return entry_ptr;
 226 }
 227
 228 /* This function deletes element with given value from hash table.
 229    The hash table entry value will be `DELETED_ENTRY' after the
 230    function call.  Naturally the hash table must already exist.  Hash
 231    table entry for given value should be not empty (or deleted). */
 232
 233 void
 234 remove_element_from_hash_table_entry (htab, element)
 235      hash_table_t htab;
 236      hash_table_entry_t element;
 237 {
 238   hash_table_entry_t *entry_ptr;
 239
 240   entry_ptr = find_hash_table_entry (htab, element, 0);
 241   *entry_ptr = DELETED_ENTRY;
 242   htab->number_of_deleted_elements++;
 243 }
 244
 245 /* This function clears a specified slot in a hash table.
 246    It is useful when you've already done the lookup and don't want to
 247    do it again.  */
 248
 249 void
 250 clear_hash_table_slot (htab, slot)
 251      hash_table_t htab;
 252      hash_table_entry_t *slot;
 253 {
 254   if (slot < htab->entries || slot >= htab->entries + htab->size
 255       || *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY)
 256     abort ();
 257   *slot = DELETED_ENTRY;
 258   htab->number_of_deleted_elements++;
 259 }
 260
 261 /* This function scans over the entire hash table calling
 262    CALLBACK for each live entry.  If CALLBACK returns false,
 263    the iteration stops.  INFO is passed as CALLBACK's second
 264    argument.  */
 265
 266 void
 267 traverse_hash_table (htab, callback, info)
 268      hash_table_t htab;
 269      int (*callback) (hash_table_entry_t, void *);
 270      void *info;
 271 {
 272   hash_table_entry_t *entry_ptr;
 273   for (entry_ptr = htab->entries; entry_ptr < htab->entries + htab->size;
 274        entry_ptr++)
 275     if (*entry_ptr != EMPTY_ENTRY && *entry_ptr != DELETED_ENTRY)
 276       if (!callback (*entry_ptr, info))
 277         break;
 278 }
 279
 280 /* The following function returns current size of given hash table. */
 281
 282 size_t
 283 hash_table_size (htab)
 284      hash_table_t htab;
 285 {
 286   return htab->size;
 287 }
 288
 289 /* The following function returns current number of elements in given
 290    hash table. */
 291
 292 size_t
 293 hash_table_elements_number (htab)
 294      hash_table_t htab;
 295 {
 296   return htab->number_of_elements - htab->number_of_deleted_elements;
 297 }
 298
 299 /* The following function returns number of percents of fixed
 300    collisions during all work with given hash table. */
 301
 302 int
 303 hash_table_collisions (htab)
 304      hash_table_t htab;
 305 {
 306   int searches;
 307
 308   searches = htab->searches;
 309   if (searches == 0)
 310     searches++;
 311   return htab->collisions * 100 / searches;
 312 }
 313
 314 /* The following function returns number of percents of fixed
 315    collisions during all work with all hash tables. */
 316
 317 int
 318 all_hash_table_collisions ()
 319 {
 320   int searches;
 321
 322   searches = all_searches;
 323   if (searches == 0)
 324     searches++;
 325   return all_collisions * 100 / searches;
 326 }