Annotation of embedaddon/ntp/lib/isc/symtab.c, revision 1.1.1.1

1.1       misho       1: /*
                      2:  * Copyright (C) 2004, 2005, 2007  Internet Systems Consortium, Inc. ("ISC")
                      3:  * Copyright (C) 1996-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 DISCLAIMS ALL WARRANTIES WITH
                     10:  * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
                     11:  * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
                     12:  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
                     13:  * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
                     14:  * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
                     15:  * PERFORMANCE OF THIS SOFTWARE.
                     16:  */
                     17: 
                     18: /* $Id: symtab.c,v 1.30 2007/06/19 23:47:17 tbox Exp $ */
                     19: 
                     20: /*! \file */
                     21: 
                     22: #include <config.h>
                     23: 
                     24: #include <ctype.h>
                     25: 
                     26: #include <isc/magic.h>
                     27: #include <isc/mem.h>
                     28: #include <isc/string.h>
                     29: #include <isc/symtab.h>
                     30: #include <isc/util.h>
                     31: 
                     32: typedef struct elt {
                     33:        char *                          key;
                     34:        unsigned int                    type;
                     35:        isc_symvalue_t                  value;
                     36:        LINK(struct elt)                link;
                     37: } elt_t;
                     38: 
                     39: typedef LIST(elt_t)                    eltlist_t;
                     40: 
                     41: #define SYMTAB_MAGIC                   ISC_MAGIC('S', 'y', 'm', 'T')
                     42: #define VALID_SYMTAB(st)               ISC_MAGIC_VALID(st, SYMTAB_MAGIC)
                     43: 
                     44: struct isc_symtab {
                     45:        /* Unlocked. */
                     46:        unsigned int                    magic;
                     47:        isc_mem_t *                     mctx;
                     48:        unsigned int                    size;
                     49:        eltlist_t *                     table;
                     50:        isc_symtabaction_t              undefine_action;
                     51:        void *                          undefine_arg;
                     52:        isc_boolean_t                   case_sensitive;
                     53: };
                     54: 
                     55: isc_result_t
                     56: isc_symtab_create(isc_mem_t *mctx, unsigned int size,
                     57:                  isc_symtabaction_t undefine_action,
                     58:                  void *undefine_arg,
                     59:                  isc_boolean_t case_sensitive,
                     60:                  isc_symtab_t **symtabp)
                     61: {
                     62:        isc_symtab_t *symtab;
                     63:        unsigned int i;
                     64: 
                     65:        REQUIRE(mctx != NULL);
                     66:        REQUIRE(symtabp != NULL && *symtabp == NULL);
                     67:        REQUIRE(size > 0);      /* Should be prime. */
                     68: 
                     69:        symtab = (isc_symtab_t *)isc_mem_get(mctx, sizeof(*symtab));
                     70:        if (symtab == NULL)
                     71:                return (ISC_R_NOMEMORY);
                     72:        symtab->table = (eltlist_t *)isc_mem_get(mctx,
                     73:                                                 size * sizeof(eltlist_t));
                     74:        if (symtab->table == NULL) {
                     75:                isc_mem_put(mctx, symtab, sizeof(*symtab));
                     76:                return (ISC_R_NOMEMORY);
                     77:        }
                     78:        for (i = 0; i < size; i++)
                     79:                INIT_LIST(symtab->table[i]);
                     80:        symtab->mctx = mctx;
                     81:        symtab->size = size;
                     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_put(symtab->mctx, symtab, sizeof(*symtab));
                    117: 
                    118:        *symtabp = NULL;
                    119: }
                    120: 
                    121: static inline unsigned int
                    122: hash(const char *key, isc_boolean_t 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: isc_result_t
                    185: isc_symtab_define(isc_symtab_t *symtab, const char *key, unsigned int type,
                    186:                  isc_symvalue_t value, isc_symexists_t exists_policy)
                    187: {
                    188:        unsigned int bucket;
                    189:        elt_t *elt;
                    190: 
                    191:        REQUIRE(VALID_SYMTAB(symtab));
                    192:        REQUIRE(key != NULL);
                    193:        REQUIRE(type != 0);
                    194: 
                    195:        FIND(symtab, key, type, bucket, elt);
                    196: 
                    197:        if (exists_policy != isc_symexists_add && elt != NULL) {
                    198:                if (exists_policy == isc_symexists_reject)
                    199:                        return (ISC_R_EXISTS);
                    200:                INSIST(exists_policy == isc_symexists_replace);
                    201:                UNLINK(symtab->table[bucket], elt, link);
                    202:                if (symtab->undefine_action != NULL)
                    203:                        (symtab->undefine_action)(elt->key, elt->type,
                    204:                                                  elt->value,
                    205:                                                  symtab->undefine_arg);
                    206:        } else {
                    207:                elt = (elt_t *)isc_mem_get(symtab->mctx, sizeof(*elt));
                    208:                if (elt == NULL)
                    209:                        return (ISC_R_NOMEMORY);
                    210:                ISC_LINK_INIT(elt, link);
                    211:        }
                    212: 
                    213:        /*
                    214:         * Though the "key" can be const coming in, it is not stored as const
                    215:         * so that the calling program can easily have writable access to
                    216:         * it in its undefine_action function.  In the event that it *was*
                    217:         * truly const coming in and then the caller modified it anyway ...
                    218:         * well, don't do that!
                    219:         */
                    220:        DE_CONST(key, elt->key);
                    221:        elt->type = type;
                    222:        elt->value = value;
                    223: 
                    224:        /*
                    225:         * We prepend so that the most recent definition will be found.
                    226:         */
                    227:        PREPEND(symtab->table[bucket], elt, link);
                    228: 
                    229:        return (ISC_R_SUCCESS);
                    230: }
                    231: 
                    232: isc_result_t
                    233: isc_symtab_undefine(isc_symtab_t *symtab, const char *key, unsigned int type) {
                    234:        unsigned int bucket;
                    235:        elt_t *elt;
                    236: 
                    237:        REQUIRE(VALID_SYMTAB(symtab));
                    238:        REQUIRE(key != NULL);
                    239: 
                    240:        FIND(symtab, key, type, bucket, elt);
                    241: 
                    242:        if (elt == NULL)
                    243:                return (ISC_R_NOTFOUND);
                    244: 
                    245:        if (symtab->undefine_action != NULL)
                    246:                (symtab->undefine_action)(elt->key, elt->type,
                    247:                                          elt->value, symtab->undefine_arg);
                    248:        UNLINK(symtab->table[bucket], elt, link);
                    249:        isc_mem_put(symtab->mctx, elt, sizeof(*elt));
                    250: 
                    251:        return (ISC_R_SUCCESS);
                    252: }

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>