hash.c

   1 /* hash.c -- hash table maintenance
   2    Copyright (C) 1995, 1999, 2002 Free Software Foundation, Inc.
   3    Written by Greg McGary <gkm@gnu.org> <greg@mcgary.org>
   4
   5 This program is free software; you can redistribute it and/or modify
   6 it under the terms of the GNU General Public License as published by
   7 the Free Software Foundation; either version 2, or (at your option)
   8 any later version.
   9
  10 This program is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU General Public License for more details.
  14
  15 You should have received a copy of the GNU General Public License along with
  16 this program; see the file COPYING.  If not, write to the Free Software
  17 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.  */
  18
  19 #include "make.h"
  20 #include "hash.h"
  21
  22 #define CALLOC(t, n) ((t *) calloc (sizeof (t), (n)))
  23 #define MALLOC(t, n) ((t *) xmalloc (sizeof (t) * (n)))
  24 #define REALLOC(o, t, n) ((t *) xrealloc ((o), sizeof (t) * (n)))
  25 #define CLONE(o, t, n) ((t *) memcpy (MALLOC (t, (n)), (o), sizeof (t) * (n)))
  26
  27 static void hash_rehash __P((struct hash_table* ht));
  28 static unsigned long round_up_2 __P((unsigned long rough));
  29
  30 /* Implement double hashing with open addressing.  The table size is
  31    always a power of two.  The secondary (`increment') hash function
  32    is forced to return an odd-value, in order to be relatively prime
  33    to the table size.  This guarantees that the increment can
  34    potentially hit every slot in the table during collision
  35    resolution.  */
  36
  37 void *hash_deleted_item = &hash_deleted_item;
  38
  39 /* Force the table size to be a power of two, possibly rounding up the
  40    given size.  */
  41
  42 void
  43 hash_init (struct hash_table *ht, unsigned long size,
  44            hash_func_t hash_1, hash_func_t hash_2, hash_cmp_func_t hash_cmp)
  45 {
  46   ht->ht_size = round_up_2 (size);
  47   ht->ht_empty_slots = ht->ht_size;
  48   ht->ht_vec = (void**) CALLOC (struct token *, ht->ht_size);
  49   if (ht->ht_vec == 0)
  50     {
  51       fprintf (stderr, _("can't allocate %ld bytes for hash table: memory exhausted"),
  52                ht->ht_size * sizeof(struct token *));
  53       exit (1);
  54     }
  55
  56   ht->ht_capacity = ht->ht_size - (ht->ht_size / 16); /* 93.75% loading factor */
  57   ht->ht_fill = 0;
  58   ht->ht_collisions = 0;
  59   ht->ht_lookups = 0;
  60   ht->ht_rehashes = 0;
  61   ht->ht_hash_1 = hash_1;
  62   ht->ht_hash_2 = hash_2;
  63   ht->ht_compare = hash_cmp;
  64 }
  65
  66 /* Load an array of items into `ht'.  */
  67
  68 void
  69 hash_load (struct hash_table *ht, void *item_table,
  70            unsigned long cardinality, unsigned long size)
  71 {
  72   char *items = (char *) item_table;
  73   while (cardinality--)
  74     {
  75       hash_insert (ht, items);
  76       items += size;
  77     }
  78 }
  79
  80 /* Returns the address of the table slot matching `key'.  If `key' is
  81    not found, return the address of an empty slot suitable for
  82    inserting `key'.  The caller is responsible for incrementing
  83    ht_fill on insertion.  */
  84
  85 void **
  86 hash_find_slot (struct hash_table *ht, const void *key)
  87 {
  88   void **slot;
  89   void **deleted_slot = 0;
  90   unsigned int hash_2 = 0;
  91   unsigned int hash_1 = (*ht->ht_hash_1) (key);
  92
  93   ht->ht_lookups++;
  94   for (;;)
  95     {
  96       hash_1 &= (ht->ht_size - 1);
  97       slot = &ht->ht_vec[hash_1];
  98
  99       if (*slot == 0)
 100         return (deleted_slot ? deleted_slot : slot);
 101       if (*slot == hash_deleted_item)
 102         {
 103           if (deleted_slot == 0)
 104             deleted_slot = slot;
 105         }
 106       else
 107         {
 108           if (key == *slot)
 109             return slot;
 110           if ((*ht->ht_compare) (key, *slot) == 0)
 111             return slot;
 112           ht->ht_collisions++;
 113         }
 114       if (!hash_2)
 115           hash_2 = (*ht->ht_hash_2) (key) | 1;
 116       hash_1 += hash_2;
 117     }
 118 }
 119
 120 void *
 121 hash_find_item (struct hash_table *ht, const void *key)
 122 {
 123   void **slot = hash_find_slot (ht, key);
 124   return ((HASH_VACANT (*slot)) ? 0 : *slot);
 125 }
 126
 127 void *
 128 hash_insert (struct hash_table *ht, const void *item)
 129 {
 130   void **slot = hash_find_slot (ht, item);
 131   const void *old_item = slot ? *slot : 0;
 132   hash_insert_at (ht, item, slot);
 133   return (void *)((HASH_VACANT (old_item)) ? 0 : old_item);
 134 }
 135
 136 void *
 137 hash_insert_at (struct hash_table *ht, const void *item, const void *slot)
 138 {
 139   const void *old_item = *(void **) slot;
 140   if (HASH_VACANT (old_item))
 141     {
 142       ht->ht_fill++;
 143       if (old_item == 0)
 144         ht->ht_empty_slots--;
 145       old_item = item;
 146     }
 147   *(void const **) slot = item;
 148   if (ht->ht_empty_slots < ht->ht_size - ht->ht_capacity)
 149     {
 150       hash_rehash (ht);
 151       return (void *) hash_find_slot (ht, item);
 152     }
 153   else
 154     return (void *) slot;
 155 }
 156
 157 void *
 158 hash_delete (struct hash_table *ht, const void *item)
 159 {
 160   void **slot = hash_find_slot (ht, item);
 161   return hash_delete_at (ht, slot);
 162 }
 163
 164 void *
 165 hash_delete_at (struct hash_table *ht, const void *slot)
 166 {
 167   void *item = *(void **) slot;
 168   if (!HASH_VACANT (item))
 169     {
 170       *(void const **) slot = hash_deleted_item;
 171       ht->ht_fill--;
 172       return item;
 173     }
 174   else
 175     return 0;
 176 }
 177
 178 void
 179 hash_free_items (struct hash_table *ht)
 180 {
 181   void **vec = ht->ht_vec;
 182   void **end = &vec[ht->ht_size];
 183   for (; vec < end; vec++)
 184     {
 185       void *item = *vec;
 186       if (!HASH_VACANT (item))
 187         free (item);
 188       *vec = 0;
 189     }
 190   ht->ht_fill = 0;
 191   ht->ht_empty_slots = ht->ht_size;
 192 }
 193
 194 void
 195 hash_delete_items (struct hash_table *ht)
 196 {
 197   void **vec = ht->ht_vec;
 198   void **end = &vec[ht->ht_size];
 199   for (; vec < end; vec++)
 200     *vec = 0;
 201   ht->ht_fill = 0;
 202   ht->ht_collisions = 0;
 203   ht->ht_lookups = 0;
 204   ht->ht_rehashes = 0;
 205   ht->ht_empty_slots = ht->ht_size;
 206 }
 207
 208 void
 209 hash_free (struct hash_table *ht, int free_items)
 210 {
 211   if (free_items)
 212     hash_free_items (ht);
 213   else
 214     {
 215       ht->ht_fill = 0;
 216       ht->ht_empty_slots = ht->ht_size;
 217     }
 218   free (ht->ht_vec);
 219   ht->ht_vec = 0;
 220   ht->ht_capacity = 0;
 221 }
 222
 223 void
 224 hash_map (struct hash_table *ht, hash_map_func_t map)
 225 {
 226   void **slot;
 227   void **end = &ht->ht_vec[ht->ht_size];
 228
 229   for (slot = ht->ht_vec; slot < end; slot++)
 230     {
 231       if (!HASH_VACANT (*slot))
 232         (*map) (*slot);
 233     }
 234 }
 235
 236 void
 237 hash_map_arg (struct hash_table *ht, hash_map_arg_func_t map, void *arg)
 238 {
 239   void **slot;
 240   void **end = &ht->ht_vec[ht->ht_size];
 241
 242   for (slot = ht->ht_vec; slot < end; slot++)
 243     {
 244       if (!HASH_VACANT (*slot))
 245         (*map) (*slot, arg);
 246     }
 247 }
 248
 249 /* Double the size of the hash table in the event of overflow... */
 250
 251 static void
 252 hash_rehash (struct hash_table *ht)
 253 {
 254   unsigned long old_ht_size = ht->ht_size;
 255   void **old_vec = ht->ht_vec;
 256   void **ovp;
 257
 258   if (ht->ht_fill >= ht->ht_capacity)
 259     {
 260       ht->ht_size *= 2;
 261       ht->ht_capacity = ht->ht_size - (ht->ht_size >> 4);
 262     }
 263   ht->ht_rehashes++;
 264   ht->ht_vec = (void **) CALLOC (struct token *, ht->ht_size);
 265
 266   for (ovp = old_vec; ovp < &old_vec[old_ht_size]; ovp++)
 267     {
 268       if (! HASH_VACANT (*ovp))
 269         {
 270           void **slot = hash_find_slot (ht, *ovp);
 271           *slot = *ovp;
 272         }
 273     }
 274   ht->ht_empty_slots = ht->ht_size - ht->ht_fill;
 275   free (old_vec);
 276 }
 277
 278 void
 279 hash_print_stats (struct hash_table *ht, FILE *out_FILE)
 280 {
 281   /* GKM FIXME: honor NO_FLOAT */
 282   fprintf (out_FILE, _("Load=%ld/%ld=%.0f%%, "), ht->ht_fill, ht->ht_size,
 283            100.0 * (double) ht->ht_fill / (double) ht->ht_size);
 284   fprintf (out_FILE, _("Rehash=%d, "), ht->ht_rehashes);
 285   fprintf (out_FILE, _("Collisions=%ld/%ld=%.0f%%"), ht->ht_collisions, ht->ht_lookups,
 286            (ht->ht_lookups
 287             ? (100.0 * (double) ht->ht_collisions / (double) ht->ht_lookups)
 288             : 0));
 289 }
 290
 291 /* Dump all items into a NULL-terminated vector.  Use the
 292    user-supplied vector, or malloc one.  */
 293
 294 void **
 295 hash_dump (struct hash_table *ht, void **vector_0, qsort_cmp_t compare)
 296 {
 297   void **vector;
 298   void **slot;
 299   void **end = &ht->ht_vec[ht->ht_size];
 300
 301   if (vector_0 == 0)
 302     vector_0 = MALLOC (void *, ht->ht_fill + 1);
 303   vector = vector_0;
 304
 305   for (slot = ht->ht_vec; slot < end; slot++)
 306     if (!HASH_VACANT (*slot))
 307       *vector++ = *slot;
 308   *vector = 0;
 309
 310   if (compare)
 311     qsort (vector_0, ht->ht_fill, sizeof (void *), compare);
 312   return vector_0;
 313 }
 314
 315 /* Round a given number up to the nearest power of 2. */
 316
 317 static unsigned long
 318 round_up_2 (unsigned long n)
 319 {
 320   n |= (n >> 1);
 321   n |= (n >> 2);
 322   n |= (n >> 4);
 323   n |= (n >> 8);
 324   n |= (n >> 16);
 325
 326 #if !defined(HAVE_LIMITS_H) || ULONG_MAX > 4294967295
 327   /* We only need this on systems where unsigned long is >32 bits.  */
 328   n |= (n >> 32);
 329 #endif
 330
 331   return n + 1;
 332 }