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