lib/hash.c

   1 /* hash - hashing table processing.
   2
   3    Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003 Free Software
   4    Foundation, Inc.
   5
   6    Written by Jim Meyering, 1992.
   7
   8    This program is free software; you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation; either version 2, or (at your option)
  11    any later version.
  12
  13    This program is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program; if not, write to the Free Software Foundation,
  20    Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
  21
  22 /* A generic hash table package.  */
  23
  24 /* Define USE_OBSTACK to 1 if you want the allocator to use obstacks instead
  25    of malloc.  If you change USE_OBSTACK, you have to recompile!  */
  26
  27 #if HAVE_CONFIG_H
  28 # include <config.h>
  29 #endif
  30
  31 #include "hash.h"
  32
  33 #include <limits.h>
  34 #include <stdio.h>
  35 #include <stdlib.h>
  36
  37 #if USE_OBSTACK
  38 # include "obstack.h"
  39 # ifndef obstack_chunk_alloc
  40 #  define obstack_chunk_alloc malloc
  41 # endif
  42 # ifndef obstack_chunk_free
  43 #  define obstack_chunk_free free
  44 # endif
  45 #endif
  46
  47 #ifndef SIZE_MAX
  48 # define SIZE_MAX ((size_t) -1)
  49 #endif
  50
  51 struct hash_table
  52   {
  53     /* The array of buckets starts at BUCKET and extends to BUCKET_LIMIT-1,
  54        for a possibility of N_BUCKETS.  Among those, N_BUCKETS_USED buckets
  55        are not empty, there are N_ENTRIES active entries in the table.  */
  56     struct hash_entry *bucket;
  57     struct hash_entry const *bucket_limit;
  58     size_t n_buckets;
  59     size_t n_buckets_used;
  60     size_t n_entries;
  61
  62     /* Tuning arguments, kept in a physicaly separate structure.  */
  63     const Hash_tuning *tuning;
  64
  65     /* Three functions are given to `hash_initialize', see the documentation
  66        block for this function.  In a word, HASHER randomizes a user entry
  67        into a number up from 0 up to some maximum minus 1; COMPARATOR returns
  68        true if two user entries compare equally; and DATA_FREER is the cleanup
  69        function for a user entry.  */
  70     Hash_hasher hasher;
  71     Hash_comparator comparator;
  72     Hash_data_freer data_freer;
  73
  74     /* A linked list of freed struct hash_entry structs.  */
  75     struct hash_entry *free_entry_list;
  76
  77 #if USE_OBSTACK
  78     /* Whenever obstacks are used, it is possible to allocate all overflowed
  79        entries into a single stack, so they all can be freed in a single
  80        operation.  It is not clear if the speedup is worth the trouble.  */
  81     struct obstack entry_stack;
  82 #endif
  83   };
  84
  85 /* A hash table contains many internal entries, each holding a pointer to
  86    some user provided data (also called a user entry).  An entry indistinctly
  87    refers to both the internal entry and its associated user entry.  A user
  88    entry contents may be hashed by a randomization function (the hashing
  89    function, or just `hasher' for short) into a number (or `slot') between 0
  90    and the current table size.  At each slot position in the hash table,
  91    starts a linked chain of entries for which the user data all hash to this
  92    slot.  A bucket is the collection of all entries hashing to the same slot.
  93
  94    A good `hasher' function will distribute entries rather evenly in buckets.
  95    In the ideal case, the length of each bucket is roughly the number of
  96    entries divided by the table size.  Finding the slot for a data is usually
  97    done in constant time by the `hasher', and the later finding of a precise
  98    entry is linear in time with the size of the bucket.  Consequently, a
  99    larger hash table size (that is, a larger number of buckets) is prone to
 100    yielding shorter chains, *given* the `hasher' function behaves properly.
 101
 102    Long buckets slow down the lookup algorithm.  One might use big hash table
 103    sizes in hope to reduce the average length of buckets, but this might
 104    become inordinate, as unused slots in the hash table take some space.  The
 105    best bet is to make sure you are using a good `hasher' function (beware
 106    that those are not that easy to write! :-), and to use a table size
 107    larger than the actual number of entries.  */
 108
 109 /* If an insertion makes the ratio of nonempty buckets to table size larger
 110    than the growth threshold (a number between 0.0 and 1.0), then increase
 111    the table size by multiplying by the growth factor (a number greater than
 112    1.0).  The growth threshold defaults to 0.8, and the growth factor
 113    defaults to 1.414, meaning that the table will have doubled its size
 114    every second time 80% of the buckets get used.  */
 115 #define DEFAULT_GROWTH_THRESHOLD 0.8
 116 #define DEFAULT_GROWTH_FACTOR 1.414
 117
 118 /* If a deletion empties a bucket and causes the ratio of used buckets to
 119    table size to become smaller than the shrink threshold (a number between
 120    0.0 and 1.0), then shrink the table by multiplying by the shrink factor (a
 121    number greater than the shrink threshold but smaller than 1.0).  The shrink
 122    threshold and factor default to 0.0 and 1.0, meaning that the table never
 123    shrinks.  */
 124 #define DEFAULT_SHRINK_THRESHOLD 0.0
 125 #define DEFAULT_SHRINK_FACTOR 1.0
 126
 127 /* Use this to initialize or reset a TUNING structure to
 128    some sensible values. */
 129 static const Hash_tuning default_tuning =
 130   {
 131     DEFAULT_SHRINK_THRESHOLD,
 132     DEFAULT_SHRINK_FACTOR,
 133     DEFAULT_GROWTH_THRESHOLD,
 134     DEFAULT_GROWTH_FACTOR,
 135     false
 136   };
 137
 138 /* Information and lookup.  */
 139
 140 /* The following few functions provide information about the overall hash
 141    table organization: the number of entries, number of buckets and maximum
 142    length of buckets.  */
 143
 144 /* Return the number of buckets in the hash table.  The table size, the total
 145    number of buckets (used plus unused), or the maximum number of slots, are
 146    the same quantity.  */
 147
 148 size_t
 149 hash_get_n_buckets (const Hash_table *table)
 150 {
 151   return table->n_buckets;
 152 }
 153
 154 /* Return the number of slots in use (non-empty buckets).  */
 155
 156 size_t
 157 hash_get_n_buckets_used (const Hash_table *table)
 158 {
 159   return table->n_buckets_used;
 160 }
 161
 162 /* Return the number of active entries.  */
 163
 164 size_t
 165 hash_get_n_entries (const Hash_table *table)
 166 {
 167   return table->n_entries;
 168 }
 169
 170 /* Return the length of the longest chain (bucket).  */
 171
 172 size_t
 173 hash_get_max_bucket_length (const Hash_table *table)
 174 {
 175   struct hash_entry const *bucket;
 176   size_t max_bucket_length = 0;
 177
 178   for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
 179     {
 180       if (bucket->data)
 181         {
 182           struct hash_entry const *cursor = bucket;
 183           size_t bucket_length = 1;
 184
 185           while (cursor = cursor->next, cursor)
 186             bucket_length++;
 187
 188           if (bucket_length > max_bucket_length)
 189             max_bucket_length = bucket_length;
 190         }
 191     }
 192
 193   return max_bucket_length;
 194 }
 195
 196 /* Do a mild validation of a hash table, by traversing it and checking two
 197    statistics.  */
 198
 199 bool
 200 hash_table_ok (const Hash_table *table)
 201 {
 202   struct hash_entry const *bucket;
 203   size_t n_buckets_used = 0;
 204   size_t n_entries = 0;
 205
 206   for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
 207     {
 208       if (bucket->data)
 209         {
 210           struct hash_entry const *cursor = bucket;
 211
 212           /* Count bucket head.  */
 213           n_buckets_used++;
 214           n_entries++;
 215
 216           /* Count bucket overflow.  */
 217           while (cursor = cursor->next, cursor)
 218             n_entries++;
 219         }
 220     }
 221
 222   if (n_buckets_used == table->n_buckets_used && n_entries == table->n_entries)
 223     return true;
 224
 225   return false;
 226 }
 227
 228 void
 229 hash_print_statistics (const Hash_table *table, FILE *stream)
 230 {
 231   size_t n_entries = hash_get_n_entries (table);
 232   size_t n_buckets = hash_get_n_buckets (table);
 233   size_t n_buckets_used = hash_get_n_buckets_used (table);
 234   size_t max_bucket_length = hash_get_max_bucket_length (table);
 235
 236   fprintf (stream, "# entries:         %lu\n", (unsigned long int) n_entries);
 237   fprintf (stream, "# buckets:         %lu\n", (unsigned long int) n_buckets);
 238   fprintf (stream, "# buckets used:    %lu (%.2f%%)\n",
 239            (unsigned long int) n_buckets_used,
 240            (100.0 * n_buckets_used) / n_buckets);
 241   fprintf (stream, "max bucket length: %lu\n",
 242            (unsigned long int) max_bucket_length);
 243 }
 244
 245 /* If ENTRY matches an entry already in the hash table, return the
 246    entry from the table.  Otherwise, return NULL.  */
 247
 248 void *
 249 hash_lookup (const Hash_table *table, const void *entry)
 250 {
 251   struct hash_entry const *bucket
 252     = table->bucket + table->hasher (entry, table->n_buckets);
 253   struct hash_entry const *cursor;
 254
 255   if (! (bucket < table->bucket_limit))
 256     abort ();
 257
 258   if (bucket->data == NULL)
 259     return NULL;
 260
 261   for (cursor = bucket; cursor; cursor = cursor->next)
 262     if (table->comparator (entry, cursor->data))
 263       return cursor->data;
 264
 265   return NULL;
 266 }
 267
 268 /* Walking.  */
 269
 270 /* The functions in this page traverse the hash table and process the
 271    contained entries.  For the traversal to work properly, the hash table
 272    should not be resized nor modified while any particular entry is being
 273    processed.  In particular, entries should not be added or removed.  */
 274
 275 /* Return the first data in the table, or NULL if the table is empty.  */
 276
 277 void *
 278 hash_get_first (const Hash_table *table)
 279 {
 280   struct hash_entry const *bucket;
 281
 282   if (table->n_entries == 0)
 283     return NULL;
 284
 285   for (bucket = table->bucket; ; bucket++)
 286     if (! (bucket < table->bucket_limit))
 287       abort ();
 288     else if (bucket->data)
 289       return bucket->data;
 290 }
 291
 292 /* Return the user data for the entry following ENTRY, where ENTRY has been
 293    returned by a previous call to either `hash_get_first' or `hash_get_next'.
 294    Return NULL if there are no more entries.  */
 295
 296 void *
 297 hash_get_next (const Hash_table *table, const void *entry)
 298 {
 299   struct hash_entry const *bucket
 300     = table->bucket + table->hasher (entry, table->n_buckets);
 301   struct hash_entry const *cursor;
 302
 303   if (! (bucket < table->bucket_limit))
 304     abort ();
 305
 306   /* Find next entry in the same bucket.  */
 307   for (cursor = bucket; cursor; cursor = cursor->next)
 308     if (cursor->data == entry && cursor->next)
 309       return cursor->next->data;
 310
 311   /* Find first entry in any subsequent bucket.  */
 312   while (++bucket < table->bucket_limit)
 313     if (bucket->data)
 314       return bucket->data;
 315
 316   /* None found.  */
 317   return NULL;
 318 }
 319
 320 /* Fill BUFFER with pointers to active user entries in the hash table, then
 321    return the number of pointers copied.  Do not copy more than BUFFER_SIZE
 322    pointers.  */
 323
 324 size_t
 325 hash_get_entries (const Hash_table *table, void **buffer,
 326                   size_t buffer_size)
 327 {
 328   size_t counter = 0;
 329   struct hash_entry const *bucket;
 330   struct hash_entry const *cursor;
 331
 332   for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
 333     {
 334       if (bucket->data)
 335         {
 336           for (cursor = bucket; cursor; cursor = cursor->next)
 337             {
 338               if (counter >= buffer_size)
 339                 return counter;
 340               buffer[counter++] = cursor->data;
 341             }
 342         }
 343     }
 344
 345   return counter;
 346 }
 347
 348 /* Call a PROCESSOR function for each entry of a hash table, and return the
 349    number of entries for which the processor function returned success.  A
 350    pointer to some PROCESSOR_DATA which will be made available to each call to
 351    the processor function.  The PROCESSOR accepts two arguments: the first is
 352    the user entry being walked into, the second is the value of PROCESSOR_DATA
 353    as received.  The walking continue for as long as the PROCESSOR function
 354    returns nonzero.  When it returns zero, the walking is interrupted.  */
 355
 356 size_t
 357 hash_do_for_each (const Hash_table *table, Hash_processor processor,
 358                   void *processor_data)
 359 {
 360   size_t counter = 0;
 361   struct hash_entry const *bucket;
 362   struct hash_entry const *cursor;
 363
 364   for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
 365     {
 366       if (bucket->data)
 367         {
 368           for (cursor = bucket; cursor; cursor = cursor->next)
 369             {
 370               if (!(*processor) (cursor->data, processor_data))
 371                 return counter;
 372               counter++;
 373             }
 374         }
 375     }
 376
 377   return counter;
 378 }
 379
 380 /* Allocation and clean-up.  */
 381
 382 /* Return a hash index for a NUL-terminated STRING between 0 and N_BUCKETS-1.
 383    This is a convenience routine for constructing other hashing functions.  */
 384
 385 #if USE_DIFF_HASH
 386
 387 /* About hashings, Paul Eggert writes to me (FP), on 1994-01-01: "Please see
 388    B. J. McKenzie, R. Harries & T. Bell, Selecting a hashing algorithm,
 389    Software--practice & experience 20, 2 (Feb 1990), 209-224.  Good hash
 390    algorithms tend to be domain-specific, so what's good for [diffutils'] io.c
 391    may not be good for your application."  */
 392
 393 size_t
 394 hash_string (const char *string, size_t n_buckets)
 395 {
 396 # define ROTATE_LEFT(Value, Shift) \
 397   ((Value) << (Shift) | (Value) >> ((sizeof (size_t) * CHAR_BIT) - (Shift)))
 398 # define HASH_ONE_CHAR(Value, Byte) \
 399   ((Byte) + ROTATE_LEFT (Value, 7))
 400
 401   size_t value = 0;
 402
 403   for (; *string; string++)
 404     value = HASH_ONE_CHAR (value, (unsigned char) *string);
 405   return value % n_buckets;
 406
 407 # undef ROTATE_LEFT
 408 # undef HASH_ONE_CHAR
 409 }
 410
 411 #else /* not USE_DIFF_HASH */
 412
 413 /* This one comes from `recode', and performs a bit better than the above as
 414    per a few experiments.  It is inspired from a hashing routine found in the
 415    very old Cyber `snoop', itself written in typical Greg Mansfield style.
 416    (By the way, what happened to this excellent man?  Is he still alive?)  */
 417
 418 size_t
 419 hash_string (const char *string, size_t n_buckets)
 420 {
 421   size_t value = 0;
 422
 423   while (*string)
 424     value = (value * 31 + (unsigned char) *string++) % n_buckets;
 425   return value;
 426 }
 427
 428 #endif /* not USE_DIFF_HASH */
 429
 430 /* Return true if CANDIDATE is a prime number.  CANDIDATE should be an odd
 431    number at least equal to 11.  */
 432
 433 static bool
 434 is_prime (size_t candidate)
 435 {
 436   size_t divisor = 3;
 437   size_t square = divisor * divisor;
 438
 439   while (square < candidate && (candidate % divisor))
 440     {
 441       divisor++;
 442       square += 4 * divisor;
 443       divisor++;
 444     }
 445
 446   return (candidate % divisor ? true : false);
 447 }
 448
 449 /* Round a given CANDIDATE number up to the nearest prime, and return that
 450    prime.  Primes lower than 10 are merely skipped.  */
 451
 452 static size_t
 453 next_prime (size_t candidate)
 454 {
 455   /* Skip small primes.  */
 456   if (candidate < 10)
 457     candidate = 10;
 458
 459   /* Make it definitely odd.  */
 460   candidate |= 1;
 461
 462   while (!is_prime (candidate))
 463     candidate += 2;
 464
 465   return candidate;
 466 }
 467
 468 void
 469 hash_reset_tuning (Hash_tuning *tuning)
 470 {
 471   *tuning = default_tuning;
 472 }
 473
 474 /* For the given hash TABLE, check the user supplied tuning structure for
 475    reasonable values, and return true if there is no gross error with it.
 476    Otherwise, definitively reset the TUNING field to some acceptable default
 477    in the hash table (that is, the user loses the right of further modifying
 478    tuning arguments), and return false.  */
 479
 480 static bool
 481 check_tuning (Hash_table *table)
 482 {
 483   const Hash_tuning *tuning = table->tuning;
 484
 485   /* Be a bit stricter than mathematics would require, so that
 486      rounding errors in size calculations do not cause allocations to
 487      fail to grow or shrink as they should.  The smallest allocation
 488      is 11 (due to next_prime's algorithm), so an epsilon of 0.1
 489      should be good enough.  */
 490   float epsilon = 0.1f;
 491
 492   if (epsilon < tuning->growth_threshold
 493       && tuning->growth_threshold < 1 - epsilon
 494       && 1 + epsilon < tuning->growth_factor
 495       && 0 <= tuning->shrink_threshold
 496       && tuning->shrink_threshold + epsilon < tuning->shrink_factor
 497       && tuning->shrink_factor <= 1
 498       && tuning->shrink_threshold + epsilon < tuning->growth_threshold)
 499     return true;
 500
 501   table->tuning = &default_tuning;
 502   return false;
 503 }
 504
 505 /* Allocate and return a new hash table, or NULL upon failure.  The initial
 506    number of buckets is automatically selected so as to _guarantee_ that you
 507    may insert at least CANDIDATE different user entries before any growth of
 508    the hash table size occurs.  So, if have a reasonably tight a-priori upper
 509    bound on the number of entries you intend to insert in the hash table, you
 510    may save some table memory and insertion time, by specifying it here.  If
 511    the IS_N_BUCKETS field of the TUNING structure is true, the CANDIDATE
 512    argument has its meaning changed to the wanted number of buckets.
 513
 514    TUNING points to a structure of user-supplied values, in case some fine
 515    tuning is wanted over the default behavior of the hasher.  If TUNING is
 516    NULL, the default tuning parameters are used instead.
 517
 518    The user-supplied HASHER function should be provided.  It accepts two
 519    arguments ENTRY and TABLE_SIZE.  It computes, by hashing ENTRY contents, a
 520    slot number for that entry which should be in the range 0..TABLE_SIZE-1.
 521    This slot number is then returned.
 522
 523    The user-supplied COMPARATOR function should be provided.  It accepts two
 524    arguments pointing to user data, it then returns true for a pair of entries
 525    that compare equal, or false otherwise.  This function is internally called
 526    on entries which are already known to hash to the same bucket index.
 527
 528    The user-supplied DATA_FREER function, when not NULL, may be later called
 529    with the user data as an argument, just before the entry containing the
 530    data gets freed.  This happens from within `hash_free' or `hash_clear'.
 531    You should specify this function only if you want these functions to free
 532    all of your `data' data.  This is typically the case when your data is
 533    simply an auxiliary struct that you have malloc'd to aggregate several
 534    values.  */
 535
 536 Hash_table *
 537 hash_initialize (size_t candidate, const Hash_tuning *tuning,
 538                  Hash_hasher hasher, Hash_comparator comparator,
 539                  Hash_data_freer data_freer)
 540 {
 541   Hash_table *table;
 542
 543   if (hasher == NULL || comparator == NULL)
 544     return NULL;
 545
 546   table = malloc (sizeof *table);
 547   if (table == NULL)
 548     return NULL;
 549
 550   if (!tuning)
 551     tuning = &default_tuning;
 552   table->tuning = tuning;
 553   if (!check_tuning (table))
 554     {
 555       /* Fail if the tuning options are invalid.  This is the only occasion
 556          when the user gets some feedback about it.  Once the table is created,
 557          if the user provides invalid tuning options, we silently revert to
 558          using the defaults, and ignore further request to change the tuning
 559          options.  */
 560       goto fail;
 561     }
 562
 563   if (!tuning->is_n_buckets)
 564     {
 565       float new_candidate = candidate / tuning->growth_threshold;
 566       if (SIZE_MAX <= new_candidate)
 567         goto fail;
 568       candidate = new_candidate;
 569     }
 570
 571   if (SIZE_MAX / sizeof *table->bucket < candidate)
 572     goto fail;
 573   table->n_buckets = next_prime (candidate);
 574   if (SIZE_MAX / sizeof *table->bucket < table->n_buckets)
 575     goto fail;
 576
 577   table->bucket = calloc (table->n_buckets, sizeof *table->bucket);
 578   table->bucket_limit = table->bucket + table->n_buckets;
 579   table->n_buckets_used = 0;
 580   table->n_entries = 0;
 581
 582   table->hasher = hasher;
 583   table->comparator = comparator;
 584   table->data_freer = data_freer;
 585
 586   table->free_entry_list = NULL;
 587 #if USE_OBSTACK
 588   obstack_init (&table->entry_stack);
 589 #endif
 590   return table;
 591
 592  fail:
 593   free (table);
 594   return NULL;
 595 }
 596
 597 /* Make all buckets empty, placing any chained entries on the free list.
 598    Apply the user-specified function data_freer (if any) to the datas of any
 599    affected entries.  */
 600
 601 void
 602 hash_clear (Hash_table *table)
 603 {
 604   struct hash_entry *bucket;
 605
 606   for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
 607     {
 608       if (bucket->data)
 609         {
 610           struct hash_entry *cursor;
 611           struct hash_entry *next;
 612
 613           /* Free the bucket overflow.  */
 614           for (cursor = bucket->next; cursor; cursor = next)
 615             {
 616               if (table->data_freer)
 617                 (*table->data_freer) (cursor->data);
 618               cursor->data = NULL;
 619
 620               next = cursor->next;
 621               /* Relinking is done one entry at a time, as it is to be expected
 622                  that overflows are either rare or short.  */
 623               cursor->next = table->free_entry_list;
 624               table->free_entry_list = cursor;
 625             }
 626
 627           /* Free the bucket head.  */
 628           if (table->data_freer)
 629             (*table->data_freer) (bucket->data);
 630           bucket->data = NULL;
 631           bucket->next = NULL;
 632         }
 633     }
 634
 635   table->n_buckets_used = 0;
 636   table->n_entries = 0;
 637 }
 638
 639 /* Reclaim all storage associated with a hash table.  If a data_freer
 640    function has been supplied by the user when the hash table was created,
 641    this function applies it to the data of each entry before freeing that
 642    entry.  */
 643
 644 void
 645 hash_free (Hash_table *table)
 646 {
 647   struct hash_entry *bucket;
 648   struct hash_entry *cursor;
 649   struct hash_entry *next;
 650
 651   /* Call the user data_freer function.  */
 652   if (table->data_freer && table->n_entries)
 653     {
 654       for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
 655         {
 656           if (bucket->data)
 657             {
 658               for (cursor = bucket; cursor; cursor = cursor->next)
 659                 {
 660                   (*table->data_freer) (cursor->data);
 661                 }
 662             }
 663         }
 664     }
 665
 666 #if USE_OBSTACK
 667
 668   obstack_free (&table->entry_stack, NULL);
 669
 670 #else
 671
 672   /* Free all bucket overflowed entries.  */
 673   for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
 674     {
 675       for (cursor = bucket->next; cursor; cursor = next)
 676         {
 677           next = cursor->next;
 678           free (cursor);
 679         }
 680     }
 681
 682   /* Also reclaim the internal list of previously freed entries.  */
 683   for (cursor = table->free_entry_list; cursor; cursor = next)
 684     {
 685       next = cursor->next;
 686       free (cursor);
 687     }
 688
 689 #endif
 690
 691   /* Free the remainder of the hash table structure.  */
 692   free (table->bucket);
 693   free (table);
 694 }
 695
 696 /* Insertion and deletion.  */
 697
 698 /* Get a new hash entry for a bucket overflow, possibly by reclying a
 699    previously freed one.  If this is not possible, allocate a new one.  */
 700
 701 static struct hash_entry *
 702 allocate_entry (Hash_table *table)
 703 {
 704   struct hash_entry *new;
 705
 706   if (table->free_entry_list)
 707     {
 708       new = table->free_entry_list;
 709       table->free_entry_list = new->next;
 710     }
 711   else
 712     {
 713 #if USE_OBSTACK
 714       new = obstack_alloc (&table->entry_stack, sizeof *new);
 715 #else
 716       new = malloc (sizeof *new);
 717 #endif
 718     }
 719
 720   return new;
 721 }
 722
 723 /* Free a hash entry which was part of some bucket overflow,
 724    saving it for later recycling.  */
 725
 726 static void
 727 free_entry (Hash_table *table, struct hash_entry *entry)
 728 {
 729   entry->data = NULL;
 730   entry->next = table->free_entry_list;
 731   table->free_entry_list = entry;
 732 }
 733
 734 /* This private function is used to help with insertion and deletion.  When
 735    ENTRY matches an entry in the table, return a pointer to the corresponding
 736    user data and set *BUCKET_HEAD to the head of the selected bucket.
 737    Otherwise, return NULL.  When DELETE is true and ENTRY matches an entry in
 738    the table, unlink the matching entry.  */
 739
 740 static void *
 741 hash_find_entry (Hash_table *table, const void *entry,
 742                  struct hash_entry **bucket_head, bool delete)
 743 {
 744   struct hash_entry *bucket
 745     = table->bucket + table->hasher (entry, table->n_buckets);
 746   struct hash_entry *cursor;
 747
 748   if (! (bucket < table->bucket_limit))
 749     abort ();
 750
 751   *bucket_head = bucket;
 752
 753   /* Test for empty bucket.  */
 754   if (bucket->data == NULL)
 755     return NULL;
 756
 757   /* See if the entry is the first in the bucket.  */
 758   if ((*table->comparator) (entry, bucket->data))
 759     {
 760       void *data = bucket->data;
 761
 762       if (delete)
 763         {
 764           if (bucket->next)
 765             {
 766               struct hash_entry *next = bucket->next;
 767
 768               /* Bump the first overflow entry into the bucket head, then save
 769                  the previous first overflow entry for later recycling.  */
 770               *bucket = *next;
 771               free_entry (table, next);
 772             }
 773           else
 774             {
 775               bucket->data = NULL;
 776             }
 777         }
 778
 779       return data;
 780     }
 781
 782   /* Scan the bucket overflow.  */
 783   for (cursor = bucket; cursor->next; cursor = cursor->next)
 784     {
 785       if ((*table->comparator) (entry, cursor->next->data))
 786         {
 787           void *data = cursor->next->data;
 788
 789           if (delete)
 790             {
 791               struct hash_entry *next = cursor->next;
 792
 793               /* Unlink the entry to delete, then save the freed entry for later
 794                  recycling.  */
 795               cursor->next = next->next;
 796               free_entry (table, next);
 797             }
 798
 799           return data;
 800         }
 801     }
 802
 803   /* No entry found.  */
 804   return NULL;
 805 }
 806
 807 /* For an already existing hash table, change the number of buckets through
 808    specifying CANDIDATE.  The contents of the hash table are preserved.  The
 809    new number of buckets is automatically selected so as to _guarantee_ that
 810    the table may receive at least CANDIDATE different user entries, including
 811    those already in the table, before any other growth of the hash table size
 812    occurs.  If TUNING->IS_N_BUCKETS is true, then CANDIDATE specifies the
 813    exact number of buckets desired.  */
 814
 815 bool
 816 hash_rehash (Hash_table *table, size_t candidate)
 817 {
 818   Hash_table *new_table;
 819   struct hash_entry *bucket;
 820   struct hash_entry *cursor;
 821   struct hash_entry *next;
 822
 823   new_table = hash_initialize (candidate, table->tuning, table->hasher,
 824                                table->comparator, table->data_freer);
 825   if (new_table == NULL)
 826     return false;
 827
 828   /* Merely reuse the extra old space into the new table.  */
 829 #if USE_OBSTACK
 830   obstack_free (&new_table->entry_stack, NULL);
 831   new_table->entry_stack = table->entry_stack;
 832 #endif
 833   new_table->free_entry_list = table->free_entry_list;
 834
 835   for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
 836     if (bucket->data)
 837       for (cursor = bucket; cursor; cursor = next)
 838         {
 839           void *data = cursor->data;
 840           struct hash_entry *new_bucket
 841             = (new_table->bucket
 842                + new_table->hasher (data, new_table->n_buckets));
 843
 844           if (! (new_bucket < new_table->bucket_limit))
 845             abort ();
 846
 847           next = cursor->next;
 848
 849           if (new_bucket->data)
 850             {
 851               if (cursor == bucket)
 852                 {
 853                   /* Allocate or recycle an entry, when moving from a bucket
 854                      header into a bucket overflow.  */
 855                   struct hash_entry *new_entry = allocate_entry (new_table);
 856
 857                   if (new_entry == NULL)
 858                     return false;
 859
 860                   new_entry->data = data;
 861                   new_entry->next = new_bucket->next;
 862                   new_bucket->next = new_entry;
 863                 }
 864               else
 865                 {
 866                   /* Merely relink an existing entry, when moving from a
 867                      bucket overflow into a bucket overflow.  */
 868                   cursor->next = new_bucket->next;
 869                   new_bucket->next = cursor;
 870                 }
 871             }
 872           else
 873             {
 874               /* Free an existing entry, when moving from a bucket
 875                  overflow into a bucket header.  Also take care of the
 876                  simple case of moving from a bucket header into a bucket
 877                  header.  */
 878               new_bucket->data = data;
 879               new_table->n_buckets_used++;
 880               if (cursor != bucket)
 881                 free_entry (new_table, cursor);
 882             }
 883         }
 884
 885   free (table->bucket);
 886   table->bucket = new_table->bucket;
 887   table->bucket_limit = new_table->bucket_limit;
 888   table->n_buckets = new_table->n_buckets;
 889   table->n_buckets_used = new_table->n_buckets_used;
 890   table->free_entry_list = new_table->free_entry_list;
 891   /* table->n_entries already holds its value.  */
 892 #if USE_OBSTACK
 893   table->entry_stack = new_table->entry_stack;
 894 #endif
 895   free (new_table);
 896
 897   return true;
 898 }
 899
 900 /* If ENTRY matches an entry already in the hash table, return the pointer
 901    to the entry from the table.  Otherwise, insert ENTRY and return ENTRY.
 902    Return NULL if the storage required for insertion cannot be allocated.  */
 903
 904 void *
 905 hash_insert (Hash_table *table, const void *entry)
 906 {
 907   void *data;
 908   struct hash_entry *bucket;
 909
 910   /* The caller cannot insert a NULL entry.  */
 911   if (! entry)
 912     abort ();
 913
 914   /* If there's a matching entry already in the table, return that.  */
 915   if ((data = hash_find_entry (table, entry, &bucket, false)) != NULL)
 916     return data;
 917
 918   /* ENTRY is not matched, it should be inserted.  */
 919
 920   if (bucket->data)
 921     {
 922       struct hash_entry *new_entry = allocate_entry (table);
 923
 924       if (new_entry == NULL)
 925         return NULL;
 926
 927       /* Add ENTRY in the overflow of the bucket.  */
 928
 929       new_entry->data = (void *) entry;
 930       new_entry->next = bucket->next;
 931       bucket->next = new_entry;
 932       table->n_entries++;
 933       return (void *) entry;
 934     }
 935
 936   /* Add ENTRY right in the bucket head.  */
 937
 938   bucket->data = (void *) entry;
 939   table->n_entries++;
 940   table->n_buckets_used++;
 941
 942   /* If the growth threshold of the buckets in use has been reached, increase
 943      the table size and rehash.  There's no point in checking the number of
 944      entries:  if the hashing function is ill-conditioned, rehashing is not
 945      likely to improve it.  */
 946
 947   if (table->n_buckets_used
 948       > table->tuning->growth_threshold * table->n_buckets)
 949     {
 950       /* Check more fully, before starting real work.  If tuning arguments
 951          became invalid, the second check will rely on proper defaults.  */
 952       check_tuning (table);
 953       if (table->n_buckets_used
 954           > table->tuning->growth_threshold * table->n_buckets)
 955         {
 956           const Hash_tuning *tuning = table->tuning;
 957           float candidate =
 958             (tuning->is_n_buckets
 959              ? (table->n_buckets * tuning->growth_factor)
 960              : (table->n_buckets * tuning->growth_factor
 961                 * tuning->growth_threshold));
 962
 963           if (SIZE_MAX <= candidate)
 964             return NULL;
 965
 966           /* If the rehash fails, arrange to return NULL.  */
 967           if (!hash_rehash (table, candidate))
 968             entry = NULL;
 969         }
 970     }
 971
 972   return (void *) entry;
 973 }
 974
 975 /* If ENTRY is already in the table, remove it and return the just-deleted
 976    data (the user may want to deallocate its storage).  If ENTRY is not in the
 977    table, don't modify the table and return NULL.  */
 978
 979 void *
 980 hash_delete (Hash_table *table, const void *entry)
 981 {
 982   void *data;
 983   struct hash_entry *bucket;
 984
 985   data = hash_find_entry (table, entry, &bucket, true);
 986   if (!data)
 987     return NULL;
 988
 989   table->n_entries--;
 990   if (!bucket->data)
 991     {
 992       table->n_buckets_used--;
 993
 994       /* If the shrink threshold of the buckets in use has been reached,
 995          rehash into a smaller table.  */
 996
 997       if (table->n_buckets_used
 998           < table->tuning->shrink_threshold * table->n_buckets)
 999         {
1000           /* Check more fully, before starting real work.  If tuning arguments
1001              became invalid, the second check will rely on proper defaults.  */
1002           check_tuning (table);
1003           if (table->n_buckets_used
1004               < table->tuning->shrink_threshold * table->n_buckets)
1005             {
1006               const Hash_tuning *tuning = table->tuning;
1007               size_t candidate =
1008                 (tuning->is_n_buckets
1009                  ? table->n_buckets * tuning->shrink_factor
1010                  : (table->n_buckets * tuning->shrink_factor
1011                     * tuning->growth_threshold));
1012
1013               hash_rehash (table, candidate);
1014             }
1015         }
1016     }
1017
1018   return data;
1019 }
1020
1021 /* Testing.  */
1022
1023 #if TESTING
1024
1025 void
1026 hash_print (const Hash_table *table)
1027 {
1028   struct hash_entry const *bucket;
1029
1030   for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
1031     {
1032       struct hash_entry *cursor;
1033
1034       if (bucket)
1035         printf ("%lu:\n", (unsigned long int) (bucket - table->bucket));
1036
1037       for (cursor = bucket; cursor; cursor = cursor->next)
1038         {
1039           char const *s = cursor->data;
1040           /* FIXME */
1041           if (s)
1042             printf ("  %s\n", s);
1043         }
1044     }
1045 }
1046
1047 #endif /* TESTING */