"Fossies" - the Fresh Open Source Software Archive

Member "bind-9.11.23/lib/isc/symtab.c" (7 Sep 2020, 7064 Bytes) of package /linux/misc/dns/bind9/9.11.23/bind-9.11.23.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "symtab.c" see the Fossies "Dox" file reference documentation.

    1 /*
    2  * Copyright (C) Internet Systems Consortium, Inc. ("ISC")
    3  *
    4  * This Source Code Form is subject to the terms of the Mozilla Public
    5  * License, v. 2.0. If a copy of the MPL was not distributed with this
    6  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
    7  *
    8  * See the COPYRIGHT file distributed with this work for additional
    9  * information regarding copyright ownership.
   10  */
   11 
   12 
   13 /*! \file */
   14 
   15 #include <config.h>
   16 
   17 #include <ctype.h>
   18 #include <stdbool.h>
   19 
   20 #include <isc/magic.h>
   21 #include <isc/mem.h>
   22 #include <isc/string.h>
   23 #include <isc/symtab.h>
   24 #include <isc/util.h>
   25 
   26 typedef struct elt {
   27     char *              key;
   28     unsigned int            type;
   29     isc_symvalue_t          value;
   30     LINK(struct elt)        link;
   31 } elt_t;
   32 
   33 typedef LIST(elt_t)         eltlist_t;
   34 
   35 #define SYMTAB_MAGIC            ISC_MAGIC('S', 'y', 'm', 'T')
   36 #define VALID_SYMTAB(st)        ISC_MAGIC_VALID(st, SYMTAB_MAGIC)
   37 
   38 struct isc_symtab {
   39     /* Unlocked. */
   40     unsigned int            magic;
   41     isc_mem_t *         mctx;
   42     unsigned int            size;
   43     unsigned int            count;
   44     unsigned int            maxload;
   45     eltlist_t *         table;
   46     isc_symtabaction_t      undefine_action;
   47     void *              undefine_arg;
   48     bool            case_sensitive;
   49 };
   50 
   51 isc_result_t
   52 isc_symtab_create(isc_mem_t *mctx, unsigned int size,
   53           isc_symtabaction_t undefine_action,
   54           void *undefine_arg,
   55           bool case_sensitive,
   56           isc_symtab_t **symtabp)
   57 {
   58     isc_symtab_t *symtab;
   59     unsigned int i;
   60 
   61     REQUIRE(mctx != NULL);
   62     REQUIRE(symtabp != NULL && *symtabp == NULL);
   63     REQUIRE(size > 0);  /* Should be prime. */
   64 
   65     symtab = (isc_symtab_t *)isc_mem_get(mctx, sizeof(*symtab));
   66     if (symtab == NULL)
   67         return (ISC_R_NOMEMORY);
   68 
   69     symtab->mctx = NULL;
   70     isc_mem_attach(mctx, &symtab->mctx);
   71     symtab->table = (eltlist_t *)isc_mem_get(mctx,
   72                          size * sizeof(eltlist_t));
   73     if (symtab->table == NULL) {
   74         isc_mem_putanddetach(&symtab->mctx, symtab, sizeof(*symtab));
   75         return (ISC_R_NOMEMORY);
   76     }
   77     for (i = 0; i < size; i++)
   78         INIT_LIST(symtab->table[i]);
   79     symtab->size = size;
   80     symtab->count = 0;
   81     symtab->maxload = size * 3 / 4;
   82     symtab->undefine_action = undefine_action;
   83     symtab->undefine_arg = undefine_arg;
   84     symtab->case_sensitive = case_sensitive;
   85     symtab->magic = SYMTAB_MAGIC;
   86 
   87     *symtabp = symtab;
   88 
   89     return (ISC_R_SUCCESS);
   90 }
   91 
   92 void
   93 isc_symtab_destroy(isc_symtab_t **symtabp) {
   94     isc_symtab_t *symtab;
   95     unsigned int i;
   96     elt_t *elt, *nelt;
   97 
   98     REQUIRE(symtabp != NULL);
   99     symtab = *symtabp;
  100     REQUIRE(VALID_SYMTAB(symtab));
  101 
  102     for (i = 0; i < symtab->size; i++) {
  103         for (elt = HEAD(symtab->table[i]); elt != NULL; elt = nelt) {
  104             nelt = NEXT(elt, link);
  105             if (symtab->undefine_action != NULL)
  106                    (symtab->undefine_action)(elt->key,
  107                              elt->type,
  108                              elt->value,
  109                              symtab->undefine_arg);
  110             isc_mem_put(symtab->mctx, elt, sizeof(*elt));
  111         }
  112     }
  113     isc_mem_put(symtab->mctx, symtab->table,
  114             symtab->size * sizeof(eltlist_t));
  115     symtab->magic = 0;
  116     isc_mem_putanddetach(&symtab->mctx, symtab, sizeof(*symtab));
  117 
  118     *symtabp = NULL;
  119 }
  120 
  121 static inline unsigned int
  122 hash(const char *key, bool case_sensitive) {
  123     const char *s;
  124     unsigned int h = 0;
  125     int c;
  126 
  127     /*
  128      * This hash function is similar to the one Ousterhout
  129      * uses in Tcl.
  130      */
  131 
  132     if (case_sensitive) {
  133         for (s = key; *s != '\0'; s++) {
  134             h += (h << 3) + *s;
  135         }
  136     } else {
  137         for (s = key; *s != '\0'; s++) {
  138             c = *s;
  139             c = tolower((unsigned char)c);
  140             h += (h << 3) + c;
  141         }
  142     }
  143 
  144     return (h);
  145 }
  146 
  147 #define FIND(s, k, t, b, e) \
  148     b = hash((k), (s)->case_sensitive) % (s)->size; \
  149     if ((s)->case_sensitive) { \
  150         for (e = HEAD((s)->table[b]); e != NULL; e = NEXT(e, link)) { \
  151             if (((t) == 0 || e->type == (t)) && \
  152                 strcmp(e->key, (k)) == 0) \
  153                 break; \
  154         } \
  155     } else { \
  156         for (e = HEAD((s)->table[b]); e != NULL; e = NEXT(e, link)) { \
  157             if (((t) == 0 || e->type == (t)) && \
  158                 strcasecmp(e->key, (k)) == 0) \
  159                 break; \
  160         } \
  161     }
  162 
  163 isc_result_t
  164 isc_symtab_lookup(isc_symtab_t *symtab, const char *key, unsigned int type,
  165           isc_symvalue_t *value)
  166 {
  167     unsigned int bucket;
  168     elt_t *elt;
  169 
  170     REQUIRE(VALID_SYMTAB(symtab));
  171     REQUIRE(key != NULL);
  172 
  173     FIND(symtab, key, type, bucket, elt);
  174 
  175     if (elt == NULL)
  176         return (ISC_R_NOTFOUND);
  177 
  178     if (value != NULL)
  179         *value = elt->value;
  180 
  181     return (ISC_R_SUCCESS);
  182 }
  183 
  184 static void
  185 grow_table(isc_symtab_t *symtab) {
  186     eltlist_t *newtable;
  187     unsigned int i, newsize, newmax;
  188 
  189     REQUIRE(symtab != NULL);
  190 
  191     newsize = symtab->size * 2;
  192     newmax = newsize * 3 / 4;
  193     INSIST(newsize > 0U && newmax > 0U);
  194 
  195     newtable = isc_mem_get(symtab->mctx, newsize * sizeof(eltlist_t));
  196     if (newtable == NULL)
  197         return;
  198 
  199     for (i = 0; i < newsize; i++)
  200         INIT_LIST(newtable[i]);
  201 
  202     for (i = 0; i < symtab->size; i++) {
  203         elt_t *elt, *nelt;
  204 
  205         for (elt = HEAD(symtab->table[i]); elt != NULL; elt = nelt) {
  206             unsigned int hv;
  207 
  208             nelt = NEXT(elt, link);
  209 
  210             UNLINK(symtab->table[i], elt, link);
  211             hv = hash(elt->key, symtab->case_sensitive);
  212             APPEND(newtable[hv % newsize], elt, link);
  213         }
  214     }
  215 
  216     isc_mem_put(symtab->mctx, symtab->table,
  217             symtab->size * sizeof(eltlist_t));
  218 
  219     symtab->table = newtable;
  220     symtab->size = newsize;
  221     symtab->maxload = newmax;
  222 }
  223 
  224 isc_result_t
  225 isc_symtab_define(isc_symtab_t *symtab, const char *key, unsigned int type,
  226           isc_symvalue_t value, isc_symexists_t exists_policy)
  227 {
  228     unsigned int bucket;
  229     elt_t *elt;
  230 
  231     REQUIRE(VALID_SYMTAB(symtab));
  232     REQUIRE(key != NULL);
  233     REQUIRE(type != 0);
  234 
  235     FIND(symtab, key, type, bucket, elt);
  236 
  237     if (exists_policy != isc_symexists_add && elt != NULL) {
  238         if (exists_policy == isc_symexists_reject)
  239             return (ISC_R_EXISTS);
  240         INSIST(exists_policy == isc_symexists_replace);
  241         UNLINK(symtab->table[bucket], elt, link);
  242         if (symtab->undefine_action != NULL)
  243             (symtab->undefine_action)(elt->key, elt->type,
  244                           elt->value,
  245                           symtab->undefine_arg);
  246     } else {
  247         elt = (elt_t *)isc_mem_get(symtab->mctx, sizeof(*elt));
  248         if (elt == NULL)
  249             return (ISC_R_NOMEMORY);
  250         ISC_LINK_INIT(elt, link);
  251         symtab->count++;
  252     }
  253 
  254     /*
  255      * Though the "key" can be const coming in, it is not stored as const
  256      * so that the calling program can easily have writable access to
  257      * it in its undefine_action function.  In the event that it *was*
  258      * truly const coming in and then the caller modified it anyway ...
  259      * well, don't do that!
  260      */
  261     DE_CONST(key, elt->key);
  262     elt->type = type;
  263     elt->value = value;
  264 
  265     /*
  266      * We prepend so that the most recent definition will be found.
  267      */
  268     PREPEND(symtab->table[bucket], elt, link);
  269 
  270     if (symtab->count > symtab->maxload)
  271         grow_table(symtab);
  272 
  273     return (ISC_R_SUCCESS);
  274 }
  275 
  276 isc_result_t
  277 isc_symtab_undefine(isc_symtab_t *symtab, const char *key, unsigned int type) {
  278     unsigned int bucket;
  279     elt_t *elt;
  280 
  281     REQUIRE(VALID_SYMTAB(symtab));
  282     REQUIRE(key != NULL);
  283 
  284     FIND(symtab, key, type, bucket, elt);
  285 
  286     if (elt == NULL)
  287         return (ISC_R_NOTFOUND);
  288 
  289     if (symtab->undefine_action != NULL)
  290         (symtab->undefine_action)(elt->key, elt->type,
  291                       elt->value, symtab->undefine_arg);
  292     UNLINK(symtab->table[bucket], elt, link);
  293     isc_mem_put(symtab->mctx, elt, sizeof(*elt));
  294     symtab->count--;
  295 
  296     return (ISC_R_SUCCESS);
  297 }
  298 
  299 unsigned int
  300 isc_symtab_count(isc_symtab_t *symtab) {
  301     REQUIRE(VALID_SYMTAB(symtab));
  302     return (symtab->count);
  303 }