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 /* 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   ctf_helem_t hep = { (void *) key, NULL, NULL, NULL };
 180   htab_remove_elt (hp->htab, &hep);
 181 }
 182
 183 void *
 184 ctf_dynhash_lookup (ctf_dynhash_t *hp, const void *key)
 185 {
 186   ctf_helem_t **slot;
 187
 188   slot = ctf_hashtab_lookup (hp->htab, key, NO_INSERT);
 189
 190   if (slot)
 191     return (*slot)->value;
 192
 193   return NULL;
 194 }
 195
 196 typedef struct ctf_traverse_cb_arg
 197 {
 198   ctf_hash_iter_f fun;
 199   void *arg;
 200 } ctf_traverse_cb_arg_t;
 201
 202 static int
 203 ctf_hashtab_traverse (void **slot, void *arg_)
 204 {
 205   ctf_helem_t *helem = *((ctf_helem_t **) slot);
 206   ctf_traverse_cb_arg_t *arg = (ctf_traverse_cb_arg_t *) arg_;
 207
 208   arg->fun (helem->key, helem->value, arg->arg);
 209   return 1;
 210 }
 211
 212 void
 213 ctf_dynhash_iter (ctf_dynhash_t *hp, ctf_hash_iter_f fun, void *arg_)
 214 {
 215   ctf_traverse_cb_arg_t arg = { fun, arg_ };
 216   htab_traverse (hp->htab, ctf_hashtab_traverse, &arg);
 217 }
 218
 219 typedef struct ctf_traverse_remove_cb_arg
 220 {
 221   struct htab *htab;
 222   ctf_hash_iter_remove_f fun;
 223   void *arg;
 224 } ctf_traverse_remove_cb_arg_t;
 225
 226 static int
 227 ctf_hashtab_traverse_remove (void **slot, void *arg_)
 228 {
 229   ctf_helem_t *helem = *((ctf_helem_t **) slot);
 230   ctf_traverse_remove_cb_arg_t *arg = (ctf_traverse_remove_cb_arg_t *) arg_;
 231
 232   if (arg->fun (helem->key, helem->value, arg->arg))
 233     htab_clear_slot (arg->htab, slot);
 234   return 1;
 235 }
 236
 237 void
 238 ctf_dynhash_iter_remove (ctf_dynhash_t *hp, ctf_hash_iter_remove_f fun,
 239                          void *arg_)
 240 {
 241   ctf_traverse_remove_cb_arg_t arg = { hp->htab, fun, arg_ };
 242   htab_traverse (hp->htab, ctf_hashtab_traverse_remove, &arg);
 243 }
 244
 245 void
 246 ctf_dynhash_destroy (ctf_dynhash_t *hp)
 247 {
 248   if (hp != NULL)
 249     htab_delete (hp->htab);
 250   free (hp);
 251 }
 252
 253 /* ctf_hash, used for fixed-size maps from const char * -> ctf_id_t without
 254    removal.  This is a straight cast of a hashtab.  */
 255
 256 ctf_hash_t *
 257 ctf_hash_create (unsigned long nelems, ctf_hash_fun hash_fun,
 258                  ctf_hash_eq_fun eq_fun)
 259 {
 260   return (ctf_hash_t *) htab_create_alloc (nelems, (htab_hash) hash_fun,
 261                                            eq_fun, free, xcalloc, free);
 262 }
 263
 264 uint32_t
 265 ctf_hash_size (const ctf_hash_t *hp)
 266 {
 267   return htab_elements ((struct htab *) hp);
 268 }
 269
 270 int
 271 ctf_hash_insert_type (ctf_hash_t *hp, ctf_file_t *fp, uint32_t type,
 272                       uint32_t name)
 273 {
 274   ctf_strs_t *ctsp = &fp->ctf_str[CTF_NAME_STID (name)];
 275   const char *str = ctsp->cts_strs + CTF_NAME_OFFSET (name);
 276
 277   if (type == 0)
 278     return EINVAL;
 279
 280   if (ctsp->cts_strs == NULL)
 281     return ECTF_STRTAB;
 282
 283   if (ctsp->cts_len <= CTF_NAME_OFFSET (name))
 284     return ECTF_BADNAME;
 285
 286   if (str[0] == '\0')
 287     return 0;              /* Just ignore empty strings on behalf of caller.  */
 288
 289   if (ctf_hashtab_insert ((struct htab *) hp, (char *) str,
 290                           (void *) (ptrdiff_t) type) != NULL)
 291     return 0;
 292   return errno;
 293 }
 294
 295 /* if the key is already in the hash, override the previous definition with
 296    this new official definition. If the key is not present, then call
 297    ctf_hash_insert_type() and hash it in.  */
 298 int
 299 ctf_hash_define_type (ctf_hash_t *hp, ctf_file_t *fp, uint32_t type,
 300                       uint32_t name)
 301 {
 302   /* This matches the semantics of ctf_hash_insert_type() in this
 303      implementation anyway.  */
 304
 305   return ctf_hash_insert_type (hp, fp, type, name);
 306 }
 307
 308 ctf_id_t
 309 ctf_hash_lookup_type (ctf_hash_t *hp, ctf_file_t *fp __attribute__ ((__unused__)),
 310                       const char *key)
 311 {
 312   ctf_helem_t **slot;
 313
 314   slot = ctf_hashtab_lookup ((struct htab *) hp, key, NO_INSERT);
 315
 316   if (slot)
 317     return (ctf_id_t) ((*slot)->value);
 318
 319   return 0;
 320 }
 321
 322 void
 323 ctf_hash_destroy (ctf_hash_t *hp)
 324 {
 325   if (hp != NULL)
 326     htab_delete ((struct htab *) hp);
 327 }