Coverage Report

Created: 2023-08-28 06:23

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