libctf/ctf-hash.c

   1 /* Interface to hashtable implementations.
   2    Copyright (C) 2006-2020 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 /* Traverse a sorted dynhash, in _next iterator form.
 480
 481    See ctf_dynhash_next for notes on error returns, etc.
 482
 483    Sort keys before iterating over them using the SORT_FUN and SORT_ARG.
 484
 485    If SORT_FUN is null, thunks to ctf_dynhash_next.  */
 486 int
 487 ctf_dynhash_next_sorted (ctf_dynhash_t *h, ctf_next_t **it, void **key,
 488                          void **value, ctf_hash_sort_f sort_fun, void *sort_arg)
 489 {
 490   ctf_next_t *i = *it;
 491
 492   if (sort_fun == NULL)
 493     return ctf_dynhash_next (h, it, key, value);
 494
 495   if (!i)
 496     {
 497       size_t els = ctf_dynhash_elements (h);
 498       ctf_next_t *accum_i = NULL;
 499       void *key, *value;
 500       int err;
 501       ctf_next_hkv_t *walk;
 502
 503       if (((ssize_t) els) < 0)
 504         return EDOM;
 505
 506       if ((i = ctf_next_create ()) == NULL)
 507         return ENOMEM;
 508
 509       if ((i->u.ctn_sorted_hkv = calloc (els, sizeof (ctf_next_hkv_t))) == NULL)
 510         {
 511           ctf_next_destroy (i);
 512           return ENOMEM;
 513         }
 514       walk = i->u.ctn_sorted_hkv;
 515
 516       i->cu.ctn_h = h;
 517
 518       while ((err = ctf_dynhash_next (h, &accum_i, &key, &value)) == 0)
 519         {
 520           walk->hkv_key = key;
 521           walk->hkv_value = value;
 522           walk++;
 523         }
 524       if (err != ECTF_NEXT_END)
 525         {
 526           ctf_next_destroy (i);
 527           return err;
 528         }
 529
 530       if (sort_fun)
 531           ctf_qsort_r (i->u.ctn_sorted_hkv, els, sizeof (ctf_next_hkv_t),
 532                        (int (*) (const void *, const void *, void *)) sort_fun,
 533                        sort_arg);
 534       i->ctn_n = 0;
 535       i->ctn_size = (ssize_t) els;
 536       i->ctn_iter_fun = (void (*) (void)) ctf_dynhash_next_sorted;
 537       *it = i;
 538     }
 539
 540   if ((void (*) (void)) ctf_dynhash_next_sorted != i->ctn_iter_fun)
 541     return ECTF_NEXT_WRONGFUN;
 542
 543   if (h != i->cu.ctn_h)
 544     return ECTF_NEXT_WRONGFP;
 545
 546   if ((ssize_t) i->ctn_n == i->ctn_size)
 547     {
 548       ctf_next_destroy (i);
 549       *it = NULL;
 550       return ECTF_NEXT_END;
 551     }
 552
 553   if (key)
 554     *key = i->u.ctn_sorted_hkv[i->ctn_n].hkv_key;
 555   if (value)
 556     *value = i->u.ctn_sorted_hkv[i->ctn_n].hkv_value;
 557   i->ctn_n++;
 558   return 0;
 559 }
 560
 561 void
 562 ctf_dynhash_destroy (ctf_dynhash_t *hp)
 563 {
 564   if (hp != NULL)
 565     htab_delete (hp->htab);
 566   free (hp);
 567 }
 568
 569 /* The dynset, used for sets of keys with no value.  The implementation of this
 570    can be much simpler, because without a value the slot can simply be the
 571    stored key, which means we don't need to store the freeing functions and the
 572    dynset itself is just a htab.  */
 573
 574 ctf_dynset_t *
 575 ctf_dynset_create (htab_hash hash_fun, htab_eq eq_fun,
 576                    ctf_hash_free_fun key_free)
 577 {
 578   /* 7 is arbitrary and untested for now.  */
 579   return (ctf_dynset_t *) htab_create_alloc (7, (htab_hash) hash_fun, eq_fun,
 580                                              key_free, xcalloc, free);
 581 }
 582
 583 /* The dynset has one complexity: the underlying implementation reserves two
 584    values for internal hash table implementation details (empty versus deleted
 585    entries).  These values are otherwise very useful for pointers cast to ints,
 586    so transform the ctf_dynset_inserted value to allow for it.  (This
 587    introduces an ambiguity in that one can no longer store these two values in
 588    the dynset, but if we pick high enough values this is very unlikely to be a
 589    problem.)
 590
 591    We leak this implementation detail to the freeing functions on the grounds
 592    that any use of these functions is overwhelmingly likely to be in sets using
 593    real pointers, which will be unaffected.  */
 594
 595 #define DYNSET_EMPTY_ENTRY_REPLACEMENT ((void *) (uintptr_t) -64)
 596 #define DYNSET_DELETED_ENTRY_REPLACEMENT ((void *) (uintptr_t) -63)
 597
 598 static void *
 599 key_to_internal (const void *key)
 600 {
 601   if (key == HTAB_EMPTY_ENTRY)
 602     return DYNSET_EMPTY_ENTRY_REPLACEMENT;
 603   else if (key == HTAB_DELETED_ENTRY)
 604     return DYNSET_DELETED_ENTRY_REPLACEMENT;
 605
 606   return (void *) key;
 607 }
 608
 609 static void *
 610 internal_to_key (const void *internal)
 611 {
 612   if (internal == DYNSET_EMPTY_ENTRY_REPLACEMENT)
 613     return HTAB_EMPTY_ENTRY;
 614   else if (internal == DYNSET_DELETED_ENTRY_REPLACEMENT)
 615     return HTAB_DELETED_ENTRY;
 616   return (void *) internal;
 617 }
 618
 619 int
 620 ctf_dynset_insert (ctf_dynset_t *hp, void *key)
 621 {
 622   struct htab *htab = (struct htab *) hp;
 623   void **slot;
 624
 625   slot = htab_find_slot (htab, key, INSERT);
 626
 627   if (!slot)
 628     {
 629       errno = ENOMEM;
 630       return -errno;
 631     }
 632
 633   if (*slot)
 634     {
 635       if (htab->del_f)
 636         (*htab->del_f) (*slot);
 637     }
 638
 639   *slot = key_to_internal (key);
 640
 641   return 0;
 642 }
 643
 644 void
 645 ctf_dynset_remove (ctf_dynset_t *hp, const void *key)
 646 {
 647   htab_remove_elt ((struct htab *) hp, key_to_internal (key));
 648 }
 649
 650 void
 651 ctf_dynset_destroy (ctf_dynset_t *hp)
 652 {
 653   if (hp != NULL)
 654     htab_delete ((struct htab *) hp);
 655 }
 656
 657 void *
 658 ctf_dynset_lookup (ctf_dynset_t *hp, const void *key)
 659 {
 660   void **slot = htab_find_slot ((struct htab *) hp,
 661                                 key_to_internal (key), NO_INSERT);
 662
 663   if (slot)
 664     return internal_to_key (*slot);
 665   return NULL;
 666 }
 667
 668 /* TRUE/FALSE return.  */
 669 int
 670 ctf_dynset_exists (ctf_dynset_t *hp, const void *key, const void **orig_key)
 671 {
 672   void **slot = htab_find_slot ((struct htab *) hp,
 673                                 key_to_internal (key), NO_INSERT);
 674
 675   if (orig_key && slot)
 676     *orig_key = internal_to_key (*slot);
 677   return (slot != NULL);
 678 }
 679
 680 /* Look up a completely random value from the set, if any exist.
 681    Keys with value zero cannot be distinguished from a nonexistent key.  */
 682 void *
 683 ctf_dynset_lookup_any (ctf_dynset_t *hp)
 684 {
 685   struct htab *htab = (struct htab *) hp;
 686   void **slot = htab->entries;
 687   void **limit = slot + htab_size (htab);
 688
 689   while (slot < limit
 690          && (*slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY))
 691       slot++;
 692
 693   if (slot < limit)
 694     return internal_to_key (*slot);
 695   return NULL;
 696 }
 697
 698 /* Traverse a dynset in arbitrary order, in _next iterator form.
 699
 700    Otherwise, just like ctf_dynhash_next.  */
 701 int
 702 ctf_dynset_next (ctf_dynset_t *hp, ctf_next_t **it, void **key)
 703 {
 704   struct htab *htab = (struct htab *) hp;
 705   ctf_next_t *i = *it;
 706   void *slot;
 707
 708   if (!i)
 709     {
 710       size_t size = htab_size (htab);
 711
 712       /* If the table has too many entries to fit in an ssize_t, just give up.
 713          This might be spurious, but if any type-related hashtable has ever been
 714          nearly as large as that then somthing very odd is going on.  */
 715
 716       if (((ssize_t) size) < 0)
 717         return EDOM;
 718
 719       if ((i = ctf_next_create ()) == NULL)
 720         return ENOMEM;
 721
 722       i->u.ctn_hash_slot = htab->entries;
 723       i->cu.ctn_s = hp;
 724       i->ctn_n = 0;
 725       i->ctn_size = (ssize_t) size;
 726       i->ctn_iter_fun = (void (*) (void)) ctf_dynset_next;
 727       *it = i;
 728     }
 729
 730   if ((void (*) (void)) ctf_dynset_next != i->ctn_iter_fun)
 731     return ECTF_NEXT_WRONGFUN;
 732
 733   if (hp != i->cu.ctn_s)
 734     return ECTF_NEXT_WRONGFP;
 735
 736   if ((ssize_t) i->ctn_n == i->ctn_size)
 737     goto set_end;
 738
 739   while ((ssize_t) i->ctn_n < i->ctn_size
 740          && (*i->u.ctn_hash_slot == HTAB_EMPTY_ENTRY
 741              || *i->u.ctn_hash_slot == HTAB_DELETED_ENTRY))
 742     {
 743       i->u.ctn_hash_slot++;
 744       i->ctn_n++;
 745     }
 746
 747   if ((ssize_t) i->ctn_n == i->ctn_size)
 748     goto set_end;
 749
 750   slot = *i->u.ctn_hash_slot;
 751
 752   if (key)
 753     *key = internal_to_key (slot);
 754
 755   i->u.ctn_hash_slot++;
 756   i->ctn_n++;
 757
 758   return 0;
 759
 760  set_end:
 761   ctf_next_destroy (i);
 762   *it = NULL;
 763   return ECTF_NEXT_END;
 764 }
 765
 766 /* ctf_hash, used for fixed-size maps from const char * -> ctf_id_t without
 767    removal.  This is a straight cast of a hashtab.  */
 768
 769 ctf_hash_t *
 770 ctf_hash_create (unsigned long nelems, ctf_hash_fun hash_fun,
 771                  ctf_hash_eq_fun eq_fun)
 772 {
 773   return (ctf_hash_t *) htab_create_alloc (nelems, (htab_hash) hash_fun,
 774                                            eq_fun, free, xcalloc, free);
 775 }
 776
 777 uint32_t
 778 ctf_hash_size (const ctf_hash_t *hp)
 779 {
 780   return htab_elements ((struct htab *) hp);
 781 }
 782
 783 int
 784 ctf_hash_insert_type (ctf_hash_t *hp, ctf_dict_t *fp, uint32_t type,
 785                       uint32_t name)
 786 {
 787   const char *str = ctf_strraw (fp, name);
 788
 789   if (type == 0)
 790     return EINVAL;
 791
 792   if (str == NULL
 793       && CTF_NAME_STID (name) == CTF_STRTAB_1
 794       && fp->ctf_syn_ext_strtab == NULL
 795       && fp->ctf_str[CTF_NAME_STID (name)].cts_strs == NULL)
 796     return ECTF_STRTAB;
 797
 798   if (str == NULL)
 799     return ECTF_BADNAME;
 800
 801   if (str[0] == '\0')
 802     return 0;              /* Just ignore empty strings on behalf of caller.  */
 803
 804   if (ctf_hashtab_insert ((struct htab *) hp, (char *) str,
 805                           (void *) (ptrdiff_t) type, NULL, NULL) != NULL)
 806     return 0;
 807   return errno;
 808 }
 809
 810 /* if the key is already in the hash, override the previous definition with
 811    this new official definition. If the key is not present, then call
 812    ctf_hash_insert_type and hash it in.  */
 813 int
 814 ctf_hash_define_type (ctf_hash_t *hp, ctf_dict_t *fp, uint32_t type,
 815                       uint32_t name)
 816 {
 817   /* This matches the semantics of ctf_hash_insert_type in this
 818      implementation anyway.  */
 819
 820   return ctf_hash_insert_type (hp, fp, type, name);
 821 }
 822
 823 ctf_id_t
 824 ctf_hash_lookup_type (ctf_hash_t *hp, ctf_dict_t *fp __attribute__ ((__unused__)),
 825                       const char *key)
 826 {
 827   ctf_helem_t **slot;
 828
 829   slot = ctf_hashtab_lookup ((struct htab *) hp, key, NO_INSERT);
 830
 831   if (slot)
 832     return (ctf_id_t) (uintptr_t) ((*slot)->value);
 833
 834   return 0;
 835 }
 836
 837 void
 838 ctf_hash_destroy (ctf_hash_t *hp)
 839 {
 840   if (hp != NULL)
 841     htab_delete ((struct htab *) hp);
 842 }