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