binutils/libiberty/hashtab.c

218 #define htab_size(htab)  ((htab)->size)
221 (htab_size) (htab_t htab)
223   return htab_size (htab);
228 #define htab_elements(htab)  ((htab)->n_elements - (htab)->n_deleted)
231 (htab_elements) (htab_t htab)
233   return htab_elements (htab);
267 htab_mod (hashval_t hash, htab_t htab)
269   const struct prime_ent *p = &prime_tab[htab->size_prime_index];
276 htab_mod_m2 (hashval_t hash, htab_t htab)
278   const struct prime_ent *p = &prime_tab[htab->size_prime_index];
297   result = (htab_t) (*alloc_f) (1, sizeof (struct htab));
332   result = (htab_t) (*alloc_f) (alloc_arg, 1, sizeof (struct htab));
356 htab_set_functions_ex (htab_t htab, htab_hash hash_f, htab_eq eq_f,
360   htab->hash_f = hash_f;
361   htab->eq_f = eq_f;
362   htab->del_f = del_f;
363   htab->alloc_arg = alloc_arg;
364   htab->alloc_with_arg_f = alloc_f;
365   htab->free_with_arg_f = free_f;
387 htab_delete (htab_t htab)
389   size_t size = htab_size (htab);
390   PTR *entries = htab->entries;
393   if (htab->del_f)
396 	(*htab->del_f) (entries[i]);
398   if (htab->free_f != NULL)
400       (*htab->free_f) (entries);
401       (*htab->free_f) (htab);
403   else if (htab->free_with_arg_f != NULL)
405       (*htab->free_with_arg_f) (htab->alloc_arg, entries);
406       (*htab->free_with_arg_f) (htab->alloc_arg, htab);
413 htab_empty (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]);
430       if (htab->free_f != NULL)
431 	(*htab->free_f) (htab->entries);
432       else if (htab->free_with_arg_f != NULL)
433 	(*htab->free_with_arg_f) (htab->alloc_arg, htab->entries);
434       if (htab->alloc_with_arg_f != NULL)
435 	htab->entries = (PTR *) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize,
438 	htab->entries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR *));
439      htab->size = nsize;
440      htab->size_prime_index = nindex;
444   htab->n_deleted = 0;
445   htab->n_elements = 0;
449     - Does not call htab->eq_f when it finds an existing entry.
456 find_empty_slot_for_expand (htab_t htab, hashval_t hash)
458   hashval_t index = htab_mod (hash, htab);
459   size_t size = htab_size (htab);
460   PTR *slot = htab->entries + index;
468   hash2 = htab_mod_m2 (hash, htab);
475       slot = htab->entries + index;
492 htab_expand (htab_t htab)
501   oentries = htab->entries;
502   oindex = htab->size_prime_index;
503   osize = htab->size;
505   elts = htab_elements (htab);
520   if (htab->alloc_with_arg_f != NULL)
521     nentries = (PTR *) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize,
524     nentries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR *));
527   htab->entries = nentries;
528   htab->size = nsize;
529   htab->size_prime_index = nindex;
530   htab->n_elements -= htab->n_deleted;
531   htab->n_deleted = 0;
540 	  PTR *q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
549   if (htab->free_f != NULL)
550     (*htab->free_f) (oentries);
551   else if (htab->free_with_arg_f != NULL)
552     (*htab->free_with_arg_f) (htab->alloc_arg, oentries);
560 htab_find_with_hash (htab_t htab, const PTR element, hashval_t hash)
566   htab->searches++;
567   size = htab_size (htab);
568   index = htab_mod (hash, htab);
570   entry = htab->entries[index];
572       || (entry != HTAB_DELETED_ENTRY && (*htab->eq_f) (entry, element)))
575   hash2 = htab_mod_m2 (hash, htab);
578       htab->collisions++;
583       entry = htab->entries[index];
585 	  || (entry != HTAB_DELETED_ENTRY && (*htab->eq_f) (entry, element)))
594 htab_find (htab_t htab, const PTR element)
596   return htab_find_with_hash (htab, element, (*htab->hash_f) (element));
608 htab_find_slot_with_hash (htab_t htab, const PTR element,
616   size = htab_size (htab);
617   if (insert == INSERT && size * 3 <= htab->n_elements * 4)
619       if (htab_expand (htab) == 0)
621       size = htab_size (htab);
624   index = htab_mod (hash, htab);
626   htab->searches++;
629   entry = htab->entries[index];
633     first_deleted_slot = &htab->entries[index];
634   else if ((*htab->eq_f) (entry, element))
635     return &htab->entries[index];
637   hash2 = htab_mod_m2 (hash, htab);
640       htab->collisions++;
645       entry = htab->entries[index];
651 	    first_deleted_slot = &htab->entries[index];
653       else if ((*htab->eq_f) (entry, element))
654 	return &htab->entries[index];
663       htab->n_deleted--;
668   htab->n_elements++;
669   return &htab->entries[index];
676 htab_find_slot (htab_t htab, const PTR element, enum insert_option insert)
678   return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),
687 htab_remove_elt (htab_t htab, PTR element)
689   htab_remove_elt_with_hash (htab, element, (*htab->hash_f) (element));
698 htab_remove_elt_with_hash (htab_t htab, PTR element, hashval_t hash)
702   slot = htab_find_slot_with_hash (htab, element, hash, NO_INSERT);
706   if (htab->del_f)
707     (*htab->del_f) (*slot);
710   htab->n_deleted++;
718 htab_clear_slot (htab_t htab, PTR *slot)
720   if (slot < htab->entries || slot >= htab->entries + htab_size (htab)
724   if (htab->del_f)
725     (*htab->del_f) (*slot);
728   htab->n_deleted++;
737 htab_traverse_noresize (htab_t htab, htab_trav callback, PTR info)
742   slot = htab->entries;
743   limit = slot + htab_size (htab);
760 htab_traverse (htab_t htab, htab_trav callback, PTR info)
762   if (htab_elements (htab) * 8 < htab_size (htab))
763     htab_expand (htab);
765   htab_traverse_noresize (htab, callback, info);
772 htab_collisions (htab_t htab)
774   if (htab->searches == 0)
777   return (double) htab->collisions / (double) htab->searches;