Lines Matching refs:table
150 hash_get_n_buckets (const Hash_table *table) in hash_get_n_buckets() argument
152 return table->n_buckets; in hash_get_n_buckets()
158 hash_get_n_buckets_used (const Hash_table *table) in hash_get_n_buckets_used() argument
160 return table->n_buckets_used; in hash_get_n_buckets_used()
166 hash_get_n_entries (const Hash_table *table) in hash_get_n_entries() argument
168 return table->n_entries; in hash_get_n_entries()
174 hash_get_max_bucket_length (const Hash_table *table) in hash_get_max_bucket_length() argument
179 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++) in hash_get_max_bucket_length()
201 hash_table_ok (const Hash_table *table) in hash_table_ok() argument
207 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++) in hash_table_ok()
223 if (n_buckets_used == table->n_buckets_used && n_entries == table->n_entries) in hash_table_ok()
230 hash_print_statistics (const Hash_table *table, FILE *stream) in hash_print_statistics() argument
232 size_t n_entries = hash_get_n_entries (table); in hash_print_statistics()
233 size_t n_buckets = hash_get_n_buckets (table); in hash_print_statistics()
234 size_t n_buckets_used = hash_get_n_buckets_used (table); in hash_print_statistics()
235 size_t max_bucket_length = hash_get_max_bucket_length (table); in hash_print_statistics()
249 safe_hasher (const Hash_table *table, const void *key) in safe_hasher() argument
251 size_t n = table->hasher (key, table->n_buckets); in safe_hasher()
252 if (! (n < table->n_buckets)) in safe_hasher()
254 return table->bucket + n; in safe_hasher()
261 hash_lookup (const Hash_table *table, const void *entry) in hash_lookup() argument
263 struct hash_entry const *bucket = safe_hasher (table, entry); in hash_lookup()
270 if (entry == cursor->data || table->comparator (entry, cursor->data)) in hash_lookup()
288 hash_get_first (const Hash_table *table) in hash_get_first() argument
292 if (table->n_entries == 0) in hash_get_first()
295 for (bucket = table->bucket; ; bucket++) in hash_get_first()
296 if (! (bucket < table->bucket_limit)) in hash_get_first()
307 hash_get_next (const Hash_table *table, const void *entry) in hash_get_next() argument
309 struct hash_entry const *bucket = safe_hasher (table, entry); in hash_get_next()
323 while (++bucket < table->bucket_limit) in hash_get_next()
336 hash_get_entries (const Hash_table *table, void **buffer, in hash_get_entries() argument
343 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++) in hash_get_entries()
368 hash_do_for_each (const Hash_table *table, Hash_processor processor, in hash_do_for_each() argument
375 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++) in hash_do_for_each()
512 check_tuning (Hash_table *table) in check_tuning() argument
514 const Hash_tuning *tuning = table->tuning; in check_tuning()
535 table->tuning = &default_tuning; in check_tuning()
598 Hash_table *table; in hash_initialize() local
605 table = malloc (sizeof *table); in hash_initialize()
606 if (table == NULL) in hash_initialize()
611 table->tuning = tuning; in hash_initialize()
612 if (!check_tuning (table)) in hash_initialize()
622 table->n_buckets = compute_bucket_size (candidate, tuning); in hash_initialize()
623 if (!table->n_buckets) in hash_initialize()
626 table->bucket = calloc (table->n_buckets, sizeof *table->bucket); in hash_initialize()
627 if (table->bucket == NULL) in hash_initialize()
629 table->bucket_limit = table->bucket + table->n_buckets; in hash_initialize()
630 table->n_buckets_used = 0; in hash_initialize()
631 table->n_entries = 0; in hash_initialize()
633 table->hasher = hasher; in hash_initialize()
634 table->comparator = comparator; in hash_initialize()
635 table->data_freer = data_freer; in hash_initialize()
637 table->free_entry_list = NULL; in hash_initialize()
639 obstack_init (&table->entry_stack); in hash_initialize()
641 return table; in hash_initialize()
644 free (table); in hash_initialize()
653 hash_clear (Hash_table *table) in hash_clear() argument
657 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++) in hash_clear()
667 if (table->data_freer) in hash_clear()
668 table->data_freer (cursor->data); in hash_clear()
674 cursor->next = table->free_entry_list; in hash_clear()
675 table->free_entry_list = cursor; in hash_clear()
679 if (table->data_freer) in hash_clear()
680 table->data_freer (bucket->data); in hash_clear()
686 table->n_buckets_used = 0; in hash_clear()
687 table->n_entries = 0; in hash_clear()
696 hash_free (Hash_table *table) in hash_free() argument
703 if (table->data_freer && table->n_entries) in hash_free()
705 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++) in hash_free()
710 table->data_freer (cursor->data); in hash_free()
717 obstack_free (&table->entry_stack, NULL); in hash_free()
722 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++) in hash_free()
732 for (cursor = table->free_entry_list; cursor; cursor = next) in hash_free()
741 free (table->bucket); in hash_free()
742 free (table); in hash_free()
751 allocate_entry (Hash_table *table) in allocate_entry() argument
755 if (table->free_entry_list) in allocate_entry()
757 new = table->free_entry_list; in allocate_entry()
758 table->free_entry_list = new->next; in allocate_entry()
763 new = obstack_alloc (&table->entry_stack, sizeof *new); in allocate_entry()
776 free_entry (Hash_table *table, struct hash_entry *entry) in free_entry() argument
779 entry->next = table->free_entry_list; in free_entry()
780 table->free_entry_list = entry; in free_entry()
790 hash_find_entry (Hash_table *table, const void *entry, in hash_find_entry() argument
793 struct hash_entry *bucket = safe_hasher (table, entry); in hash_find_entry()
803 if (entry == bucket->data || table->comparator (entry, bucket->data)) in hash_find_entry()
816 free_entry (table, next); in hash_find_entry()
831 || table->comparator (entry, cursor->next->data)) in hash_find_entry()
842 free_entry (table, next); in hash_find_entry()
943 hash_rehash (Hash_table *table, size_t candidate) in hash_rehash() argument
947 size_t new_size = compute_bucket_size (candidate, table->tuning); in hash_rehash()
951 if (new_size == table->n_buckets) in hash_rehash()
961 new_table->tuning = table->tuning; in hash_rehash()
962 new_table->hasher = table->hasher; in hash_rehash()
963 new_table->comparator = table->comparator; in hash_rehash()
964 new_table->data_freer = table->data_freer; in hash_rehash()
982 new_table->entry_stack = table->entry_stack; in hash_rehash()
984 new_table->free_entry_list = table->free_entry_list; in hash_rehash()
986 if (transfer_entries (new_table, table, false)) in hash_rehash()
989 free (table->bucket); in hash_rehash()
990 table->bucket = new_table->bucket; in hash_rehash()
991 table->bucket_limit = new_table->bucket_limit; in hash_rehash()
992 table->n_buckets = new_table->n_buckets; in hash_rehash()
993 table->n_buckets_used = new_table->n_buckets_used; in hash_rehash()
994 table->free_entry_list = new_table->free_entry_list; in hash_rehash()
1012 table->free_entry_list = new_table->free_entry_list; in hash_rehash()
1013 if (! (transfer_entries (table, new_table, true) in hash_rehash()
1014 && transfer_entries (table, new_table, false))) in hash_rehash()
1038 hash_insert_if_absent (Hash_table *table, void const *entry, in hash_insert_if_absent() argument
1051 if ((data = hash_find_entry (table, entry, &bucket, false)) != NULL) in hash_insert_if_absent()
1063 if (table->n_buckets_used in hash_insert_if_absent()
1064 > table->tuning->growth_threshold * table->n_buckets) in hash_insert_if_absent()
1068 check_tuning (table); in hash_insert_if_absent()
1069 if (table->n_buckets_used in hash_insert_if_absent()
1070 > table->tuning->growth_threshold * table->n_buckets) in hash_insert_if_absent()
1072 const Hash_tuning *tuning = table->tuning; in hash_insert_if_absent()
1075 ? (table->n_buckets * tuning->growth_factor) in hash_insert_if_absent()
1076 : (table->n_buckets * tuning->growth_factor in hash_insert_if_absent()
1083 if (!hash_rehash (table, candidate)) in hash_insert_if_absent()
1087 if (hash_find_entry (table, entry, &bucket, false) != NULL) in hash_insert_if_absent()
1096 struct hash_entry *new_entry = allocate_entry (table); in hash_insert_if_absent()
1106 table->n_entries++; in hash_insert_if_absent()
1113 table->n_entries++; in hash_insert_if_absent()
1114 table->n_buckets_used++; in hash_insert_if_absent()
1126 hash_insert (Hash_table *table, void const *entry) in hash_insert() argument
1129 int err = hash_insert_if_absent (table, entry, &matched_ent); in hash_insert()
1140 hash_delete (Hash_table *table, const void *entry) in hash_delete() argument
1145 data = hash_find_entry (table, entry, &bucket, true); in hash_delete()
1149 table->n_entries--; in hash_delete()
1152 table->n_buckets_used--; in hash_delete()
1157 if (table->n_buckets_used in hash_delete()
1158 < table->tuning->shrink_threshold * table->n_buckets) in hash_delete()
1162 check_tuning (table); in hash_delete()
1163 if (table->n_buckets_used in hash_delete()
1164 < table->tuning->shrink_threshold * table->n_buckets) in hash_delete()
1166 const Hash_tuning *tuning = table->tuning; in hash_delete()
1169 ? table->n_buckets * tuning->shrink_factor in hash_delete()
1170 : (table->n_buckets * tuning->shrink_factor in hash_delete()
1173 if (!hash_rehash (table, candidate)) in hash_delete()
1181 struct hash_entry *cursor = table->free_entry_list; in hash_delete()
1189 table->free_entry_list = NULL; in hash_delete()
1204 hash_print (const Hash_table *table) in hash_print() argument
1206 struct hash_entry *bucket = (struct hash_entry *) table->bucket; in hash_print()
1208 for ( ; bucket < table->bucket_limit; bucket++) in hash_print()
1213 printf ("%lu:\n", (unsigned long int) (bucket - table->bucket)); in hash_print()