libctf/ctf-hash.c

   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 /* 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 {
 157   ctf_helem_t **slot;
 158
 159   slot = ctf_hashtab_lookup (htab, key, INSERT);
 160
 161   if (!slot)
 162     {
 163       errno = -ENOMEM;
 164       return NULL;
 165     }
 166
 167   if (!*slot)
 168     {
 169       *slot = malloc (sizeof (ctf_helem_t));
 170       if (!*slot)
 171         return NULL;
 172       (*slot)->key = key;
 173     }
 174   (*slot)->value = value;
 175   return *slot;
 176 }
 177
 178 int
 179 ctf_dynhash_insert (ctf_dynhash_t *hp, void *key, void *value)
 180 {
 181   ctf_helem_t *slot;
 182
 183   slot = ctf_hashtab_insert (hp->htab, key, value);
 184
 185   if (!slot)
 186     return errno;
 187
 188   /* We need to keep the key_free and value_free around in each item because the
 189      del function has no visibility into the hash as a whole, only into the
 190      individual items.  */
 191
 192   slot->key_free = hp->key_free;
 193   slot->value_free = hp->value_free;
 194
 195   return 0;
 196 }
 197
 198 void
 199 ctf_dynhash_remove (ctf_dynhash_t *hp, const void *key)
 200 {
 201   ctf_helem_t hep = { (void *) key, NULL, NULL, NULL };
 202   htab_remove_elt (hp->htab, &hep);
 203 }
 204
 205 void
 206 ctf_dynhash_empty (ctf_dynhash_t *hp)
 207 {
 208   htab_empty (hp->htab);
 209 }
 210
 211 void *
 212 ctf_dynhash_lookup (ctf_dynhash_t *hp, const void *key)
 213 {
 214   ctf_helem_t **slot;
 215
 216   slot = ctf_hashtab_lookup (hp->htab, key, NO_INSERT);
 217
 218   if (slot)
 219     return (*slot)->value;
 220
 221   return NULL;
 222 }
 223
 224 typedef struct ctf_traverse_cb_arg
 225 {
 226   ctf_hash_iter_f fun;
 227   void *arg;
 228 } ctf_traverse_cb_arg_t;
 229
 230 static int
 231 ctf_hashtab_traverse (void **slot, void *arg_)
 232 {
 233   ctf_helem_t *helem = *((ctf_helem_t **) slot);
 234   ctf_traverse_cb_arg_t *arg = (ctf_traverse_cb_arg_t *) arg_;
 235
 236   arg->fun (helem->key, helem->value, arg->arg);
 237   return 1;
 238 }
 239
 240 void
 241 ctf_dynhash_iter (ctf_dynhash_t *hp, ctf_hash_iter_f fun, void *arg_)
 242 {
 243   ctf_traverse_cb_arg_t arg = { fun, arg_ };
 244   htab_traverse (hp->htab, ctf_hashtab_traverse, &arg);
 245 }
 246
 247 typedef struct ctf_traverse_remove_cb_arg
 248 {
 249   struct htab *htab;
 250   ctf_hash_iter_remove_f fun;
 251   void *arg;
 252 } ctf_traverse_remove_cb_arg_t;
 253
 254 static int
 255 ctf_hashtab_traverse_remove (void **slot, void *arg_)
 256 {
 257   ctf_helem_t *helem = *((ctf_helem_t **) slot);
 258   ctf_traverse_remove_cb_arg_t *arg = (ctf_traverse_remove_cb_arg_t *) arg_;
 259
 260   if (arg->fun (helem->key, helem->value, arg->arg))
 261     htab_clear_slot (arg->htab, slot);
 262   return 1;
 263 }
 264
 265 void
 266 ctf_dynhash_iter_remove (ctf_dynhash_t *hp, ctf_hash_iter_remove_f fun,
 267                          void *arg_)
 268 {
 269   ctf_traverse_remove_cb_arg_t arg = { hp->htab, fun, arg_ };
 270   htab_traverse (hp->htab, ctf_hashtab_traverse_remove, &arg);
 271 }
 272
 273 void
 274 ctf_dynhash_destroy (ctf_dynhash_t *hp)
 275 {
 276   if (hp != NULL)
 277     htab_delete (hp->htab);
 278   free (hp);
 279 }
 280
 281 /* ctf_hash, used for fixed-size maps from const char * -> ctf_id_t without
 282    removal.  This is a straight cast of a hashtab.  */
 283
 284 ctf_hash_t *
 285 ctf_hash_create (unsigned long nelems, ctf_hash_fun hash_fun,
 286                  ctf_hash_eq_fun eq_fun)
 287 {
 288   return (ctf_hash_t *) htab_create_alloc (nelems, (htab_hash) hash_fun,
 289                                            eq_fun, free, xcalloc, free);
 290 }
 291
 292 uint32_t
 293 ctf_hash_size (const ctf_hash_t *hp)
 294 {
 295   return htab_elements ((struct htab *) hp);
 296 }
 297
 298 int
 299 ctf_hash_insert_type (ctf_hash_t *hp, ctf_file_t *fp, uint32_t type,
 300                       uint32_t name)
 301 {
 302   const char *str = ctf_strraw (fp, name);
 303
 304   if (type == 0)
 305     return EINVAL;
 306
 307   if (str == NULL
 308       && CTF_NAME_STID (name) == CTF_STRTAB_1
 309       && fp->ctf_syn_ext_strtab == NULL
 310       && fp->ctf_str[CTF_NAME_STID (name)].cts_strs == NULL)
 311     return ECTF_STRTAB;
 312
 313   if (str == NULL)
 314     return ECTF_BADNAME;
 315
 316   if (str[0] == '\0')
 317     return 0;              /* Just ignore empty strings on behalf of caller.  */
 318
 319   if (ctf_hashtab_insert ((struct htab *) hp, (char *) str,
 320                           (void *) (ptrdiff_t) type) != NULL)
 321     return 0;
 322   return errno;
 323 }
 324
 325 /* if the key is already in the hash, override the previous definition with
 326    this new official definition. If the key is not present, then call
 327    ctf_hash_insert_type() and hash it in.  */
 328 int
 329 ctf_hash_define_type (ctf_hash_t *hp, ctf_file_t *fp, uint32_t type,
 330                       uint32_t name)
 331 {
 332   /* This matches the semantics of ctf_hash_insert_type() in this
 333      implementation anyway.  */
 334
 335   return ctf_hash_insert_type (hp, fp, type, name);
 336 }
 337
 338 ctf_id_t
 339 ctf_hash_lookup_type (ctf_hash_t *hp, ctf_file_t *fp __attribute__ ((__unused__)),
 340                       const char *key)
 341 {
 342   ctf_helem_t **slot;
 343
 344   slot = ctf_hashtab_lookup ((struct htab *) hp, key, NO_INSERT);
 345
 346   if (slot)
 347     return (ctf_id_t) ((*slot)->value);
 348
 349   return 0;
 350 }
 351
 352 void
 353 ctf_hash_destroy (ctf_hash_t *hp)
 354 {
 355   if (hp != NULL)
 356     htab_delete ((struct htab *) hp);
 357 }