Annotation of embedaddon/ntp/lib/isc/symtab.c, revision 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>