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 two hashtable implementations: one, ctf_dynhash_*(), is an interface to
26 a dynamically-expanding hash with unknown size that should support addition
27 of large numbers of items, and removal as well, and is used only at
28 type-insertion time; the other, ctf_dynhash_*(), is an interface to a
29 fixed-size hash from const char * -> ctf_id_t with number of elements
30 specified at creation time, that should support addition of items but need
31 not support removal. These can be implemented by the same underlying hashmap
34 typedef struct ctf_helem
36 void *key
; /* Either a pointer, or a coerced ctf_id_t. */
37 void *value
; /* The value (possibly a coerced int). */
38 ctf_hash_free_fun key_free
;
39 ctf_hash_free_fun value_free
;
45 ctf_hash_free_fun key_free
;
46 ctf_hash_free_fun value_free
;
52 ctf_hash_integer (const void *ptr
)
54 ctf_helem_t
*hep
= (ctf_helem_t
*) ptr
;
56 return htab_hash_pointer (hep
->key
);
60 ctf_hash_eq_integer (const void *a
, const void *b
)
62 ctf_helem_t
*hep_a
= (ctf_helem_t
*) a
;
63 ctf_helem_t
*hep_b
= (ctf_helem_t
*) b
;
65 return htab_eq_pointer (hep_a
->key
, hep_b
->key
);
69 ctf_hash_string (const void *ptr
)
71 ctf_helem_t
*hep
= (ctf_helem_t
*) ptr
;
73 return htab_hash_string (hep
->key
);
77 ctf_hash_eq_string (const void *a
, const void *b
)
79 ctf_helem_t
*hep_a
= (ctf_helem_t
*) a
;
80 ctf_helem_t
*hep_b
= (ctf_helem_t
*) b
;
82 return !strcmp((const char *) hep_a
->key
, (const char *) hep_b
->key
);
85 /* Hash a type_mapping_key. */
87 ctf_hash_type_mapping_key (const void *ptr
)
89 ctf_helem_t
*hep
= (ctf_helem_t
*) ptr
;
90 ctf_link_type_mapping_key_t
*k
= (ctf_link_type_mapping_key_t
*) hep
->key
;
92 return htab_hash_pointer (k
->cltm_fp
) + 59 * htab_hash_pointer ((void *) k
->cltm_idx
);
96 ctf_hash_eq_type_mapping_key (const void *a
, const void *b
)
98 ctf_helem_t
*hep_a
= (ctf_helem_t
*) a
;
99 ctf_helem_t
*hep_b
= (ctf_helem_t
*) b
;
100 ctf_link_type_mapping_key_t
*key_a
= (ctf_link_type_mapping_key_t
*) hep_a
->key
;
101 ctf_link_type_mapping_key_t
*key_b
= (ctf_link_type_mapping_key_t
*) hep_b
->key
;
103 return (key_a
->cltm_fp
== key_b
->cltm_fp
)
104 && (key_a
->cltm_idx
== key_b
->cltm_idx
);
107 /* The dynhash, used for hashes whose size is not known at creation time. */
109 /* Free a single ctf_helem. */
112 ctf_dynhash_item_free (void *item
)
114 ctf_helem_t
*helem
= item
;
116 if (helem
->key_free
&& helem
->key
)
117 helem
->key_free (helem
->key
);
118 if (helem
->value_free
&& helem
->value
)
119 helem
->value_free (helem
->value
);
124 ctf_dynhash_create (ctf_hash_fun hash_fun
, ctf_hash_eq_fun eq_fun
,
125 ctf_hash_free_fun key_free
, ctf_hash_free_fun value_free
)
127 ctf_dynhash_t
*dynhash
;
129 dynhash
= malloc (sizeof (ctf_dynhash_t
));
133 /* 7 is arbitrary and untested for now.. */
134 if ((dynhash
->htab
= htab_create_alloc (7, (htab_hash
) hash_fun
, eq_fun
,
135 ctf_dynhash_item_free
, xcalloc
, free
)) == NULL
)
141 dynhash
->key_free
= key_free
;
142 dynhash
->value_free
= value_free
;
147 static ctf_helem_t
**
148 ctf_hashtab_lookup (struct htab
*htab
, const void *key
, enum insert_option insert
)
150 ctf_helem_t tmp
= { .key
= (void *) key
};
151 return (ctf_helem_t
**) htab_find_slot (htab
, &tmp
, insert
);
155 ctf_hashtab_insert (struct htab
*htab
, void *key
, void *value
,
156 ctf_hash_free_fun key_free
,
157 ctf_hash_free_fun value_free
)
161 slot
= ctf_hashtab_lookup (htab
, key
, INSERT
);
171 *slot
= malloc (sizeof (ctf_helem_t
));
178 key_free ((*slot
)->key
);
180 value_free ((*slot
)->value
);
183 (*slot
)->value
= value
;
188 ctf_dynhash_insert (ctf_dynhash_t
*hp
, void *key
, void *value
)
192 slot
= ctf_hashtab_insert (hp
->htab
, key
, value
,
193 hp
->key_free
, hp
->value_free
);
198 /* We need to keep the key_free and value_free around in each item because the
199 del function has no visibility into the hash as a whole, only into the
202 slot
->key_free
= hp
->key_free
;
203 slot
->value_free
= hp
->value_free
;
209 ctf_dynhash_remove (ctf_dynhash_t
*hp
, const void *key
)
211 ctf_helem_t hep
= { (void *) key
, NULL
, NULL
, NULL
};
212 htab_remove_elt (hp
->htab
, &hep
);
216 ctf_dynhash_empty (ctf_dynhash_t
*hp
)
218 htab_empty (hp
->htab
);
222 ctf_dynhash_lookup (ctf_dynhash_t
*hp
, const void *key
)
226 slot
= ctf_hashtab_lookup (hp
->htab
, key
, NO_INSERT
);
229 return (*slot
)->value
;
234 typedef struct ctf_traverse_cb_arg
238 } ctf_traverse_cb_arg_t
;
241 ctf_hashtab_traverse (void **slot
, void *arg_
)
243 ctf_helem_t
*helem
= *((ctf_helem_t
**) slot
);
244 ctf_traverse_cb_arg_t
*arg
= (ctf_traverse_cb_arg_t
*) arg_
;
246 arg
->fun (helem
->key
, helem
->value
, arg
->arg
);
251 ctf_dynhash_iter (ctf_dynhash_t
*hp
, ctf_hash_iter_f fun
, void *arg_
)
253 ctf_traverse_cb_arg_t arg
= { fun
, arg_
};
254 htab_traverse (hp
->htab
, ctf_hashtab_traverse
, &arg
);
257 typedef struct ctf_traverse_remove_cb_arg
260 ctf_hash_iter_remove_f fun
;
262 } ctf_traverse_remove_cb_arg_t
;
265 ctf_hashtab_traverse_remove (void **slot
, void *arg_
)
267 ctf_helem_t
*helem
= *((ctf_helem_t
**) slot
);
268 ctf_traverse_remove_cb_arg_t
*arg
= (ctf_traverse_remove_cb_arg_t
*) arg_
;
270 if (arg
->fun (helem
->key
, helem
->value
, arg
->arg
))
271 htab_clear_slot (arg
->htab
, slot
);
276 ctf_dynhash_iter_remove (ctf_dynhash_t
*hp
, ctf_hash_iter_remove_f fun
,
279 ctf_traverse_remove_cb_arg_t arg
= { hp
->htab
, fun
, arg_
};
280 htab_traverse (hp
->htab
, ctf_hashtab_traverse_remove
, &arg
);
284 ctf_dynhash_destroy (ctf_dynhash_t
*hp
)
287 htab_delete (hp
->htab
);
291 /* ctf_hash, used for fixed-size maps from const char * -> ctf_id_t without
292 removal. This is a straight cast of a hashtab. */
295 ctf_hash_create (unsigned long nelems
, ctf_hash_fun hash_fun
,
296 ctf_hash_eq_fun eq_fun
)
298 return (ctf_hash_t
*) htab_create_alloc (nelems
, (htab_hash
) hash_fun
,
299 eq_fun
, free
, xcalloc
, free
);
303 ctf_hash_size (const ctf_hash_t
*hp
)
305 return htab_elements ((struct htab
*) hp
);
309 ctf_hash_insert_type (ctf_hash_t
*hp
, ctf_file_t
*fp
, uint32_t type
,
312 const char *str
= ctf_strraw (fp
, name
);
318 && CTF_NAME_STID (name
) == CTF_STRTAB_1
319 && fp
->ctf_syn_ext_strtab
== NULL
320 && fp
->ctf_str
[CTF_NAME_STID (name
)].cts_strs
== NULL
)
327 return 0; /* Just ignore empty strings on behalf of caller. */
329 if (ctf_hashtab_insert ((struct htab
*) hp
, (char *) str
,
330 (void *) (ptrdiff_t) type
, NULL
, NULL
) != NULL
)
335 /* if the key is already in the hash, override the previous definition with
336 this new official definition. If the key is not present, then call
337 ctf_hash_insert_type() and hash it in. */
339 ctf_hash_define_type (ctf_hash_t
*hp
, ctf_file_t
*fp
, uint32_t type
,
342 /* This matches the semantics of ctf_hash_insert_type() in this
343 implementation anyway. */
345 return ctf_hash_insert_type (hp
, fp
, type
, name
);
349 ctf_hash_lookup_type (ctf_hash_t
*hp
, ctf_file_t
*fp
__attribute__ ((__unused__
)),
354 slot
= ctf_hashtab_lookup ((struct htab
*) hp
, key
, NO_INSERT
);
357 return (ctf_id_t
) ((*slot
)->value
);
363 ctf_hash_destroy (ctf_hash_t
*hp
)
366 htab_delete ((struct htab
*) hp
);