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