libctf/ctf-hash.c

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