1 /* Interface to hashtable implementations.
2 Copyright (C) 2006-2020 Free Software Foundation, Inc.
4 This file is part of libctf.
6 libctf is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 This program is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
14 See the GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program; see the file COPYING. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "libiberty.h"
25 /* We have three hashtable implementations:
27 - ctf_hash_* is an interface to a fixed-size hash from const char * ->
28 ctf_id_t with number of elements specified at creation time, that should
29 support addition of items but need not support removal.
31 - ctf_dynhash_* is an interface to a dynamically-expanding hash with
32 unknown size that should support addition of large numbers of items, and
33 removal as well, and is used only at type-insertion time and during
36 - ctf_dynset_* is an interface to a dynamically-expanding hash that contains
39 These can be implemented by the same underlying hashmap if you wish. */
41 /* The helem is used for general key/value mappings in both the ctf_hash and
42 ctf_dynhash: the owner may not have space allocated for it, and will be
43 garbage (not NULL!) in that case. */
45 typedef struct ctf_helem
47 void *key
; /* Either a pointer, or a coerced ctf_id_t. */
48 void *value
; /* The value (possibly a coerced int). */
49 ctf_dynhash_t
*owner
; /* The hash that owns us. */
52 /* Equally, the key_free and value_free may not exist. */
57 ctf_hash_free_fun key_free
;
58 ctf_hash_free_fun value_free
;
61 /* Hash and eq functions for the dynhash and hash. */
64 ctf_hash_integer (const void *ptr
)
66 ctf_helem_t
*hep
= (ctf_helem_t
*) ptr
;
68 return htab_hash_pointer (hep
->key
);
72 ctf_hash_eq_integer (const void *a
, const void *b
)
74 ctf_helem_t
*hep_a
= (ctf_helem_t
*) a
;
75 ctf_helem_t
*hep_b
= (ctf_helem_t
*) b
;
77 return htab_eq_pointer (hep_a
->key
, hep_b
->key
);
81 ctf_hash_string (const void *ptr
)
83 ctf_helem_t
*hep
= (ctf_helem_t
*) ptr
;
85 return htab_hash_string (hep
->key
);
89 ctf_hash_eq_string (const void *a
, const void *b
)
91 ctf_helem_t
*hep_a
= (ctf_helem_t
*) a
;
92 ctf_helem_t
*hep_b
= (ctf_helem_t
*) b
;
94 return !strcmp((const char *) hep_a
->key
, (const char *) hep_b
->key
);
97 /* Hash a type_mapping_key. */
99 ctf_hash_type_mapping_key (const void *ptr
)
101 ctf_helem_t
*hep
= (ctf_helem_t
*) ptr
;
102 ctf_link_type_mapping_key_t
*k
= (ctf_link_type_mapping_key_t
*) hep
->key
;
104 return htab_hash_pointer (k
->cltm_fp
) + 59 * htab_hash_pointer ((void *) k
->cltm_idx
);
108 ctf_hash_eq_type_mapping_key (const void *a
, const void *b
)
110 ctf_helem_t
*hep_a
= (ctf_helem_t
*) a
;
111 ctf_helem_t
*hep_b
= (ctf_helem_t
*) b
;
112 ctf_link_type_mapping_key_t
*key_a
= (ctf_link_type_mapping_key_t
*) hep_a
->key
;
113 ctf_link_type_mapping_key_t
*key_b
= (ctf_link_type_mapping_key_t
*) hep_b
->key
;
115 return (key_a
->cltm_fp
== key_b
->cltm_fp
)
116 && (key_a
->cltm_idx
== key_b
->cltm_idx
);
120 /* Hash and eq functions for the dynset. Most of these can just use the
121 underlying hashtab functions directly. */
124 ctf_dynset_eq_string (const void *a
, const void *b
)
126 return !strcmp((const char *) a
, (const char *) b
);
129 /* The dynhash, used for hashes whose size is not known at creation time. */
131 /* Free a single ctf_helem with arbitrary key/value functions. */
134 ctf_dynhash_item_free (void *item
)
136 ctf_helem_t
*helem
= item
;
138 if (helem
->owner
->key_free
&& helem
->key
)
139 helem
->owner
->key_free (helem
->key
);
140 if (helem
->owner
->value_free
&& helem
->value
)
141 helem
->owner
->value_free (helem
->value
);
146 ctf_dynhash_create (ctf_hash_fun hash_fun
, ctf_hash_eq_fun eq_fun
,
147 ctf_hash_free_fun key_free
, ctf_hash_free_fun value_free
)
149 ctf_dynhash_t
*dynhash
;
150 htab_del del
= ctf_dynhash_item_free
;
152 if (key_free
|| value_free
)
153 dynhash
= malloc (sizeof (ctf_dynhash_t
));
155 dynhash
= malloc (offsetof (ctf_dynhash_t
, key_free
));
159 if (key_free
== NULL
&& value_free
== NULL
)
162 /* 7 is arbitrary and untested for now. */
163 if ((dynhash
->htab
= htab_create_alloc (7, (htab_hash
) hash_fun
, eq_fun
,
164 del
, xcalloc
, free
)) == NULL
)
170 if (key_free
|| value_free
)
172 dynhash
->key_free
= key_free
;
173 dynhash
->value_free
= value_free
;
179 static ctf_helem_t
**
180 ctf_hashtab_lookup (struct htab
*htab
, const void *key
, enum insert_option insert
)
182 ctf_helem_t tmp
= { .key
= (void *) key
};
183 return (ctf_helem_t
**) htab_find_slot (htab
, &tmp
, insert
);
187 ctf_hashtab_insert (struct htab
*htab
, void *key
, void *value
,
188 ctf_hash_free_fun key_free
,
189 ctf_hash_free_fun value_free
)
193 slot
= ctf_hashtab_lookup (htab
, key
, INSERT
);
203 /* Only spend space on the owner if we're going to use it: if there is a
204 key or value freeing function. */
205 if (key_free
|| value_free
)
206 *slot
= malloc (sizeof (ctf_helem_t
));
208 *slot
= malloc (offsetof (ctf_helem_t
, owner
));
218 value_free ((*slot
)->value
);
220 (*slot
)->value
= value
;
225 ctf_dynhash_insert (ctf_dynhash_t
*hp
, void *key
, void *value
)
228 ctf_hash_free_fun key_free
= NULL
, value_free
= NULL
;
230 if (hp
->htab
->del_f
== ctf_dynhash_item_free
)
232 key_free
= hp
->key_free
;
233 value_free
= hp
->value_free
;
235 slot
= ctf_hashtab_insert (hp
->htab
, key
, value
,
236 key_free
, value_free
);
241 /* Keep track of the owner, so that the del function can get at the key_free
242 and value_free functions. Only do this if one of those functions is set:
243 if not, the owner is not even present in the helem. */
245 if (key_free
|| value_free
)
252 ctf_dynhash_remove (ctf_dynhash_t
*hp
, const void *key
)
254 ctf_helem_t hep
= { (void *) key
, NULL
, NULL
};
255 htab_remove_elt (hp
->htab
, &hep
);
259 ctf_dynhash_empty (ctf_dynhash_t
*hp
)
261 htab_empty (hp
->htab
);
265 ctf_dynhash_elements (ctf_dynhash_t
*hp
)
267 return htab_elements (hp
->htab
);
271 ctf_dynhash_lookup (ctf_dynhash_t
*hp
, const void *key
)
275 slot
= ctf_hashtab_lookup (hp
->htab
, key
, NO_INSERT
);
278 return (*slot
)->value
;
283 /* TRUE/FALSE return. */
285 ctf_dynhash_lookup_kv (ctf_dynhash_t
*hp
, const void *key
,
286 const void **orig_key
, void **value
)
290 slot
= ctf_hashtab_lookup (hp
->htab
, key
, NO_INSERT
);
295 *orig_key
= (*slot
)->key
;
297 *value
= (*slot
)->value
;
303 typedef struct ctf_traverse_cb_arg
307 } ctf_traverse_cb_arg_t
;
310 ctf_hashtab_traverse (void **slot
, void *arg_
)
312 ctf_helem_t
*helem
= *((ctf_helem_t
**) slot
);
313 ctf_traverse_cb_arg_t
*arg
= (ctf_traverse_cb_arg_t
*) arg_
;
315 arg
->fun (helem
->key
, helem
->value
, arg
->arg
);
320 ctf_dynhash_iter (ctf_dynhash_t
*hp
, ctf_hash_iter_f fun
, void *arg_
)
322 ctf_traverse_cb_arg_t arg
= { fun
, arg_
};
323 htab_traverse (hp
->htab
, ctf_hashtab_traverse
, &arg
);
326 typedef struct ctf_traverse_find_cb_arg
328 ctf_hash_iter_find_f fun
;
331 } ctf_traverse_find_cb_arg_t
;
334 ctf_hashtab_traverse_find (void **slot
, void *arg_
)
336 ctf_helem_t
*helem
= *((ctf_helem_t
**) slot
);
337 ctf_traverse_find_cb_arg_t
*arg
= (ctf_traverse_find_cb_arg_t
*) arg_
;
339 if (arg
->fun (helem
->key
, helem
->value
, arg
->arg
))
341 arg
->found_key
= helem
->key
;
348 ctf_dynhash_iter_find (ctf_dynhash_t
*hp
, ctf_hash_iter_find_f fun
, void *arg_
)
350 ctf_traverse_find_cb_arg_t arg
= { fun
, arg_
, NULL
};
351 htab_traverse (hp
->htab
, ctf_hashtab_traverse_find
, &arg
);
352 return arg
.found_key
;
355 typedef struct ctf_traverse_remove_cb_arg
358 ctf_hash_iter_remove_f fun
;
360 } ctf_traverse_remove_cb_arg_t
;
363 ctf_hashtab_traverse_remove (void **slot
, void *arg_
)
365 ctf_helem_t
*helem
= *((ctf_helem_t
**) slot
);
366 ctf_traverse_remove_cb_arg_t
*arg
= (ctf_traverse_remove_cb_arg_t
*) arg_
;
368 if (arg
->fun (helem
->key
, helem
->value
, arg
->arg
))
369 htab_clear_slot (arg
->htab
, slot
);
374 ctf_dynhash_iter_remove (ctf_dynhash_t
*hp
, ctf_hash_iter_remove_f fun
,
377 ctf_traverse_remove_cb_arg_t arg
= { hp
->htab
, fun
, arg_
};
378 htab_traverse (hp
->htab
, ctf_hashtab_traverse_remove
, &arg
);
381 /* Traverse a dynhash in arbitrary order, in _next iterator form.
383 Mutating the dynhash while iterating is not supported (just as it isn't for
386 Note: unusually, this returns zero on success and a *positive* value on
387 error, because it does not take an fp, taking an error pointer would be
388 incredibly clunky, and nearly all error-handling ends up stuffing the result
389 of this into some sort of errno or ctf_errno, which is invariably
390 positive. So doing this simplifies essentially all callers. */
392 ctf_dynhash_next (ctf_dynhash_t
*h
, ctf_next_t
**it
, void **key
, void **value
)
399 size_t size
= htab_size (h
->htab
);
401 /* If the table has too many entries to fit in an ssize_t, just give up.
402 This might be spurious, but if any type-related hashtable has ever been
403 nearly as large as that then something very odd is going on. */
404 if (((ssize_t
) size
) < 0)
407 if ((i
= ctf_next_create ()) == NULL
)
410 i
->u
.ctn_hash_slot
= h
->htab
->entries
;
413 i
->ctn_size
= (ssize_t
) size
;
414 i
->ctn_iter_fun
= (void (*) (void)) ctf_dynhash_next
;
418 if ((void (*) (void)) ctf_dynhash_next
!= i
->ctn_iter_fun
)
419 return ECTF_NEXT_WRONGFUN
;
421 if (h
!= i
->cu
.ctn_h
)
422 return ECTF_NEXT_WRONGFP
;
424 if ((ssize_t
) i
->ctn_n
== i
->ctn_size
)
427 while ((ssize_t
) i
->ctn_n
< i
->ctn_size
428 && (*i
->u
.ctn_hash_slot
== HTAB_EMPTY_ENTRY
429 || *i
->u
.ctn_hash_slot
== HTAB_DELETED_ENTRY
))
431 i
->u
.ctn_hash_slot
++;
435 if ((ssize_t
) i
->ctn_n
== i
->ctn_size
)
438 slot
= *i
->u
.ctn_hash_slot
;
443 *value
= slot
->value
;
445 i
->u
.ctn_hash_slot
++;
451 ctf_next_destroy (i
);
453 return ECTF_NEXT_END
;
456 /* Traverse a sorted dynhash, in _next iterator form.
458 See ctf_dynhash_next for notes on error returns, etc.
460 Sort keys before iterating over them using the SORT_FUN and SORT_ARG.
462 If SORT_FUN is null, thunks to ctf_dynhash_next. */
464 ctf_dynhash_next_sorted (ctf_dynhash_t
*h
, ctf_next_t
**it
, void **key
,
465 void **value
, ctf_hash_sort_f sort_fun
, void *sort_arg
)
469 if (sort_fun
== NULL
)
470 return ctf_dynhash_next (h
, it
, key
, value
);
474 size_t els
= ctf_dynhash_elements (h
);
475 ctf_next_t
*accum_i
= NULL
;
478 ctf_next_hkv_t
*walk
;
480 if (((ssize_t
) els
) < 0)
483 if ((i
= ctf_next_create ()) == NULL
)
486 if ((i
->u
.ctn_sorted_hkv
= calloc (els
, sizeof (ctf_next_hkv_t
))) == NULL
)
488 ctf_next_destroy (i
);
491 walk
= i
->u
.ctn_sorted_hkv
;
495 while ((err
= ctf_dynhash_next (h
, &accum_i
, &key
, &value
)) == 0)
498 walk
->hkv_value
= value
;
501 if (err
!= ECTF_NEXT_END
)
503 ctf_next_destroy (i
);
508 ctf_qsort_r (i
->u
.ctn_sorted_hkv
, els
, sizeof (ctf_next_hkv_t
),
509 (int (*) (const void *, const void *, void *)) sort_fun
,
512 i
->ctn_size
= (ssize_t
) els
;
513 i
->ctn_iter_fun
= (void (*) (void)) ctf_dynhash_next_sorted
;
517 if ((void (*) (void)) ctf_dynhash_next_sorted
!= i
->ctn_iter_fun
)
518 return ECTF_NEXT_WRONGFUN
;
520 if (h
!= i
->cu
.ctn_h
)
521 return ECTF_NEXT_WRONGFP
;
523 if ((ssize_t
) i
->ctn_n
== i
->ctn_size
)
525 ctf_next_destroy (i
);
527 return ECTF_NEXT_END
;
531 *key
= i
->u
.ctn_sorted_hkv
[i
->ctn_n
].hkv_key
;
533 *value
= i
->u
.ctn_sorted_hkv
[i
->ctn_n
].hkv_value
;
539 ctf_dynhash_destroy (ctf_dynhash_t
*hp
)
542 htab_delete (hp
->htab
);
546 /* The dynset, used for sets of keys with no value. The implementation of this
547 can be much simpler, because without a value the slot can simply be the
548 stored key, which means we don't need to store the freeing functions and the
549 dynset itself is just a htab. */
552 ctf_dynset_create (htab_hash hash_fun
, htab_eq eq_fun
,
553 ctf_hash_free_fun key_free
)
555 /* 7 is arbitrary and untested for now. */
556 return (ctf_dynset_t
*) htab_create_alloc (7, (htab_hash
) hash_fun
, eq_fun
,
557 key_free
, xcalloc
, free
);
560 /* The dynset has one complexity: the underlying implementation reserves two
561 values for internal hash table implementation details (empty versus deleted
562 entries). These values are otherwise very useful for pointers cast to ints,
563 so transform the ctf_dynset_inserted value to allow for it. (This
564 introduces an ambiguity in that one can no longer store these two values in
565 the dynset, but if we pick high enough values this is very unlikely to be a
568 We leak this implementation detail to the freeing functions on the grounds
569 that any use of these functions is overwhelmingly likely to be in sets using
570 real pointers, which will be unaffected. */
572 #define DYNSET_EMPTY_ENTRY_REPLACEMENT ((void *) (uintptr_t) -64)
573 #define DYNSET_DELETED_ENTRY_REPLACEMENT ((void *) (uintptr_t) -63)
576 key_to_internal (const void *key
)
578 if (key
== HTAB_EMPTY_ENTRY
)
579 return DYNSET_EMPTY_ENTRY_REPLACEMENT
;
580 else if (key
== HTAB_DELETED_ENTRY
)
581 return DYNSET_DELETED_ENTRY_REPLACEMENT
;
587 internal_to_key (const void *internal
)
589 if (internal
== DYNSET_EMPTY_ENTRY_REPLACEMENT
)
590 return HTAB_EMPTY_ENTRY
;
591 else if (internal
== DYNSET_DELETED_ENTRY_REPLACEMENT
)
592 return HTAB_DELETED_ENTRY
;
593 return (void *) internal
;
597 ctf_dynset_insert (ctf_dynset_t
*hp
, void *key
)
599 struct htab
*htab
= (struct htab
*) hp
;
602 slot
= htab_find_slot (htab
, key
, INSERT
);
613 (*htab
->del_f
) (*slot
);
616 *slot
= key_to_internal (key
);
622 ctf_dynset_remove (ctf_dynset_t
*hp
, const void *key
)
624 htab_remove_elt ((struct htab
*) hp
, key_to_internal (key
));
628 ctf_dynset_destroy (ctf_dynset_t
*hp
)
631 htab_delete ((struct htab
*) hp
);
635 ctf_dynset_lookup (ctf_dynset_t
*hp
, const void *key
)
637 void **slot
= htab_find_slot ((struct htab
*) hp
,
638 key_to_internal (key
), NO_INSERT
);
641 return internal_to_key (*slot
);
645 /* TRUE/FALSE return. */
647 ctf_dynset_exists (ctf_dynset_t
*hp
, const void *key
, const void **orig_key
)
649 void **slot
= htab_find_slot ((struct htab
*) hp
,
650 key_to_internal (key
), NO_INSERT
);
652 if (orig_key
&& slot
)
653 *orig_key
= internal_to_key (*slot
);
654 return (slot
!= NULL
);
657 /* Look up a completely random value from the set, if any exist.
658 Keys with value zero cannot be distinguished from a nonexistent key. */
660 ctf_dynset_lookup_any (ctf_dynset_t
*hp
)
662 struct htab
*htab
= (struct htab
*) hp
;
663 void **slot
= htab
->entries
;
664 void **limit
= slot
+ htab_size (htab
);
667 && (*slot
== HTAB_EMPTY_ENTRY
|| *slot
== HTAB_DELETED_ENTRY
))
671 return internal_to_key (*slot
);
675 /* Traverse a dynset in arbitrary order, in _next iterator form.
677 Otherwise, just like ctf_dynhash_next. */
679 ctf_dynset_next (ctf_dynset_t
*hp
, ctf_next_t
**it
, void **key
)
681 struct htab
*htab
= (struct htab
*) hp
;
687 size_t size
= htab_size (htab
);
689 /* If the table has too many entries to fit in an ssize_t, just give up.
690 This might be spurious, but if any type-related hashtable has ever been
691 nearly as large as that then somthing very odd is going on. */
693 if (((ssize_t
) size
) < 0)
696 if ((i
= ctf_next_create ()) == NULL
)
699 i
->u
.ctn_hash_slot
= htab
->entries
;
702 i
->ctn_size
= (ssize_t
) size
;
703 i
->ctn_iter_fun
= (void (*) (void)) ctf_dynset_next
;
707 if ((void (*) (void)) ctf_dynset_next
!= i
->ctn_iter_fun
)
708 return ECTF_NEXT_WRONGFUN
;
710 if (hp
!= i
->cu
.ctn_s
)
711 return ECTF_NEXT_WRONGFP
;
713 if ((ssize_t
) i
->ctn_n
== i
->ctn_size
)
716 while ((ssize_t
) i
->ctn_n
< i
->ctn_size
717 && (*i
->u
.ctn_hash_slot
== HTAB_EMPTY_ENTRY
718 || *i
->u
.ctn_hash_slot
== HTAB_DELETED_ENTRY
))
720 i
->u
.ctn_hash_slot
++;
724 if ((ssize_t
) i
->ctn_n
== i
->ctn_size
)
727 slot
= *i
->u
.ctn_hash_slot
;
730 *key
= internal_to_key (slot
);
732 i
->u
.ctn_hash_slot
++;
738 ctf_next_destroy (i
);
740 return ECTF_NEXT_END
;
743 /* ctf_hash, used for fixed-size maps from const char * -> ctf_id_t without
744 removal. This is a straight cast of a hashtab. */
747 ctf_hash_create (unsigned long nelems
, ctf_hash_fun hash_fun
,
748 ctf_hash_eq_fun eq_fun
)
750 return (ctf_hash_t
*) htab_create_alloc (nelems
, (htab_hash
) hash_fun
,
751 eq_fun
, free
, xcalloc
, free
);
755 ctf_hash_size (const ctf_hash_t
*hp
)
757 return htab_elements ((struct htab
*) hp
);
761 ctf_hash_insert_type (ctf_hash_t
*hp
, ctf_file_t
*fp
, uint32_t type
,
764 const char *str
= ctf_strraw (fp
, name
);
770 && CTF_NAME_STID (name
) == CTF_STRTAB_1
771 && fp
->ctf_syn_ext_strtab
== NULL
772 && fp
->ctf_str
[CTF_NAME_STID (name
)].cts_strs
== NULL
)
779 return 0; /* Just ignore empty strings on behalf of caller. */
781 if (ctf_hashtab_insert ((struct htab
*) hp
, (char *) str
,
782 (void *) (ptrdiff_t) type
, NULL
, NULL
) != NULL
)
787 /* if the key is already in the hash, override the previous definition with
788 this new official definition. If the key is not present, then call
789 ctf_hash_insert_type and hash it in. */
791 ctf_hash_define_type (ctf_hash_t
*hp
, ctf_file_t
*fp
, uint32_t type
,
794 /* This matches the semantics of ctf_hash_insert_type in this
795 implementation anyway. */
797 return ctf_hash_insert_type (hp
, fp
, type
, name
);
801 ctf_hash_lookup_type (ctf_hash_t
*hp
, ctf_file_t
*fp
__attribute__ ((__unused__
)),
806 slot
= ctf_hashtab_lookup ((struct htab
*) hp
, key
, NO_INSERT
);
809 return (ctf_id_t
) ((*slot
)->value
);
815 ctf_hash_destroy (ctf_hash_t
*hp
)
818 htab_delete ((struct htab
*) hp
);