1 /* hash - hashing table processing.
2 Copyright (C) 1998, 1999 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;
47 # ifndef obstack_chunk_alloc
48 # define obstack_chunk_alloc malloc
50 # ifndef obstack_chunk_free
51 # define obstack_chunk_free free
57 /* A hash table contains many internal entries, each holding a pointer to
58 some user provided data (also called a user entry). An entry indistinctly
59 refers to both the internal entry and its associated user entry. A user
60 entry contents may be hashed by a randomization function (the hashing
61 function, or just `hasher' for short) into a number (or `slot') between 0
62 and the current table size. At each slot position in the hash table,
63 starts a linked chain of entries for which the user data all hash to this
64 slot. A bucket is the collection of all entries hashing to the same slot.
66 A good `hasher' function will distribute entries rather evenly in buckets.
67 In the ideal case, the length of each bucket is roughly the number of
68 entries divided by the table size. Finding the slot for a data is usually
69 done in constant time by the `hasher', and the later finding of a precise
70 entry is linear in time with the size of the bucket. Consequently, a
71 larger hash table size (that is, a larger number of buckets) is prone to
72 yielding shorter chains, *given* the `hasher' function behaves properly.
74 Long buckets slow down the lookup algorithm. One might use big hash table
75 sizes in hope to reduce the average length of buckets, but this might
76 become inordinate, as unused slots in the hash table take some space. The
77 best bet is to make sure you are using a good `hasher' function (beware
78 that those are not that easy to write! :-), and to use a table size
79 larger than the actual number of entries. */
81 /* If an insertion makes the ratio of nonempty buckets to table size larger
82 than the growth threshold (a number between 0.0 and 1.0), then increase
83 the table size by multiplying by the growth factor (a number greater than
84 1.0). The growth threshold defaults to 0.8, and the growth factor
85 defaults to 1.414, meaning that the table will have doubled its size
86 every second time 80% of the buckets get used. */
87 #define DEFAULT_GROWTH_THRESHOLD 0.8
88 #define DEFAULT_GROWTH_FACTOR 1.414
90 /* If a deletion empties a bucket and causes the ratio of used buckets to
91 table size to become smaller than the shrink threshold (a number between
92 0.0 and 1.0), then shrink the table by multiplying by the shrink factor (a
93 number greater than the shrink threshold but smaller than 1.0). The shrink
94 threshold and factor default to 0.0 and 1.0, meaning that the table never
96 #define DEFAULT_SHRINK_THRESHOLD 0.0
97 #define DEFAULT_SHRINK_FACTOR 1.0
99 /* Use this to initialize or reset a TUNING structure to
100 some sensible values. */
101 static const Hash_tuning default_tuning =
103 DEFAULT_SHRINK_THRESHOLD,
104 DEFAULT_SHRINK_FACTOR,
105 DEFAULT_GROWTH_THRESHOLD,
106 DEFAULT_GROWTH_FACTOR,
110 /* Information and lookup. */
112 /* The following few functions provide information about the overall hash
113 table organization: the number of entries, number of buckets and maximum
114 length of buckets. */
116 /* Return the number of buckets in the hash table. The table size, the total
117 number of buckets (used plus unused), or the maximum number of slots, are
118 the same quantity. */
121 hash_get_n_buckets (const Hash_table *table)
123 return table->n_buckets;
126 /* Return the number of slots in use (non-empty buckets). */
129 hash_get_n_buckets_used (const Hash_table *table)
131 return table->n_buckets_used;
134 /* Return the number of active entries. */
137 hash_get_n_entries (const Hash_table *table)
139 return table->n_entries;
142 /* Return the length of the longest chain (bucket). */
145 hash_get_max_bucket_length (const Hash_table *table)
147 struct hash_entry *bucket;
148 unsigned max_bucket_length = 0;
150 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
154 struct hash_entry *cursor = bucket;
155 unsigned bucket_length = 1;
157 while (cursor = cursor->next, cursor)
160 if (bucket_length > max_bucket_length)
161 max_bucket_length = bucket_length;
165 return max_bucket_length;
168 /* Do a mild validation of a hash table, by traversing it and checking two
172 hash_table_ok (const Hash_table *table)
174 struct hash_entry *bucket;
175 unsigned n_buckets_used = 0;
176 unsigned n_entries = 0;
178 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
182 struct hash_entry *cursor = bucket;
184 /* Count bucket head. */
188 /* Count bucket overflow. */
189 while (cursor = cursor->next, cursor)
194 if (n_buckets_used == table->n_buckets_used && n_entries == table->n_entries)
201 hash_print_statistics (const Hash_table *table, FILE *stream)
203 unsigned n_entries = hash_get_n_entries (table);
204 unsigned n_buckets = hash_get_n_buckets (table);
205 unsigned n_buckets_used = hash_get_n_buckets_used (table);
206 unsigned max_bucket_length = hash_get_max_bucket_length (table);
208 fprintf (stream, "# entries: %u\n", n_entries);
209 fprintf (stream, "# buckets: %u\n", n_buckets);
210 fprintf (stream, "# buckets used: %u (%.2f%%)\n", n_buckets_used,
211 (100.0 * n_buckets_used) / n_buckets);
212 fprintf (stream, "max bucket length: %u\n", max_bucket_length);
215 /* If ENTRY matches an entry already in the hash table, return the
216 entry from the table. Otherwise, return NULL. */
219 hash_lookup (const Hash_table *table, const void *entry)
221 struct hash_entry *bucket
222 = table->bucket + table->hasher (entry, table->n_buckets);
223 struct hash_entry *cursor;
225 assert (bucket < table->bucket_limit);
227 if (bucket->data == NULL)
230 for (cursor = bucket; cursor; cursor = cursor->next)
231 if (table->comparator (entry, cursor->data))
239 /* The functions in this page traverse the hash table and process the
240 contained entries. For the traversal to work properly, the hash table
241 should not be resized nor modified while any particular entry is being
242 processed. In particular, entries should not be added or removed. */
244 /* Return the first data in the table, or NULL if the table is empty. */
247 hash_get_first (const Hash_table *table)
249 struct hash_entry *bucket;
251 if (table->n_entries == 0)
254 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
261 /* Return the user data for the entry following ENTRY, where ENTRY has been
262 returned by a previous call to either `hash_get_first' or `hash_get_next'.
263 Return NULL if there is no more entries. */
266 hash_get_next (const Hash_table *table, const void *entry)
268 struct hash_entry *bucket
269 = table->bucket + table->hasher (entry, table->n_buckets);
270 struct hash_entry *cursor;
272 assert (bucket < table->bucket_limit);
274 /* Find next entry in the same bucket. */
275 for (cursor = bucket; cursor; cursor = cursor->next)
276 if (cursor->data == entry && cursor->next)
277 return cursor->next->data;
279 /* Find first entry in any subsequent bucket. */
280 for (; bucket < table->bucket_limit; bucket++)
288 /* Fill BUFFER with pointers to active user entries in the hash table, then
289 return the number of pointers copied. Do not copy more than BUFFER_SIZE
293 hash_get_entries (const Hash_table *table, void **buffer,
294 unsigned buffer_size)
296 unsigned counter = 0;
297 struct hash_entry *bucket;
298 struct hash_entry *cursor;
300 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
304 for (cursor = bucket; cursor; cursor = cursor->next)
306 if (counter >= buffer_size)
308 buffer[counter++] = cursor->data;
316 /* Call a PROCESSOR function for each entry of a hash table, and return the
317 number of entries for which the processor function returned success. A
318 pointer to some PROCESSOR_DATA which will be made available to each call to
319 the processor function. The PROCESSOR accepts two arguments: the first is
320 the user entry being walked into, the second is the value of PROCESSOR_DATA
321 as received. The walking continue for as long as the PROCESSOR function
322 returns nonzero. When it returns zero, the walking is interrupted. */
325 hash_do_for_each (const Hash_table *table, Hash_processor processor,
326 void *processor_data)
328 unsigned counter = 0;
329 struct hash_entry *bucket;
330 struct hash_entry *cursor;
332 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
336 for (cursor = bucket; cursor; cursor = cursor->next)
338 if (!(*processor) (cursor->data, processor_data))
348 /* Allocation and clean-up. */
350 /* Return a hash index for a NUL-terminated STRING between 0 and N_BUCKETS-1.
351 This is a convenience routine for constructing other hashing functions. */
355 /* About hashings, Paul Eggert writes to me (FP), on 1994-01-01: "Please see
356 B. J. McKenzie, R. Harries & T. Bell, Selecting a hashing algorithm,
357 Software--practice & experience 20, 2 (Feb 1990), 209-224. Good hash
358 algorithms tend to be domain-specific, so what's good for [diffutils'] io.c
359 may not be good for your application." */
362 hash_string (const char *string, unsigned n_buckets)
367 # define ROTATE_LEFT(Value, Shift) \
368 ((Value) << (Shift) | (Value) >> ((sizeof (unsigned) * CHAR_BIT) - (Shift)))
369 # define HASH_ONE_CHAR(Value, Byte) \
370 ((Byte) + ROTATE_LEFT (Value, 7))
374 for (; *string; string++)
375 value = HASH_ONE_CHAR (value, *(const unsigned char *) string);
376 return value % n_buckets;
379 # undef HASH_ONE_CHAR
382 #else /* not USE_DIFF_HASH */
384 /* This one comes from `recode', and performs a bit better than the above as
385 per a few experiments. It is inspired from a hashing routine found in the
386 very old Cyber `snoop', itself written in typical Greg Mansfield style.
387 (By the way, what happened to this excellent man? Is he still alive?) */
390 hash_string (const char *string, unsigned n_buckets)
395 value = ((value * 31 + (int) *(const unsigned char *) string++)
400 #endif /* not USE_DIFF_HASH */
402 /* Return true if CANDIDATE is a prime number. CANDIDATE should be an odd
403 number at least equal to 11. */
406 is_prime (unsigned long candidate)
408 unsigned long divisor = 3;
409 unsigned long square = divisor * divisor;
411 while (square < candidate && (candidate % divisor))
414 square += 4 * divisor;
418 return candidate % divisor != 0;
421 /* Round a given CANDIDATE number up to the nearest prime, and return that
422 prime. Primes lower than 10 are merely skipped. */
425 next_prime (unsigned long candidate)
427 /* Skip small primes. */
431 /* Make it definitely odd. */
434 while (!is_prime (candidate))
441 hash_reset_tuning (Hash_tuning *tuning)
443 *tuning = default_tuning;
446 /* For the given hash TABLE, check the user supplied tuning structure for
447 reasonable values, and return true if there is no gross error with it.
448 Otherwise, definitively reset the TUNING field to some acceptable default
449 in the hash table (that is, the user loses the right of further modifying
450 tuning arguments), and return false. */
453 check_tuning (Hash_table *table)
455 const Hash_tuning *tuning = table->tuning;
457 if (tuning->growth_threshold > 0.0
458 && tuning->growth_threshold < 1.0
459 && tuning->growth_factor > 1.0
460 && tuning->shrink_threshold >= 0.0
461 && tuning->shrink_threshold < 1.0
462 && tuning->shrink_factor > tuning->shrink_threshold
463 && tuning->shrink_factor <= 1.0
464 && tuning->shrink_threshold < tuning->growth_threshold)
467 table->tuning = &default_tuning;
471 /* Allocate and return a new hash table, or NULL upon failure. The initial
472 number of buckets is automatically selected so as to _guarantee_ that you
473 may insert at least CANDIDATE different user entries before any growth of
474 the hash table size occurs. So, if have a reasonably tight a-priori upper
475 bound on the number of entries you intend to insert in the hash table, you
476 may save some table memory and insertion time, by specifying it here. If
477 the IS_N_BUCKETS field of the TUNING structure is true, the CANDIDATE
478 argument has its meaning changed to the wanted number of buckets.
480 TUNING points to a structure of user-supplied values, in case some fine
481 tuning is wanted over the default behavior of the hasher. If TUNING is
482 NULL, the default tuning parameters are used instead.
484 The user-supplied HASHER function should be provided. It accepts two
485 arguments ENTRY and TABLE_SIZE. It computes, by hashing ENTRY contents, a
486 slot number for that entry which should be in the range 0..TABLE_SIZE-1.
487 This slot number is then returned.
489 The user-supplied COMPARATOR function should be provided. It accepts two
490 arguments pointing to user data, it then returns true for a pair of entries
491 that compare equal, or false otherwise. This function is internally called
492 on entries which are already known to hash to the same bucket index.
494 The user-supplied DATA_FREER function, when not NULL, may be later called
495 with the user data as an argument, just before the entry containing the
496 data gets freed. This happens from within `hash_free' or `hash_clear'.
497 You should specify this function only if you want these functions to free
498 all of your `data' data. This is typically the case when your data is
499 simply an auxiliary struct that you have malloc'd to aggregate several
503 hash_initialize (unsigned candidate, const Hash_tuning *tuning,
504 Hash_hasher hasher, Hash_comparator comparator,
505 Hash_data_freer data_freer)
508 struct hash_entry *bucket;
510 if (hasher == NULL || comparator == NULL)
513 table = (Hash_table *) malloc (sizeof (Hash_table));
518 tuning = &default_tuning;
519 table->tuning = tuning;
520 if (!check_tuning (table))
522 /* Fail if the tuning options are invalid. This is the only occasion
523 when the user gets some feedback about it. Once the table is created,
524 if the user provides invalid tuning options, we silently revert to
525 using the defaults, and ignore further request to change the tuning
532 = next_prime (tuning->is_n_buckets ? candidate
533 : (unsigned) (candidate / tuning->growth_threshold));
535 table->bucket = (struct hash_entry *)
536 malloc (table->n_buckets * sizeof (struct hash_entry));
537 if (table->bucket == NULL)
542 table->bucket_limit = table->bucket + table->n_buckets;
544 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
549 table->n_buckets_used = 0;
550 table->n_entries = 0;
552 table->hasher = hasher;
553 table->comparator = comparator;
554 table->data_freer = data_freer;
556 table->free_entry_list = NULL;
558 obstack_init (&table->entry_stack);
563 /* Make all buckets empty, placing any chained entries on the free list.
564 Apply the user-specified function data_freer (if any) to the datas of any
568 hash_clear (Hash_table *table)
570 struct hash_entry *bucket;
571 struct hash_entry *cursor;
573 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
577 /* Free the bucket overflow. */
578 for (cursor = bucket->next; cursor; cursor = cursor->next)
580 if (table->data_freer)
581 (*table->data_freer) (cursor->data);
584 /* Relinking is done one entry at a time, as it is to be expected
585 that overflows are either rare or short. */
586 cursor->next = table->free_entry_list;
587 table->free_entry_list = cursor;
590 /* Free the bucket head. */
591 if (table->data_freer)
592 (*table->data_freer) (bucket->data);
598 table->n_buckets_used = 0;
599 table->n_entries = 0;
602 /* Reclaim all storage associated with a hash table. If a data_freer
603 function has been supplied by the user when the hash table was created,
604 this function applies it to the data of each entry before freeing that
608 hash_free (Hash_table *table)
610 struct hash_entry *bucket;
611 struct hash_entry *cursor;
612 struct hash_entry *next;
614 /* Call the user data_freer function. */
615 if (table->data_freer && table->n_entries)
617 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
621 for (cursor = bucket; cursor; cursor = cursor->next)
623 (*table->data_freer) (cursor->data);
631 obstack_free (&table->entry_stack, NULL);
635 /* Free all bucket overflowed entries. */
636 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
638 for (cursor = bucket->next; cursor; cursor = next)
645 /* Also reclaim the internal list of previously freed entries. */
646 for (cursor = table->free_entry_list; cursor; cursor = next)
654 /* Free the remainder of the hash table structure. */
655 free (table->bucket);
659 /* Insertion and deletion. */
661 /* Get a new hash entry for a bucket overflow, possibly by reclying a
662 previously freed one. If this is not possible, allocate a new one. */
664 static struct hash_entry *
665 allocate_entry (Hash_table *table)
667 struct hash_entry *new;
669 if (table->free_entry_list)
671 new = table->free_entry_list;
672 table->free_entry_list = new->next;
677 new = (struct hash_entry *)
678 obstack_alloc (&table->entry_stack, sizeof (struct hash_entry));
680 new = (struct hash_entry *) malloc (sizeof (struct hash_entry));
687 /* Free a hash entry which was part of some bucket overflow,
688 saving it for later recycling. */
691 free_entry (Hash_table *table, struct hash_entry *entry)
694 entry->next = table->free_entry_list;
695 table->free_entry_list = entry;
698 /* This private function is used to help with insertion and deletion. When
699 ENTRY matches an entry in the table, return a pointer to the corresponding
700 user data and set *BUCKET_HEAD to the head of the selected bucket.
701 Otherwise, return NULL. When DELETE is true and ENTRY matches an entry in
702 the table, unlink the matching entry. */
705 hash_find_entry (Hash_table *table, const void *entry,
706 struct hash_entry **bucket_head, bool delete)
708 struct hash_entry *bucket
709 = table->bucket + table->hasher (entry, table->n_buckets);
710 struct hash_entry *cursor;
712 assert (bucket < table->bucket_limit);
713 *bucket_head = bucket;
715 /* Test for empty bucket. */
716 if (bucket->data == NULL)
719 /* Check if then entry is found as the bucket head. */
720 if ((*table->comparator) (entry, bucket->data))
722 void *data = bucket->data;
728 struct hash_entry *next = bucket->next;
730 /* Bump the first overflow entry into the bucket head, then save
731 the previous first overflow entry for later recycling. */
733 free_entry (table, next);
744 /* Scan the bucket overflow. */
745 for (cursor = bucket; cursor->next; cursor = cursor->next)
747 if ((*table->comparator) (entry, cursor->next->data))
749 void *data = cursor->next->data;
753 struct hash_entry *next = cursor->next;
755 /* Unlink the entry to delete, then save the freed entry for later
757 cursor->next = next->next;
758 free_entry (table, next);
765 /* No entry found. */
769 /* For an already existing hash table, change the number of buckets through
770 specifying CANDIDATE. The contents of the hash table are preserved. The
771 new number of buckets is automatically selected so as to _guarantee_ that
772 the table may receive at least CANDIDATE different user entries, including
773 those already in the table, before any other growth of the hash table size
774 occurs. If TUNING->IS_N_BUCKETS is true, then CANDIDATE specifies the
775 exact number of buckets desired. */
778 hash_rehash (Hash_table *table, unsigned candidate)
780 Hash_table *new_table;
781 struct hash_entry *bucket;
782 struct hash_entry *cursor;
783 struct hash_entry *next;
785 new_table = hash_initialize (candidate, table->tuning, table->hasher,
786 table->comparator, table->data_freer);
787 if (new_table == NULL)
790 /* Merely reuse the extra old space into the new table. */
792 obstack_free (&new_table->entry_stack, NULL);
793 new_table->entry_stack = table->entry_stack;
795 new_table->free_entry_list = table->free_entry_list;
797 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
799 for (cursor = bucket; cursor; cursor = next)
801 void *data = cursor->data;
802 struct hash_entry *new_bucket
804 + new_table->hasher (data, new_table->n_buckets));
806 assert (new_bucket < new_table->bucket_limit);
809 if (new_bucket->data)
811 if (cursor == bucket)
813 /* Allocate or recycle an entry, when moving from a bucket
814 header into a bucket overflow. */
815 struct hash_entry *new_entry = allocate_entry (new_table);
817 if (new_entry == NULL)
820 new_entry->data = data;
821 new_entry->next = new_bucket->next;
822 new_bucket->next = new_entry;
826 /* Merely relink an existing entry, when moving from a
827 bucket overflow into a bucket overflow. */
828 cursor->next = new_bucket->next;
829 new_bucket->next = cursor;
834 /* Free an existing entry, when moving from a bucket
835 overflow into a bucket header. Also take care of the
836 simple case of moving from a bucket header into a bucket
838 new_bucket->data = data;
839 new_table->n_buckets_used++;
840 if (cursor != bucket)
841 free_entry (new_table, cursor);
845 free (table->bucket);
846 table->bucket = new_table->bucket;
847 table->bucket_limit = new_table->bucket_limit;
848 table->n_buckets = new_table->n_buckets;
849 table->n_buckets_used = new_table->n_buckets_used;
850 /* table->n_entries already holds its value. */
852 table->entry_stack = new_table->entry_stack;
859 /* If ENTRY matches an entry already in the hash table, return the pointer
860 to the entry from the table. Otherwise, insert ENTRY and return ENTRY.
861 Return NULL if the storage required for insertion cannot be allocated. */
864 hash_insert (Hash_table *table, const void *entry)
867 struct hash_entry *bucket;
869 assert (entry); /* cannot insert a NULL entry */
871 /* If there's a matching entry already in the table, return that. */
872 if ((data = hash_find_entry (table, entry, &bucket, false)) != NULL)
875 /* ENTRY is not matched, it should be inserted. */
879 struct hash_entry *new_entry = allocate_entry (table);
881 if (new_entry == NULL)
884 /* Add ENTRY in the overflow of the bucket. */
886 new_entry->data = (void *) entry;
887 new_entry->next = bucket->next;
888 bucket->next = new_entry;
890 return (void *) entry;
893 /* Add ENTRY right in the bucket head. */
895 bucket->data = (void *) entry;
897 table->n_buckets_used++;
899 /* If the growth threshold of the buckets in use has been reached, increase
900 the table size and rehash. There's no point in checking the number of
901 entries: if the hashing function is ill-conditioned, rehashing is not
902 likely to improve it. */
904 if (table->n_buckets_used
905 > table->tuning->growth_threshold * table->n_buckets)
907 /* Check more fully, before starting real work. If tuning arguments
908 became invalid, the second check will rely on proper defaults. */
909 check_tuning (table);
910 if (table->n_buckets_used
911 > table->tuning->growth_threshold * table->n_buckets)
913 const Hash_tuning *tuning = table->tuning;
915 = (unsigned) (tuning->is_n_buckets
916 ? (table->n_buckets * tuning->growth_factor)
917 : (table->n_buckets * tuning->growth_factor
918 * tuning->growth_threshold));
920 /* If the rehash fails, arrange to return NULL. */
921 if (!hash_rehash (table, candidate))
926 return (void *) entry;
929 /* If ENTRY is already in the table, remove it and return the just-deleted
930 data (the user may want to deallocate its storage). If ENTRY is not in the
931 table, don't modify the table and return NULL. */
934 hash_delete (Hash_table *table, const void *entry)
937 struct hash_entry *bucket;
939 if (data = hash_find_entry (table, entry, &bucket, true), !data)
945 table->n_buckets_used--;
947 /* If the shrink threshold of the buckets in use has been reached,
948 rehash into a smaller table. */
950 if (table->n_buckets_used
951 < table->tuning->shrink_threshold * table->n_buckets)
953 /* Check more fully, before starting real work. If tuning arguments
954 became invalid, the second check will rely on proper defaults. */
955 check_tuning (table);
956 if (table->n_buckets_used
957 < table->tuning->shrink_threshold * table->n_buckets)
959 const Hash_tuning *tuning = table->tuning;
961 = (unsigned) (tuning->is_n_buckets
962 ? table->n_buckets * tuning->shrink_factor
963 : (table->n_buckets * tuning->shrink_factor
964 * tuning->growth_threshold));
966 hash_rehash (table, candidate);
979 hash_print (const Hash_table *table)
981 struct hash_entry *bucket;
983 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
985 struct hash_entry *cursor;
988 printf ("%d:\n", slot);
990 for (cursor = bucket; cursor; cursor = cursor->next)
992 char *s = (char *) cursor->data;