external/bsd/bind/dist/lib/isc/symtab.c

   1 /*      $NetBSD: symtab.c,v 1.6 2014/12/10 04:37:59 christos Exp $      */
   2
   3 /*
   4  * Copyright (C) 2004, 2005, 2007, 2011-2013  Internet Systems Consortium, Inc. ("ISC")
   5  * Copyright (C) 1996-2001  Internet Software Consortium.
   6  *
   7  * Permission to use, copy, modify, and/or distribute this software for any
   8  * purpose with or without fee is hereby granted, provided that the above
   9  * copyright notice and this permission notice appear in all copies.
  10  *
  11  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
  12  * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
  13  * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
  14  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
  15  * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
  16  * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  17  * PERFORMANCE OF THIS SOFTWARE.
  18  */
  19
  20 /* Id */
  21
  22 /*! \file */
  23
  24 #include <config.h>
  25
  26 #include <ctype.h>
  27
  28 #include <isc/magic.h>
  29 #include <isc/mem.h>
  30 #include <isc/string.h>
  31 #include <isc/symtab.h>
  32 #include <isc/util.h>
  33
  34 typedef struct elt {
  35         char *                          key;
  36         unsigned int                    type;
  37         isc_symvalue_t                  value;
  38         LINK(struct elt)                link;
  39 } elt_t;
  40
  41 typedef LIST(elt_t)                     eltlist_t;
  42
  43 #define SYMTAB_MAGIC                    ISC_MAGIC('S', 'y', 'm', 'T')
  44 #define VALID_SYMTAB(st)                ISC_MAGIC_VALID(st, SYMTAB_MAGIC)
  45
  46 struct isc_symtab {
  47         /* Unlocked. */
  48         unsigned int                    magic;
  49         isc_mem_t *                     mctx;
  50         unsigned int                    size;
  51         unsigned int                    count;
  52         unsigned int                    maxload;
  53         eltlist_t *                     table;
  54         isc_symtabaction_t              undefine_action;
  55         void *                          undefine_arg;
  56         isc_boolean_t                   case_sensitive;
  57 };
  58
  59 isc_result_t
  60 isc_symtab_create(isc_mem_t *mctx, unsigned int size,
  61                   isc_symtabaction_t undefine_action,
  62                   void *undefine_arg,
  63                   isc_boolean_t case_sensitive,
  64                   isc_symtab_t **symtabp)
  65 {
  66         isc_symtab_t *symtab;
  67         unsigned int i;
  68
  69         REQUIRE(mctx != NULL);
  70         REQUIRE(symtabp != NULL && *symtabp == NULL);
  71         REQUIRE(size > 0);      /* Should be prime. */
  72
  73         symtab = (isc_symtab_t *)isc_mem_get(mctx, sizeof(*symtab));
  74         if (symtab == NULL)
  75                 return (ISC_R_NOMEMORY);
  76
  77         symtab->mctx = NULL;
  78         isc_mem_attach(mctx, &symtab->mctx);
  79         symtab->table = (eltlist_t *)isc_mem_get(mctx,
  80                                                  size * sizeof(eltlist_t));
  81         if (symtab->table == NULL) {
  82                 isc_mem_putanddetach(&symtab->mctx, symtab, sizeof(*symtab));
  83                 return (ISC_R_NOMEMORY);
  84         }
  85         for (i = 0; i < size; i++)
  86                 INIT_LIST(symtab->table[i]);
  87         symtab->size = size;
  88         symtab->count = 0;
  89         symtab->maxload = size * 3 / 4;
  90         symtab->undefine_action = undefine_action;
  91         symtab->undefine_arg = undefine_arg;
  92         symtab->case_sensitive = case_sensitive;
  93         symtab->magic = SYMTAB_MAGIC;
  94
  95         *symtabp = symtab;
  96
  97         return (ISC_R_SUCCESS);
  98 }
  99
 100 void
 101 isc_symtab_destroy(isc_symtab_t **symtabp) {
 102         isc_symtab_t *symtab;
 103         unsigned int i;
 104         elt_t *elt, *nelt;
 105
 106         REQUIRE(symtabp != NULL);
 107         symtab = *symtabp;
 108         REQUIRE(VALID_SYMTAB(symtab));
 109
 110         for (i = 0; i < symtab->size; i++) {
 111                 for (elt = HEAD(symtab->table[i]); elt != NULL; elt = nelt) {
 112                         nelt = NEXT(elt, link);
 113                         if (symtab->undefine_action != NULL)
 114                                (symtab->undefine_action)(elt->key,
 115                                                          elt->type,
 116                                                          elt->value,
 117                                                          symtab->undefine_arg);
 118                         isc_mem_put(symtab->mctx, elt, sizeof(*elt));
 119                 }
 120         }
 121         isc_mem_put(symtab->mctx, symtab->table,
 122                     symtab->size * sizeof(eltlist_t));
 123         symtab->magic = 0;
 124         isc_mem_putanddetach(&symtab->mctx, symtab, sizeof(*symtab));
 125
 126         *symtabp = NULL;
 127 }
 128
 129 static inline unsigned int
 130 hash(const char *key, isc_boolean_t case_sensitive) {
 131         const char *s;
 132         unsigned int h = 0;
 133         int c;
 134
 135         /*
 136          * This hash function is similar to the one Ousterhout
 137          * uses in Tcl.
 138          */
 139
 140         if (case_sensitive) {
 141                 for (s = key; *s != '\0'; s++) {
 142                         h += (h << 3) + *s;
 143                 }
 144         } else {
 145                 for (s = key; *s != '\0'; s++) {
 146                         c = *s;
 147                         c = tolower((unsigned char)c);
 148                         h += (h << 3) + c;
 149                 }
 150         }
 151
 152         return (h);
 153 }
 154
 155 #define FIND(s, k, t, b, e) \
 156         b = hash((k), (s)->case_sensitive) % (s)->size; \
 157         if ((s)->case_sensitive) { \
 158                 for (e = HEAD((s)->table[b]); e != NULL; e = NEXT(e, link)) { \
 159                         if (((t) == 0 || e->type == (t)) && \
 160                             strcmp(e->key, (k)) == 0) \
 161                                 break; \
 162                 } \
 163         } else { \
 164                 for (e = HEAD((s)->table[b]); e != NULL; e = NEXT(e, link)) { \
 165                         if (((t) == 0 || e->type == (t)) && \
 166                             strcasecmp(e->key, (k)) == 0) \
 167                                 break; \
 168                 } \
 169         }
 170
 171 isc_result_t
 172 isc_symtab_lookup(isc_symtab_t *symtab, const char *key, unsigned int type,
 173                   isc_symvalue_t *value)
 174 {
 175         unsigned int bucket;
 176         elt_t *elt;
 177
 178         REQUIRE(VALID_SYMTAB(symtab));
 179         REQUIRE(key != NULL);
 180
 181         FIND(symtab, key, type, bucket, elt);
 182
 183         if (elt == NULL)
 184                 return (ISC_R_NOTFOUND);
 185
 186         if (value != NULL)
 187                 *value = elt->value;
 188
 189         return (ISC_R_SUCCESS);
 190 }
 191
 192 static void
 193 grow_table(isc_symtab_t *symtab) {
 194         eltlist_t *newtable;
 195         unsigned int i, newsize, newmax;
 196
 197         REQUIRE(symtab != NULL);
 198
 199         newsize = symtab->size * 2;
 200         newmax = newsize * 3 / 4;
 201         INSIST(newsize > 0U && newmax > 0U);
 202
 203         newtable = isc_mem_get(symtab->mctx, newsize * sizeof(eltlist_t));
 204         if (newtable == NULL)
 205                 return;
 206
 207         for (i = 0; i < newsize; i++)
 208                 INIT_LIST(newtable[i]);
 209
 210         for (i = 0; i < symtab->size; i++) {
 211                 elt_t *elt, *nelt;
 212
 213                 for (elt = HEAD(symtab->table[i]); elt != NULL; elt = nelt) {
 214                         unsigned int hv;
 215
 216                         nelt = NEXT(elt, link);
 217
 218                         UNLINK(symtab->table[i], elt, link);
 219                         hv = hash(elt->key, symtab->case_sensitive);
 220                         APPEND(newtable[hv % newsize], elt, link);
 221                 }
 222         }
 223
 224         isc_mem_put(symtab->mctx, symtab->table,
 225                     symtab->size * sizeof(eltlist_t));
 226
 227         symtab->table = newtable;
 228         symtab->size = newsize;
 229         symtab->maxload = newmax;
 230 }
 231
 232 isc_result_t
 233 isc_symtab_define(isc_symtab_t *symtab, const char *key, unsigned int type,
 234                   isc_symvalue_t value, isc_symexists_t exists_policy)
 235 {
 236         unsigned int bucket;
 237         elt_t *elt;
 238
 239         REQUIRE(VALID_SYMTAB(symtab));
 240         REQUIRE(key != NULL);
 241         REQUIRE(type != 0);
 242
 243         FIND(symtab, key, type, bucket, elt);
 244
 245         if (exists_policy != isc_symexists_add && elt != NULL) {
 246                 if (exists_policy == isc_symexists_reject)
 247                         return (ISC_R_EXISTS);
 248                 INSIST(exists_policy == isc_symexists_replace);
 249                 UNLINK(symtab->table[bucket], elt, link);
 250                 if (symtab->undefine_action != NULL)
 251                         (symtab->undefine_action)(elt->key, elt->type,
 252                                                   elt->value,
 253                                                   symtab->undefine_arg);
 254         } else {
 255                 elt = (elt_t *)isc_mem_get(symtab->mctx, sizeof(*elt));
 256                 if (elt == NULL)
 257                         return (ISC_R_NOMEMORY);
 258                 ISC_LINK_INIT(elt, link);
 259                 symtab->count++;
 260         }
 261
 262         /*
 263          * Though the "key" can be const coming in, it is not stored as const
 264          * so that the calling program can easily have writable access to
 265          * it in its undefine_action function.  In the event that it *was*
 266          * truly const coming in and then the caller modified it anyway ...
 267          * well, don't do that!
 268          */
 269         DE_CONST(key, elt->key);
 270         elt->type = type;
 271         elt->value = value;
 272
 273         /*
 274          * We prepend so that the most recent definition will be found.
 275          */
 276         PREPEND(symtab->table[bucket], elt, link);
 277
 278         if (symtab->count > symtab->maxload)
 279                 grow_table(symtab);
 280
 281         return (ISC_R_SUCCESS);
 282 }
 283
 284 isc_result_t
 285 isc_symtab_undefine(isc_symtab_t *symtab, const char *key, unsigned int type) {
 286         unsigned int bucket;
 287         elt_t *elt;
 288
 289         REQUIRE(VALID_SYMTAB(symtab));
 290         REQUIRE(key != NULL);
 291
 292         FIND(symtab, key, type, bucket, elt);
 293
 294         if (elt == NULL)
 295                 return (ISC_R_NOTFOUND);
 296
 297         if (symtab->undefine_action != NULL)
 298                 (symtab->undefine_action)(elt->key, elt->type,
 299                                           elt->value, symtab->undefine_arg);
 300         UNLINK(symtab->table[bucket], elt, link);
 301         isc_mem_put(symtab->mctx, elt, sizeof(*elt));
 302         symtab->count--;
 303
 304         return (ISC_R_SUCCESS);
 305 }
 306
 307 unsigned int
 308 isc_symtab_count(isc_symtab_t *symtab) {
 309         REQUIRE(VALID_SYMTAB(symtab));
 310         return (symtab->count);
 311 }