1 /* hash - hashing table processing.
3 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003 Free Software
6 Written by Jim Meyering, 1992.
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)
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.
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. */
22 /* A generic hash table package. */
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! */
39 # ifndef obstack_chunk_alloc
40 # define obstack_chunk_alloc malloc
42 # ifndef obstack_chunk_free
43 # define obstack_chunk_free free
48 # define SIZE_MAX ((size_t) -1)
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;
59 size_t n_buckets_used;
62 /* Tuning arguments, kept in a physicaly separate structure. */
63 const Hash_tuning *tuning;
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. */
71 Hash_comparator comparator;
72 Hash_data_freer data_freer;
74 /* A linked list of freed struct hash_entry structs. */
75 struct hash_entry *free_entry_list;
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;
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.
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.
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. */
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
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
124 #define DEFAULT_SHRINK_THRESHOLD 0.0
125 #define DEFAULT_SHRINK_FACTOR 1.0
127 /* Use this to initialize or reset a TUNING structure to
128 some sensible values. */
129 static const Hash_tuning default_tuning =
131 DEFAULT_SHRINK_THRESHOLD,
132 DEFAULT_SHRINK_FACTOR,
133 DEFAULT_GROWTH_THRESHOLD,
134 DEFAULT_GROWTH_FACTOR,
138 /* Information and lookup. */
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. */
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. */
149 hash_get_n_buckets (const Hash_table *table)
151 return table->n_buckets;
154 /* Return the number of slots in use (non-empty buckets). */
157 hash_get_n_buckets_used (const Hash_table *table)
159 return table->n_buckets_used;
162 /* Return the number of active entries. */
165 hash_get_n_entries (const Hash_table *table)
167 return table->n_entries;
170 /* Return the length of the longest chain (bucket). */
173 hash_get_max_bucket_length (const Hash_table *table)
175 struct hash_entry const *bucket;
176 size_t max_bucket_length = 0;
178 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
182 struct hash_entry const *cursor = bucket;
183 size_t bucket_length = 1;
185 while (cursor = cursor->next, cursor)
188 if (bucket_length > max_bucket_length)
189 max_bucket_length = bucket_length;
193 return max_bucket_length;
196 /* Do a mild validation of a hash table, by traversing it and checking two
200 hash_table_ok (const Hash_table *table)
202 struct hash_entry const *bucket;
203 size_t n_buckets_used = 0;
204 size_t n_entries = 0;
206 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
210 struct hash_entry const *cursor = bucket;
212 /* Count bucket head. */
216 /* Count bucket overflow. */
217 while (cursor = cursor->next, cursor)
222 if (n_buckets_used == table->n_buckets_used && n_entries == table->n_entries)
229 hash_print_statistics (const Hash_table *table, FILE *stream)
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);
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);
245 /* If ENTRY matches an entry already in the hash table, return the
246 entry from the table. Otherwise, return NULL. */
249 hash_lookup (const Hash_table *table, const void *entry)
251 struct hash_entry const *bucket
252 = table->bucket + table->hasher (entry, table->n_buckets);
253 struct hash_entry const *cursor;
255 if (! (bucket < table->bucket_limit))
258 if (bucket->data == NULL)
261 for (cursor = bucket; cursor; cursor = cursor->next)
262 if (table->comparator (entry, cursor->data))
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. */
275 /* Return the first data in the table, or NULL if the table is empty. */
278 hash_get_first (const Hash_table *table)
280 struct hash_entry const *bucket;
282 if (table->n_entries == 0)
285 for (bucket = table->bucket; ; bucket++)
286 if (! (bucket < table->bucket_limit))
288 else if (bucket->data)
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. */
297 hash_get_next (const Hash_table *table, const void *entry)
299 struct hash_entry const *bucket
300 = table->bucket + table->hasher (entry, table->n_buckets);
301 struct hash_entry const *cursor;
303 if (! (bucket < table->bucket_limit))
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;
311 /* Find first entry in any subsequent bucket. */
312 while (++bucket < table->bucket_limit)
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
325 hash_get_entries (const Hash_table *table, void **buffer,
329 struct hash_entry const *bucket;
330 struct hash_entry const *cursor;
332 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
336 for (cursor = bucket; cursor; cursor = cursor->next)
338 if (counter >= buffer_size)
340 buffer[counter++] = cursor->data;
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. */
357 hash_do_for_each (const Hash_table *table, Hash_processor processor,
358 void *processor_data)
361 struct hash_entry const *bucket;
362 struct hash_entry const *cursor;
364 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
368 for (cursor = bucket; cursor; cursor = cursor->next)
370 if (!(*processor) (cursor->data, processor_data))
380 /* Allocation and clean-up. */
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. */
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." */
394 hash_string (const char *string, size_t n_buckets)
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))
403 for (; *string; string++)
404 value = HASH_ONE_CHAR (value, (unsigned char) *string);
405 return value % n_buckets;
408 # undef HASH_ONE_CHAR
411 #else /* not USE_DIFF_HASH */
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?) */
419 hash_string (const char *string, size_t n_buckets)
424 value = (value * 31 + (unsigned char) *string++) % n_buckets;
428 #endif /* not USE_DIFF_HASH */
430 /* Return true if CANDIDATE is a prime number. CANDIDATE should be an odd
431 number at least equal to 11. */
434 is_prime (size_t candidate)
437 size_t square = divisor * divisor;
439 while (square < candidate && (candidate % divisor))
442 square += 4 * divisor;
446 return (candidate % divisor ? true : false);
449 /* Round a given CANDIDATE number up to the nearest prime, and return that
450 prime. Primes lower than 10 are merely skipped. */
453 next_prime (size_t candidate)
455 /* Skip small primes. */
459 /* Make it definitely odd. */
462 while (!is_prime (candidate))
469 hash_reset_tuning (Hash_tuning *tuning)
471 *tuning = default_tuning;
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. */
481 check_tuning (Hash_table *table)
483 const Hash_tuning *tuning = table->tuning;
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;
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)
501 table->tuning = &default_tuning;
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.
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.
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.
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.
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
537 hash_initialize (size_t candidate, const Hash_tuning *tuning,
538 Hash_hasher hasher, Hash_comparator comparator,
539 Hash_data_freer data_freer)
543 if (hasher == NULL || comparator == NULL)
546 table = malloc (sizeof *table);
551 tuning = &default_tuning;
552 table->tuning = tuning;
553 if (!check_tuning (table))
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
563 if (!tuning->is_n_buckets)
565 float new_candidate = candidate / tuning->growth_threshold;
566 if (SIZE_MAX <= new_candidate)
568 candidate = new_candidate;
571 if (SIZE_MAX / sizeof *table->bucket < candidate)
573 table->n_buckets = next_prime (candidate);
574 if (SIZE_MAX / sizeof *table->bucket < table->n_buckets)
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;
582 table->hasher = hasher;
583 table->comparator = comparator;
584 table->data_freer = data_freer;
586 table->free_entry_list = NULL;
588 obstack_init (&table->entry_stack);
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
602 hash_clear (Hash_table *table)
604 struct hash_entry *bucket;
606 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
610 struct hash_entry *cursor;
611 struct hash_entry *next;
613 /* Free the bucket overflow. */
614 for (cursor = bucket->next; cursor; cursor = next)
616 if (table->data_freer)
617 (*table->data_freer) (cursor->data);
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;
627 /* Free the bucket head. */
628 if (table->data_freer)
629 (*table->data_freer) (bucket->data);
635 table->n_buckets_used = 0;
636 table->n_entries = 0;
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
645 hash_free (Hash_table *table)
647 struct hash_entry *bucket;
648 struct hash_entry *cursor;
649 struct hash_entry *next;
651 /* Call the user data_freer function. */
652 if (table->data_freer && table->n_entries)
654 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
658 for (cursor = bucket; cursor; cursor = cursor->next)
660 (*table->data_freer) (cursor->data);
668 obstack_free (&table->entry_stack, NULL);
672 /* Free all bucket overflowed entries. */
673 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
675 for (cursor = bucket->next; cursor; cursor = next)
682 /* Also reclaim the internal list of previously freed entries. */
683 for (cursor = table->free_entry_list; cursor; cursor = next)
691 /* Free the remainder of the hash table structure. */
692 free (table->bucket);
696 /* Insertion and deletion. */
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. */
701 static struct hash_entry *
702 allocate_entry (Hash_table *table)
704 struct hash_entry *new;
706 if (table->free_entry_list)
708 new = table->free_entry_list;
709 table->free_entry_list = new->next;
714 new = obstack_alloc (&table->entry_stack, sizeof *new);
716 new = malloc (sizeof *new);
723 /* Free a hash entry which was part of some bucket overflow,
724 saving it for later recycling. */
727 free_entry (Hash_table *table, struct hash_entry *entry)
730 entry->next = table->free_entry_list;
731 table->free_entry_list = entry;
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. */
741 hash_find_entry (Hash_table *table, const void *entry,
742 struct hash_entry **bucket_head, bool delete)
744 struct hash_entry *bucket
745 = table->bucket + table->hasher (entry, table->n_buckets);
746 struct hash_entry *cursor;
748 if (! (bucket < table->bucket_limit))
751 *bucket_head = bucket;
753 /* Test for empty bucket. */
754 if (bucket->data == NULL)
757 /* See if the entry is the first in the bucket. */
758 if ((*table->comparator) (entry, bucket->data))
760 void *data = bucket->data;
766 struct hash_entry *next = bucket->next;
768 /* Bump the first overflow entry into the bucket head, then save
769 the previous first overflow entry for later recycling. */
771 free_entry (table, next);
782 /* Scan the bucket overflow. */
783 for (cursor = bucket; cursor->next; cursor = cursor->next)
785 if ((*table->comparator) (entry, cursor->next->data))
787 void *data = cursor->next->data;
791 struct hash_entry *next = cursor->next;
793 /* Unlink the entry to delete, then save the freed entry for later
795 cursor->next = next->next;
796 free_entry (table, next);
803 /* No entry found. */
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. */
816 hash_rehash (Hash_table *table, size_t candidate)
818 Hash_table *new_table;
819 struct hash_entry *bucket;
820 struct hash_entry *cursor;
821 struct hash_entry *next;
823 new_table = hash_initialize (candidate, table->tuning, table->hasher,
824 table->comparator, table->data_freer);
825 if (new_table == NULL)
828 /* Merely reuse the extra old space into the new table. */
830 obstack_free (&new_table->entry_stack, NULL);
831 new_table->entry_stack = table->entry_stack;
833 new_table->free_entry_list = table->free_entry_list;
835 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
837 for (cursor = bucket; cursor; cursor = next)
839 void *data = cursor->data;
840 struct hash_entry *new_bucket
842 + new_table->hasher (data, new_table->n_buckets));
844 if (! (new_bucket < new_table->bucket_limit))
849 if (new_bucket->data)
851 if (cursor == bucket)
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);
857 if (new_entry == NULL)
860 new_entry->data = data;
861 new_entry->next = new_bucket->next;
862 new_bucket->next = new_entry;
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;
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
878 new_bucket->data = data;
879 new_table->n_buckets_used++;
880 if (cursor != bucket)
881 free_entry (new_table, cursor);
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. */
893 table->entry_stack = new_table->entry_stack;
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. */
905 hash_insert (Hash_table *table, const void *entry)
908 struct hash_entry *bucket;
910 /* The caller cannot insert a NULL entry. */
914 /* If there's a matching entry already in the table, return that. */
915 if ((data = hash_find_entry (table, entry, &bucket, false)) != NULL)
918 /* ENTRY is not matched, it should be inserted. */
922 struct hash_entry *new_entry = allocate_entry (table);
924 if (new_entry == NULL)
927 /* Add ENTRY in the overflow of the bucket. */
929 new_entry->data = (void *) entry;
930 new_entry->next = bucket->next;
931 bucket->next = new_entry;
933 return (void *) entry;
936 /* Add ENTRY right in the bucket head. */
938 bucket->data = (void *) entry;
940 table->n_buckets_used++;
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. */
947 if (table->n_buckets_used
948 > table->tuning->growth_threshold * table->n_buckets)
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)
956 const Hash_tuning *tuning = table->tuning;
958 (tuning->is_n_buckets
959 ? (table->n_buckets * tuning->growth_factor)
960 : (table->n_buckets * tuning->growth_factor
961 * tuning->growth_threshold));
963 if (SIZE_MAX <= candidate)
966 /* If the rehash fails, arrange to return NULL. */
967 if (!hash_rehash (table, candidate))
972 return (void *) entry;
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. */
980 hash_delete (Hash_table *table, const void *entry)
983 struct hash_entry *bucket;
985 data = hash_find_entry (table, entry, &bucket, true);
992 table->n_buckets_used--;
994 /* If the shrink threshold of the buckets in use has been reached,
995 rehash into a smaller table. */
997 if (table->n_buckets_used
998 < table->tuning->shrink_threshold * table->n_buckets)
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)
1006 const Hash_tuning *tuning = table->tuning;
1008 (tuning->is_n_buckets
1009 ? table->n_buckets * tuning->shrink_factor
1010 : (table->n_buckets * tuning->shrink_factor
1011 * tuning->growth_threshold));
1013 hash_rehash (table, candidate);
1026 hash_print (const Hash_table *table)
1028 struct hash_entry const *bucket;
1030 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
1032 struct hash_entry *cursor;
1035 printf ("%lu:\n", (unsigned long int) (bucket - table->bucket));
1037 for (cursor = bucket; cursor; cursor = cursor->next)
1039 char const *s = cursor->data;
1042 printf (" %s\n", s);
1047 #endif /* TESTING */