Lines Matching +defs:new +defs:table
1 /* hash - hashing table processing.
22 /* A generic hash table package. */
54 are not empty, there are N_ENTRIES active entries in the table. */
84 /* A hash table contains many internal entries, each holding a pointer to
89 and the current table size. At each slot position in the hash table,
95 entries divided by the table size. Finding the slot for a data is usually
98 larger hash table size (that is, a larger number of buckets) is prone to
101 Long buckets slow down the lookup algorithm. One might use big hash table
103 become inordinate, as unused slots in the hash table take some space. The
105 that those are not that easy to write! :-), and to use a table size
108 /* If an insertion makes the ratio of nonempty buckets to table size larger
110 the table size by multiplying by the growth factor (a number greater than
112 defaults to 1.414, meaning that the table will have doubled its size
118 table size to become smaller than the shrink threshold (a number between
119 0.0 and 1.0), then shrink the table by multiplying by the shrink factor (a
121 threshold and factor default to 0.0 and 1.0, meaning that the table never
140 table organization: the number of entries, number of buckets and maximum
143 /* Return the number of buckets in the hash table. The table size, the total
148 hash_get_n_buckets (const Hash_table *table)
150 return table->n_buckets;
156 hash_get_n_buckets_used (const Hash_table *table)
158 return table->n_buckets_used;
164 hash_get_n_entries (const Hash_table *table)
166 return table->n_entries;
172 hash_get_max_bucket_length (const Hash_table *table)
177 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
195 /* Do a mild validation of a hash table, by traversing it and checking two
199 hash_table_ok (const Hash_table *table)
205 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
221 if (n_buckets_used == table->n_buckets_used && n_entries == table->n_entries)
228 hash_print_statistics (const Hash_table *table, FILE *stream)
230 size_t n_entries = hash_get_n_entries (table);
231 size_t n_buckets = hash_get_n_buckets (table);
232 size_t n_buckets_used = hash_get_n_buckets_used (table);
233 size_t max_bucket_length = hash_get_max_bucket_length (table);
244 /* If ENTRY matches an entry already in the hash table, return the
245 entry from the table. Otherwise, return NULL. */
248 hash_lookup (const Hash_table *table, const void *entry)
251 = table->bucket + table->hasher (entry, table->n_buckets);
254 if (! (bucket < table->bucket_limit))
261 if (table->comparator (entry, cursor->data))
269 /* The functions in this page traverse the hash table and process the
270 contained entries. For the traversal to work properly, the hash table
274 /* Return the first data in the table, or NULL if the table is empty. */
277 hash_get_first (const Hash_table *table)
281 if (table->n_entries == 0)
284 for (bucket = table->bucket; ; bucket++)
285 if (! (bucket < table->bucket_limit))
296 hash_get_next (const Hash_table *table, const void *entry)
299 = table->bucket + table->hasher (entry, table->n_buckets);
302 if (! (bucket < table->bucket_limit))
311 while (++bucket < table->bucket_limit)
319 /* Fill BUFFER with pointers to active user entries in the hash table, then
324 hash_get_entries (const Hash_table *table, void **buffer,
331 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
347 /* Call a PROCESSOR function for each entry of a hash table, and return the
356 hash_do_for_each (const Hash_table *table, Hash_processor processor,
363 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
478 in the hash table (that is, the user loses the right of further modifying
482 check_tuning (Hash_table *table)
484 const Hash_tuning *tuning = table->tuning;
502 table->tuning = &default_tuning;
506 /* Allocate and return a new hash table, or NULL upon failure. The initial
509 the hash table size occurs. So, if have a reasonably tight a-priori upper
510 bound on the number of entries you intend to insert in the hash table, you
511 may save some table memory and insertion time, by specifying it here. If
542 Hash_table *table;
547 table = malloc (sizeof *table);
548 if (table == NULL)
553 table->tuning = tuning;
554 if (!check_tuning (table))
557 when the user gets some feedback about it. Once the table is created,
572 if (xalloc_oversized (candidate, sizeof *table->bucket))
574 table->n_buckets = next_prime (candidate);
575 if (xalloc_oversized (table->n_buckets, sizeof *table->bucket))
578 table->bucket = calloc (table->n_buckets, sizeof *table->bucket);
579 table->bucket_limit = table->bucket + table->n_buckets;
580 table->n_buckets_used = 0;
581 table->n_entries = 0;
583 table->hasher = hasher;
584 table->comparator = comparator;
585 table->data_freer = data_freer;
587 table->free_entry_list = NULL;
589 obstack_init (&table->entry_stack);
591 return table;
594 free (table);
603 hash_clear (Hash_table *table)
607 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
617 if (table->data_freer)
618 (*table->data_freer) (cursor->data);
624 cursor->next = table->free_entry_list;
625 table->free_entry_list = cursor;
629 if (table->data_freer)
630 (*table->data_freer) (bucket->data);
636 table->n_buckets_used = 0;
637 table->n_entries = 0;
640 /* Reclaim all storage associated with a hash table. If a data_freer
641 function has been supplied by the user when the hash table was created,
646 hash_free (Hash_table *table)
653 if (table->data_freer && table->n_entries)
655 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
661 (*table->data_freer) (cursor->data);
669 obstack_free (&table->entry_stack, NULL);
674 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
684 for (cursor = table->free_entry_list; cursor; cursor = next)
692 /* Free the remainder of the hash table structure. */
693 free (table->bucket);
694 free (table);
699 /* Get a new hash entry for a bucket overflow, possibly by reclying a
700 previously freed one. If this is not possible, allocate a new one. */
703 allocate_entry (Hash_table *table)
705 struct hash_entry *new;
707 if (table->free_entry_list)
709 new = table->free_entry_list;
710 table->free_entry_list = new->next;
715 new = obstack_alloc (&table->entry_stack, sizeof *new);
717 new = malloc (sizeof *new);
721 return new;
728 free_entry (Hash_table *table, struct hash_entry *entry)
731 entry->next = table->free_entry_list;
732 table->free_entry_list = entry;
736 ENTRY matches an entry in the table, return a pointer to the corresponding
739 the table, unlink the matching entry. */
742 hash_find_entry (Hash_table *table, const void *entry,
746 = table->bucket + table->hasher (entry, table->n_buckets);
749 if (! (bucket < table->bucket_limit))
759 if ((*table->comparator) (entry, bucket->data))
772 free_entry (table, next);
786 if ((*table->comparator) (entry, cursor->next->data))
797 free_entry (table, next);
808 /* For an already existing hash table, change the number of buckets through
809 specifying CANDIDATE. The contents of the hash table are preserved. The
810 new number of buckets is automatically selected so as to _guarantee_ that
811 the table may receive at least CANDIDATE different user entries, including
812 those already in the table, before any other growth of the hash table size
817 hash_rehash (Hash_table *table, size_t candidate)
824 new_table = hash_initialize (candidate, table->tuning, table->hasher,
825 table->comparator, table->data_freer);
829 /* Merely reuse the extra old space into the new table. */
832 new_table->entry_stack = table->entry_stack;
834 new_table->free_entry_list = table->free_entry_list;
836 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
886 free (table->bucket);
887 table->bucket = new_table->bucket;
888 table->bucket_limit = new_table->bucket_limit;
889 table->n_buckets = new_table->n_buckets;
890 table->n_buckets_used = new_table->n_buckets_used;
891 table->free_entry_list = new_table->free_entry_list;
892 /* table->n_entries already holds its value. */
894 table->entry_stack = new_table->entry_stack;
901 /* If ENTRY matches an entry already in the hash table, return the pointer
902 to the entry from the table. Otherwise, insert ENTRY and return ENTRY.
906 hash_insert (Hash_table *table, const void *entry)
915 /* If there's a matching entry already in the table, return that. */
916 if ((data = hash_find_entry (table, entry, &bucket, false)) != NULL)
923 struct hash_entry *new_entry = allocate_entry (table);
933 table->n_entries++;
940 table->n_entries++;
941 table->n_buckets_used++;
944 the table size and rehash. There's no point in checking the number of
948 if (table->n_buckets_used
949 > table->tuning->growth_threshold * table->n_buckets)
953 check_tuning (table);
954 if (table->n_buckets_used
955 > table->tuning->growth_threshold * table->n_buckets)
957 const Hash_tuning *tuning = table->tuning;
960 ? (table->n_buckets * tuning->growth_factor)
961 : (table->n_buckets * tuning->growth_factor
968 if (!hash_rehash (table, candidate))
976 /* If ENTRY is already in the table, remove it and return the just-deleted
978 table, don't modify the table and return NULL. */
981 hash_delete (Hash_table *table, const void *entry)
986 data = hash_find_entry (table, entry, &bucket, true);
990 table->n_entries--;
993 table->n_buckets_used--;
996 rehash into a smaller table. */
998 if (table->n_buckets_used
999 < table->tuning->shrink_threshold * table->n_buckets)
1003 check_tuning (table);
1004 if (table->n_buckets_used
1005 < table->tuning->shrink_threshold * table->n_buckets)
1007 const Hash_tuning *tuning = table->tuning;
1010 ? table->n_buckets * tuning->shrink_factor
1011 : (table->n_buckets * tuning->shrink_factor
1014 hash_rehash (table, candidate);
1027 hash_print (const Hash_table *table)
1031 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
1036 printf ("%lu:\n", (unsigned long int) (bucket - table->bucket));