symtab.c revision 258945
1139749Simp/* 2120056Stakawata * Copyright (C) 2004, 2005, 2007 Internet Systems Consortium, Inc. ("ISC") 3120056Stakawata * Copyright (C) 1996-2001 Internet Software Consortium. 4120056Stakawata * 5120056Stakawata * Permission to use, copy, modify, and/or distribute this software for any 6120056Stakawata * purpose with or without fee is hereby granted, provided that the above 7120056Stakawata * copyright notice and this permission notice appear in all copies. 8120056Stakawata * 9120056Stakawata * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 10120056Stakawata * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 11120056Stakawata * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 12120056Stakawata * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 13120056Stakawata * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 14120056Stakawata * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 15120056Stakawata * PERFORMANCE OF THIS SOFTWARE. 16120056Stakawata */ 17120056Stakawata 18120056Stakawata/* $Id: symtab.c,v 1.30 2007/06/19 23:47:17 tbox Exp $ */ 19120056Stakawata 20120056Stakawata/*! \file */ 21120056Stakawata 22120056Stakawata#include <config.h> 23120056Stakawata 24120056Stakawata#include <ctype.h> 25120056Stakawata 26120056Stakawata#include <isc/magic.h> 27120056Stakawata#include <isc/mem.h> 28120056Stakawata#include <isc/string.h> 29120056Stakawata#include <isc/symtab.h> 30120056Stakawata#include <isc/util.h> 31120056Stakawata 32120056Stakawatatypedef struct elt { 33120056Stakawata char * key; 34120056Stakawata unsigned int type; 35120056Stakawata isc_symvalue_t value; 36120056Stakawata LINK(struct elt) link; 37120056Stakawata} elt_t; 38120871Simp 39120056Stakawatatypedef LIST(elt_t) eltlist_t; 40120056Stakawata 41120056Stakawata#define SYMTAB_MAGIC ISC_MAGIC('S', 'y', 'm', 'T') 42120056Stakawata#define VALID_SYMTAB(st) ISC_MAGIC_VALID(st, SYMTAB_MAGIC) 43120056Stakawata 44129764Simpstruct isc_symtab { 45129764Simp /* Unlocked. */ 46120056Stakawata unsigned int magic; 47150440Simp isc_mem_t * mctx; 48120056Stakawata unsigned int size; 49120056Stakawata eltlist_t * table; 50120056Stakawata isc_symtabaction_t undefine_action; 51150440Simp void * undefine_arg; 52150440Simp isc_boolean_t case_sensitive; 53120056Stakawata}; 54120056Stakawata 55120056Stakawataisc_result_t 56120056Stakawataisc_symtab_create(isc_mem_t *mctx, unsigned int size, 57120056Stakawata isc_symtabaction_t undefine_action, 58120056Stakawata void *undefine_arg, 59120056Stakawata isc_boolean_t case_sensitive, 60120056Stakawata isc_symtab_t **symtabp) 61120056Stakawata{ 62120056Stakawata isc_symtab_t *symtab; 63120056Stakawata unsigned int i; 64120056Stakawata 65150440Simp REQUIRE(mctx != NULL); 66120056Stakawata REQUIRE(symtabp != NULL && *symtabp == NULL); 67151791Smarcel REQUIRE(size > 0); /* Should be prime. */ 68151791Smarcel 69120056Stakawata symtab = (isc_symtab_t *)isc_mem_get(mctx, sizeof(*symtab)); 70151791Smarcel if (symtab == NULL) 71120056Stakawata return (ISC_R_NOMEMORY); 72120056Stakawata symtab->table = (eltlist_t *)isc_mem_get(mctx, 73120056Stakawata size * sizeof(eltlist_t)); 74120056Stakawata if (symtab->table == NULL) { 75120056Stakawata isc_mem_put(mctx, symtab, sizeof(*symtab)); 76151791Smarcel return (ISC_R_NOMEMORY); 77120056Stakawata } 78120056Stakawata for (i = 0; i < size; i++) 79120056Stakawata INIT_LIST(symtab->table[i]); 80151791Smarcel symtab->mctx = mctx; 81120056Stakawata symtab->size = size; 82150440Simp symtab->undefine_action = undefine_action; 83120056Stakawata symtab->undefine_arg = undefine_arg; 84120056Stakawata symtab->case_sensitive = case_sensitive; 85120056Stakawata symtab->magic = SYMTAB_MAGIC; 86150440Simp 87120056Stakawata *symtabp = symtab; 88120056Stakawata 89151791Smarcel return (ISC_R_SUCCESS); 90150440Simp} 91120056Stakawata 92120056Stakawatavoid 93120081Stakawataisc_symtab_destroy(isc_symtab_t **symtabp) { 94151791Smarcel isc_symtab_t *symtab; 95151791Smarcel unsigned int i; 96151791Smarcel elt_t *elt, *nelt; 97150440Simp 98120056Stakawata REQUIRE(symtabp != NULL); 99120056Stakawata symtab = *symtabp; 100120056Stakawata 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 121static inline unsigned int 122hash(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 163isc_result_t 164isc_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 184isc_result_t 185isc_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 232isc_result_t 233isc_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} 253