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