contrib/bind-9.3/lib/isc/symtab.c

   1 /*
   2  * Copyright (C) 2004  Internet Systems Consortium, Inc. ("ISC")
   3  * Copyright (C) 1996-2001  Internet Software Consortium.
   4  *
   5  * Permission to use, copy, modify, and 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: symtab.c,v 1.24.12.3 2004/03/08 09:04:50 marka Exp $ */
  19
  20 #include <config.h>
  21
  22 #include <ctype.h>
  23
  24 #include <isc/magic.h>
  25 #include <isc/mem.h>
  26 #include <isc/string.h>
  27 #include <isc/symtab.h>
  28 #include <isc/util.h>
  29
  30 typedef struct elt {
  31         char *                          key;
  32         unsigned int                    type;
  33         isc_symvalue_t                  value;
  34         LINK(struct elt)                link;
  35 } elt_t;
  36
  37 typedef LIST(elt_t)                     eltlist_t;
  38
  39 #define SYMTAB_MAGIC                    ISC_MAGIC('S', 'y', 'm', 'T')
  40 #define VALID_SYMTAB(st)                ISC_MAGIC_VALID(st, SYMTAB_MAGIC)
  41
  42 struct isc_symtab {
  43         /* Unlocked. */
  44         unsigned int                    magic;
  45         isc_mem_t *                     mctx;
  46         unsigned int                    size;
  47         eltlist_t *                     table;
  48         isc_symtabaction_t              undefine_action;
  49         void *                          undefine_arg;
  50         isc_boolean_t                   case_sensitive;
  51 };
  52
  53 isc_result_t
  54 isc_symtab_create(isc_mem_t *mctx, unsigned int size,
  55                   isc_symtabaction_t undefine_action,
  56                   void *undefine_arg,
  57                   isc_boolean_t case_sensitive,
  58                   isc_symtab_t **symtabp)
  59 {
  60         isc_symtab_t *symtab;
  61         unsigned int i;
  62
  63         REQUIRE(mctx != NULL);
  64         REQUIRE(symtabp != NULL && *symtabp == NULL);
  65         REQUIRE(size > 0);      /* Should be prime. */
  66
  67         symtab = (isc_symtab_t *)isc_mem_get(mctx, sizeof(*symtab));
  68         if (symtab == NULL)
  69                 return (ISC_R_NOMEMORY);
  70         symtab->table = (eltlist_t *)isc_mem_get(mctx,
  71                                                  size * sizeof(eltlist_t));
  72         if (symtab->table == NULL) {
  73                 isc_mem_put(mctx, symtab, sizeof(*symtab));
  74                 return (ISC_R_NOMEMORY);
  75         }
  76         for (i = 0; i < size; i++)
  77                 INIT_LIST(symtab->table[i]);
  78         symtab->mctx = mctx;
  79         symtab->size = size;
  80         symtab->undefine_action = undefine_action;
  81         symtab->undefine_arg = undefine_arg;
  82         symtab->case_sensitive = case_sensitive;
  83         symtab->magic = SYMTAB_MAGIC;
  84
  85         *symtabp = symtab;
  86
  87         return (ISC_R_SUCCESS);
  88 }
  89
  90 void
  91 isc_symtab_destroy(isc_symtab_t **symtabp) {
  92         isc_symtab_t *symtab;
  93         unsigned int i;
  94         elt_t *elt, *nelt;
  95
  96         REQUIRE(symtabp != NULL);
  97         symtab = *symtabp;
  98         REQUIRE(VALID_SYMTAB(symtab));
  99
 100         for (i = 0; i < symtab->size; i++) {
 101                 for (elt = HEAD(symtab->table[i]); elt != NULL; elt = nelt) {
 102                         nelt = NEXT(elt, link);
 103                         if (symtab->undefine_action != NULL)
 104                                (symtab->undefine_action)(elt->key,
 105                                                          elt->type,
 106                                                          elt->value,
 107                                                          symtab->undefine_arg);
 108                         isc_mem_put(symtab->mctx, elt, sizeof(*elt));
 109                 }
 110         }
 111         isc_mem_put(symtab->mctx, symtab->table,
 112                     symtab->size * sizeof(eltlist_t));
 113         symtab->magic = 0;
 114         isc_mem_put(symtab->mctx, symtab, sizeof(*symtab));
 115
 116         *symtabp = NULL;
 117 }
 118
 119 static inline unsigned int
 120 hash(const char *key, isc_boolean_t case_sensitive) {
 121         const char *s;
 122         unsigned int h = 0;
 123         int c;
 124
 125         /*
 126          * This hash function is similar to the one Ousterhout
 127          * uses in Tcl.
 128          */
 129
 130         if (case_sensitive) {
 131                 for (s = key; *s != '\0'; s++) {
 132                         h += (h << 3) + *s;
 133                 }
 134         } else {
 135                 for (s = key; *s != '\0'; s++) {
 136                         c = *s;
 137                         c = tolower((unsigned char)c);
 138                         h += (h << 3) + c;
 139                 }
 140         }
 141
 142         return (h);
 143 }
 144
 145 #define FIND(s, k, t, b, e) \
 146         b = hash((k), (s)->case_sensitive) % (s)->size; \
 147         if ((s)->case_sensitive) { \
 148                 for (e = HEAD((s)->table[b]); e != NULL; e = NEXT(e, link)) { \
 149                         if (((t) == 0 || e->type == (t)) && \
 150                             strcmp(e->key, (k)) == 0) \
 151                                 break; \
 152                 } \
 153         } else { \
 154                 for (e = HEAD((s)->table[b]); e != NULL; e = NEXT(e, link)) { \
 155                         if (((t) == 0 || e->type == (t)) && \
 156                             strcasecmp(e->key, (k)) == 0) \
 157                                 break; \
 158                 } \
 159         }
 160
 161 isc_result_t
 162 isc_symtab_lookup(isc_symtab_t *symtab, const char *key, unsigned int type,
 163                   isc_symvalue_t *value)
 164 {
 165         unsigned int bucket;
 166         elt_t *elt;
 167
 168         REQUIRE(VALID_SYMTAB(symtab));
 169         REQUIRE(key != NULL);
 170
 171         FIND(symtab, key, type, bucket, elt);
 172
 173         if (elt == NULL)
 174                 return (ISC_R_NOTFOUND);
 175
 176         if (value != NULL)
 177                 *value = elt->value;
 178
 179         return (ISC_R_SUCCESS);
 180 }
 181
 182 isc_result_t
 183 isc_symtab_define(isc_symtab_t *symtab, const char *key, unsigned int type,
 184                   isc_symvalue_t value, isc_symexists_t exists_policy)
 185 {
 186         unsigned int bucket;
 187         elt_t *elt;
 188
 189         REQUIRE(VALID_SYMTAB(symtab));
 190         REQUIRE(key != NULL);
 191         REQUIRE(type != 0);
 192
 193         FIND(symtab, key, type, bucket, elt);
 194
 195         if (exists_policy != isc_symexists_add && elt != NULL) {
 196                 if (exists_policy == isc_symexists_reject)
 197                         return (ISC_R_EXISTS);
 198                 INSIST(exists_policy == isc_symexists_replace);
 199                 UNLINK(symtab->table[bucket], elt, link);
 200                 if (symtab->undefine_action != NULL)
 201                         (symtab->undefine_action)(elt->key, elt->type,
 202                                                   elt->value,
 203                                                   symtab->undefine_arg);
 204         } else {
 205                 elt = (elt_t *)isc_mem_get(symtab->mctx, sizeof(*elt));
 206                 if (elt == NULL)
 207                         return (ISC_R_NOMEMORY);
 208                 ISC_LINK_INIT(elt, link);
 209         }
 210
 211         /*
 212          * Though the "key" can be const coming in, it is not stored as const
 213          * so that the calling program can easily have writable access to
 214          * it in its undefine_action function.  In the event that it *was*
 215          * truly const coming in and then the caller modified it anyway ...
 216          * well, don't do that!
 217          */
 218         DE_CONST(key, elt->key);
 219         elt->type = type;
 220         elt->value = value;
 221
 222         /*
 223          * We prepend so that the most recent definition will be found.
 224          */
 225         PREPEND(symtab->table[bucket], elt, link);
 226
 227         return (ISC_R_SUCCESS);
 228 }
 229
 230 isc_result_t
 231 isc_symtab_undefine(isc_symtab_t *symtab, const char *key, unsigned int type) {
 232         unsigned int bucket;
 233         elt_t *elt;
 234
 235         REQUIRE(VALID_SYMTAB(symtab));
 236         REQUIRE(key != NULL);
 237
 238         FIND(symtab, key, type, bucket, elt);
 239
 240         if (elt == NULL)
 241                 return (ISC_R_NOTFOUND);
 242
 243         if (symtab->undefine_action != NULL)
 244                 (symtab->undefine_action)(elt->key, elt->type,
 245                                           elt->value, symtab->undefine_arg);
 246         UNLINK(symtab->table[bucket], elt, link);
 247         isc_mem_put(symtab->mctx, elt, sizeof(*elt));
 248
 249         return (ISC_R_SUCCESS);
 250 }