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