src/kmk/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 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 "make.h"
  18 #include "hash.h"
  19 #ifdef CONFIG_WITH_STRCACHE2
  20 # include <assert.h>
  21 #endif
  22
  23
  24 #define CALLOC(t, n) ((t *) calloc (sizeof (t), (n)))
  25 #define MALLOC(t, n) ((t *) xmalloc (sizeof (t) * (n)))
  26 #define REALLOC(o, t, n) ((t *) xrealloc ((o), sizeof (t) * (n)))
  27 #define CLONE(o, t, n) ((t *) memcpy (MALLOC (t, (n)), (o), sizeof (t) * (n)))
  28
  29 static void hash_rehash __P((struct hash_table* ht));
  30 static unsigned long round_up_2 __P((unsigned long rough));
  31
  32 /* Implement double hashing with open addressing.  The table size is
  33    always a power of two.  The secondary (`increment') hash function
  34    is forced to return an odd-value, in order to be relatively prime
  35    to the table size.  This guarantees that the increment can
  36    potentially hit every slot in the table during collision
  37    resolution.  */
  38
  39 void *hash_deleted_item = &hash_deleted_item;
  40
  41 /* Force the table size to be a power of two, possibly rounding up the
  42    given size.  */
  43
  44 void
  45 hash_init (struct hash_table *ht, unsigned long size,
  46            hash_func_t hash_1, hash_func_t hash_2, hash_cmp_func_t hash_cmp)
  47 {
  48   ht->ht_size = round_up_2 (size);
  49   ht->ht_empty_slots = ht->ht_size;
  50   ht->ht_vec = (void**) CALLOC (struct token *, ht->ht_size);
  51   if (ht->ht_vec == 0)
  52     {
  53       fprintf (stderr, _("can't allocate %ld bytes for hash table: memory exhausted"),
  54                ht->ht_size * sizeof(struct token *));
  55       exit (1);
  56     }
  57
  58   ht->ht_capacity = ht->ht_size - (ht->ht_size / 16); /* 93.75% loading factor */
  59   ht->ht_fill = 0;
  60   ht->ht_collisions = 0;
  61   ht->ht_lookups = 0;
  62   ht->ht_rehashes = 0;
  63   ht->ht_hash_1 = hash_1;
  64   ht->ht_hash_2 = hash_2;
  65   ht->ht_compare = hash_cmp;
  66 #ifdef CONFIG_WITH_STRCACHE2
  67   ht->ht_strcache = 0;
  68   ht->ht_off_string = 0;
  69 #endif
  70 }
  71
  72 #ifdef CONFIG_WITH_STRCACHE2
  73 /* Same as hash_init, except that no callbacks are needed since all
  74    keys - including the ones being searched for - are from a string
  75    cache.  This means that any give string will only have one pointer
  76    value and that the hash and length can be retrived very cheaply,
  77    thus permitting some nice optimizations.
  78
  79    STRCACHE points to the string cache, while OFF_STRING gives the
  80    offset of the string pointer in the item structures the hash table
  81    entries points to.  */
  82 void hash_init_strcached (struct hash_table *ht, unsigned long size,
  83                           struct strcache2 *strcache, unsigned int off_string)
  84 {
  85   hash_init (ht, size, 0, 0, 0);
  86   ht->ht_strcache = strcache;
  87   ht->ht_off_string = off_string;
  88 }
  89 #endif /* CONFIG_WITH_STRCACHE2 */
  90
  91 /* Load an array of items into `ht'.  */
  92
  93 void
  94 hash_load (struct hash_table *ht, void *item_table,
  95            unsigned long cardinality, unsigned long size)
  96 {
  97   char *items = (char *) item_table;
  98 #ifndef CONFIG_WITH_STRCACHE2
  99   while (cardinality--)
 100     {
 101       hash_insert (ht, items);
 102       items += size;
 103     }
 104 #else  /* CONFIG_WITH_STRCACHE2 */
 105   if (ht->ht_strcache)
 106     while (cardinality--)
 107       {
 108         hash_insert_strcached (ht, items);
 109         items += size;
 110       }
 111   else
 112     while (cardinality--)
 113       {
 114         hash_insert (ht, items);
 115         items += size;
 116       }
 117 #endif /* CONFIG_WITH_STRCACHE2 */
 118 }
 119
 120 /* Returns the address of the table slot matching `key'.  If `key' is
 121    not found, return the address of an empty slot suitable for
 122    inserting `key'.  The caller is responsible for incrementing
 123    ht_fill on insertion.  */
 124
 125 void **
 126 hash_find_slot (struct hash_table *ht, const void *key)
 127 {
 128   void **slot;
 129   void **deleted_slot = 0;
 130   unsigned int hash_2 = 0;
 131   unsigned int hash_1 = (*ht->ht_hash_1) (key);
 132
 133 #ifdef CONFIG_WITH_STRCACHE2
 134   assert (ht->ht_strcache == 0);
 135 #endif
 136
 137   MAKE_STATS (ht->ht_lookups++);
 138   MAKE_STATS_3 (make_stats_ht_lookups++);
 139   for (;;)
 140     {
 141       hash_1 &= (ht->ht_size - 1);
 142       slot = &ht->ht_vec[hash_1];
 143
 144       if (*slot == 0)
 145         return (deleted_slot ? deleted_slot : slot);
 146       if (*slot == hash_deleted_item)
 147         {
 148           if (deleted_slot == 0)
 149             deleted_slot = slot;
 150         }
 151       else
 152         {
 153           if (key == *slot)
 154             return slot;
 155           if ((*ht->ht_compare) (key, *slot) == 0)
 156             return slot;
 157           MAKE_STATS (ht->ht_collisions++);
 158           MAKE_STATS_3 (make_stats_ht_collisions++);
 159         }
 160       if (!hash_2)
 161           hash_2 = (*ht->ht_hash_2) (key) | 1;
 162       hash_1 += hash_2;
 163     }
 164 }
 165
 166 #ifdef CONFIG_WITH_STRCACHE2
 167 /* hash_find_slot version for tables created with hash_init_strcached.  */
 168 void **
 169 hash_find_slot_strcached (struct hash_table *ht, const void *key)
 170 {
 171   void **slot;
 172   void **deleted_slot = 0;
 173   const char *str1 = *(const char **)((const char *)key + ht->ht_off_string);
 174   const char *str2;
 175   unsigned int hash_1 = strcache2_calc_ptr_hash (ht->ht_strcache, str1);
 176   unsigned int hash_2;
 177
 178 #ifdef CONFIG_WITH_STRCACHE2
 179   assert (ht->ht_strcache != 0);
 180 #endif
 181
 182   MAKE_STATS (ht->ht_lookups++);
 183   MAKE_STATS_3 (make_stats_ht_lookups++);
 184
 185   /* first iteration unrolled. */
 186
 187   hash_1 &= (ht->ht_size - 1);
 188   slot = &ht->ht_vec[hash_1];
 189   if (*slot == 0)
 190     return slot;
 191   if (*slot != hash_deleted_item)
 192     {
 193       str2 = *(const char **)((const char *)(*slot) + ht->ht_off_string);
 194       if (str1 == str2)
 195         return slot;
 196
 197       MAKE_STATS (ht->ht_collisions++);
 198       MAKE_STATS_3 (make_stats_ht_collisions++);
 199     }
 200   else
 201     deleted_slot = slot;
 202
 203   /* the rest of the loop. */
 204
 205   hash_2 = strcache2_get_hash (ht->ht_strcache, str1) | 1;
 206   hash_1 += hash_2;
 207   for (;;)
 208     {
 209       hash_1 &= (ht->ht_size - 1);
 210       slot = &ht->ht_vec[hash_1];
 211
 212       if (*slot == 0)
 213         return (deleted_slot ? deleted_slot : slot);
 214       if (*slot == hash_deleted_item)
 215         {
 216           if (deleted_slot == 0)
 217             deleted_slot = slot;
 218         }
 219       else
 220         {
 221           str2 = *(const char **)((const char *)(*slot) + ht->ht_off_string);
 222           if (str1 == str2)
 223             return slot;
 224
 225           MAKE_STATS (ht->ht_collisions++);
 226           MAKE_STATS_3 (make_stats_ht_collisions++);
 227         }
 228
 229       hash_1 += hash_2;
 230     }
 231 }
 232 #endif /* CONFIG_WITH_STRCACHE2 */
 233
 234 void *
 235 hash_find_item (struct hash_table *ht, const void *key)
 236 {
 237   void **slot = hash_find_slot (ht, key);
 238   return ((HASH_VACANT (*slot)) ? 0 : *slot);
 239 }
 240
 241 #ifdef CONFIG_WITH_STRCACHE2
 242 void *
 243 hash_find_item_strcached (struct hash_table *ht, const void *key)
 244 {
 245   void **slot = hash_find_slot_strcached (ht, key);
 246   return ((HASH_VACANT (*slot)) ? 0 : *slot);
 247 }
 248 #endif /* CONFIG_WITH_STRCACHE2 */
 249
 250 void *
 251 hash_insert (struct hash_table *ht, const void *item)
 252 {
 253   void **slot = hash_find_slot (ht, item);
 254   const void *old_item = slot ? *slot : 0;
 255   hash_insert_at (ht, item, slot);
 256   return (void *)((HASH_VACANT (old_item)) ? 0 : old_item);
 257 }
 258
 259 #ifdef CONFIG_WITH_STRCACHE2
 260 void *
 261 hash_insert_strcached (struct hash_table *ht, const void *item)
 262 {
 263   void **slot = hash_find_slot_strcached (ht, item);
 264   const void *old_item = slot ? *slot : 0;
 265   hash_insert_at (ht, item, slot);
 266   return (void *)((HASH_VACANT (old_item)) ? 0 : old_item);
 267 }
 268 #endif /* CONFIG_WITH_STRCACHE2 */
 269
 270 void *
 271 hash_insert_at (struct hash_table *ht, const void *item, const void *slot)
 272 {
 273   const void *old_item = *(void **) slot;
 274   if (HASH_VACANT (old_item))
 275     {
 276       ht->ht_fill++;
 277       if (old_item == 0)
 278         ht->ht_empty_slots--;
 279       old_item = item;
 280     }
 281   *(void const **) slot = item;
 282   if (ht->ht_empty_slots < ht->ht_size - ht->ht_capacity)
 283     {
 284       hash_rehash (ht);
 285 #ifdef CONFIG_WITH_STRCACHE2
 286       if (ht->ht_strcache)
 287         return (void *)hash_find_slot_strcached (ht, item);
 288 #endif /* CONFIG_WITH_STRCACHE2 */
 289       return (void *) hash_find_slot (ht, item);
 290     }
 291   else
 292     return (void *) slot;
 293 }
 294
 295 void *
 296 hash_delete (struct hash_table *ht, const void *item)
 297 {
 298   void **slot = hash_find_slot (ht, item);
 299   return hash_delete_at (ht, slot);
 300 }
 301
 302 #ifdef CONFIG_WITH_STRCACHE2
 303 void *
 304 hash_delete_strcached (struct hash_table *ht, const void *item)
 305 {
 306   void **slot = hash_find_slot_strcached (ht, item);
 307   return hash_delete_at (ht, slot);
 308 }
 309 #endif /* CONFIG_WITH_STRCACHE2 */
 310
 311 void *
 312 hash_delete_at (struct hash_table *ht, const void *slot)
 313 {
 314   void *item = *(void **) slot;
 315   if (!HASH_VACANT (item))
 316     {
 317       *(void const **) slot = hash_deleted_item;
 318       ht->ht_fill--;
 319       return item;
 320     }
 321   else
 322     return 0;
 323 }
 324
 325 void
 326 hash_free_items (struct hash_table *ht)
 327 {
 328   void **vec = ht->ht_vec;
 329   void **end = &vec[ht->ht_size];
 330   for (; vec < end; vec++)
 331     {
 332       void *item = *vec;
 333       if (!HASH_VACANT (item))
 334         free (item);
 335       *vec = 0;
 336     }
 337   ht->ht_fill = 0;
 338   ht->ht_empty_slots = ht->ht_size;
 339 }
 340
 341 #ifdef CONFIG_WITH_ALLOC_CACHES
 342 void
 343 hash_free_items_cached (struct hash_table *ht, struct alloccache *cache)
 344 {
 345   void **vec = ht->ht_vec;
 346   void **end = &vec[ht->ht_size];
 347   for (; vec < end; vec++)
 348     {
 349       void *item = *vec;
 350       if (!HASH_VACANT (item))
 351         alloccache_free (cache, item);
 352       *vec = 0;
 353     }
 354   ht->ht_fill = 0;
 355   ht->ht_empty_slots = ht->ht_size;
 356 }
 357 #endif /* CONFIG_WITH_ALLOC_CACHES */
 358
 359 void
 360 hash_delete_items (struct hash_table *ht)
 361 {
 362   void **vec = ht->ht_vec;
 363   void **end = &vec[ht->ht_size];
 364   for (; vec < end; vec++)
 365     *vec = 0;
 366   ht->ht_fill = 0;
 367   ht->ht_collisions = 0;
 368   ht->ht_lookups = 0;
 369   ht->ht_rehashes = 0;
 370   ht->ht_empty_slots = ht->ht_size;
 371 }
 372
 373 void
 374 hash_free (struct hash_table *ht, int free_items)
 375 {
 376   if (free_items)
 377     hash_free_items (ht);
 378   else
 379     {
 380       ht->ht_fill = 0;
 381       ht->ht_empty_slots = ht->ht_size;
 382     }
 383   free (ht->ht_vec);
 384   ht->ht_vec = 0;
 385   ht->ht_capacity = 0;
 386 }
 387
 388 #ifdef CONFIG_WITH_ALLOC_CACHES
 389 void
 390 hash_free_cached (struct hash_table *ht, int free_items, struct alloccache *cache)
 391 {
 392   if (free_items)
 393     hash_free_items_cached (ht, cache);
 394   else
 395     {
 396       ht->ht_fill = 0;
 397       ht->ht_empty_slots = ht->ht_size;
 398     }
 399   free (ht->ht_vec);
 400   ht->ht_vec = 0;
 401   ht->ht_capacity = 0;
 402 }
 403 #endif /* CONFIG_WITH_ALLOC_CACHES */
 404
 405 void
 406 hash_map (struct hash_table *ht, hash_map_func_t map)
 407 {
 408   void **slot;
 409   void **end = &ht->ht_vec[ht->ht_size];
 410
 411   for (slot = ht->ht_vec; slot < end; slot++)
 412     {
 413       if (!HASH_VACANT (*slot))
 414         (*map) (*slot);
 415     }
 416 }
 417
 418 void
 419 hash_map_arg (struct hash_table *ht, hash_map_arg_func_t map, void *arg)
 420 {
 421   void **slot;
 422   void **end = &ht->ht_vec[ht->ht_size];
 423
 424   for (slot = ht->ht_vec; slot < end; slot++)
 425     {
 426       if (!HASH_VACANT (*slot))
 427         (*map) (*slot, arg);
 428     }
 429 }
 430
 431 /* Double the size of the hash table in the event of overflow... */
 432
 433 static void
 434 hash_rehash (struct hash_table *ht)
 435 {
 436   unsigned long old_ht_size = ht->ht_size;
 437   void **old_vec = ht->ht_vec;
 438   void **ovp;
 439
 440   if (ht->ht_fill >= ht->ht_capacity)
 441     {
 442       ht->ht_size *= 2;
 443       ht->ht_capacity = ht->ht_size - (ht->ht_size >> 4);
 444     }
 445   ht->ht_rehashes++;
 446   ht->ht_vec = (void **) CALLOC (struct token *, ht->ht_size);
 447
 448 #ifndef CONFIG_WITH_STRCACHE2
 449   for (ovp = old_vec; ovp < &old_vec[old_ht_size]; ovp++)
 450     {
 451       if (! HASH_VACANT (*ovp))
 452         {
 453           void **slot = hash_find_slot (ht, *ovp);
 454           *slot = *ovp;
 455         }
 456     }
 457 #else  /* CONFIG_WITH_STRCACHE2 */
 458   if (ht->ht_strcache)
 459     for (ovp = old_vec; ovp < &old_vec[old_ht_size]; ovp++)
 460       {
 461         if (! HASH_VACANT (*ovp))
 462           {
 463             void **slot = hash_find_slot_strcached (ht, *ovp);
 464             *slot = *ovp;
 465           }
 466       }
 467   else
 468     for (ovp = old_vec; ovp < &old_vec[old_ht_size]; ovp++)
 469       {
 470         if (! HASH_VACANT (*ovp))
 471           {
 472             void **slot = hash_find_slot (ht, *ovp);
 473             *slot = *ovp;
 474           }
 475       }
 476 #endif /* CONFIG_WITH_STRCACHE2 */
 477   ht->ht_empty_slots = ht->ht_size - ht->ht_fill;
 478   free (old_vec);
 479 }
 480
 481 void
 482 hash_print_stats (struct hash_table *ht, FILE *out_FILE)
 483 {
 484   /* GKM FIXME: honor NO_FLOAT */
 485   fprintf (out_FILE, _("Load=%ld/%ld=%.0f%%, "), ht->ht_fill, ht->ht_size,
 486            100.0 * (double) ht->ht_fill / (double) ht->ht_size);
 487   fprintf (out_FILE, _("Rehash=%d, "), ht->ht_rehashes);
 488   MAKE_STATS(
 489   fprintf (out_FILE, _("Collisions=%ld/%ld=%.0f%%"), ht->ht_collisions, ht->ht_lookups,
 490            (ht->ht_lookups
 491             ? (100.0 * (double) ht->ht_collisions / (double) ht->ht_lookups)
 492             : 0));
 493   );
 494 }
 495
 496 /* Dump all items into a NULL-terminated vector.  Use the
 497    user-supplied vector, or malloc one.  */
 498
 499 void **
 500 hash_dump (struct hash_table *ht, void **vector_0, qsort_cmp_t compare)
 501 {
 502   void **vector;
 503   void **slot;
 504   void **end = &ht->ht_vec[ht->ht_size];
 505
 506   if (vector_0 == 0)
 507     vector_0 = MALLOC (void *, ht->ht_fill + 1);
 508   vector = vector_0;
 509
 510   for (slot = ht->ht_vec; slot < end; slot++)
 511     if (!HASH_VACANT (*slot))
 512       *vector++ = *slot;
 513   *vector = 0;
 514
 515   if (compare)
 516     qsort (vector_0, ht->ht_fill, sizeof (void *), compare);
 517   return vector_0;
 518 }
 519
 520 /* Round a given number up to the nearest power of 2. */
 521
 522 static unsigned long
 523 round_up_2 (unsigned long n)
 524 {
 525   n |= (n >> 1);
 526   n |= (n >> 2);
 527   n |= (n >> 4);
 528   n |= (n >> 8);
 529   n |= (n >> 16);
 530
 531 #if !defined(HAVE_LIMITS_H) || ULONG_MAX > 4294967295
 532   /* We only need this on systems where unsigned long is >32 bits.  */
 533   n |= (n >> 32);
 534 #endif
 535
 536   return n + 1;
 537 }