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