1 /* hash - hashing table processing.
2 Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc.
3 Written by Jim Meyering, 1992.
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)
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.
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software Foundation,
17 Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
19 /* A generic hash table package. */
21 /* Define USE_OBSTACK to 1 if you want the allocator to use obstacks instead
22 of malloc. If you change USE_OBSTACK, you have to recompile! */
33 typedef enum {false = 0, true = 1} bool;
38 #ifndef HAVE_DECL_FREE
39 'this configure-time declaration test was not run'
45 #ifndef HAVE_DECL_MALLOC
46 'this configure-time declaration test was not run'
54 # ifndef obstack_chunk_alloc
55 # define obstack_chunk_alloc malloc
57 # ifndef obstack_chunk_free
58 # define obstack_chunk_free free
64 /* A hash table contains many internal entries, each holding a pointer to
65 some user provided data (also called a user entry). An entry indistinctly
66 refers to both the internal entry and its associated user entry. A user
67 entry contents may be hashed by a randomization function (the hashing
68 function, or just `hasher' for short) into a number (or `slot') between 0
69 and the current table size. At each slot position in the hash table,
70 starts a linked chain of entries for which the user data all hash to this
71 slot. A bucket is the collection of all entries hashing to the same slot.
73 A good `hasher' function will distribute entries rather evenly in buckets.
74 In the ideal case, the length of each bucket is roughly the number of
75 entries divided by the table size. Finding the slot for a data is usually
76 done in constant time by the `hasher', and the later finding of a precise
77 entry is linear in time with the size of the bucket. Consequently, a
78 larger hash table size (that is, a larger number of buckets) is prone to
79 yielding shorter chains, *given* the `hasher' function behaves properly.
81 Long buckets slow down the lookup algorithm. One might use big hash table
82 sizes in hope to reduce the average length of buckets, but this might
83 become inordinate, as unused slots in the hash table take some space. The
84 best bet is to make sure you are using a good `hasher' function (beware
85 that those are not that easy to write! :-), and to use a table size
86 larger than the actual number of entries. */
88 /* If an insertion makes the ratio of nonempty buckets to table size larger
89 than the growth threshold (a number between 0.0 and 1.0), then increase
90 the table size by multiplying by the growth factor (a number greater than
91 1.0). The growth threshold defaults to 0.8, and the growth factor
92 defaults to 1.414, meaning that the table will have doubled its size
93 every second time 80% of the buckets get used. */
94 #define DEFAULT_GROWTH_THRESHOLD 0.8
95 #define DEFAULT_GROWTH_FACTOR 1.414
97 /* If a deletion empties a bucket and causes the ratio of used buckets to
98 table size to become smaller than the shrink threshold (a number between
99 0.0 and 1.0), then shrink the table by multiplying by the shrink factor (a
100 number greater than the shrink threshold but smaller than 1.0). The shrink
101 threshold and factor default to 0.0 and 1.0, meaning that the table never
103 #define DEFAULT_SHRINK_THRESHOLD 0.0
104 #define DEFAULT_SHRINK_FACTOR 1.0
106 /* Use this to initialize or reset a TUNING structure to
107 some sensible values. */
108 static const Hash_tuning default_tuning =
110 DEFAULT_SHRINK_THRESHOLD,
111 DEFAULT_SHRINK_FACTOR,
112 DEFAULT_GROWTH_THRESHOLD,
113 DEFAULT_GROWTH_FACTOR,
117 /* Information and lookup. */
119 /* The following few functions provide information about the overall hash
120 table organization: the number of entries, number of buckets and maximum
121 length of buckets. */
123 /* Return the number of buckets in the hash table. The table size, the total
124 number of buckets (used plus unused), or the maximum number of slots, are
125 the same quantity. */
128 hash_get_n_buckets (const Hash_table *table)
130 return table->n_buckets;
133 /* Return the number of slots in use (non-empty buckets). */
136 hash_get_n_buckets_used (const Hash_table *table)
138 return table->n_buckets_used;
141 /* Return the number of active entries. */
144 hash_get_n_entries (const Hash_table *table)
146 return table->n_entries;
149 /* Return the length of the longest chain (bucket). */
152 hash_get_max_bucket_length (const Hash_table *table)
154 struct hash_entry *bucket;
155 unsigned max_bucket_length = 0;
157 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
161 struct hash_entry *cursor = bucket;
162 unsigned bucket_length = 1;
164 while (cursor = cursor->next, cursor)
167 if (bucket_length > max_bucket_length)
168 max_bucket_length = bucket_length;
172 return max_bucket_length;
175 /* Do a mild validation of a hash table, by traversing it and checking two
179 hash_table_ok (const Hash_table *table)
181 struct hash_entry *bucket;
182 unsigned n_buckets_used = 0;
183 unsigned n_entries = 0;
185 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
189 struct hash_entry *cursor = bucket;
191 /* Count bucket head. */
195 /* Count bucket overflow. */
196 while (cursor = cursor->next, cursor)
201 if (n_buckets_used == table->n_buckets_used && n_entries == table->n_entries)
208 hash_print_statistics (const Hash_table *table, FILE *stream)
210 unsigned n_entries = hash_get_n_entries (table);
211 unsigned n_buckets = hash_get_n_buckets (table);
212 unsigned n_buckets_used = hash_get_n_buckets_used (table);
213 unsigned max_bucket_length = hash_get_max_bucket_length (table);
215 fprintf (stream, "# entries: %u\n", n_entries);
216 fprintf (stream, "# buckets: %u\n", n_buckets);
217 fprintf (stream, "# buckets used: %u (%.2f%%)\n", n_buckets_used,
218 (100.0 * n_buckets_used) / n_buckets);
219 fprintf (stream, "max bucket length: %u\n", max_bucket_length);
222 /* If ENTRY matches an entry already in the hash table, return the
223 entry from the table. Otherwise, return NULL. */
226 hash_lookup (const Hash_table *table, const void *entry)
228 struct hash_entry *bucket
229 = table->bucket + table->hasher (entry, table->n_buckets);
230 struct hash_entry *cursor;
232 assert (bucket < table->bucket_limit);
234 if (bucket->data == NULL)
237 for (cursor = bucket; cursor; cursor = cursor->next)
238 if (table->comparator (entry, cursor->data))
246 /* The functions in this page traverse the hash table and process the
247 contained entries. For the traversal to work properly, the hash table
248 should not be resized nor modified while any particular entry is being
249 processed. In particular, entries should not be added or removed. */
251 /* Return the first data in the table, or NULL if the table is empty. */
254 hash_get_first (const Hash_table *table)
256 struct hash_entry *bucket;
258 if (table->n_entries == 0)
261 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
268 /* Return the user data for the entry following ENTRY, where ENTRY has been
269 returned by a previous call to either `hash_get_first' or `hash_get_next'.
270 Return NULL if there is no more entries. */
273 hash_get_next (const Hash_table *table, const void *entry)
275 struct hash_entry *bucket
276 = table->bucket + table->hasher (entry, table->n_buckets);
277 struct hash_entry *cursor;
279 assert (bucket < table->bucket_limit);
281 /* Find next entry in the same bucket. */
282 for (cursor = bucket; cursor; cursor = cursor->next)
283 if (cursor->data == entry && cursor->next)
284 return cursor->next->data;
286 /* Find first entry in any subsequent bucket. */
287 for (; bucket < table->bucket_limit; bucket++)
295 /* Fill BUFFER with pointers to active user entries in the hash table, then
296 return the number of pointers copied. Do not copy more than BUFFER_SIZE
300 hash_get_entries (const Hash_table *table, void **buffer,
301 unsigned buffer_size)
303 unsigned counter = 0;
304 struct hash_entry *bucket;
305 struct hash_entry *cursor;
307 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
311 for (cursor = bucket; cursor; cursor = cursor->next)
313 if (counter >= buffer_size)
315 buffer[counter++] = cursor->data;
323 /* Call a PROCESSOR function for each entry of a hash table, and return the
324 number of entries for which the processor function returned success. A
325 pointer to some PROCESSOR_DATA which will be made available to each call to
326 the processor function. The PROCESSOR accepts two arguments: the first is
327 the user entry being walked into, the second is the value of PROCESSOR_DATA
328 as received. The walking continue for as long as the PROCESSOR function
329 returns nonzero. When it returns zero, the walking is interrupted. */
332 hash_do_for_each (const Hash_table *table, Hash_processor processor,
333 void *processor_data)
335 unsigned counter = 0;
336 struct hash_entry *bucket;
337 struct hash_entry *cursor;
339 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
343 for (cursor = bucket; cursor; cursor = cursor->next)
345 if (!(*processor) (cursor->data, processor_data))
355 /* Allocation and clean-up. */
357 /* Return a hash index for a NUL-terminated STRING between 0 and N_BUCKETS-1.
358 This is a convenience routine for constructing other hashing functions. */
362 /* About hashings, Paul Eggert writes to me (FP), on 1994-01-01: "Please see
363 B. J. McKenzie, R. Harries & T. Bell, Selecting a hashing algorithm,
364 Software--practice & experience 20, 2 (Feb 1990), 209-224. Good hash
365 algorithms tend to be domain-specific, so what's good for [diffutils'] io.c
366 may not be good for your application." */
369 hash_string (const char *string, unsigned n_buckets)
374 # define ROTATE_LEFT(Value, Shift) \
375 ((Value) << (Shift) | (Value) >> ((sizeof (unsigned) * CHAR_BIT) - (Shift)))
376 # define HASH_ONE_CHAR(Value, Byte) \
377 ((Byte) + ROTATE_LEFT (Value, 7))
381 for (; *string; string++)
382 value = HASH_ONE_CHAR (value, *(const unsigned char *) string);
383 return value % n_buckets;
386 # undef HASH_ONE_CHAR
389 #else /* not USE_DIFF_HASH */
391 /* This one comes from `recode', and performs a bit better than the above as
392 per a few experiments. It is inspired from a hashing routine found in the
393 very old Cyber `snoop', itself written in typical Greg Mansfield style.
394 (By the way, what happened to this excellent man? Is he still alive?) */
397 hash_string (const char *string, unsigned n_buckets)
402 value = ((value * 31 + (int) *(const unsigned char *) string++)
407 #endif /* not USE_DIFF_HASH */
409 /* Return true if CANDIDATE is a prime number. CANDIDATE should be an odd
410 number at least equal to 11. */
413 is_prime (unsigned long candidate)
415 unsigned long divisor = 3;
416 unsigned long square = divisor * divisor;
418 while (square < candidate && (candidate % divisor))
421 square += 4 * divisor;
425 return candidate % divisor != 0;
428 /* Round a given CANDIDATE number up to the nearest prime, and return that
429 prime. Primes lower than 10 are merely skipped. */
432 next_prime (unsigned long candidate)
434 /* Skip small primes. */
438 /* Make it definitely odd. */
441 while (!is_prime (candidate))
448 hash_reset_tuning (Hash_tuning *tuning)
450 *tuning = default_tuning;
453 /* For the given hash TABLE, check the user supplied tuning structure for
454 reasonable values, and return true if there is no gross error with it.
455 Otherwise, definitively reset the TUNING field to some acceptable default
456 in the hash table (that is, the user loses the right of further modifying
457 tuning arguments), and return false. */
460 check_tuning (Hash_table *table)
462 const Hash_tuning *tuning = table->tuning;
464 if (tuning->growth_threshold > 0.0
465 && tuning->growth_threshold < 1.0
466 && tuning->growth_factor > 1.0
467 && tuning->shrink_threshold >= 0.0
468 && tuning->shrink_threshold < 1.0
469 && tuning->shrink_factor > tuning->shrink_threshold
470 && tuning->shrink_factor <= 1.0
471 && tuning->shrink_threshold < tuning->growth_threshold)
474 table->tuning = &default_tuning;
478 /* Allocate and return a new hash table, or NULL upon failure. The initial
479 number of buckets is automatically selected so as to _guarantee_ that you
480 may insert at least CANDIDATE different user entries before any growth of
481 the hash table size occurs. So, if have a reasonably tight a-priori upper
482 bound on the number of entries you intend to insert in the hash table, you
483 may save some table memory and insertion time, by specifying it here. If
484 the IS_N_BUCKETS field of the TUNING structure is true, the CANDIDATE
485 argument has its meaning changed to the wanted number of buckets.
487 TUNING points to a structure of user-supplied values, in case some fine
488 tuning is wanted over the default behavior of the hasher. If TUNING is
489 NULL, the default tuning parameters are used instead.
491 The user-supplied HASHER function should be provided. It accepts two
492 arguments ENTRY and TABLE_SIZE. It computes, by hashing ENTRY contents, a
493 slot number for that entry which should be in the range 0..TABLE_SIZE-1.
494 This slot number is then returned.
496 The user-supplied COMPARATOR function should be provided. It accepts two
497 arguments pointing to user data, it then returns true for a pair of entries
498 that compare equal, or false otherwise. This function is internally called
499 on entries which are already known to hash to the same bucket index.
501 The user-supplied DATA_FREER function, when not NULL, may be later called
502 with the user data as an argument, just before the entry containing the
503 data gets freed. This happens from within `hash_free' or `hash_clear'.
504 You should specify this function only if you want these functions to free
505 all of your `data' data. This is typically the case when your data is
506 simply an auxiliary struct that you have malloc'd to aggregate several
510 hash_initialize (unsigned candidate, const Hash_tuning *tuning,
511 Hash_hasher hasher, Hash_comparator comparator,
512 Hash_data_freer data_freer)
515 struct hash_entry *bucket;
517 if (hasher == NULL || comparator == NULL)
520 table = (Hash_table *) malloc (sizeof (Hash_table));
525 tuning = &default_tuning;
526 table->tuning = tuning;
527 if (!check_tuning (table))
529 /* Fail if the tuning options are invalid. This is the only occasion
530 when the user gets some feedback about it. Once the table is created,
531 if the user provides invalid tuning options, we silently revert to
532 using the defaults, and ignore further request to change the tuning
539 = next_prime (tuning->is_n_buckets ? candidate
540 : (unsigned) (candidate / tuning->growth_threshold));
542 table->bucket = (struct hash_entry *)
543 malloc (table->n_buckets * sizeof (struct hash_entry));
544 if (table->bucket == NULL)
549 table->bucket_limit = table->bucket + table->n_buckets;
551 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
556 table->n_buckets_used = 0;
557 table->n_entries = 0;
559 table->hasher = hasher;
560 table->comparator = comparator;
561 table->data_freer = data_freer;
563 table->free_entry_list = NULL;
565 obstack_init (&table->entry_stack);
570 /* Make all buckets empty, placing any chained entries on the free list.
571 Apply the user-specified function data_freer (if any) to the datas of any
575 hash_clear (Hash_table *table)
577 struct hash_entry *bucket;
578 struct hash_entry *cursor;
580 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
584 /* Free the bucket overflow. */
585 for (cursor = bucket->next; cursor; cursor = cursor->next)
587 if (table->data_freer)
588 (*table->data_freer) (cursor->data);
591 /* Relinking is done one entry at a time, as it is to be expected
592 that overflows are either rare or short. */
593 cursor->next = table->free_entry_list;
594 table->free_entry_list = cursor;
597 /* Free the bucket head. */
598 if (table->data_freer)
599 (*table->data_freer) (bucket->data);
605 table->n_buckets_used = 0;
606 table->n_entries = 0;
609 /* Reclaim all storage associated with a hash table. If a data_freer
610 function has been supplied by the user when the hash table was created,
611 this function applies it to the data of each entry before freeing that
615 hash_free (Hash_table *table)
617 struct hash_entry *bucket;
618 struct hash_entry *cursor;
619 struct hash_entry *next;
621 /* Call the user data_freer function. */
622 if (table->data_freer && table->n_entries)
624 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
628 for (cursor = bucket; cursor; cursor = cursor->next)
630 (*table->data_freer) (cursor->data);
638 obstack_free (&table->entry_stack, NULL);
642 /* Free all bucket overflowed entries. */
643 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
645 for (cursor = bucket->next; cursor; cursor = next)
652 /* Also reclaim the internal list of previously freed entries. */
653 for (cursor = table->free_entry_list; cursor; cursor = next)
661 /* Free the remainder of the hash table structure. */
662 free (table->bucket);
666 /* Insertion and deletion. */
668 /* Get a new hash entry for a bucket overflow, possibly by reclying a
669 previously freed one. If this is not possible, allocate a new one. */
671 static struct hash_entry *
672 allocate_entry (Hash_table *table)
674 struct hash_entry *new;
676 if (table->free_entry_list)
678 new = table->free_entry_list;
679 table->free_entry_list = new->next;
684 new = (struct hash_entry *)
685 obstack_alloc (&table->entry_stack, sizeof (struct hash_entry));
687 new = (struct hash_entry *) malloc (sizeof (struct hash_entry));
694 /* Free a hash entry which was part of some bucket overflow,
695 saving it for later recycling. */
698 free_entry (Hash_table *table, struct hash_entry *entry)
701 entry->next = table->free_entry_list;
702 table->free_entry_list = entry;
705 /* This private function is used to help with insertion and deletion. When
706 ENTRY matches an entry in the table, return a pointer to the corresponding
707 user data and set *BUCKET_HEAD to the head of the selected bucket.
708 Otherwise, return NULL. When DELETE is true and ENTRY matches an entry in
709 the table, unlink the matching entry. */
712 hash_find_entry (Hash_table *table, const void *entry,
713 struct hash_entry **bucket_head, bool delete)
715 struct hash_entry *bucket
716 = table->bucket + table->hasher (entry, table->n_buckets);
717 struct hash_entry *cursor;
719 assert (bucket < table->bucket_limit);
720 *bucket_head = bucket;
722 /* Test for empty bucket. */
723 if (bucket->data == NULL)
726 /* Check if then entry is found as the bucket head. */
727 if ((*table->comparator) (entry, bucket->data))
729 void *data = bucket->data;
735 struct hash_entry *next = bucket->next;
737 /* Bump the first overflow entry into the bucket head, then save
738 the previous first overflow entry for later recycling. */
740 free_entry (table, next);
751 /* Scan the bucket overflow. */
752 for (cursor = bucket; cursor->next; cursor = cursor->next)
754 if ((*table->comparator) (entry, cursor->next->data))
756 void *data = cursor->next->data;
760 struct hash_entry *next = cursor->next;
762 /* Unlink the entry to delete, then save the freed entry for later
764 cursor->next = next->next;
765 free_entry (table, next);
772 /* No entry found. */
776 /* For an already existing hash table, change the number of buckets through
777 specifying CANDIDATE. The contents of the hash table are preserved. The
778 new number of buckets is automatically selected so as to _guarantee_ that
779 the table may receive at least CANDIDATE different user entries, including
780 those already in the table, before any other growth of the hash table size
781 occurs. If TUNING->IS_N_BUCKETS is true, then CANDIDATE specifies the
782 exact number of buckets desired. */
785 hash_rehash (Hash_table *table, unsigned candidate)
787 Hash_table *new_table;
788 struct hash_entry *bucket;
789 struct hash_entry *cursor;
790 struct hash_entry *next;
792 new_table = hash_initialize (candidate, table->tuning, table->hasher,
793 table->comparator, table->data_freer);
794 if (new_table == NULL)
797 /* Merely reuse the extra old space into the new table. */
799 obstack_free (&new_table->entry_stack, NULL);
800 new_table->entry_stack = table->entry_stack;
802 new_table->free_entry_list = table->free_entry_list;
804 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
806 for (cursor = bucket; cursor; cursor = next)
808 void *data = cursor->data;
809 struct hash_entry *new_bucket
811 + new_table->hasher (data, new_table->n_buckets));
813 assert (new_bucket < new_table->bucket_limit);
816 if (new_bucket->data)
818 if (cursor == bucket)
820 /* Allocate or recycle an entry, when moving from a bucket
821 header into a bucket overflow. */
822 struct hash_entry *new_entry = allocate_entry (new_table);
824 if (new_entry == NULL)
827 new_entry->data = data;
828 new_entry->next = new_bucket->next;
829 new_bucket->next = new_entry;
833 /* Merely relink an existing entry, when moving from a
834 bucket overflow into a bucket overflow. */
835 cursor->next = new_bucket->next;
836 new_bucket->next = cursor;
841 /* Free an existing entry, when moving from a bucket
842 overflow into a bucket header. Also take care of the
843 simple case of moving from a bucket header into a bucket
845 new_bucket->data = data;
846 new_table->n_buckets_used++;
847 if (cursor != bucket)
848 free_entry (new_table, cursor);
852 free (table->bucket);
853 table->bucket = new_table->bucket;
854 table->bucket_limit = new_table->bucket_limit;
855 table->n_buckets = new_table->n_buckets;
856 table->n_buckets_used = new_table->n_buckets_used;
857 /* table->n_entries already holds its value. */
859 table->entry_stack = new_table->entry_stack;
866 /* If ENTRY matches an entry already in the hash table, return the pointer
867 to the entry from the table. Otherwise, insert ENTRY and return ENTRY.
868 Return NULL if the storage required for insertion cannot be allocated. */
871 hash_insert (Hash_table *table, const void *entry)
874 struct hash_entry *bucket;
876 assert (entry); /* cannot insert a NULL entry */
878 /* If there's a matching entry already in the table, return that. */
879 if ((data = hash_find_entry (table, entry, &bucket, false)) != NULL)
882 /* ENTRY is not matched, it should be inserted. */
886 struct hash_entry *new_entry = allocate_entry (table);
888 if (new_entry == NULL)
891 /* Add ENTRY in the overflow of the bucket. */
893 new_entry->data = (void *) entry;
894 new_entry->next = bucket->next;
895 bucket->next = new_entry;
897 return (void *) entry;
900 /* Add ENTRY right in the bucket head. */
902 bucket->data = (void *) entry;
904 table->n_buckets_used++;
906 /* If the growth threshold of the buckets in use has been reached, increase
907 the table size and rehash. There's no point in checking the number of
908 entries: if the hashing function is ill-conditioned, rehashing is not
909 likely to improve it. */
911 if (table->n_buckets_used
912 > table->tuning->growth_threshold * table->n_buckets)
914 /* Check more fully, before starting real work. If tuning arguments
915 became invalid, the second check will rely on proper defaults. */
916 check_tuning (table);
917 if (table->n_buckets_used
918 > table->tuning->growth_threshold * table->n_buckets)
920 const Hash_tuning *tuning = table->tuning;
922 = (unsigned) (tuning->is_n_buckets
923 ? (table->n_buckets * tuning->growth_factor)
924 : (table->n_buckets * tuning->growth_factor
925 * tuning->growth_threshold));
927 /* If the rehash fails, arrange to return NULL. */
928 if (!hash_rehash (table, candidate))
933 return (void *) entry;
936 /* If ENTRY is already in the table, remove it and return the just-deleted
937 data (the user may want to deallocate its storage). If ENTRY is not in the
938 table, don't modify the table and return NULL. */
941 hash_delete (Hash_table *table, const void *entry)
944 struct hash_entry *bucket;
946 if (data = hash_find_entry (table, entry, &bucket, true), !data)
952 table->n_buckets_used--;
954 /* If the shrink threshold of the buckets in use has been reached,
955 rehash into a smaller table. */
957 if (table->n_buckets_used
958 < table->tuning->shrink_threshold * table->n_buckets)
960 /* Check more fully, before starting real work. If tuning arguments
961 became invalid, the second check will rely on proper defaults. */
962 check_tuning (table);
963 if (table->n_buckets_used
964 < table->tuning->shrink_threshold * table->n_buckets)
966 const Hash_tuning *tuning = table->tuning;
968 = (unsigned) (tuning->is_n_buckets
969 ? table->n_buckets * tuning->shrink_factor
970 : (table->n_buckets * tuning->shrink_factor
971 * tuning->growth_threshold));
973 hash_rehash (table, candidate);
986 hash_print (const Hash_table *table)
988 struct hash_entry *bucket;
990 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
992 struct hash_entry *cursor;
995 printf ("%d:\n", slot);
997 for (cursor = bucket; cursor; cursor = cursor->next)
999 char *s = (char *) cursor->data;
1001 printf (" %s\n", s);
1006 #endif /* TESTING */