contrib/bind-9.2.4rc7/lib/isccc/symtab.c

   1 /*
   2  * Portions Copyright (C) 2004  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 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.3.2.1 2004/03/09 06:12:26 marka Exp $ */
  20
  21 #include <config.h>
  22
  23 #include <ctype.h>
  24 #include <stdlib.h>
  25 #include <string.h>
  26
  27 #include <isc/assertions.h>
  28 #include <isc/magic.h>
  29
  30 #include <isccc/result.h>
  31 #include <isccc/symtab.h>
  32 #include <isccc/util.h>
  33
  34 typedef struct elt {
  35         char *                          key;
  36         unsigned int                    type;
  37         isccc_symvalue_t                        value;
  38         ISC_LINK(struct elt)            link;
  39 } elt_t;
  40
  41 typedef ISC_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 isccc_symtab {
  47         unsigned int                    magic;
  48         unsigned int                    size;
  49         eltlist_t *                     table;
  50         isccc_symtabundefaction_t               undefine_action;
  51         void *                          undefine_arg;
  52         isc_boolean_t                   case_sensitive;
  53 };
  54
  55 isc_result_t
  56 isccc_symtab_create(unsigned int size,
  57                   isccc_symtabundefaction_t undefine_action,
  58                   void *undefine_arg,
  59                   isc_boolean_t case_sensitive,
  60                   isccc_symtab_t **symtabp)
  61 {
  62         isccc_symtab_t *symtab;
  63         unsigned int i;
  64
  65         REQUIRE(symtabp != NULL && *symtabp == NULL);
  66         REQUIRE(size > 0);      /* Should be prime. */
  67
  68         symtab = malloc(sizeof *symtab);
  69         if (symtab == NULL)
  70                 return (ISC_R_NOMEMORY);
  71         symtab->table = malloc(size * sizeof (eltlist_t));
  72         if (symtab->table == NULL) {
  73                 free(symtab);
  74                 return (ISC_R_NOMEMORY);
  75         }
  76         for (i = 0; i < size; i++)
  77                 ISC_LIST_INIT(symtab->table[i]);
  78         symtab->size = size;
  79         symtab->undefine_action = undefine_action;
  80         symtab->undefine_arg = undefine_arg;
  81         symtab->case_sensitive = case_sensitive;
  82         symtab->magic = SYMTAB_MAGIC;
  83
  84         *symtabp = symtab;
  85
  86         return (ISC_R_SUCCESS);
  87 }
  88
  89 static inline void
  90 free_elt(isccc_symtab_t *symtab, unsigned int bucket, elt_t *elt) {
  91         ISC_LIST_UNLINK(symtab->table[bucket], elt, link);
  92         if (symtab->undefine_action != NULL)
  93                 (symtab->undefine_action)(elt->key, elt->type, elt->value,
  94                                           symtab->undefine_arg);
  95         free(elt);
  96 }
  97
  98 void
  99 isccc_symtab_destroy(isccc_symtab_t **symtabp) {
 100         isccc_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 = ISC_LIST_HEAD(symtab->table[i]);
 110                      elt != NULL;
 111                      elt = nelt) {
 112                         nelt = ISC_LIST_NEXT(elt, link);
 113                         free_elt(symtab, i, elt);
 114                 }
 115         }
 116         free(symtab->table);
 117         symtab->magic = 0;
 118         free(symtab);
 119
 120         *symtabp = NULL;
 121 }
 122
 123 static inline unsigned int
 124 hash(const char *key, isc_boolean_t case_sensitive) {
 125         const char *s;
 126         unsigned int h = 0;
 127         unsigned int g;
 128         int c;
 129
 130         /*
 131          * P. J. Weinberger's hash function, adapted from p. 436 of
 132          * _Compilers: Principles, Techniques, and Tools_, Aho, Sethi
 133          * and Ullman, Addison-Wesley, 1986, ISBN 0-201-10088-6.
 134          */
 135
 136         if (case_sensitive) {
 137                 for (s = key; *s != '\0'; s++) {
 138                         h = ( h << 4 ) + *s;
 139                         if ((g = ( h & 0xf0000000 )) != 0) {
 140                                 h = h ^ (g >> 24);
 141                                 h = h ^ g;
 142                         }
 143                 }
 144         } else {
 145                 for (s = key; *s != '\0'; s++) {
 146                         c = *s;
 147                         c = tolower((unsigned char)c);
 148                         h = ( h << 4 ) + c;
 149                         if ((g = ( h & 0xf0000000 )) != 0) {
 150                                 h = h ^ (g >> 24);
 151                                 h = h ^ g;
 152                         }
 153                 }
 154         }
 155
 156         return (h);
 157 }
 158
 159 #define FIND(s, k, t, b, e) \
 160         b = hash((k), (s)->case_sensitive) % (s)->size; \
 161         if ((s)->case_sensitive) { \
 162                 for (e = ISC_LIST_HEAD((s)->table[b]); \
 163                      e != NULL; \
 164                      e = ISC_LIST_NEXT(e, link)) { \
 165                         if (((t) == 0 || e->type == (t)) && \
 166                             strcmp(e->key, (k)) == 0) \
 167                                 break; \
 168                 } \
 169         } else { \
 170                 for (e = ISC_LIST_HEAD((s)->table[b]); \
 171                      e != NULL; \
 172                      e = ISC_LIST_NEXT(e, link)) { \
 173                         if (((t) == 0 || e->type == (t)) && \
 174                             strcasecmp(e->key, (k)) == 0) \
 175                                 break; \
 176                 } \
 177         }
 178
 179 isc_result_t
 180 isccc_symtab_lookup(isccc_symtab_t *symtab, const char *key, unsigned int type,
 181                   isccc_symvalue_t *value)
 182 {
 183         unsigned int bucket;
 184         elt_t *elt;
 185
 186         REQUIRE(VALID_SYMTAB(symtab));
 187         REQUIRE(key != NULL);
 188
 189         FIND(symtab, key, type, bucket, elt);
 190
 191         if (elt == NULL)
 192                 return (ISC_R_NOTFOUND);
 193
 194         if (value != NULL)
 195                 *value = elt->value;
 196
 197         return (ISC_R_SUCCESS);
 198 }
 199
 200 isc_result_t
 201 isccc_symtab_define(isccc_symtab_t *symtab, char *key, unsigned int type,
 202                   isccc_symvalue_t value, isccc_symexists_t exists_policy)
 203 {
 204         unsigned int bucket;
 205         elt_t *elt;
 206
 207         REQUIRE(VALID_SYMTAB(symtab));
 208         REQUIRE(key != NULL);
 209         REQUIRE(type != 0);
 210
 211         FIND(symtab, key, type, bucket, elt);
 212
 213         if (exists_policy != isccc_symexists_add && elt != NULL) {
 214                 if (exists_policy == isccc_symexists_reject)
 215                         return (ISC_R_EXISTS);
 216                 INSIST(exists_policy == isccc_symexists_replace);
 217                 ISC_LIST_UNLINK(symtab->table[bucket], elt, link);
 218                 if (symtab->undefine_action != NULL)
 219                         (symtab->undefine_action)(elt->key, elt->type,
 220                                                   elt->value,
 221                                                   symtab->undefine_arg);
 222         } else {
 223                 elt = malloc(sizeof *elt);
 224                 if (elt == NULL)
 225                         return (ISC_R_NOMEMORY);
 226                 ISC_LINK_INIT(elt, link);
 227         }
 228
 229         elt->key = key;
 230         elt->type = type;
 231         elt->value = value;
 232
 233         /*
 234          * We prepend so that the most recent definition will be found.
 235          */
 236         ISC_LIST_PREPEND(symtab->table[bucket], elt, link);
 237
 238         return (ISC_R_SUCCESS);
 239 }
 240
 241 isc_result_t
 242 isccc_symtab_undefine(isccc_symtab_t *symtab, const char *key, unsigned int type) {
 243         unsigned int bucket;
 244         elt_t *elt;
 245
 246         REQUIRE(VALID_SYMTAB(symtab));
 247         REQUIRE(key != NULL);
 248
 249         FIND(symtab, key, type, bucket, elt);
 250
 251         if (elt == NULL)
 252                 return (ISC_R_NOTFOUND);
 253
 254         free_elt(symtab, bucket, elt);
 255
 256         return (ISC_R_SUCCESS);
 257 }
 258
 259 void
 260 isccc_symtab_foreach(isccc_symtab_t *symtab, isccc_symtabforeachaction_t action,
 261                    void *arg)
 262 {
 263         unsigned int i;
 264         elt_t *elt, *nelt;
 265
 266         REQUIRE(VALID_SYMTAB(symtab));
 267         REQUIRE(action != NULL);
 268
 269         for (i = 0; i < symtab->size; i++) {
 270                 for (elt = ISC_LIST_HEAD(symtab->table[i]);
 271                      elt != NULL;
 272                      elt = nelt) {
 273                         nelt = ISC_LIST_NEXT(elt, link);
 274                         if ((action)(elt->key, elt->type, elt->value, arg))
 275                                 free_elt(symtab, i, elt);
 276                 }
 277         }
 278 }