Lines Matching refs:htab
213 #define htab_size(htab) ((htab)->size)
216 (htab_size) (htab_t htab)
218 return htab_size (htab);
223 #define htab_elements(htab) ((htab)->n_elements - (htab)->n_deleted)
226 (htab_elements) (htab_t htab)
228 return htab_elements (htab);
259 /* Compute the primary hash for HASH given HTAB's current size. */
262 htab_mod (hashval_t hash, htab_t htab)
264 const struct prime_ent *p = &prime_tab[htab->size_prime_index];
268 /* Compute the secondary hash for HASH given HTAB's current size. */
271 htab_mod_m2 (hashval_t hash, htab_t htab)
273 const struct prime_ent *p = &prime_tab[htab->size_prime_index];
305 result = (htab_t) (*alloc_f) (alloc_arg, 1, sizeof (struct htab));
358 result = (htab_t) (*alloc_tab_f) (1, sizeof (struct htab));
382 htab_set_functions_ex (htab_t htab, htab_hash hash_f, htab_eq eq_f,
386 htab->hash_f = hash_f;
387 htab->eq_f = eq_f;
388 htab->del_f = del_f;
389 htab->alloc_arg = alloc_arg;
390 htab->alloc_with_arg_f = alloc_f;
391 htab->free_with_arg_f = free_f;
413 htab_delete (htab_t htab)
415 size_t size = htab_size (htab);
416 PTR *entries = htab->entries;
419 if (htab->del_f)
422 (*htab->del_f) (entries[i]);
424 if (htab->free_f != NULL)
426 (*htab->free_f) (entries);
427 (*htab->free_f) (htab);
429 else if (htab->free_with_arg_f != NULL)
431 (*htab->free_with_arg_f) (htab->alloc_arg, entries);
432 (*htab->free_with_arg_f) (htab->alloc_arg, htab);
439 htab_empty (htab_t htab)
441 size_t size = htab_size (htab);
442 PTR *entries = htab->entries;
445 if (htab->del_f)
448 (*htab->del_f) (entries[i]);
456 if (htab->free_f != NULL)
457 (*htab->free_f) (htab->entries);
458 else if (htab->free_with_arg_f != NULL)
459 (*htab->free_with_arg_f) (htab->alloc_arg, htab->entries);
460 if (htab->alloc_with_arg_f != NULL)
461 htab->entries = (PTR *) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize,
464 htab->entries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR *));
465 htab->size = nsize;
466 htab->size_prime_index = nindex;
470 htab->n_deleted = 0;
471 htab->n_elements = 0;
475 - Does not call htab->eq_f when it finds an existing entry.
482 find_empty_slot_for_expand (htab_t htab, hashval_t hash)
484 hashval_t index = htab_mod (hash, htab);
485 size_t size = htab_size (htab);
486 PTR *slot = htab->entries + index;
494 hash2 = htab_mod_m2 (hash, htab);
501 slot = htab->entries + index;
518 htab_expand (htab_t htab)
527 oentries = htab->entries;
528 oindex = htab->size_prime_index;
529 osize = htab->size;
531 elts = htab_elements (htab);
546 if (htab->alloc_with_arg_f != NULL)
547 nentries = (PTR *) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize,
550 nentries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR *));
553 htab->entries = nentries;
554 htab->size = nsize;
555 htab->size_prime_index = nindex;
556 htab->n_elements -= htab->n_deleted;
557 htab->n_deleted = 0;
566 PTR *q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
575 if (htab->free_f != NULL)
576 (*htab->free_f) (oentries);
577 htab->free_with_arg_f != NULL)
578 (*htab->free_with_arg_f) (htab->alloc_arg, oentries);
586 htab_find_with_hash (htab_t htab, const PTR element, hashval_t hash)
592 htab->searches++;
593 size = htab_size (htab);
594 index = htab_mod (hash, htab);
596 entry = htab->entries[index];
598 || (entry != HTAB_DELETED_ENTRY && (*htab->eq_f) (entry, element)))
601 hash2 = htab_mod_m2 (hash, htab);
604 htab->collisions++;
609 entry = htab->entries[index];
611 || (entry != HTAB_DELETED_ENTRY && (*htab->eq_f) (entry, element)))
620 htab_find (htab_t htab, const PTR element)
622 return htab_find_with_hash (htab, element, (*htab->hash_f) (element));
634 htab_find_slot_with_hash (htab_t htab, const PTR element,
642 size = htab_size (htab);
643 if (insert == INSERT && size * 3 <= htab->n_elements * 4)
645 if (htab_expand (htab) == 0)
647 size = htab_size (htab);
650 index = htab_mod (hash, htab);
652 htab->searches++;
655 entry = htab->entries[index];
659 first_deleted_slot = &htab->entries[index];
660 else if ((*htab->eq_f) (entry, element))
661 return &htab->entries[index];
663 hash2 = htab_mod_m2 (hash, htab);
666 htab->collisions++;
671 entry = htab->entries[index];
677 first_deleted_slot = &htab->entries[index];
679 else if ((*htab->eq_f) (entry, element))
680 return &htab->entries[index];
689 htab->n_deleted--;
694 htab->n_elements++;
695 return &htab->entries[index];
702 htab_find_slot (htab_t htab, const PTR element, enum insert_option insert)
704 return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),
713 htab_remove_elt (htab_t htab, PTR element)
715 htab_remove_elt_with_hash (htab, element, (*htab->hash_f) (element));
724 htab_remove_elt_with_hash (htab_t htab, PTR element, hashval_t hash)
728 slot = htab_find_slot_with_hash (htab, element, hash, NO_INSERT);
732 if (htab->del_f)
733 (*htab->del_f) (*slot);
736 htab->n_deleted++;
744 htab_clear_slot (htab_t htab, PTR *slot)
746 if (slot < htab->entries || slot >= htab->entries + htab_size (htab)
750 if (htab->del_f)
751 (*htab->del_f) (*slot);
754 htab->n_deleted++;
763 htab_traverse_noresize (htab_t htab, htab_trav callback, PTR info)
768 slot = htab->entries;
769 limit = slot + htab_size (htab);
786 htab_traverse (htab_t htab, htab_trav callback, PTR info)
788 size_t size = htab_size (htab);
789 if (htab_elements (htab) * 8 < size && size > 32)
790 htab_expand (htab);
792 htab_traverse_noresize (htab, callback, info);
799 htab_collisions (htab_t htab)
801 if (htab->searches == 0)
804 return (double) htab->collisions / (double) htab->searches;
