libctf/ctf-hash.c

   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 }