Coverage Report

Created: 2024-05-21 06:29

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