/src/binutils-gdb/libctf/ctf-hash.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* Interface to hashtable implementations. |
2 | | Copyright (C) 2006-2024 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: |
26 | | |
27 | | - ctf_dynhash_* is an interface to a dynamically-expanding hash with |
28 | | unknown size that should support addition of large numbers of items, |
29 | | and removal as well, and is used only at type-insertion time and during |
30 | | linking. It can be constructed with an expected initial number of |
31 | | elements, but need not be. |
32 | | |
33 | | - ctf_dynset_* is an interface to a dynamically-expanding hash that contains |
34 | | only keys: no values. |
35 | | |
36 | | These can be implemented by the same underlying hashmap if you wish. */ |
37 | | |
38 | | /* The helem is used for general key/value mappings in the ctf_dynhash: the |
39 | | owner may not have space allocated for it, and will be garbage (not |
40 | | NULL!) in that case. */ |
41 | | |
42 | | typedef struct ctf_helem |
43 | | { |
44 | | void *key; /* Either a pointer, or a coerced ctf_id_t. */ |
45 | | void *value; /* The value (possibly a coerced int). */ |
46 | | ctf_dynhash_t *owner; /* The hash that owns us. */ |
47 | | } ctf_helem_t; |
48 | | |
49 | | /* Equally, the key_free and value_free may not exist. */ |
50 | | |
51 | | struct ctf_dynhash |
52 | | { |
53 | | struct htab *htab; |
54 | | ctf_hash_free_fun key_free; |
55 | | ctf_hash_free_fun value_free; |
56 | | }; |
57 | | |
58 | | /* Hash and eq functions for the dynhash and hash. */ |
59 | | |
60 | | unsigned int |
61 | | ctf_hash_integer (const void *ptr) |
62 | 0 | { |
63 | 0 | ctf_helem_t *hep = (ctf_helem_t *) ptr; |
64 | |
|
65 | 0 | return htab_hash_pointer (hep->key); |
66 | 0 | } |
67 | | |
68 | | int |
69 | | ctf_hash_eq_integer (const void *a, const void *b) |
70 | 0 | { |
71 | 0 | ctf_helem_t *hep_a = (ctf_helem_t *) a; |
72 | 0 | ctf_helem_t *hep_b = (ctf_helem_t *) b; |
73 | |
|
74 | 0 | return htab_eq_pointer (hep_a->key, hep_b->key); |
75 | 0 | } |
76 | | |
77 | | unsigned int |
78 | | ctf_hash_string (const void *ptr) |
79 | 0 | { |
80 | 0 | ctf_helem_t *hep = (ctf_helem_t *) ptr; |
81 | |
|
82 | 0 | return htab_hash_string (hep->key); |
83 | 0 | } |
84 | | |
85 | | int |
86 | | ctf_hash_eq_string (const void *a, const void *b) |
87 | 0 | { |
88 | 0 | ctf_helem_t *hep_a = (ctf_helem_t *) a; |
89 | 0 | ctf_helem_t *hep_b = (ctf_helem_t *) b; |
90 | |
|
91 | 0 | return !strcmp((const char *) hep_a->key, (const char *) hep_b->key); |
92 | 0 | } |
93 | | |
94 | | /* Hash a type_key. */ |
95 | | unsigned int |
96 | | ctf_hash_type_key (const void *ptr) |
97 | 0 | { |
98 | 0 | ctf_helem_t *hep = (ctf_helem_t *) ptr; |
99 | 0 | ctf_link_type_key_t *k = (ctf_link_type_key_t *) hep->key; |
100 | |
|
101 | 0 | return htab_hash_pointer (k->cltk_fp) + 59 |
102 | 0 | * htab_hash_pointer ((void *) (uintptr_t) k->cltk_idx); |
103 | 0 | } |
104 | | |
105 | | int |
106 | | ctf_hash_eq_type_key (const void *a, const void *b) |
107 | 0 | { |
108 | 0 | ctf_helem_t *hep_a = (ctf_helem_t *) a; |
109 | 0 | ctf_helem_t *hep_b = (ctf_helem_t *) b; |
110 | 0 | ctf_link_type_key_t *key_a = (ctf_link_type_key_t *) hep_a->key; |
111 | 0 | ctf_link_type_key_t *key_b = (ctf_link_type_key_t *) hep_b->key; |
112 | |
|
113 | 0 | return (key_a->cltk_fp == key_b->cltk_fp) |
114 | 0 | && (key_a->cltk_idx == key_b->cltk_idx); |
115 | 0 | } |
116 | | |
117 | | /* Hash a type_id_key. */ |
118 | | unsigned int |
119 | | ctf_hash_type_id_key (const void *ptr) |
120 | 0 | { |
121 | 0 | ctf_helem_t *hep = (ctf_helem_t *) ptr; |
122 | 0 | ctf_type_id_key_t *k = (ctf_type_id_key_t *) hep->key; |
123 | |
|
124 | 0 | return htab_hash_pointer ((void *) (uintptr_t) k->ctii_input_num) |
125 | 0 | + 59 * htab_hash_pointer ((void *) (uintptr_t) k->ctii_type); |
126 | 0 | } |
127 | | |
128 | | int |
129 | | ctf_hash_eq_type_id_key (const void *a, const void *b) |
130 | 0 | { |
131 | 0 | ctf_helem_t *hep_a = (ctf_helem_t *) a; |
132 | 0 | ctf_helem_t *hep_b = (ctf_helem_t *) b; |
133 | 0 | ctf_type_id_key_t *key_a = (ctf_type_id_key_t *) hep_a->key; |
134 | 0 | ctf_type_id_key_t *key_b = (ctf_type_id_key_t *) hep_b->key; |
135 | |
|
136 | 0 | return (key_a->ctii_input_num == key_b->ctii_input_num) |
137 | 0 | && (key_a->ctii_type == key_b->ctii_type); |
138 | 0 | } |
139 | | |
140 | | /* The dynhash, used for hashes whose size is not known at creation time. */ |
141 | | |
142 | | /* Free a single ctf_helem with arbitrary key/value functions. */ |
143 | | |
144 | | static void |
145 | | ctf_dynhash_item_free (void *item) |
146 | 0 | { |
147 | 0 | ctf_helem_t *helem = item; |
148 | |
|
149 | 0 | if (helem->owner->key_free && helem->key) |
150 | 0 | helem->owner->key_free (helem->key); |
151 | 0 | if (helem->owner->value_free && helem->value) |
152 | 0 | helem->owner->value_free (helem->value); |
153 | 0 | free (helem); |
154 | 0 | } |
155 | | |
156 | | ctf_dynhash_t * |
157 | | ctf_dynhash_create_sized (unsigned long nelems, ctf_hash_fun hash_fun, |
158 | | ctf_hash_eq_fun eq_fun, ctf_hash_free_fun key_free, |
159 | | ctf_hash_free_fun value_free) |
160 | 0 | { |
161 | 0 | ctf_dynhash_t *dynhash; |
162 | 0 | htab_del del = ctf_dynhash_item_free; |
163 | |
|
164 | 0 | if (key_free || value_free) |
165 | 0 | dynhash = malloc (sizeof (ctf_dynhash_t)); |
166 | 0 | else |
167 | 0 | dynhash = malloc (offsetof (ctf_dynhash_t, key_free)); |
168 | 0 | if (!dynhash) |
169 | 0 | return NULL; |
170 | | |
171 | 0 | if (key_free == NULL && value_free == NULL) |
172 | 0 | del = free; |
173 | |
|
174 | 0 | if ((dynhash->htab = htab_create_alloc (nelems, (htab_hash) hash_fun, eq_fun, |
175 | 0 | del, xcalloc, free)) == NULL) |
176 | 0 | { |
177 | 0 | free (dynhash); |
178 | 0 | return NULL; |
179 | 0 | } |
180 | | |
181 | 0 | if (key_free || value_free) |
182 | 0 | { |
183 | 0 | dynhash->key_free = key_free; |
184 | 0 | dynhash->value_free = value_free; |
185 | 0 | } |
186 | |
|
187 | 0 | return dynhash; |
188 | 0 | } |
189 | | |
190 | | ctf_dynhash_t * |
191 | | ctf_dynhash_create (ctf_hash_fun hash_fun, ctf_hash_eq_fun eq_fun, |
192 | | ctf_hash_free_fun key_free, ctf_hash_free_fun value_free) |
193 | 0 | { |
194 | | /* 7 is arbitrary and not benchmarked yet. */ |
195 | |
|
196 | 0 | return ctf_dynhash_create_sized (7, hash_fun, eq_fun, key_free, value_free); |
197 | 0 | } |
198 | | |
199 | | static ctf_helem_t ** |
200 | | ctf_hashtab_lookup (struct htab *htab, const void *key, enum insert_option insert) |
201 | 0 | { |
202 | 0 | ctf_helem_t tmp = { .key = (void *) key }; |
203 | 0 | return (ctf_helem_t **) htab_find_slot (htab, &tmp, insert); |
204 | 0 | } |
205 | | |
206 | | static ctf_helem_t * |
207 | | ctf_hashtab_insert (struct htab *htab, void *key, void *value, |
208 | | ctf_hash_free_fun key_free, |
209 | | ctf_hash_free_fun value_free) |
210 | 0 | { |
211 | 0 | ctf_helem_t **slot; |
212 | |
|
213 | 0 | slot = ctf_hashtab_lookup (htab, key, INSERT); |
214 | |
|
215 | 0 | if (!slot) |
216 | 0 | { |
217 | 0 | errno = ENOMEM; |
218 | 0 | return NULL; |
219 | 0 | } |
220 | | |
221 | 0 | if (!*slot) |
222 | 0 | { |
223 | | /* Only spend space on the owner if we're going to use it: if there is a |
224 | | key or value freeing function. */ |
225 | 0 | if (key_free || value_free) |
226 | 0 | *slot = malloc (sizeof (ctf_helem_t)); |
227 | 0 | else |
228 | 0 | *slot = malloc (offsetof (ctf_helem_t, owner)); |
229 | 0 | if (!*slot) |
230 | 0 | return NULL; |
231 | 0 | (*slot)->key = key; |
232 | 0 | } |
233 | 0 | else |
234 | 0 | { |
235 | 0 | if (key_free) |
236 | 0 | key_free (key); |
237 | 0 | if (value_free) |
238 | 0 | value_free ((*slot)->value); |
239 | 0 | } |
240 | 0 | (*slot)->value = value; |
241 | 0 | return *slot; |
242 | 0 | } |
243 | | |
244 | | int |
245 | | ctf_dynhash_insert (ctf_dynhash_t *hp, void *key, void *value) |
246 | 0 | { |
247 | 0 | ctf_helem_t *slot; |
248 | 0 | ctf_hash_free_fun key_free = NULL, value_free = NULL; |
249 | |
|
250 | 0 | if (hp->htab->del_f == ctf_dynhash_item_free) |
251 | 0 | { |
252 | 0 | key_free = hp->key_free; |
253 | 0 | value_free = hp->value_free; |
254 | 0 | } |
255 | 0 | slot = ctf_hashtab_insert (hp->htab, key, value, |
256 | 0 | key_free, value_free); |
257 | |
|
258 | 0 | if (!slot) |
259 | 0 | return errno; |
260 | | |
261 | | /* Keep track of the owner, so that the del function can get at the key_free |
262 | | and value_free functions. Only do this if one of those functions is set: |
263 | | if not, the owner is not even present in the helem. */ |
264 | | |
265 | 0 | if (key_free || value_free) |
266 | 0 | slot->owner = hp; |
267 | |
|
268 | 0 | return 0; |
269 | 0 | } |
270 | | |
271 | | void |
272 | | ctf_dynhash_remove (ctf_dynhash_t *hp, const void *key) |
273 | 0 | { |
274 | 0 | ctf_helem_t hep = { (void *) key, NULL, NULL }; |
275 | 0 | htab_remove_elt (hp->htab, &hep); |
276 | 0 | } |
277 | | |
278 | | void |
279 | | ctf_dynhash_empty (ctf_dynhash_t *hp) |
280 | 0 | { |
281 | 0 | htab_empty (hp->htab); |
282 | 0 | } |
283 | | |
284 | | size_t |
285 | | ctf_dynhash_elements (ctf_dynhash_t *hp) |
286 | 0 | { |
287 | 0 | return htab_elements (hp->htab); |
288 | 0 | } |
289 | | |
290 | | void * |
291 | | ctf_dynhash_lookup (ctf_dynhash_t *hp, const void *key) |
292 | 0 | { |
293 | 0 | ctf_helem_t **slot; |
294 | |
|
295 | 0 | slot = ctf_hashtab_lookup (hp->htab, key, NO_INSERT); |
296 | |
|
297 | 0 | if (slot) |
298 | 0 | return (*slot)->value; |
299 | | |
300 | 0 | return NULL; |
301 | 0 | } |
302 | | |
303 | | /* TRUE/FALSE return. */ |
304 | | int |
305 | | ctf_dynhash_lookup_kv (ctf_dynhash_t *hp, const void *key, |
306 | | const void **orig_key, void **value) |
307 | 0 | { |
308 | 0 | ctf_helem_t **slot; |
309 | |
|
310 | 0 | slot = ctf_hashtab_lookup (hp->htab, key, NO_INSERT); |
311 | |
|
312 | 0 | if (slot) |
313 | 0 | { |
314 | 0 | if (orig_key) |
315 | 0 | *orig_key = (*slot)->key; |
316 | 0 | if (value) |
317 | 0 | *value = (*slot)->value; |
318 | 0 | return 1; |
319 | 0 | } |
320 | 0 | return 0; |
321 | 0 | } |
322 | | |
323 | | typedef struct ctf_traverse_cb_arg |
324 | | { |
325 | | ctf_hash_iter_f fun; |
326 | | void *arg; |
327 | | } ctf_traverse_cb_arg_t; |
328 | | |
329 | | static int |
330 | | ctf_hashtab_traverse (void **slot, void *arg_) |
331 | 0 | { |
332 | 0 | ctf_helem_t *helem = *((ctf_helem_t **) slot); |
333 | 0 | ctf_traverse_cb_arg_t *arg = (ctf_traverse_cb_arg_t *) arg_; |
334 | |
|
335 | 0 | arg->fun (helem->key, helem->value, arg->arg); |
336 | 0 | return 1; |
337 | 0 | } |
338 | | |
339 | | void |
340 | | ctf_dynhash_iter (ctf_dynhash_t *hp, ctf_hash_iter_f fun, void *arg_) |
341 | 0 | { |
342 | 0 | ctf_traverse_cb_arg_t arg = { fun, arg_ }; |
343 | 0 | htab_traverse (hp->htab, ctf_hashtab_traverse, &arg); |
344 | 0 | } |
345 | | |
346 | | typedef struct ctf_traverse_find_cb_arg |
347 | | { |
348 | | ctf_hash_iter_find_f fun; |
349 | | void *arg; |
350 | | void *found_key; |
351 | | } ctf_traverse_find_cb_arg_t; |
352 | | |
353 | | static int |
354 | | ctf_hashtab_traverse_find (void **slot, void *arg_) |
355 | 0 | { |
356 | 0 | ctf_helem_t *helem = *((ctf_helem_t **) slot); |
357 | 0 | ctf_traverse_find_cb_arg_t *arg = (ctf_traverse_find_cb_arg_t *) arg_; |
358 | |
|
359 | 0 | if (arg->fun (helem->key, helem->value, arg->arg)) |
360 | 0 | { |
361 | 0 | arg->found_key = helem->key; |
362 | 0 | return 0; |
363 | 0 | } |
364 | 0 | return 1; |
365 | 0 | } |
366 | | |
367 | | void * |
368 | | ctf_dynhash_iter_find (ctf_dynhash_t *hp, ctf_hash_iter_find_f fun, void *arg_) |
369 | 0 | { |
370 | 0 | ctf_traverse_find_cb_arg_t arg = { fun, arg_, NULL }; |
371 | 0 | htab_traverse (hp->htab, ctf_hashtab_traverse_find, &arg); |
372 | 0 | return arg.found_key; |
373 | 0 | } |
374 | | |
375 | | typedef struct ctf_traverse_remove_cb_arg |
376 | | { |
377 | | struct htab *htab; |
378 | | ctf_hash_iter_remove_f fun; |
379 | | void *arg; |
380 | | } ctf_traverse_remove_cb_arg_t; |
381 | | |
382 | | static int |
383 | | ctf_hashtab_traverse_remove (void **slot, void *arg_) |
384 | 0 | { |
385 | 0 | ctf_helem_t *helem = *((ctf_helem_t **) slot); |
386 | 0 | ctf_traverse_remove_cb_arg_t *arg = (ctf_traverse_remove_cb_arg_t *) arg_; |
387 | |
|
388 | 0 | if (arg->fun (helem->key, helem->value, arg->arg)) |
389 | 0 | htab_clear_slot (arg->htab, slot); |
390 | 0 | return 1; |
391 | 0 | } |
392 | | |
393 | | void |
394 | | ctf_dynhash_iter_remove (ctf_dynhash_t *hp, ctf_hash_iter_remove_f fun, |
395 | | void *arg_) |
396 | 0 | { |
397 | 0 | ctf_traverse_remove_cb_arg_t arg = { hp->htab, fun, arg_ }; |
398 | 0 | htab_traverse (hp->htab, ctf_hashtab_traverse_remove, &arg); |
399 | 0 | } |
400 | | |
401 | | /* Traverse a dynhash in arbitrary order, in _next iterator form. |
402 | | |
403 | | Mutating the dynhash while iterating is not supported (just as it isn't for |
404 | | htab_traverse). |
405 | | |
406 | | Note: unusually, this returns zero on success and a *positive* value on |
407 | | error, because it does not take an fp, taking an error pointer would be |
408 | | incredibly clunky, and nearly all error-handling ends up stuffing the result |
409 | | of this into some sort of errno or ctf_errno, which is invariably |
410 | | positive. So doing this simplifies essentially all callers. */ |
411 | | int |
412 | | ctf_dynhash_next (ctf_dynhash_t *h, ctf_next_t **it, void **key, void **value) |
413 | 0 | { |
414 | 0 | ctf_next_t *i = *it; |
415 | 0 | ctf_helem_t *slot; |
416 | |
|
417 | 0 | if (!i) |
418 | 0 | { |
419 | 0 | size_t size = htab_size (h->htab); |
420 | | |
421 | | /* If the table has too many entries to fit in an ssize_t, just give up. |
422 | | This might be spurious, but if any type-related hashtable has ever been |
423 | | nearly as large as that then something very odd is going on. */ |
424 | 0 | if (((ssize_t) size) < 0) |
425 | 0 | return EDOM; |
426 | | |
427 | 0 | if ((i = ctf_next_create ()) == NULL) |
428 | 0 | return ENOMEM; |
429 | | |
430 | 0 | i->u.ctn_hash_slot = h->htab->entries; |
431 | 0 | i->cu.ctn_h = h; |
432 | 0 | i->ctn_n = 0; |
433 | 0 | i->ctn_size = (ssize_t) size; |
434 | 0 | i->ctn_iter_fun = (void (*) (void)) ctf_dynhash_next; |
435 | 0 | *it = i; |
436 | 0 | } |
437 | | |
438 | 0 | if ((void (*) (void)) ctf_dynhash_next != i->ctn_iter_fun) |
439 | 0 | return ECTF_NEXT_WRONGFUN; |
440 | | |
441 | 0 | if (h != i->cu.ctn_h) |
442 | 0 | return ECTF_NEXT_WRONGFP; |
443 | | |
444 | 0 | if ((ssize_t) i->ctn_n == i->ctn_size) |
445 | 0 | goto hash_end; |
446 | | |
447 | 0 | while ((ssize_t) i->ctn_n < i->ctn_size |
448 | 0 | && (*i->u.ctn_hash_slot == HTAB_EMPTY_ENTRY |
449 | 0 | || *i->u.ctn_hash_slot == HTAB_DELETED_ENTRY)) |
450 | 0 | { |
451 | 0 | i->u.ctn_hash_slot++; |
452 | 0 | i->ctn_n++; |
453 | 0 | } |
454 | |
|
455 | 0 | if ((ssize_t) i->ctn_n == i->ctn_size) |
456 | 0 | goto hash_end; |
457 | | |
458 | 0 | slot = *i->u.ctn_hash_slot; |
459 | |
|
460 | 0 | if (key) |
461 | 0 | *key = slot->key; |
462 | 0 | if (value) |
463 | 0 | *value = slot->value; |
464 | |
|
465 | 0 | i->u.ctn_hash_slot++; |
466 | 0 | i->ctn_n++; |
467 | |
|
468 | 0 | return 0; |
469 | | |
470 | 0 | hash_end: |
471 | 0 | ctf_next_destroy (i); |
472 | 0 | *it = NULL; |
473 | 0 | return ECTF_NEXT_END; |
474 | 0 | } |
475 | | |
476 | | int |
477 | | ctf_dynhash_sort_by_name (const ctf_next_hkv_t *one, const ctf_next_hkv_t *two, |
478 | | void *unused _libctf_unused_) |
479 | 0 | { |
480 | 0 | return strcmp ((char *) one->hkv_key, (char *) two->hkv_key); |
481 | 0 | } |
482 | | |
483 | | /* Traverse a sorted dynhash, in _next iterator form. |
484 | | |
485 | | See ctf_dynhash_next for notes on error returns, etc. |
486 | | |
487 | | Sort keys before iterating over them using the SORT_FUN and SORT_ARG. |
488 | | |
489 | | If SORT_FUN is null, thunks to ctf_dynhash_next. */ |
490 | | int |
491 | | ctf_dynhash_next_sorted (ctf_dynhash_t *h, ctf_next_t **it, void **key, |
492 | | void **value, ctf_hash_sort_f sort_fun, void *sort_arg) |
493 | 0 | { |
494 | 0 | ctf_next_t *i = *it; |
495 | |
|
496 | 0 | if (sort_fun == NULL) |
497 | 0 | return ctf_dynhash_next (h, it, key, value); |
498 | | |
499 | 0 | if (!i) |
500 | 0 | { |
501 | 0 | size_t els = ctf_dynhash_elements (h); |
502 | 0 | ctf_next_t *accum_i = NULL; |
503 | 0 | void *key, *value; |
504 | 0 | int err; |
505 | 0 | ctf_next_hkv_t *walk; |
506 | |
|
507 | 0 | if (((ssize_t) els) < 0) |
508 | 0 | return EDOM; |
509 | | |
510 | 0 | if ((i = ctf_next_create ()) == NULL) |
511 | 0 | return ENOMEM; |
512 | | |
513 | 0 | if ((i->u.ctn_sorted_hkv = calloc (els, sizeof (ctf_next_hkv_t))) == NULL) |
514 | 0 | { |
515 | 0 | ctf_next_destroy (i); |
516 | 0 | return ENOMEM; |
517 | 0 | } |
518 | 0 | walk = i->u.ctn_sorted_hkv; |
519 | |
|
520 | 0 | i->cu.ctn_h = h; |
521 | |
|
522 | 0 | while ((err = ctf_dynhash_next (h, &accum_i, &key, &value)) == 0) |
523 | 0 | { |
524 | 0 | walk->hkv_key = key; |
525 | 0 | walk->hkv_value = value; |
526 | 0 | walk++; |
527 | 0 | } |
528 | 0 | if (err != ECTF_NEXT_END) |
529 | 0 | { |
530 | 0 | ctf_next_destroy (i); |
531 | 0 | return err; |
532 | 0 | } |
533 | | |
534 | 0 | if (sort_fun) |
535 | 0 | ctf_qsort_r (i->u.ctn_sorted_hkv, els, sizeof (ctf_next_hkv_t), |
536 | 0 | (int (*) (const void *, const void *, void *)) sort_fun, |
537 | 0 | sort_arg); |
538 | 0 | i->ctn_n = 0; |
539 | 0 | i->ctn_size = (ssize_t) els; |
540 | 0 | i->ctn_iter_fun = (void (*) (void)) ctf_dynhash_next_sorted; |
541 | 0 | *it = i; |
542 | 0 | } |
543 | | |
544 | 0 | if ((void (*) (void)) ctf_dynhash_next_sorted != i->ctn_iter_fun) |
545 | 0 | return ECTF_NEXT_WRONGFUN; |
546 | | |
547 | 0 | if (h != i->cu.ctn_h) |
548 | 0 | return ECTF_NEXT_WRONGFP; |
549 | | |
550 | 0 | if ((ssize_t) i->ctn_n == i->ctn_size) |
551 | 0 | { |
552 | 0 | ctf_next_destroy (i); |
553 | 0 | *it = NULL; |
554 | 0 | return ECTF_NEXT_END; |
555 | 0 | } |
556 | | |
557 | 0 | if (key) |
558 | 0 | *key = i->u.ctn_sorted_hkv[i->ctn_n].hkv_key; |
559 | 0 | if (value) |
560 | 0 | *value = i->u.ctn_sorted_hkv[i->ctn_n].hkv_value; |
561 | 0 | i->ctn_n++; |
562 | 0 | return 0; |
563 | 0 | } |
564 | | |
565 | | void |
566 | | ctf_dynhash_destroy (ctf_dynhash_t *hp) |
567 | 0 | { |
568 | 0 | if (hp != NULL) |
569 | 0 | htab_delete (hp->htab); |
570 | 0 | free (hp); |
571 | 0 | } |
572 | | |
573 | | /* The dynset, used for sets of keys with no value. The implementation of this |
574 | | can be much simpler, because without a value the slot can simply be the |
575 | | stored key, which means we don't need to store the freeing functions and the |
576 | | dynset itself is just a htab. */ |
577 | | |
578 | | ctf_dynset_t * |
579 | | ctf_dynset_create (htab_hash hash_fun, htab_eq eq_fun, |
580 | | ctf_hash_free_fun key_free) |
581 | 0 | { |
582 | | /* 7 is arbitrary and untested for now. */ |
583 | 0 | return (ctf_dynset_t *) htab_create_alloc (7, (htab_hash) hash_fun, eq_fun, |
584 | 0 | key_free, xcalloc, free); |
585 | 0 | } |
586 | | |
587 | | /* The dynset has one complexity: the underlying implementation reserves two |
588 | | values for internal hash table implementation details (empty versus deleted |
589 | | entries). These values are otherwise very useful for pointers cast to ints, |
590 | | so transform the ctf_dynset_inserted value to allow for it. (This |
591 | | introduces an ambiguity in that one can no longer store these two values in |
592 | | the dynset, but if we pick high enough values this is very unlikely to be a |
593 | | problem.) |
594 | | |
595 | | We leak this implementation detail to the freeing functions on the grounds |
596 | | that any use of these functions is overwhelmingly likely to be in sets using |
597 | | real pointers, which will be unaffected. */ |
598 | | |
599 | 0 | #define DYNSET_EMPTY_ENTRY_REPLACEMENT ((void *) (uintptr_t) -64) |
600 | 0 | #define DYNSET_DELETED_ENTRY_REPLACEMENT ((void *) (uintptr_t) -63) |
601 | | |
602 | | static void * |
603 | | key_to_internal (const void *key) |
604 | 0 | { |
605 | 0 | if (key == HTAB_EMPTY_ENTRY) |
606 | 0 | return DYNSET_EMPTY_ENTRY_REPLACEMENT; |
607 | 0 | else if (key == HTAB_DELETED_ENTRY) |
608 | 0 | return DYNSET_DELETED_ENTRY_REPLACEMENT; |
609 | | |
610 | 0 | return (void *) key; |
611 | 0 | } |
612 | | |
613 | | static void * |
614 | | internal_to_key (const void *internal) |
615 | 0 | { |
616 | 0 | if (internal == DYNSET_EMPTY_ENTRY_REPLACEMENT) |
617 | 0 | return HTAB_EMPTY_ENTRY; |
618 | 0 | else if (internal == DYNSET_DELETED_ENTRY_REPLACEMENT) |
619 | 0 | return HTAB_DELETED_ENTRY; |
620 | 0 | return (void *) internal; |
621 | 0 | } |
622 | | |
623 | | int |
624 | | ctf_dynset_insert (ctf_dynset_t *hp, void *key) |
625 | 0 | { |
626 | 0 | struct htab *htab = (struct htab *) hp; |
627 | 0 | void **slot; |
628 | |
|
629 | 0 | slot = htab_find_slot (htab, key, INSERT); |
630 | |
|
631 | 0 | if (!slot) |
632 | 0 | { |
633 | 0 | errno = ENOMEM; |
634 | 0 | return -errno; |
635 | 0 | } |
636 | | |
637 | 0 | if (*slot) |
638 | 0 | { |
639 | 0 | if (htab->del_f) |
640 | 0 | (*htab->del_f) (*slot); |
641 | 0 | } |
642 | |
|
643 | 0 | *slot = key_to_internal (key); |
644 | |
|
645 | 0 | return 0; |
646 | 0 | } |
647 | | |
648 | | void |
649 | | ctf_dynset_remove (ctf_dynset_t *hp, const void *key) |
650 | 0 | { |
651 | 0 | htab_remove_elt ((struct htab *) hp, key_to_internal (key)); |
652 | 0 | } |
653 | | |
654 | | void |
655 | | ctf_dynset_destroy (ctf_dynset_t *hp) |
656 | 0 | { |
657 | 0 | if (hp != NULL) |
658 | 0 | htab_delete ((struct htab *) hp); |
659 | 0 | } |
660 | | |
661 | | void * |
662 | | ctf_dynset_lookup (ctf_dynset_t *hp, const void *key) |
663 | 0 | { |
664 | 0 | void **slot = htab_find_slot ((struct htab *) hp, |
665 | 0 | key_to_internal (key), NO_INSERT); |
666 | |
|
667 | 0 | if (slot) |
668 | 0 | return internal_to_key (*slot); |
669 | 0 | return NULL; |
670 | 0 | } |
671 | | |
672 | | /* TRUE/FALSE return. */ |
673 | | int |
674 | | ctf_dynset_exists (ctf_dynset_t *hp, const void *key, const void **orig_key) |
675 | 0 | { |
676 | 0 | void **slot = htab_find_slot ((struct htab *) hp, |
677 | 0 | key_to_internal (key), NO_INSERT); |
678 | |
|
679 | 0 | if (orig_key && slot) |
680 | 0 | *orig_key = internal_to_key (*slot); |
681 | 0 | return (slot != NULL); |
682 | 0 | } |
683 | | |
684 | | /* Look up a completely random value from the set, if any exist. |
685 | | Keys with value zero cannot be distinguished from a nonexistent key. */ |
686 | | void * |
687 | | ctf_dynset_lookup_any (ctf_dynset_t *hp) |
688 | 0 | { |
689 | 0 | struct htab *htab = (struct htab *) hp; |
690 | 0 | void **slot = htab->entries; |
691 | 0 | void **limit = slot + htab_size (htab); |
692 | |
|
693 | 0 | while (slot < limit |
694 | 0 | && (*slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)) |
695 | 0 | slot++; |
696 | |
|
697 | 0 | if (slot < limit) |
698 | 0 | return internal_to_key (*slot); |
699 | 0 | return NULL; |
700 | 0 | } |
701 | | |
702 | | /* Traverse a dynset in arbitrary order, in _next iterator form. |
703 | | |
704 | | Otherwise, just like ctf_dynhash_next. */ |
705 | | int |
706 | | ctf_dynset_next (ctf_dynset_t *hp, ctf_next_t **it, void **key) |
707 | 0 | { |
708 | 0 | struct htab *htab = (struct htab *) hp; |
709 | 0 | ctf_next_t *i = *it; |
710 | 0 | void *slot; |
711 | |
|
712 | 0 | if (!i) |
713 | 0 | { |
714 | 0 | size_t size = htab_size (htab); |
715 | | |
716 | | /* If the table has too many entries to fit in an ssize_t, just give up. |
717 | | This might be spurious, but if any type-related hashtable has ever been |
718 | | nearly as large as that then somthing very odd is going on. */ |
719 | |
|
720 | 0 | if (((ssize_t) size) < 0) |
721 | 0 | return EDOM; |
722 | | |
723 | 0 | if ((i = ctf_next_create ()) == NULL) |
724 | 0 | return ENOMEM; |
725 | | |
726 | 0 | i->u.ctn_hash_slot = htab->entries; |
727 | 0 | i->cu.ctn_s = hp; |
728 | 0 | i->ctn_n = 0; |
729 | 0 | i->ctn_size = (ssize_t) size; |
730 | 0 | i->ctn_iter_fun = (void (*) (void)) ctf_dynset_next; |
731 | 0 | *it = i; |
732 | 0 | } |
733 | | |
734 | 0 | if ((void (*) (void)) ctf_dynset_next != i->ctn_iter_fun) |
735 | 0 | return ECTF_NEXT_WRONGFUN; |
736 | | |
737 | 0 | if (hp != i->cu.ctn_s) |
738 | 0 | return ECTF_NEXT_WRONGFP; |
739 | | |
740 | 0 | if ((ssize_t) i->ctn_n == i->ctn_size) |
741 | 0 | goto set_end; |
742 | | |
743 | 0 | while ((ssize_t) i->ctn_n < i->ctn_size |
744 | 0 | && (*i->u.ctn_hash_slot == HTAB_EMPTY_ENTRY |
745 | 0 | || *i->u.ctn_hash_slot == HTAB_DELETED_ENTRY)) |
746 | 0 | { |
747 | 0 | i->u.ctn_hash_slot++; |
748 | 0 | i->ctn_n++; |
749 | 0 | } |
750 | |
|
751 | 0 | if ((ssize_t) i->ctn_n == i->ctn_size) |
752 | 0 | goto set_end; |
753 | | |
754 | 0 | slot = *i->u.ctn_hash_slot; |
755 | |
|
756 | 0 | if (key) |
757 | 0 | *key = internal_to_key (slot); |
758 | |
|
759 | 0 | i->u.ctn_hash_slot++; |
760 | 0 | i->ctn_n++; |
761 | |
|
762 | 0 | return 0; |
763 | | |
764 | 0 | set_end: |
765 | 0 | ctf_next_destroy (i); |
766 | 0 | *it = NULL; |
767 | 0 | return ECTF_NEXT_END; |
768 | 0 | } |
769 | | |
770 | | /* Helper functions for insertion/removal of types. */ |
771 | | |
772 | | int |
773 | | ctf_dynhash_insert_type (ctf_dict_t *fp, ctf_dynhash_t *hp, uint32_t type, |
774 | | uint32_t name) |
775 | 0 | { |
776 | 0 | const char *str; |
777 | 0 | int err; |
778 | |
|
779 | 0 | if (type == 0) |
780 | 0 | return EINVAL; |
781 | | |
782 | 0 | if ((str = ctf_strptr_validate (fp, name)) == NULL) |
783 | 0 | return ctf_errno (fp); |
784 | | |
785 | 0 | if (str[0] == '\0') |
786 | 0 | return 0; /* Just ignore empty strings on behalf of caller. */ |
787 | | |
788 | 0 | if ((err = ctf_dynhash_insert (hp, (char *) str, |
789 | 0 | (void *) (ptrdiff_t) type)) == 0) |
790 | 0 | return 0; |
791 | | |
792 | 0 | return err; |
793 | 0 | } |
794 | | |
795 | | ctf_id_t |
796 | | ctf_dynhash_lookup_type (ctf_dynhash_t *hp, const char *key) |
797 | 0 | { |
798 | 0 | void *value; |
799 | |
|
800 | 0 | if (ctf_dynhash_lookup_kv (hp, key, NULL, &value)) |
801 | 0 | return (ctf_id_t) (uintptr_t) value; |
802 | | |
803 | 0 | return 0; |
804 | 0 | } |