Lines Matching defs:table
1 /* hash - hashing table processing.
22 /* A generic hash table package. */
56 are not empty, there are N_ENTRIES active entries in the table. */
86 /* A hash table contains many internal entries, each holding a pointer to
91 and the current table size. At each slot position in the hash table,
97 entries divided by the table size. Finding the slot for a data is usually
100 larger hash table size (that is, a larger number of buckets) is prone to
103 Long buckets slow down the lookup algorithm. One might use big hash table
105 become inordinate, as unused slots in the hash table take some space. The
107 that those are not that easy to write! :-), and to use a table size
110 /* If an insertion makes the ratio of nonempty buckets to table size larger
112 the table size by multiplying by the growth factor (a number greater than
114 defaults to 1.414, meaning that the table will have doubled its size
120 table size to become smaller than the shrink threshold (a number between
121 0.0 and 1.0), then shrink the table by multiplying by the shrink factor (a
123 threshold and factor default to 0.0 and 1.0, meaning that the table never
142 table organization: the number of entries, number of buckets and maximum
145 /* Return the number of buckets in the hash table. The table size, the total
150 hash_get_n_buckets (const Hash_table *table)
152 return table->n_buckets;
158 hash_get_n_buckets_used (const Hash_table *table)
160 return table->n_buckets_used;
166 hash_get_n_entries (const Hash_table *table)
168 return table->n_entries;
174 hash_get_max_bucket_length (const Hash_table *table)
179 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
197 /* Do a mild validation of a hash table, by traversing it and checking two
201 hash_table_ok (const Hash_table *table)
207 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
223 if (n_buckets_used == table->n_buckets_used && n_entries == table->n_entries)
230 hash_print_statistics (const Hash_table *table, FILE *stream)
232 size_t n_entries = hash_get_n_entries (table);
233 size_t n_buckets = hash_get_n_buckets (table);
234 size_t n_buckets_used = hash_get_n_buckets_used (table);
235 size_t max_bucket_length = hash_get_max_bucket_length (table);
246 /* If ENTRY matches an entry already in the hash table, return the
247 entry from the table. Otherwise, return NULL. */
250 hash_lookup (const Hash_table *table, const void *entry)
253 = table->bucket + table->hasher (entry, table->n_buckets);
256 if (! (bucket < table->bucket_limit))
263 if (table->comparator (entry, cursor->data))
271 /* The functions in this page traverse the hash table and process the
272 contained entries. For the traversal to work properly, the hash table
276 /* Return the first data in the table, or NULL if the table is empty. */
279 hash_get_first (const Hash_table *table)
283 if (table->n_entries == 0)
286 for (bucket = table->bucket; ; bucket++)
287 if (! (bucket < table->bucket_limit))
298 hash_get_next (const Hash_table *table, const void *entry)
301 = table->bucket + table->hasher (entry, table->n_buckets);
304 if (! (bucket < table->bucket_limit))
313 while (++bucket < table->bucket_limit)
321 /* Fill BUFFER with pointers to active user entries in the hash table, then
326 hash_get_entries (const Hash_table *table, void **buffer,
333 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
349 /* Call a PROCESSOR function for each entry of a hash table, and return the
358 hash_do_for_each (const Hash_table *table, Hash_processor processor,
365 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
477 /* For the given hash TABLE, check the user supplied tuning structure for
480 in the hash table (that is, the user loses the right of further modifying
484 check_tuning (Hash_table *table)
486 const Hash_tuning *tuning = table->tuning;
504 table->tuning = &default_tuning;
508 /* Allocate and return a new hash table, or NULL upon failure. The initial
511 the hash table size occurs. So, if have a reasonably tight a-priori upper
512 bound on the number of entries you intend to insert in the hash table, you
513 may save some table memory and insertion time, by specifying it here. If
544 Hash_table *table;
549 table = malloc (sizeof *table);
550 if (table == NULL)
555 table->tuning = tuning;
556 if (!check_tuning (table))
559 when the user gets some feedback about it. Once the table is created,
574 if (xalloc_oversized (candidate, sizeof *table->bucket))
576 table->n_buckets = next_prime (candidate);
577 if (xalloc_oversized (table->n_buckets, sizeof *table->bucket))
580 table->bucket = calloc (table->n_buckets, sizeof *table->bucket);
581 table->bucket_limit = table->bucket + table->n_buckets;
582 table->n_buckets_used = 0;
583 table->n_entries = 0;
585 table->hasher = hasher;
586 table->comparator = comparator;
587 table->data_freer = data_freer;
589 table->free_entry_list = NULL;
591 obstack_init (&table->entry_stack);
593 return table;
596 free (table);
605 hash_clear (Hash_table *table)
609 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
619 if (table->data_freer)
620 (*table->data_freer) (cursor->data);
626 cursor->next = table->free_entry_list;
627 table->free_entry_list = cursor;
631 if (table->data_freer)
632 (*table->data_freer) (bucket->data);
638 table->n_buckets_used = 0;
639 table->n_entries = 0;
642 /* Reclaim all storage associated with a hash table. If a data_freer
643 function has been supplied by the user when the hash table was created,
648 hash_free (Hash_table *table)
655 if (table->data_freer && table->n_entries)
657 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
663 (*table->data_freer) (cursor->data);
671 obstack_free (&table->entry_stack, NULL);
676 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
686 for (cursor = table->free_entry_list; cursor; cursor = next)
694 /* Free the remainder of the hash table structure. */
695 free (table->bucket);
696 free (table);
705 allocate_entry (Hash_table *table)
709 if (table->free_entry_list)
711 new = table->free_entry_list;
712 table->free_entry_list = new->next;
717 new = obstack_alloc (&table->entry_stack, sizeof *new);
730 free_entry (Hash_table *table, struct hash_entry *entry)
733 entry->next = table->free_entry_list;
734 table->free_entry_list = entry;
738 ENTRY matches an entry in the table, return a pointer to the corresponding
741 the table, unlink the matching entry. */
744 hash_find_entry (Hash_table *table, const void *entry,
748 = table->bucket + table->hasher (entry, table->n_buckets);
751 if (! (bucket < table->bucket_limit))
761 if ((*table->comparator) (entry, bucket->data))
774 free_entry (table, next);
788 if ((*table->comparator) (entry, cursor->next->data))
799 free_entry (table, next);
810 /* For an already existing hash table, change the number of buckets through
811 specifying CANDIDATE. The contents of the hash table are preserved. The
813 the table may receive at least CANDIDATE different user entries, including
814 those already in the table, before any other growth of the hash table size
819 hash_rehash (Hash_table *table, size_t candidate)
826 new_table = hash_initialize (candidate, table->tuning, table->hasher,
827 table->comparator, table->data_freer);
831 /* Merely reuse the extra old space into the new table. */
834 new_table->entry_stack = table->entry_stack;
836 new_table->free_entry_list = table->free_entry_list;
838 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
888 free (table->bucket);
889 table->bucket = new_table->bucket;
890 table->bucket_limit = new_table->bucket_limit;
891 table->n_buckets = new_table->n_buckets;
892 table->n_buckets_used = new_table->n_buckets_used;
893 table->free_entry_list = new_table->free_entry_list;
894 /* table->n_entries already holds its value. */
896 table->entry_stack = new_table->entry_stack;
903 /* If ENTRY matches an entry already in the hash table, return the pointer
904 to the entry from the table. Otherwise, insert ENTRY and return ENTRY.
908 hash_insert (Hash_table *table, const void *entry)
917 /* If there's a matching entry already in the table, return that. */
918 if ((data = hash_find_entry (table, entry, &bucket, false)) != NULL)
925 struct hash_entry *new_entry = allocate_entry (table);
935 table->n_entries++;
942 table->n_entries++;
943 table->n_buckets_used++;
946 the table size and rehash. There's no point in checking the number of
950 if (table->n_buckets_used
951 > table->tuning->growth_threshold * table->n_buckets)
955 check_tuning (table);
956 if (table->n_buckets_used
957 > table->tuning->growth_threshold * table->n_buckets)
959 const Hash_tuning *tuning = table->tuning;
962 ? (table->n_buckets * tuning->growth_factor)
963 : (table->n_buckets * tuning->growth_factor
970 if (!hash_rehash (table, candidate))
978 /* If ENTRY is already in the table, remove it and return the just-deleted
980 table, don't modify the table and return NULL. */
983 hash_delete (Hash_table *table, const void *entry)
988 data = hash_find_entry (table, entry, &bucket, true);
992 table->n_entries--;
995 table->n_buckets_used--;
998 rehash into a smaller table. */
1000 if (table->n_buckets_used
1001 < table->tuning->shrink_threshold * table->n_buckets)
1005 check_tuning (table);
1006 if (table->n_buckets_used
1007 < table->tuning->shrink_threshold * table->n_buckets)
1009 const Hash_tuning *tuning = table->tuning;
1012 ? table->n_buckets * tuning->shrink_factor
1013 : (table->n_buckets * tuning->shrink_factor
1016 hash_rehash (table, candidate);
1029 hash_print (const Hash_table *table)
1033 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
1038 printf ("%lu:\n", (unsigned long int) (bucket - table->bucket));
