Commit | Line | Data |
---|---|---|
c0754cdd NA |
1 | /* Interface to hashtable implementations. |
2 | Copyright (C) 2006-2019 Free Software Foundation, Inc. | |
3 | ||
4 | This file is part of libctf. | |
5 | ||
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 | |
9 | version. | |
10 | ||
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. | |
15 | ||
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/>. */ | |
19 | ||
20 | #include <ctf-impl.h> | |
21 | #include <string.h> | |
22 | #include "libiberty.h" | |
23 | #include "hashtab.h" | |
24 | ||
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 | |
32 | if you wish. */ | |
33 | ||
34 | typedef struct ctf_helem | |
35 | { | |
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; | |
40 | } ctf_helem_t; | |
41 | ||
42 | struct ctf_dynhash | |
43 | { | |
44 | struct htab *htab; | |
45 | ctf_hash_free_fun key_free; | |
46 | ctf_hash_free_fun value_free; | |
47 | }; | |
48 | ||
49 | /* Hash functions. */ | |
50 | ||
51 | unsigned int | |
52 | ctf_hash_integer (const void *ptr) | |
53 | { | |
54 | ctf_helem_t *hep = (ctf_helem_t *) ptr; | |
55 | ||
56 | return htab_hash_pointer (hep->key); | |
57 | } | |
58 | ||
59 | int | |
60 | ctf_hash_eq_integer (const void *a, const void *b) | |
61 | { | |
62 | ctf_helem_t *hep_a = (ctf_helem_t *) a; | |
63 | ctf_helem_t *hep_b = (ctf_helem_t *) b; | |
64 | ||
65 | return htab_eq_pointer (hep_a->key, hep_b->key); | |
66 | } | |
67 | ||
68 | unsigned int | |
69 | ctf_hash_string (const void *ptr) | |
70 | { | |
71 | ctf_helem_t *hep = (ctf_helem_t *) ptr; | |
72 | ||
73 | return htab_hash_string (hep->key); | |
74 | } | |
75 | ||
76 | int | |
77 | ctf_hash_eq_string (const void *a, const void *b) | |
78 | { | |
79 | ctf_helem_t *hep_a = (ctf_helem_t *) a; | |
80 | ctf_helem_t *hep_b = (ctf_helem_t *) b; | |
81 | ||
82 | return !strcmp((const char *) hep_a->key, (const char *) hep_b->key); | |
83 | } | |
84 | ||
886453cb NA |
85 | /* Hash a type_mapping_key. */ |
86 | unsigned int | |
87 | ctf_hash_type_mapping_key (const void *ptr) | |
88 | { | |
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; | |
91 | ||
92 | return htab_hash_pointer (k->cltm_fp) + 59 * htab_hash_pointer ((void *) k->cltm_idx); | |
93 | } | |
94 | ||
95 | int | |
96 | ctf_hash_eq_type_mapping_key (const void *a, const void *b) | |
97 | { | |
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; | |
102 | ||
103 | return (key_a->cltm_fp == key_b->cltm_fp) | |
104 | && (key_a->cltm_idx == key_b->cltm_idx); | |
105 | } | |
106 | ||
c0754cdd NA |
107 | /* The dynhash, used for hashes whose size is not known at creation time. */ |
108 | ||
109 | /* Free a single ctf_helem. */ | |
110 | ||
111 | static void | |
112 | ctf_dynhash_item_free (void *item) | |
113 | { | |
114 | ctf_helem_t *helem = item; | |
115 | ||
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); | |
120 | free (helem); | |
121 | } | |
122 | ||
123 | ctf_dynhash_t * | |
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) | |
126 | { | |
127 | ctf_dynhash_t *dynhash; | |
128 | ||
129 | dynhash = malloc (sizeof (ctf_dynhash_t)); | |
130 | if (!dynhash) | |
131 | return NULL; | |
132 | ||
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) | |
136 | { | |
137 | free (dynhash); | |
138 | return NULL; | |
139 | } | |
140 | ||
141 | dynhash->key_free = key_free; | |
142 | dynhash->value_free = value_free; | |
143 | ||
144 | return dynhash; | |
145 | } | |
146 | ||
147 | static ctf_helem_t ** | |
148 | ctf_hashtab_lookup (struct htab *htab, const void *key, enum insert_option insert) | |
149 | { | |
150 | ctf_helem_t tmp = { .key = (void *) key }; | |
151 | return (ctf_helem_t **) htab_find_slot (htab, &tmp, insert); | |
152 | } | |
153 | ||
154 | static ctf_helem_t * | |
1820745a NA |
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) | |
c0754cdd NA |
158 | { |
159 | ctf_helem_t **slot; | |
160 | ||
161 | slot = ctf_hashtab_lookup (htab, key, INSERT); | |
162 | ||
163 | if (!slot) | |
164 | { | |
165 | errno = -ENOMEM; | |
166 | return NULL; | |
167 | } | |
168 | ||
169 | if (!*slot) | |
170 | { | |
171 | *slot = malloc (sizeof (ctf_helem_t)); | |
172 | if (!*slot) | |
173 | return NULL; | |
c0754cdd | 174 | } |
1820745a NA |
175 | else |
176 | { | |
177 | if (key_free) | |
178 | key_free ((*slot)->key); | |
179 | if (value_free) | |
180 | value_free ((*slot)->value); | |
181 | } | |
182 | (*slot)->key = key; | |
c0754cdd NA |
183 | (*slot)->value = value; |
184 | return *slot; | |
185 | } | |
186 | ||
187 | int | |
188 | ctf_dynhash_insert (ctf_dynhash_t *hp, void *key, void *value) | |
189 | { | |
190 | ctf_helem_t *slot; | |
191 | ||
1820745a NA |
192 | slot = ctf_hashtab_insert (hp->htab, key, value, |
193 | hp->key_free, hp->value_free); | |
c0754cdd NA |
194 | |
195 | if (!slot) | |
196 | return errno; | |
197 | ||
198 | /* We need to keep the key_free and value_free around in each item because the | |
886453cb | 199 | del function has no visibility into the hash as a whole, only into the |
c0754cdd NA |
200 | individual items. */ |
201 | ||
202 | slot->key_free = hp->key_free; | |
203 | slot->value_free = hp->value_free; | |
204 | ||
205 | return 0; | |
206 | } | |
207 | ||
208 | void | |
209 | ctf_dynhash_remove (ctf_dynhash_t *hp, const void *key) | |
210 | { | |
3e10cffc NA |
211 | ctf_helem_t hep = { (void *) key, NULL, NULL, NULL }; |
212 | htab_remove_elt (hp->htab, &hep); | |
c0754cdd NA |
213 | } |
214 | ||
886453cb NA |
215 | void |
216 | ctf_dynhash_empty (ctf_dynhash_t *hp) | |
217 | { | |
218 | htab_empty (hp->htab); | |
219 | } | |
220 | ||
c0754cdd NA |
221 | void * |
222 | ctf_dynhash_lookup (ctf_dynhash_t *hp, const void *key) | |
223 | { | |
224 | ctf_helem_t **slot; | |
225 | ||
226 | slot = ctf_hashtab_lookup (hp->htab, key, NO_INSERT); | |
227 | ||
228 | if (slot) | |
229 | return (*slot)->value; | |
230 | ||
231 | return NULL; | |
232 | } | |
233 | ||
9658dc39 NA |
234 | typedef struct ctf_traverse_cb_arg |
235 | { | |
236 | ctf_hash_iter_f fun; | |
237 | void *arg; | |
238 | } ctf_traverse_cb_arg_t; | |
239 | ||
240 | static int | |
241 | ctf_hashtab_traverse (void **slot, void *arg_) | |
242 | { | |
243 | ctf_helem_t *helem = *((ctf_helem_t **) slot); | |
244 | ctf_traverse_cb_arg_t *arg = (ctf_traverse_cb_arg_t *) arg_; | |
245 | ||
246 | arg->fun (helem->key, helem->value, arg->arg); | |
247 | return 1; | |
248 | } | |
249 | ||
250 | void | |
251 | ctf_dynhash_iter (ctf_dynhash_t *hp, ctf_hash_iter_f fun, void *arg_) | |
252 | { | |
253 | ctf_traverse_cb_arg_t arg = { fun, arg_ }; | |
254 | htab_traverse (hp->htab, ctf_hashtab_traverse, &arg); | |
255 | } | |
256 | ||
257 | typedef struct ctf_traverse_remove_cb_arg | |
258 | { | |
259 | struct htab *htab; | |
260 | ctf_hash_iter_remove_f fun; | |
261 | void *arg; | |
262 | } ctf_traverse_remove_cb_arg_t; | |
263 | ||
264 | static int | |
265 | ctf_hashtab_traverse_remove (void **slot, void *arg_) | |
266 | { | |
267 | ctf_helem_t *helem = *((ctf_helem_t **) slot); | |
268 | ctf_traverse_remove_cb_arg_t *arg = (ctf_traverse_remove_cb_arg_t *) arg_; | |
269 | ||
270 | if (arg->fun (helem->key, helem->value, arg->arg)) | |
271 | htab_clear_slot (arg->htab, slot); | |
272 | return 1; | |
273 | } | |
274 | ||
275 | void | |
276 | ctf_dynhash_iter_remove (ctf_dynhash_t *hp, ctf_hash_iter_remove_f fun, | |
277 | void *arg_) | |
278 | { | |
279 | ctf_traverse_remove_cb_arg_t arg = { hp->htab, fun, arg_ }; | |
280 | htab_traverse (hp->htab, ctf_hashtab_traverse_remove, &arg); | |
281 | } | |
282 | ||
c0754cdd NA |
283 | void |
284 | ctf_dynhash_destroy (ctf_dynhash_t *hp) | |
285 | { | |
286 | if (hp != NULL) | |
287 | htab_delete (hp->htab); | |
288 | free (hp); | |
289 | } | |
290 | ||
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. */ | |
293 | ||
294 | ctf_hash_t * | |
295 | ctf_hash_create (unsigned long nelems, ctf_hash_fun hash_fun, | |
296 | ctf_hash_eq_fun eq_fun) | |
297 | { | |
298 | return (ctf_hash_t *) htab_create_alloc (nelems, (htab_hash) hash_fun, | |
299 | eq_fun, free, xcalloc, free); | |
300 | } | |
301 | ||
302 | uint32_t | |
303 | ctf_hash_size (const ctf_hash_t *hp) | |
304 | { | |
305 | return htab_elements ((struct htab *) hp); | |
306 | } | |
307 | ||
308 | int | |
309 | ctf_hash_insert_type (ctf_hash_t *hp, ctf_file_t *fp, uint32_t type, | |
310 | uint32_t name) | |
311 | { | |
d851ecd3 | 312 | const char *str = ctf_strraw (fp, name); |
c0754cdd NA |
313 | |
314 | if (type == 0) | |
315 | return EINVAL; | |
316 | ||
d851ecd3 NA |
317 | if (str == NULL |
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) | |
c0754cdd NA |
321 | return ECTF_STRTAB; |
322 | ||
d851ecd3 | 323 | if (str == NULL) |
c0754cdd NA |
324 | return ECTF_BADNAME; |
325 | ||
326 | if (str[0] == '\0') | |
327 | return 0; /* Just ignore empty strings on behalf of caller. */ | |
328 | ||
329 | if (ctf_hashtab_insert ((struct htab *) hp, (char *) str, | |
1820745a | 330 | (void *) (ptrdiff_t) type, NULL, NULL) != NULL) |
c0754cdd NA |
331 | return 0; |
332 | return errno; | |
333 | } | |
334 | ||
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. */ | |
338 | int | |
339 | ctf_hash_define_type (ctf_hash_t *hp, ctf_file_t *fp, uint32_t type, | |
340 | uint32_t name) | |
341 | { | |
342 | /* This matches the semantics of ctf_hash_insert_type() in this | |
343 | implementation anyway. */ | |
344 | ||
345 | return ctf_hash_insert_type (hp, fp, type, name); | |
346 | } | |
347 | ||
348 | ctf_id_t | |
349 | ctf_hash_lookup_type (ctf_hash_t *hp, ctf_file_t *fp __attribute__ ((__unused__)), | |
350 | const char *key) | |
351 | { | |
352 | ctf_helem_t **slot; | |
353 | ||
354 | slot = ctf_hashtab_lookup ((struct htab *) hp, key, NO_INSERT); | |
355 | ||
356 | if (slot) | |
357 | return (ctf_id_t) ((*slot)->value); | |
358 | ||
359 | return 0; | |
360 | } | |
361 | ||
362 | void | |
363 | ctf_hash_destroy (ctf_hash_t *hp) | |
364 | { | |
365 | if (hp != NULL) | |
366 | htab_delete ((struct htab *) hp); | |
367 | } |