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 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 /* Hash a type_mapping_key. */ 86 unsigned int 87 ctf_hash_type_mapping_key (const void *ptr) 88 { 89 ctf_helem_t *hep = (ctf_helem_t *) ptr; 90 ctf_link_type_mapping_key_t *k = (ctf_link_type_mapping_key_t *) hep->key; 91 92 return htab_hash_pointer (k->cltm_fp) + 59 * htab_hash_pointer ((void *) k->cltm_idx); 93 } 94 95 int 96 ctf_hash_eq_type_mapping_key (const void *a, const void *b) 97 { 98 ctf_helem_t *hep_a = (ctf_helem_t *) a; 99 ctf_helem_t *hep_b = (ctf_helem_t *) b; 100 ctf_link_type_mapping_key_t *key_a = (ctf_link_type_mapping_key_t *) hep_a->key; 101 ctf_link_type_mapping_key_t *key_b = (ctf_link_type_mapping_key_t *) hep_b->key; 102 103 return (key_a->cltm_fp == key_b->cltm_fp) 104 && (key_a->cltm_idx == key_b->cltm_idx); 105 } 106 107 /* The dynhash, used for hashes whose size is not known at creation time. */ 108 109 /* Free a single ctf_helem. */ 110 111 static void 112 ctf_dynhash_item_free (void *item) 113 { 114 ctf_helem_t *helem = item; 115 116 if (helem->key_free && helem->key) 117 helem->key_free (helem->key); 118 if (helem->value_free && helem->value) 119 helem->value_free (helem->value); 120 free (helem); 121 } 122 123 ctf_dynhash_t * 124 ctf_dynhash_create (ctf_hash_fun hash_fun, ctf_hash_eq_fun eq_fun, 125 ctf_hash_free_fun key_free, ctf_hash_free_fun value_free) 126 { 127 ctf_dynhash_t *dynhash; 128 129 dynhash = malloc (sizeof (ctf_dynhash_t)); 130 if (!dynhash) 131 return NULL; 132 133 /* 7 is arbitrary and untested for now.. */ 134 if ((dynhash->htab = htab_create_alloc (7, (htab_hash) hash_fun, eq_fun, 135 ctf_dynhash_item_free, xcalloc, free)) == NULL) 136 { 137 free (dynhash); 138 return NULL; 139 } 140 141 dynhash->key_free = key_free; 142 dynhash->value_free = value_free; 143 144 return dynhash; 145 } 146 147 static ctf_helem_t ** 148 ctf_hashtab_lookup (struct htab *htab, const void *key, enum insert_option insert) 149 { 150 ctf_helem_t tmp = { .key = (void *) key }; 151 return (ctf_helem_t **) htab_find_slot (htab, &tmp, insert); 152 } 153 154 static ctf_helem_t * 155 ctf_hashtab_insert (struct htab *htab, void *key, void *value, 156 ctf_hash_free_fun key_free, 157 ctf_hash_free_fun value_free) 158 { 159 ctf_helem_t **slot; 160 161 slot = ctf_hashtab_lookup (htab, key, INSERT); 162 163 if (!slot) 164 { 165 errno = -ENOMEM; 166 return NULL; 167 } 168 169 if (!*slot) 170 { 171 *slot = malloc (sizeof (ctf_helem_t)); 172 if (!*slot) 173 return NULL; 174 } 175 else 176 { 177 if (key_free) 178 key_free ((*slot)->key); 179 if (value_free) 180 value_free ((*slot)->value); 181 } 182 (*slot)->key = key; 183 (*slot)->value = value; 184 return *slot; 185 } 186 187 int 188 ctf_dynhash_insert (ctf_dynhash_t *hp, void *key, void *value) 189 { 190 ctf_helem_t *slot; 191 192 slot = ctf_hashtab_insert (hp->htab, key, value, 193 hp->key_free, hp->value_free); 194 195 if (!slot) 196 return errno; 197 198 /* We need to keep the key_free and value_free around in each item because the 199 del function has no visibility into the hash as a whole, only into the 200 individual items. */ 201 202 slot->key_free = hp->key_free; 203 slot->value_free = hp->value_free; 204 205 return 0; 206 } 207 208 void 209 ctf_dynhash_remove (ctf_dynhash_t *hp, const void *key) 210 { 211 ctf_helem_t hep = { (void *) key, NULL, NULL, NULL }; 212 htab_remove_elt (hp->htab, &hep); 213 } 214 215 void 216 ctf_dynhash_empty (ctf_dynhash_t *hp) 217 { 218 htab_empty (hp->htab); 219 } 220 221 void * 222 ctf_dynhash_lookup (ctf_dynhash_t *hp, const void *key) 223 { 224 ctf_helem_t **slot; 225 226 slot = ctf_hashtab_lookup (hp->htab, key, NO_INSERT); 227 228 if (slot) 229 return (*slot)->value; 230 231 return NULL; 232 } 233 234 typedef struct ctf_traverse_cb_arg 235 { 236 ctf_hash_iter_f fun; 237 void *arg; 238 } ctf_traverse_cb_arg_t; 239 240 static int 241 ctf_hashtab_traverse (void **slot, void *arg_) 242 { 243 ctf_helem_t *helem = *((ctf_helem_t **) slot); 244 ctf_traverse_cb_arg_t *arg = (ctf_traverse_cb_arg_t *) arg_; 245 246 arg->fun (helem->key, helem->value, arg->arg); 247 return 1; 248 } 249 250 void 251 ctf_dynhash_iter (ctf_dynhash_t *hp, ctf_hash_iter_f fun, void *arg_) 252 { 253 ctf_traverse_cb_arg_t arg = { fun, arg_ }; 254 htab_traverse (hp->htab, ctf_hashtab_traverse, &arg); 255 } 256 257 typedef struct ctf_traverse_remove_cb_arg 258 { 259 struct htab *htab; 260 ctf_hash_iter_remove_f fun; 261 void *arg; 262 } ctf_traverse_remove_cb_arg_t; 263 264 static int 265 ctf_hashtab_traverse_remove (void **slot, void *arg_) 266 { 267 ctf_helem_t *helem = *((ctf_helem_t **) slot); 268 ctf_traverse_remove_cb_arg_t *arg = (ctf_traverse_remove_cb_arg_t *) arg_; 269 270 if (arg->fun (helem->key, helem->value, arg->arg)) 271 htab_clear_slot (arg->htab, slot); 272 return 1; 273 } 274 275 void 276 ctf_dynhash_iter_remove (ctf_dynhash_t *hp, ctf_hash_iter_remove_f fun, 277 void *arg_) 278 { 279 ctf_traverse_remove_cb_arg_t arg = { hp->htab, fun, arg_ }; 280 htab_traverse (hp->htab, ctf_hashtab_traverse_remove, &arg); 281 } 282 283 void 284 ctf_dynhash_destroy (ctf_dynhash_t *hp) 285 { 286 if (hp != NULL) 287 htab_delete (hp->htab); 288 free (hp); 289 } 290 291 /* ctf_hash, used for fixed-size maps from const char * -> ctf_id_t without 292 removal. This is a straight cast of a hashtab. */ 293 294 ctf_hash_t * 295 ctf_hash_create (unsigned long nelems, ctf_hash_fun hash_fun, 296 ctf_hash_eq_fun eq_fun) 297 { 298 return (ctf_hash_t *) htab_create_alloc (nelems, (htab_hash) hash_fun, 299 eq_fun, free, xcalloc, free); 300 } 301 302 uint32_t 303 ctf_hash_size (const ctf_hash_t *hp) 304 { 305 return htab_elements ((struct htab *) hp); 306 } 307 308 int 309 ctf_hash_insert_type (ctf_hash_t *hp, ctf_file_t *fp, uint32_t type, 310 uint32_t name) 311 { 312 const char *str = ctf_strraw (fp, name); 313 314 if (type == 0) 315 return EINVAL; 316 317 if (str == NULL 318 && CTF_NAME_STID (name) == CTF_STRTAB_1 319 && fp->ctf_syn_ext_strtab == NULL 320 && fp->ctf_str[CTF_NAME_STID (name)].cts_strs == NULL) 321 return ECTF_STRTAB; 322 323 if (str == NULL) 324 return ECTF_BADNAME; 325 326 if (str[0] == '\0') 327 return 0; /* Just ignore empty strings on behalf of caller. */ 328 329 if (ctf_hashtab_insert ((struct htab *) hp, (char *) str, 330 (void *) (ptrdiff_t) type, NULL, NULL) != NULL) 331 return 0; 332 return errno; 333 } 334 335 /* if the key is already in the hash, override the previous definition with 336 this new official definition. If the key is not present, then call 337 ctf_hash_insert_type() and hash it in. */ 338 int 339 ctf_hash_define_type (ctf_hash_t *hp, ctf_file_t *fp, uint32_t type, 340 uint32_t name) 341 { 342 /* This matches the semantics of ctf_hash_insert_type() in this 343 implementation anyway. */ 344 345 return ctf_hash_insert_type (hp, fp, type, name); 346 } 347 348 ctf_id_t 349 ctf_hash_lookup_type (ctf_hash_t *hp, ctf_file_t *fp __attribute__ ((__unused__)), 350 const char *key) 351 { 352 ctf_helem_t **slot; 353 354 slot = ctf_hashtab_lookup ((struct htab *) hp, key, NO_INSERT); 355 356 if (slot) 357 return (ctf_id_t) ((*slot)->value); 358 359 return 0; 360 } 361 362 void 363 ctf_hash_destroy (ctf_hash_t *hp) 364 { 365 if (hp != NULL) 366 htab_delete ((struct htab *) hp); 367 } 368