hash.c

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