contrib/bind9/lib/isc/symtab.c

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