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 void
 197 ctf_dynhash_destroy (ctf_dynhash_t *hp)
 198 {
 199   if (hp != NULL)
 200     htab_delete (hp->htab);
 201   free (hp);
 202 }
 203
 204 /* ctf_hash, used for fixed-size maps from const char * -> ctf_id_t without
 205    removal.  This is a straight cast of a hashtab.  */
 206
 207 ctf_hash_t *
 208 ctf_hash_create (unsigned long nelems, ctf_hash_fun hash_fun,
 209                  ctf_hash_eq_fun eq_fun)
 210 {
 211   return (ctf_hash_t *) htab_create_alloc (nelems, (htab_hash) hash_fun,
 212                                            eq_fun, free, xcalloc, free);
 213 }
 214
 215 uint32_t
 216 ctf_hash_size (const ctf_hash_t *hp)
 217 {
 218   return htab_elements ((struct htab *) hp);
 219 }
 220
 221 int
 222 ctf_hash_insert_type (ctf_hash_t *hp, ctf_file_t *fp, uint32_t type,
 223                       uint32_t name)
 224 {
 225   ctf_strs_t *ctsp = &fp->ctf_str[CTF_NAME_STID (name)];
 226   const char *str = ctsp->cts_strs + CTF_NAME_OFFSET (name);
 227
 228   if (type == 0)
 229     return EINVAL;
 230
 231   if (ctsp->cts_strs == NULL)
 232     return ECTF_STRTAB;
 233
 234   if (ctsp->cts_len <= CTF_NAME_OFFSET (name))
 235     return ECTF_BADNAME;
 236
 237   if (str[0] == '\0')
 238     return 0;              /* Just ignore empty strings on behalf of caller.  */
 239
 240   if (ctf_hashtab_insert ((struct htab *) hp, (char *) str,
 241                           (void *) (ptrdiff_t) type) != NULL)
 242     return 0;
 243   return errno;
 244 }
 245
 246 /* if the key is already in the hash, override the previous definition with
 247    this new official definition. If the key is not present, then call
 248    ctf_hash_insert_type() and hash it in.  */
 249 int
 250 ctf_hash_define_type (ctf_hash_t *hp, ctf_file_t *fp, uint32_t type,
 251                       uint32_t name)
 252 {
 253   /* This matches the semantics of ctf_hash_insert_type() in this
 254      implementation anyway.  */
 255
 256   return ctf_hash_insert_type (hp, fp, type, name);
 257 }
 258
 259 ctf_id_t
 260 ctf_hash_lookup_type (ctf_hash_t *hp, ctf_file_t *fp __attribute__ ((__unused__)),
 261                       const char *key)
 262 {
 263   ctf_helem_t **slot;
 264
 265   slot = ctf_hashtab_lookup ((struct htab *) hp, key, NO_INSERT);
 266
 267   if (slot)
 268     return (ctf_id_t) ((*slot)->value);
 269
 270   return 0;
 271 }
 272
 273 void
 274 ctf_hash_destroy (ctf_hash_t *hp)
 275 {
 276   if (hp != NULL)
 277     htab_delete ((struct htab *) hp);
 278 }