| 1 | /* Interface to hashtable implementations. |
| 2 | Copyright (C) 2006-2019 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: 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 |
| 32 | if you wish. */ |
| 33 | |
| 34 | typedef struct ctf_helem |
| 35 | { |
| 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; |
| 40 | } ctf_helem_t; |
| 41 | |
| 42 | struct ctf_dynhash |
| 43 | { |
| 44 | struct htab *htab; |
| 45 | ctf_hash_free_fun key_free; |
| 46 | ctf_hash_free_fun value_free; |
| 47 | }; |
| 48 | |
| 49 | /* Hash functions. */ |
| 50 | |
| 51 | unsigned int |
| 52 | ctf_hash_integer (const void *ptr) |
| 53 | { |
| 54 | ctf_helem_t *hep = (ctf_helem_t *) ptr; |
| 55 | |
| 56 | return htab_hash_pointer (hep->key); |
| 57 | } |
| 58 | |
| 59 | int |
| 60 | ctf_hash_eq_integer (const void *a, const void *b) |
| 61 | { |
| 62 | ctf_helem_t *hep_a = (ctf_helem_t *) a; |
| 63 | ctf_helem_t *hep_b = (ctf_helem_t *) b; |
| 64 | |
| 65 | return htab_eq_pointer (hep_a->key, hep_b->key); |
| 66 | } |
| 67 | |
| 68 | unsigned int |
| 69 | ctf_hash_string (const void *ptr) |
| 70 | { |
| 71 | ctf_helem_t *hep = (ctf_helem_t *) ptr; |
| 72 | |
| 73 | return htab_hash_string (hep->key); |
| 74 | } |
| 75 | |
| 76 | int |
| 77 | ctf_hash_eq_string (const void *a, const void *b) |
| 78 | { |
| 79 | ctf_helem_t *hep_a = (ctf_helem_t *) a; |
| 80 | ctf_helem_t *hep_b = (ctf_helem_t *) b; |
| 81 | |
| 82 | return !strcmp((const char *) hep_a->key, (const char *) hep_b->key); |
| 83 | } |
| 84 | |
| 85 | /* The dynhash, used for hashes whose size is not known at creation time. */ |
| 86 | |
| 87 | /* Free a single ctf_helem. */ |
| 88 | |
| 89 | static void |
| 90 | ctf_dynhash_item_free (void *item) |
| 91 | { |
| 92 | ctf_helem_t *helem = item; |
| 93 | |
| 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); |
| 98 | free (helem); |
| 99 | } |
| 100 | |
| 101 | ctf_dynhash_t * |
| 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) |
| 104 | { |
| 105 | ctf_dynhash_t *dynhash; |
| 106 | |
| 107 | dynhash = malloc (sizeof (ctf_dynhash_t)); |
| 108 | if (!dynhash) |
| 109 | return NULL; |
| 110 | |
| 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) |
| 114 | { |
| 115 | free (dynhash); |
| 116 | return NULL; |
| 117 | } |
| 118 | |
| 119 | dynhash->key_free = key_free; |
| 120 | dynhash->value_free = value_free; |
| 121 | |
| 122 | return dynhash; |
| 123 | } |
| 124 | |
| 125 | static ctf_helem_t ** |
| 126 | ctf_hashtab_lookup (struct htab *htab, const void *key, enum insert_option insert) |
| 127 | { |
| 128 | ctf_helem_t tmp = { .key = (void *) key }; |
| 129 | return (ctf_helem_t **) htab_find_slot (htab, &tmp, insert); |
| 130 | } |
| 131 | |
| 132 | static ctf_helem_t * |
| 133 | ctf_hashtab_insert (struct htab *htab, void *key, void *value) |
| 134 | { |
| 135 | ctf_helem_t **slot; |
| 136 | |
| 137 | slot = ctf_hashtab_lookup (htab, key, INSERT); |
| 138 | |
| 139 | if (!slot) |
| 140 | { |
| 141 | errno = -ENOMEM; |
| 142 | return NULL; |
| 143 | } |
| 144 | |
| 145 | if (!*slot) |
| 146 | { |
| 147 | *slot = malloc (sizeof (ctf_helem_t)); |
| 148 | if (!*slot) |
| 149 | return NULL; |
| 150 | (*slot)->key = key; |
| 151 | } |
| 152 | (*slot)->value = value; |
| 153 | return *slot; |
| 154 | } |
| 155 | |
| 156 | int |
| 157 | ctf_dynhash_insert (ctf_dynhash_t *hp, void *key, void *value) |
| 158 | { |
| 159 | ctf_helem_t *slot; |
| 160 | |
| 161 | slot = ctf_hashtab_insert (hp->htab, key, value); |
| 162 | |
| 163 | if (!slot) |
| 164 | return errno; |
| 165 | |
| 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 |
| 168 | individual items. */ |
| 169 | |
| 170 | slot->key_free = hp->key_free; |
| 171 | slot->value_free = hp->value_free; |
| 172 | |
| 173 | return 0; |
| 174 | } |
| 175 | |
| 176 | void |
| 177 | ctf_dynhash_remove (ctf_dynhash_t *hp, const void *key) |
| 178 | { |
| 179 | htab_remove_elt (hp->htab, (void *) key); |
| 180 | } |
| 181 | |
| 182 | void * |
| 183 | ctf_dynhash_lookup (ctf_dynhash_t *hp, const void *key) |
| 184 | { |
| 185 | ctf_helem_t **slot; |
| 186 | |
| 187 | slot = ctf_hashtab_lookup (hp->htab, key, NO_INSERT); |
| 188 | |
| 189 | if (slot) |
| 190 | return (*slot)->value; |
| 191 | |
| 192 | return NULL; |
| 193 | } |
| 194 | |
| 195 | void |
| 196 | ctf_dynhash_destroy (ctf_dynhash_t *hp) |
| 197 | { |
| 198 | if (hp != NULL) |
| 199 | htab_delete (hp->htab); |
| 200 | free (hp); |
| 201 | } |
| 202 | |
| 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. */ |
| 205 | |
| 206 | ctf_hash_t * |
| 207 | ctf_hash_create (unsigned long nelems, ctf_hash_fun hash_fun, |
| 208 | ctf_hash_eq_fun eq_fun) |
| 209 | { |
| 210 | return (ctf_hash_t *) htab_create_alloc (nelems, (htab_hash) hash_fun, |
| 211 | eq_fun, free, xcalloc, free); |
| 212 | } |
| 213 | |
| 214 | uint32_t |
| 215 | ctf_hash_size (const ctf_hash_t *hp) |
| 216 | { |
| 217 | return htab_elements ((struct htab *) hp); |
| 218 | } |
| 219 | |
| 220 | int |
| 221 | ctf_hash_insert_type (ctf_hash_t *hp, ctf_file_t *fp, uint32_t type, |
| 222 | uint32_t name) |
| 223 | { |
| 224 | ctf_strs_t *ctsp = &fp->ctf_str[CTF_NAME_STID (name)]; |
| 225 | const char *str = ctsp->cts_strs + CTF_NAME_OFFSET (name); |
| 226 | |
| 227 | if (type == 0) |
| 228 | return EINVAL; |
| 229 | |
| 230 | if (ctsp->cts_strs == NULL) |
| 231 | return ECTF_STRTAB; |
| 232 | |
| 233 | if (ctsp->cts_len <= CTF_NAME_OFFSET (name)) |
| 234 | return ECTF_BADNAME; |
| 235 | |
| 236 | if (str[0] == '\0') |
| 237 | return 0; /* Just ignore empty strings on behalf of caller. */ |
| 238 | |
| 239 | if (ctf_hashtab_insert ((struct htab *) hp, (char *) str, |
| 240 | (void *) (ptrdiff_t) type) != NULL) |
| 241 | return 0; |
| 242 | return errno; |
| 243 | } |
| 244 | |
| 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. */ |
| 248 | int |
| 249 | ctf_hash_define_type (ctf_hash_t *hp, ctf_file_t *fp, uint32_t type, |
| 250 | uint32_t name) |
| 251 | { |
| 252 | /* This matches the semantics of ctf_hash_insert_type() in this |
| 253 | implementation anyway. */ |
| 254 | |
| 255 | return ctf_hash_insert_type (hp, fp, type, name); |
| 256 | } |
| 257 | |
| 258 | ctf_id_t |
| 259 | ctf_hash_lookup_type (ctf_hash_t *hp, ctf_file_t *fp __attribute__ ((__unused__)), |
| 260 | const char *key) |
| 261 | { |
| 262 | ctf_helem_t **slot; |
| 263 | |
| 264 | slot = ctf_hashtab_lookup ((struct htab *) hp, key, NO_INSERT); |
| 265 | |
| 266 | if (slot) |
| 267 | return (ctf_id_t) ((*slot)->value); |
| 268 | |
| 269 | return 0; |
| 270 | } |
| 271 | |
| 272 | void |
| 273 | ctf_hash_destroy (ctf_hash_t *hp) |
| 274 | { |
| 275 | if (hp != NULL) |
| 276 | htab_delete ((struct htab *) hp); |
| 277 | } |