libctf/ctf-hash.c

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