212 #define htab_size(htab)  ((htab)->size)  argument
215 (htab_size) (htab_t htab)  in size_t()
217   return htab_size (htab);  in size_t()
222 #define htab_elements(htab)  ((htab)->n_elements - (htab)->n_deleted)  argument
225 (htab_elements) (htab_t htab)  in size_t()
227   return htab_elements (htab);  in size_t()
261 htab_mod (hashval_t hash, htab_t htab)  in htab_mod()  argument
263   const struct prime_ent *p = &prime_tab[htab->size_prime_index];  in htab_mod()
270 htab_mod_m2 (hashval_t hash, htab_t htab)  in htab_mod_m2()  argument
272   const struct prime_ent *p = &prime_tab[htab->size_prime_index];  in htab_mod_m2()
304   result = (htab_t) (*alloc_f) (alloc_arg, 1, sizeof (struct htab));  in htab_create_alloc_ex()
357   result = (htab_t) (*alloc_tab_f) (1, sizeof (struct htab));  in htab_create_typed_alloc()
381 htab_set_functions_ex (htab_t htab, htab_hash hash_f, htab_eq eq_f,  in htab_set_functions_ex()  argument
385   htab->hash_f = hash_f;  in htab_set_functions_ex()
386   htab->eq_f = eq_f;  in htab_set_functions_ex()
387   htab->del_f = del_f;  in htab_set_functions_ex()
388   htab->alloc_arg = alloc_arg;  in htab_set_functions_ex()
389   htab->alloc_with_arg_f = alloc_f;  in htab_set_functions_ex()
390   htab->free_with_arg_f = free_f;  in htab_set_functions_ex()
412 htab_delete (htab_t htab)  in htab_delete()  argument
414   size_t size = htab_size (htab);  in htab_delete()
415   void **entries = htab->entries;  in htab_delete()
418   if (htab->del_f)  in htab_delete()
421           (*htab->del_f) (entries[i]);  in htab_delete()
423   if (htab->free_f != NULL)  in htab_delete()
425       (*htab->free_f) (entries);  in htab_delete()
426       (*htab->free_f) (htab);  in htab_delete()
428   else if (htab->free_with_arg_f != NULL)  in htab_delete()
430       (*htab->free_with_arg_f) (htab->alloc_arg, entries);  in htab_delete()
431       (*htab->free_with_arg_f) (htab->alloc_arg, htab);  in htab_delete()
438 htab_empty (htab_t htab)  in htab_empty()  argument
440   size_t size = htab_size (htab);  in htab_empty()
441   void **entries = htab->entries;  in htab_empty()
444   if (htab->del_f)  in htab_empty()
447           (*htab->del_f) (entries[i]);  in htab_empty()
455       if (htab->free_f != NULL)  in htab_empty()
456           (*htab->free_f) (htab->entries);  in htab_empty()
457       else if (htab->free_with_arg_f != NULL)  in htab_empty()
458           (*htab->free_with_arg_f) (htab->alloc_arg, htab->entries);  in htab_empty()
459       if (htab->alloc_with_arg_f != NULL)  in htab_empty()
460           htab->entries = (void **) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize,  in htab_empty()
463           htab->entries = (void **) (*htab->alloc_f) (nsize, sizeof (void *));  in htab_empty()
464      htab->size = nsize;  in htab_empty()
465      htab->size_prime_index = nindex;  in htab_empty()
469   htab->n_deleted = 0;  in htab_empty()
470   htab->n_elements = 0;  in htab_empty()
481 find_empty_slot_for_expand (htab_t htab, hashval_t hash)  in find_empty_slot_for_expand()  argument
483   hashval_t index = htab_mod (hash, htab);  in find_empty_slot_for_expand()
484   size_t size = htab_size (htab);  in find_empty_slot_for_expand()
485   void **slot = htab->entries + index;  in find_empty_slot_for_expand()
493   hash2 = htab_mod_m2 (hash, htab);  in find_empty_slot_for_expand()
500       slot = htab->entries + index;  in find_empty_slot_for_expand()
517 htab_expand (htab_t htab)  in htab_expand()  argument
526   oentries = htab->entries;  in htab_expand()
527   oindex = htab->size_prime_index;  in htab_expand()
528   osize = htab->size;  in htab_expand()
530   elts = htab_elements (htab);  in htab_expand()
545   if (htab->alloc_with_arg_f != NULL)  in htab_expand()
546     nentries = (void **) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize,  in htab_expand()
549     nentries = (void **) (*htab->alloc_f) (nsize, sizeof (void *));  in htab_expand()
552   htab->entries = nentries;  in htab_expand()
553   htab->size = nsize;  in htab_expand()
554   htab->size_prime_index = nindex;  in htab_expand()
555   htab->n_elements -= htab->n_deleted;  in htab_expand()
556   htab->n_deleted = 0;  in htab_expand()
565             void **q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));  in htab_expand()
574   if (htab->free_f != NULL)  in htab_expand()
575     (*htab->free_f) (oentries);  in htab_expand()
576   else if (htab->free_with_arg_f != NULL)  in htab_expand()
577     (*htab->free_with_arg_f) (htab->alloc_arg, oentries);  in htab_expand()
585 htab_find_with_hash (htab_t htab, const void *element, hashval_t hash)  in htab_find_with_hash()  argument
591   htab->searches++;  in htab_find_with_hash()
592   size = htab_size (htab);  in htab_find_with_hash()
593   index = htab_mod (hash, htab);  in htab_find_with_hash()
595   entry = htab->entries[index];  in htab_find_with_hash()
597       || (entry != HTAB_DELETED_ENTRY && (*htab->eq_f) (entry, element)))  in htab_find_with_hash()
600   hash2 = htab_mod_m2 (hash, htab);  in htab_find_with_hash()
603       htab->collisions++;  in htab_find_with_hash()
608       entry = htab->entries[index];  in htab_find_with_hash()
610             || (entry != HTAB_DELETED_ENTRY && (*htab->eq_f) (entry, element)))  in htab_find_with_hash()
619 htab_find (htab_t htab, const void *element)  in htab_find()  argument
621   return htab_find_with_hash (htab, element, (*htab->hash_f) (element));  in htab_find()
633 htab_find_slot_with_hash (htab_t htab, const void *element,  in htab_find_slot_with_hash()  argument
641   size = htab_size (htab);  in htab_find_slot_with_hash()
642   if (insert == INSERT && size * 3 <= htab->n_elements * 4)  in htab_find_slot_with_hash()
644       if (htab_expand (htab) == 0)  in htab_find_slot_with_hash()
646       size = htab_size (htab);  in htab_find_slot_with_hash()
649   index = htab_mod (hash, htab);  in htab_find_slot_with_hash()
651   htab->searches++;  in htab_find_slot_with_hash()
654   entry = htab->entries[index];  in htab_find_slot_with_hash()
658     first_deleted_slot = &htab->entries[index];  in htab_find_slot_with_hash()
659   else if ((*htab->eq_f) (entry, element))  in htab_find_slot_with_hash()
660     return &htab->entries[index];  in htab_find_slot_with_hash()
662   hash2 = htab_mod_m2 (hash, htab);  in htab_find_slot_with_hash()
665       htab->collisions++;  in htab_find_slot_with_hash()
670       entry = htab->entries[index];  in htab_find_slot_with_hash()
676               first_deleted_slot = &htab->entries[index];  in htab_find_slot_with_hash()
678       else if ((*htab->eq_f) (entry, element))  in htab_find_slot_with_hash()
679           return &htab->entries[index];  in htab_find_slot_with_hash()
688       htab->n_deleted--;  in htab_find_slot_with_hash()
693   htab->n_elements++;  in htab_find_slot_with_hash()
694   return &htab->entries[index];  in htab_find_slot_with_hash()
701 htab_find_slot (htab_t htab, const void *element, enum insert_option insert)  in htab_find_slot()  argument
703   return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),  in htab_find_slot()
712 htab_remove_elt (htab_t htab, const void *element)  in htab_remove_elt()  argument
714   htab_remove_elt_with_hash (htab, element, (*htab->hash_f) (element));  in htab_remove_elt()
723 htab_remove_elt_with_hash (htab_t htab, const void *element, hashval_t hash)  in htab_remove_elt_with_hash()  argument
727   slot = htab_find_slot_with_hash (htab, element, hash, NO_INSERT);  in htab_remove_elt_with_hash()
731   if (htab->del_f)  in htab_remove_elt_with_hash()
732     (*htab->del_f) (*slot);  in htab_remove_elt_with_hash()
735   htab->n_deleted++;  in htab_remove_elt_with_hash()
743 htab_clear_slot (htab_t htab, void **slot)  in htab_clear_slot()  argument
745   if (slot < htab->entries || slot >= htab->entries + htab_size (htab)  in htab_clear_slot()
749   if (htab->del_f)  in htab_clear_slot()
750     (*htab->del_f) (*slot);  in htab_clear_slot()
753   htab->n_deleted++;  in htab_clear_slot()
762 htab_traverse_noresize (htab_t htab, htab_trav callback, void *info)  in htab_traverse_noresize()  argument
767   slot = htab->entries;  in htab_traverse_noresize()
768   limit = slot + htab_size (htab);  in htab_traverse_noresize()
785 htab_traverse (htab_t htab, htab_trav callback, void *info)  in htab_traverse()  argument
787   size_t size = htab_size (htab);  in htab_traverse()
788   if (htab_elements (htab) * 8 < size && size > 32)  in htab_traverse()
789     htab_expand (htab);  in htab_traverse()
791   htab_traverse_noresize (htab, callback, info);  in htab_traverse()
798 htab_collisions (htab_t htab)  in htab_collisions()  argument
800   if (htab->searches == 0)  in htab_collisions()
803   return (double) htab->collisions / (double) htab->searches;  in htab_collisions()