1 /* Interface to hashtable implementations.
2 Copyright (C) 2006-2019 Free Software Foundation, Inc.
4 This file is part of libctf.
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
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.
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/>. */
22 #include "libiberty.h"
25 /* We have two hashtable implementations: one, ctf_dynhash_*(), is an interface to
26 a dynamically-expanding hash with unknown size that should support addition
27 of large numbers of items, and removal as well, and is used only at
28 type-insertion time; the other, ctf_dynhash_*(), is an interface to a
29 fixed-size hash from const char * -> ctf_id_t with number of elements
30 specified at creation time, that should support addition of items but need
31 not support removal. These can be implemented by the same underlying hashmap
34 typedef struct ctf_helem
36 void *key
; /* Either a pointer, or a coerced ctf_id_t. */
37 void *value
; /* The value (possibly a coerced int). */
38 ctf_hash_free_fun key_free
;
39 ctf_hash_free_fun value_free
;
45 ctf_hash_free_fun key_free
;
46 ctf_hash_free_fun value_free
;
52 ctf_hash_integer (const void *ptr
)
54 ctf_helem_t
*hep
= (ctf_helem_t
*) ptr
;
56 return htab_hash_pointer (hep
->key
);
60 ctf_hash_eq_integer (const void *a
, const void *b
)
62 ctf_helem_t
*hep_a
= (ctf_helem_t
*) a
;
63 ctf_helem_t
*hep_b
= (ctf_helem_t
*) b
;
65 return htab_eq_pointer (hep_a
->key
, hep_b
->key
);
69 ctf_hash_string (const void *ptr
)
71 ctf_helem_t
*hep
= (ctf_helem_t
*) ptr
;
73 return htab_hash_string (hep
->key
);
77 ctf_hash_eq_string (const void *a
, const void *b
)
79 ctf_helem_t
*hep_a
= (ctf_helem_t
*) a
;
80 ctf_helem_t
*hep_b
= (ctf_helem_t
*) b
;
82 return !strcmp((const char *) hep_a
->key
, (const char *) hep_b
->key
);
85 /* The dynhash, used for hashes whose size is not known at creation time. */
87 /* Free a single ctf_helem. */
90 ctf_dynhash_item_free (void *item
)
92 ctf_helem_t
*helem
= item
;
94 if (helem
->key_free
&& helem
->key
)
95 helem
->key_free (helem
->key
);
96 if (helem
->value_free
&& helem
->value
)
97 helem
->value_free (helem
->value
);
102 ctf_dynhash_create (ctf_hash_fun hash_fun
, ctf_hash_eq_fun eq_fun
,
103 ctf_hash_free_fun key_free
, ctf_hash_free_fun value_free
)
105 ctf_dynhash_t
*dynhash
;
107 dynhash
= malloc (sizeof (ctf_dynhash_t
));
111 /* 7 is arbitrary and untested for now.. */
112 if ((dynhash
->htab
= htab_create_alloc (7, (htab_hash
) hash_fun
, eq_fun
,
113 ctf_dynhash_item_free
, xcalloc
, free
)) == NULL
)
119 dynhash
->key_free
= key_free
;
120 dynhash
->value_free
= value_free
;
125 static ctf_helem_t
**
126 ctf_hashtab_lookup (struct htab
*htab
, const void *key
, enum insert_option insert
)
128 ctf_helem_t tmp
= { .key
= (void *) key
};
129 return (ctf_helem_t
**) htab_find_slot (htab
, &tmp
, insert
);
133 ctf_hashtab_insert (struct htab
*htab
, void *key
, void *value
)
137 slot
= ctf_hashtab_lookup (htab
, key
, INSERT
);
147 *slot
= malloc (sizeof (ctf_helem_t
));
152 (*slot
)->value
= value
;
157 ctf_dynhash_insert (ctf_dynhash_t
*hp
, void *key
, void *value
)
161 slot
= ctf_hashtab_insert (hp
->htab
, key
, value
);
166 /* We need to keep the key_free and value_free around in each item because the
167 del function has no visiblity into the hash as a whole, only into the
170 slot
->key_free
= hp
->key_free
;
171 slot
->value_free
= hp
->value_free
;
177 ctf_dynhash_remove (ctf_dynhash_t
*hp
, const void *key
)
179 htab_remove_elt (hp
->htab
, (void *) key
);
183 ctf_dynhash_lookup (ctf_dynhash_t
*hp
, const void *key
)
187 slot
= ctf_hashtab_lookup (hp
->htab
, key
, NO_INSERT
);
190 return (*slot
)->value
;
196 ctf_dynhash_destroy (ctf_dynhash_t
*hp
)
199 htab_delete (hp
->htab
);
203 /* ctf_hash, used for fixed-size maps from const char * -> ctf_id_t without
204 removal. This is a straight cast of a hashtab. */
207 ctf_hash_create (unsigned long nelems
, ctf_hash_fun hash_fun
,
208 ctf_hash_eq_fun eq_fun
)
210 return (ctf_hash_t
*) htab_create_alloc (nelems
, (htab_hash
) hash_fun
,
211 eq_fun
, free
, xcalloc
, free
);
215 ctf_hash_size (const ctf_hash_t
*hp
)
217 return htab_elements ((struct htab
*) hp
);
221 ctf_hash_insert_type (ctf_hash_t
*hp
, ctf_file_t
*fp
, uint32_t type
,
224 ctf_strs_t
*ctsp
= &fp
->ctf_str
[CTF_NAME_STID (name
)];
225 const char *str
= ctsp
->cts_strs
+ CTF_NAME_OFFSET (name
);
230 if (ctsp
->cts_strs
== NULL
)
233 if (ctsp
->cts_len
<= CTF_NAME_OFFSET (name
))
237 return 0; /* Just ignore empty strings on behalf of caller. */
239 if (ctf_hashtab_insert ((struct htab
*) hp
, (char *) str
,
240 (void *) (ptrdiff_t) type
) != NULL
)
245 /* if the key is already in the hash, override the previous definition with
246 this new official definition. If the key is not present, then call
247 ctf_hash_insert_type() and hash it in. */
249 ctf_hash_define_type (ctf_hash_t
*hp
, ctf_file_t
*fp
, uint32_t type
,
252 /* This matches the semantics of ctf_hash_insert_type() in this
253 implementation anyway. */
255 return ctf_hash_insert_type (hp
, fp
, type
, name
);
259 ctf_hash_lookup_type (ctf_hash_t
*hp
, ctf_file_t
*fp
__attribute__ ((__unused__
)),
264 slot
= ctf_hashtab_lookup ((struct htab
*) hp
, key
, NO_INSERT
);
267 return (ctf_id_t
) ((*slot
)->value
);
273 ctf_hash_destroy (ctf_hash_t
*hp
)
276 htab_delete ((struct htab
*) hp
);