contrib/bind9/lib/isccc/symtab.c

   1 /*
   2  * Portions Copyright (C) 2004, 2005, 2007  Internet Systems Consortium, Inc. ("ISC")
   3  * Portions Copyright (C) 2001  Internet Software Consortium.
   4  * Portions Copyright (C) 2001  Nominum, Inc.
   5  *
   6  * Permission to use, copy, modify, and/or distribute this software for any
   7  * purpose with or without fee is hereby granted, provided that the above
   8  * copyright notice and this permission notice appear in all copies.
   9  *
  10  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC AND NOMINUM DISCLAIMS ALL
  11  * WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES
  12  * OF MERCHANTABILITY AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY
  13  * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  14  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  15  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  16  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  17  */
  18
  19 /* $Id: symtab.c,v 1.5.18.4 2007/09/13 23:46:26 tbox Exp $ */
  20
  21 /*! \file */
  22
  23 #include <config.h>
  24
  25 #include <ctype.h>
  26 #include <stdlib.h>
  27
  28 #include <isc/assertions.h>
  29 #include <isc/magic.h>
  30 #include <isc/string.h>
  31
  32 #include <isccc/result.h>
  33 #include <isccc/symtab.h>
  34 #include <isccc/util.h>
  35
  36 typedef struct elt {
  37         char *                          key;
  38         unsigned int                    type;
  39         isccc_symvalue_t                        value;
  40         ISC_LINK(struct elt)            link;
  41 } elt_t;
  42
  43 typedef ISC_LIST(elt_t)                 eltlist_t;
  44
  45 #define SYMTAB_MAGIC                    ISC_MAGIC('S', 'y', 'm', 'T')
  46 #define VALID_SYMTAB(st)                ISC_MAGIC_VALID(st, SYMTAB_MAGIC)
  47
  48 struct isccc_symtab {
  49         unsigned int                    magic;
  50         unsigned int                    size;
  51         eltlist_t *                     table;
  52         isccc_symtabundefaction_t               undefine_action;
  53         void *                          undefine_arg;
  54         isc_boolean_t                   case_sensitive;
  55 };
  56
  57 isc_result_t
  58 isccc_symtab_create(unsigned int size,
  59                   isccc_symtabundefaction_t undefine_action,
  60                   void *undefine_arg,
  61                   isc_boolean_t case_sensitive,
  62                   isccc_symtab_t **symtabp)
  63 {
  64         isccc_symtab_t *symtab;
  65         unsigned int i;
  66
  67         REQUIRE(symtabp != NULL && *symtabp == NULL);
  68         REQUIRE(size > 0);      /* Should be prime. */
  69
  70         symtab = malloc(sizeof(*symtab));
  71         if (symtab == NULL)
  72                 return (ISC_R_NOMEMORY);
  73         symtab->table = malloc(size * sizeof(eltlist_t));
  74         if (symtab->table == NULL) {
  75                 free(symtab);
  76                 return (ISC_R_NOMEMORY);
  77         }
  78         for (i = 0; i < size; i++)
  79                 ISC_LIST_INIT(symtab->table[i]);
  80         symtab->size = size;
  81         symtab->undefine_action = undefine_action;
  82         symtab->undefine_arg = undefine_arg;
  83         symtab->case_sensitive = case_sensitive;
  84         symtab->magic = SYMTAB_MAGIC;
  85
  86         *symtabp = symtab;
  87
  88         return (ISC_R_SUCCESS);
  89 }
  90
  91 static inline void
  92 free_elt(isccc_symtab_t *symtab, unsigned int bucket, elt_t *elt) {
  93         ISC_LIST_UNLINK(symtab->table[bucket], elt, link);
  94         if (symtab->undefine_action != NULL)
  95                 (symtab->undefine_action)(elt->key, elt->type, elt->value,
  96                                           symtab->undefine_arg);
  97         free(elt);
  98 }
  99
 100 void
 101 isccc_symtab_destroy(isccc_symtab_t **symtabp) {
 102         isccc_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 = ISC_LIST_HEAD(symtab->table[i]);
 112                      elt != NULL;
 113                      elt = nelt) {
 114                         nelt = ISC_LIST_NEXT(elt, link);
 115                         free_elt(symtab, i, elt);
 116                 }
 117         }
 118         free(symtab->table);
 119         symtab->magic = 0;
 120         free(symtab);
 121
 122         *symtabp = NULL;
 123 }
 124
 125 static inline unsigned int
 126 hash(const char *key, isc_boolean_t case_sensitive) {
 127         const char *s;
 128         unsigned int h = 0;
 129         unsigned int g;
 130         int c;
 131
 132         /*
 133          * P. J. Weinberger's hash function, adapted from p. 436 of
 134          * _Compilers: Principles, Techniques, and Tools_, Aho, Sethi
 135          * and Ullman, Addison-Wesley, 1986, ISBN 0-201-10088-6.
 136          */
 137
 138         if (case_sensitive) {
 139                 for (s = key; *s != '\0'; s++) {
 140                         h = ( h << 4 ) + *s;
 141                         if ((g = ( h & 0xf0000000 )) != 0) {
 142                                 h = h ^ (g >> 24);
 143                                 h = h ^ g;
 144                         }
 145                 }
 146         } else {
 147                 for (s = key; *s != '\0'; s++) {
 148                         c = *s;
 149                         c = tolower((unsigned char)c);
 150                         h = ( h << 4 ) + c;
 151                         if ((g = ( h & 0xf0000000 )) != 0) {
 152                                 h = h ^ (g >> 24);
 153                                 h = h ^ g;
 154                         }
 155                 }
 156         }
 157
 158         return (h);
 159 }
 160
 161 #define FIND(s, k, t, b, e) \
 162         b = hash((k), (s)->case_sensitive) % (s)->size; \
 163         if ((s)->case_sensitive) { \
 164                 for (e = ISC_LIST_HEAD((s)->table[b]); \
 165                      e != NULL; \
 166                      e = ISC_LIST_NEXT(e, link)) { \
 167                         if (((t) == 0 || e->type == (t)) && \
 168                             strcmp(e->key, (k)) == 0) \
 169                                 break; \
 170                 } \
 171         } else { \
 172                 for (e = ISC_LIST_HEAD((s)->table[b]); \
 173                      e != NULL; \
 174                      e = ISC_LIST_NEXT(e, link)) { \
 175                         if (((t) == 0 || e->type == (t)) && \
 176                             strcasecmp(e->key, (k)) == 0) \
 177                                 break; \
 178                 } \
 179         }
 180
 181 isc_result_t
 182 isccc_symtab_lookup(isccc_symtab_t *symtab, const char *key, unsigned int type,
 183                   isccc_symvalue_t *value)
 184 {
 185         unsigned int bucket;
 186         elt_t *elt;
 187
 188         REQUIRE(VALID_SYMTAB(symtab));
 189         REQUIRE(key != NULL);
 190
 191         FIND(symtab, key, type, bucket, elt);
 192
 193         if (elt == NULL)
 194                 return (ISC_R_NOTFOUND);
 195
 196         if (value != NULL)
 197                 *value = elt->value;
 198
 199         return (ISC_R_SUCCESS);
 200 }
 201
 202 isc_result_t
 203 isccc_symtab_define(isccc_symtab_t *symtab, char *key, unsigned int type,
 204                   isccc_symvalue_t value, isccc_symexists_t exists_policy)
 205 {
 206         unsigned int bucket;
 207         elt_t *elt;
 208
 209         REQUIRE(VALID_SYMTAB(symtab));
 210         REQUIRE(key != NULL);
 211         REQUIRE(type != 0);
 212
 213         FIND(symtab, key, type, bucket, elt);
 214
 215         if (exists_policy != isccc_symexists_add && elt != NULL) {
 216                 if (exists_policy == isccc_symexists_reject)
 217                         return (ISC_R_EXISTS);
 218                 INSIST(exists_policy == isccc_symexists_replace);
 219                 ISC_LIST_UNLINK(symtab->table[bucket], elt, link);
 220                 if (symtab->undefine_action != NULL)
 221                         (symtab->undefine_action)(elt->key, elt->type,
 222                                                   elt->value,
 223                                                   symtab->undefine_arg);
 224         } else {
 225                 elt = malloc(sizeof(*elt));
 226                 if (elt == NULL)
 227                         return (ISC_R_NOMEMORY);
 228                 ISC_LINK_INIT(elt, link);
 229         }
 230
 231         elt->key = key;
 232         elt->type = type;
 233         elt->value = value;
 234
 235         /*
 236          * We prepend so that the most recent definition will be found.
 237          */
 238         ISC_LIST_PREPEND(symtab->table[bucket], elt, link);
 239
 240         return (ISC_R_SUCCESS);
 241 }
 242
 243 isc_result_t
 244 isccc_symtab_undefine(isccc_symtab_t *symtab, const char *key, unsigned int type) {
 245         unsigned int bucket;
 246         elt_t *elt;
 247
 248         REQUIRE(VALID_SYMTAB(symtab));
 249         REQUIRE(key != NULL);
 250
 251         FIND(symtab, key, type, bucket, elt);
 252
 253         if (elt == NULL)
 254                 return (ISC_R_NOTFOUND);
 255
 256         free_elt(symtab, bucket, elt);
 257
 258         return (ISC_R_SUCCESS);
 259 }
 260
 261 void
 262 isccc_symtab_foreach(isccc_symtab_t *symtab, isccc_symtabforeachaction_t action,
 263                    void *arg)
 264 {
 265         unsigned int i;
 266         elt_t *elt, *nelt;
 267
 268         REQUIRE(VALID_SYMTAB(symtab));
 269         REQUIRE(action != NULL);
 270
 271         for (i = 0; i < symtab->size; i++) {
 272                 for (elt = ISC_LIST_HEAD(symtab->table[i]);
 273                      elt != NULL;
 274                      elt = nelt) {
 275                         nelt = ISC_LIST_NEXT(elt, link);
 276                         if ((action)(elt->key, elt->type, elt->value, arg))
 277                                 free_elt(symtab, i, elt);
 278                 }
 279         }
 280 }