symtab.c

Go to the documentation of this file.
00001 /*
00002  * Portions Copyright (C) 2004, 2005, 2007  Internet Systems Consortium, Inc. ("ISC")
00003  * Portions Copyright (C) 2001  Internet Software Consortium.
00004  *
00005  * Permission to use, copy, modify, and/or distribute this software for any
00006  * purpose with or without fee is hereby granted, provided that the above
00007  * copyright notice and this permission notice appear in all copies.
00008  *
00009  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC AND NOMINUM DISCLAIMS ALL
00010  * WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES
00011  * OF MERCHANTABILITY AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY
00012  * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
00013  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
00014  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
00015  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
00016  *
00017  * Portions Copyright (C) 2001  Nominum, Inc.
00018  *
00019  * Permission to use, copy, modify, and/or distribute this software for any
00020  * purpose with or without fee is hereby granted, provided that the above
00021  * copyright notice and this permission notice appear in all copies.
00022  *
00023  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC AND NOMINUM DISCLAIMS ALL
00024  * WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES
00025  * OF MERCHANTABILITY AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY
00026  * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
00027  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
00028  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
00029  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
00030  */
00031 
00032 /* $Id: symtab.c,v 1.11 2007/09/13 04:45:18 each Exp $ */
00033 
00034 /*! \file */
00035 
00036 #include <config.h>
00037 
00038 #include <ctype.h>
00039 #include <stdlib.h>
00040 
00041 #include <isc/assertions.h>
00042 #include <isc/magic.h>
00043 #include <isc/string.h>
00044 
00045 #include <isccc/result.h>
00046 #include <isccc/symtab.h>
00047 #include <isccc/util.h>
00048 
00049 typedef struct elt {
00050         char *                          key;
00051         unsigned int                    type;
00052         isccc_symvalue_t                        value;
00053         ISC_LINK(struct elt)            link;
00054 } elt_t;
00055 
00056 typedef ISC_LIST(elt_t)                 eltlist_t;
00057 
00058 #define SYMTAB_MAGIC                    ISC_MAGIC('S', 'y', 'm', 'T')
00059 #define VALID_SYMTAB(st)                ISC_MAGIC_VALID(st, SYMTAB_MAGIC)
00060 
00061 struct isccc_symtab {
00062         unsigned int                    magic;
00063         unsigned int                    size;
00064         eltlist_t *                     table;
00065         isccc_symtabundefaction_t               undefine_action;
00066         void *                          undefine_arg;
00067         isc_boolean_t                   case_sensitive;
00068 };
00069 
00070 isc_result_t
00071 isccc_symtab_create(unsigned int size,
00072                   isccc_symtabundefaction_t undefine_action,
00073                   void *undefine_arg,
00074                   isc_boolean_t case_sensitive,
00075                   isccc_symtab_t **symtabp)
00076 {
00077         isccc_symtab_t *symtab;
00078         unsigned int i;
00079 
00080         REQUIRE(symtabp != NULL && *symtabp == NULL);
00081         REQUIRE(size > 0);      /* Should be prime. */
00082 
00083         symtab = malloc(sizeof(*symtab));
00084         if (symtab == NULL)
00085                 return (ISC_R_NOMEMORY);
00086         symtab->table = malloc(size * sizeof(eltlist_t));
00087         if (symtab->table == NULL) {
00088                 free(symtab);
00089                 return (ISC_R_NOMEMORY);
00090         }
00091         for (i = 0; i < size; i++)
00092                 ISC_LIST_INIT(symtab->table[i]);
00093         symtab->size = size;
00094         symtab->undefine_action = undefine_action;
00095         symtab->undefine_arg = undefine_arg;
00096         symtab->case_sensitive = case_sensitive;
00097         symtab->magic = SYMTAB_MAGIC;
00098 
00099         *symtabp = symtab;
00100 
00101         return (ISC_R_SUCCESS);
00102 }
00103 
00104 static inline void
00105 free_elt(isccc_symtab_t *symtab, unsigned int bucket, elt_t *elt) {
00106         ISC_LIST_UNLINK(symtab->table[bucket], elt, link);
00107         if (symtab->undefine_action != NULL)
00108                 (symtab->undefine_action)(elt->key, elt->type, elt->value,
00109                                           symtab->undefine_arg);
00110         free(elt);
00111 }
00112 
00113 void
00114 isccc_symtab_destroy(isccc_symtab_t **symtabp) {
00115         isccc_symtab_t *symtab;
00116         unsigned int i;
00117         elt_t *elt, *nelt;
00118 
00119         REQUIRE(symtabp != NULL);
00120         symtab = *symtabp;
00121         REQUIRE(VALID_SYMTAB(symtab));
00122 
00123         for (i = 0; i < symtab->size; i++) {
00124                 for (elt = ISC_LIST_HEAD(symtab->table[i]);
00125                      elt != NULL;
00126                      elt = nelt) {
00127                         nelt = ISC_LIST_NEXT(elt, link);
00128                         free_elt(symtab, i, elt);
00129                 }
00130         }
00131         free(symtab->table);
00132         symtab->magic = 0;
00133         free(symtab);
00134 
00135         *symtabp = NULL;
00136 }
00137 
00138 static inline unsigned int
00139 hash(const char *key, isc_boolean_t case_sensitive) {
00140         const char *s;
00141         unsigned int h = 0;
00142         unsigned int g;
00143         int c;
00144 
00145         /*
00146          * P. J. Weinberger's hash function, adapted from p. 436 of
00147          * _Compilers: Principles, Techniques, and Tools_, Aho, Sethi
00148          * and Ullman, Addison-Wesley, 1986, ISBN 0-201-10088-6.
00149          */
00150 
00151         if (case_sensitive) {
00152                 for (s = key; *s != '\0'; s++) {
00153                         h = ( h << 4 ) + *s;
00154                         if ((g = ( h & 0xf0000000 )) != 0) {
00155                                 h = h ^ (g >> 24);
00156                                 h = h ^ g;
00157                         }
00158                 }
00159         } else {
00160                 for (s = key; *s != '\0'; s++) {
00161                         c = *s;
00162                         c = tolower((unsigned char)c);
00163                         h = ( h << 4 ) + c;
00164                         if ((g = ( h & 0xf0000000 )) != 0) {
00165                                 h = h ^ (g >> 24);
00166                                 h = h ^ g;
00167                         }
00168                 }
00169         }
00170 
00171         return (h);
00172 }
00173 
00174 #define FIND(s, k, t, b, e) \
00175         b = hash((k), (s)->case_sensitive) % (s)->size; \
00176         if ((s)->case_sensitive) { \
00177                 for (e = ISC_LIST_HEAD((s)->table[b]); \
00178                      e != NULL; \
00179                      e = ISC_LIST_NEXT(e, link)) { \
00180                         if (((t) == 0 || e->type == (t)) && \
00181                             strcmp(e->key, (k)) == 0) \
00182                                 break; \
00183                 } \
00184         } else { \
00185                 for (e = ISC_LIST_HEAD((s)->table[b]); \
00186                      e != NULL; \
00187                      e = ISC_LIST_NEXT(e, link)) { \
00188                         if (((t) == 0 || e->type == (t)) && \
00189                             strcasecmp(e->key, (k)) == 0) \
00190                                 break; \
00191                 } \
00192         }
00193 
00194 isc_result_t
00195 isccc_symtab_lookup(isccc_symtab_t *symtab, const char *key, unsigned int type,
00196                   isccc_symvalue_t *value)
00197 {
00198         unsigned int bucket;
00199         elt_t *elt;
00200 
00201         REQUIRE(VALID_SYMTAB(symtab));
00202         REQUIRE(key != NULL);
00203 
00204         FIND(symtab, key, type, bucket, elt);
00205 
00206         if (elt == NULL)
00207                 return (ISC_R_NOTFOUND);
00208 
00209         if (value != NULL)
00210                 *value = elt->value;
00211 
00212         return (ISC_R_SUCCESS);
00213 }
00214 
00215 isc_result_t
00216 isccc_symtab_define(isccc_symtab_t *symtab, char *key, unsigned int type,
00217                   isccc_symvalue_t value, isccc_symexists_t exists_policy)
00218 {
00219         unsigned int bucket;
00220         elt_t *elt;
00221 
00222         REQUIRE(VALID_SYMTAB(symtab));
00223         REQUIRE(key != NULL);
00224         REQUIRE(type != 0);
00225 
00226         FIND(symtab, key, type, bucket, elt);
00227 
00228         if (exists_policy != isccc_symexists_add && elt != NULL) {
00229                 if (exists_policy == isccc_symexists_reject)
00230                         return (ISC_R_EXISTS);
00231                 INSIST(exists_policy == isccc_symexists_replace);
00232                 ISC_LIST_UNLINK(symtab->table[bucket], elt, link);
00233                 if (symtab->undefine_action != NULL)
00234                         (symtab->undefine_action)(elt->key, elt->type,
00235                                                   elt->value,
00236                                                   symtab->undefine_arg);
00237         } else {
00238                 elt = malloc(sizeof(*elt));
00239                 if (elt == NULL)
00240                         return (ISC_R_NOMEMORY);
00241                 ISC_LINK_INIT(elt, link);
00242         }
00243 
00244         elt->key = key;
00245         elt->type = type;
00246         elt->value = value;
00247 
00248         /*
00249          * We prepend so that the most recent definition will be found.
00250          */
00251         ISC_LIST_PREPEND(symtab->table[bucket], elt, link);
00252 
00253         return (ISC_R_SUCCESS);
00254 }
00255 
00256 isc_result_t
00257 isccc_symtab_undefine(isccc_symtab_t *symtab, const char *key, unsigned int type) {
00258         unsigned int bucket;
00259         elt_t *elt;
00260 
00261         REQUIRE(VALID_SYMTAB(symtab));
00262         REQUIRE(key != NULL);
00263 
00264         FIND(symtab, key, type, bucket, elt);
00265 
00266         if (elt == NULL)
00267                 return (ISC_R_NOTFOUND);
00268 
00269         free_elt(symtab, bucket, elt);
00270 
00271         return (ISC_R_SUCCESS);
00272 }
00273 
00274 void
00275 isccc_symtab_foreach(isccc_symtab_t *symtab, isccc_symtabforeachaction_t action,
00276                    void *arg)
00277 {
00278         unsigned int i;
00279         elt_t *elt, *nelt;
00280 
00281         REQUIRE(VALID_SYMTAB(symtab));
00282         REQUIRE(action != NULL);
00283 
00284         for (i = 0; i < symtab->size; i++) {
00285                 for (elt = ISC_LIST_HEAD(symtab->table[i]);
00286                      elt != NULL;
00287                      elt = nelt) {
00288                         nelt = ISC_LIST_NEXT(elt, link);
00289                         if ((action)(elt->key, elt->type, elt->value, arg))
00290                                 free_elt(symtab, i, elt);
00291                 }
00292         }
00293 }

Generated on Tue Apr 28 17:41:05 2015 by Doxygen 1.5.4 for BIND9 Internals 9.11.0pre-alpha