1/* $NetBSD$ */ 2 3/* 4 * Copyright (C) 2004, 2005, 2007, 2011, 2012 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 34typedef struct elt { 35 char * key; 36 unsigned int type; 37 isc_symvalue_t value; 38 LINK(struct elt) link; 39} elt_t; 40 41typedef 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 46struct 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 59isc_result_t 60isc_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 symtab->table = (eltlist_t *)isc_mem_get(mctx, 77 size * sizeof(eltlist_t)); 78 if (symtab->table == NULL) { 79 isc_mem_put(mctx, symtab, sizeof(*symtab)); 80 return (ISC_R_NOMEMORY); 81 } 82 for (i = 0; i < size; i++) 83 INIT_LIST(symtab->table[i]); 84 symtab->mctx = mctx; 85 symtab->size = size; 86 symtab->count = 0; 87 symtab->maxload = size * 3 / 4; 88 symtab->undefine_action = undefine_action; 89 symtab->undefine_arg = undefine_arg; 90 symtab->case_sensitive = case_sensitive; 91 symtab->magic = SYMTAB_MAGIC; 92 93 *symtabp = symtab; 94 95 return (ISC_R_SUCCESS); 96} 97 98void 99isc_symtab_destroy(isc_symtab_t **symtabp) { 100 isc_symtab_t *symtab; 101 unsigned int i; 102 elt_t *elt, *nelt; 103 104 REQUIRE(symtabp != NULL); 105 symtab = *symtabp; 106 REQUIRE(VALID_SYMTAB(symtab)); 107 108 for (i = 0; i < symtab->size; i++) { 109 for (elt = HEAD(symtab->table[i]); elt != NULL; elt = nelt) { 110 nelt = NEXT(elt, link); 111 if (symtab->undefine_action != NULL) 112 (symtab->undefine_action)(elt->key, 113 elt->type, 114 elt->value, 115 symtab->undefine_arg); 116 isc_mem_put(symtab->mctx, elt, sizeof(*elt)); 117 } 118 } 119 isc_mem_put(symtab->mctx, symtab->table, 120 symtab->size * sizeof(eltlist_t)); 121 symtab->magic = 0; 122 isc_mem_put(symtab->mctx, symtab, sizeof(*symtab)); 123 124 *symtabp = NULL; 125} 126 127static inline unsigned int 128hash(const char *key, isc_boolean_t case_sensitive) { 129 const char *s; 130 unsigned int h = 0; 131 int c; 132 133 /* 134 * This hash function is similar to the one Ousterhout 135 * uses in Tcl. 136 */ 137 138 if (case_sensitive) { 139 for (s = key; *s != '\0'; s++) { 140 h += (h << 3) + *s; 141 } 142 } else { 143 for (s = key; *s != '\0'; s++) { 144 c = *s; 145 c = tolower((unsigned char)c); 146 h += (h << 3) + c; 147 } 148 } 149 150 return (h); 151} 152 153#define FIND(s, k, t, b, e) \ 154 b = hash((k), (s)->case_sensitive) % (s)->size; \ 155 if ((s)->case_sensitive) { \ 156 for (e = HEAD((s)->table[b]); e != NULL; e = NEXT(e, link)) { \ 157 if (((t) == 0 || e->type == (t)) && \ 158 strcmp(e->key, (k)) == 0) \ 159 break; \ 160 } \ 161 } else { \ 162 for (e = HEAD((s)->table[b]); e != NULL; e = NEXT(e, link)) { \ 163 if (((t) == 0 || e->type == (t)) && \ 164 strcasecmp(e->key, (k)) == 0) \ 165 break; \ 166 } \ 167 } 168 169isc_result_t 170isc_symtab_lookup(isc_symtab_t *symtab, const char *key, unsigned int type, 171 isc_symvalue_t *value) 172{ 173 unsigned int bucket; 174 elt_t *elt; 175 176 REQUIRE(VALID_SYMTAB(symtab)); 177 REQUIRE(key != NULL); 178 179 FIND(symtab, key, type, bucket, elt); 180 181 if (elt == NULL) 182 return (ISC_R_NOTFOUND); 183 184 if (value != NULL) 185 *value = elt->value; 186 187 return (ISC_R_SUCCESS); 188} 189 190static void 191grow_table(isc_symtab_t *symtab) { 192 eltlist_t *newtable; 193 unsigned int i, newsize, newmax; 194 195 REQUIRE(symtab != NULL); 196 197 newsize = symtab->size * 2; 198 newmax = newsize * 3 / 4; 199 INSIST(newsize > 0U && newmax > 0U); 200 201 newtable = isc_mem_get(symtab->mctx, newsize * sizeof(eltlist_t)); 202 if (newtable == NULL) 203 return; 204 205 for (i = 0; i < newsize; i++) 206 INIT_LIST(newtable[i]); 207 208 for (i = 0; i < symtab->size; i++) { 209 elt_t *elt, *nelt; 210 211 for (elt = HEAD(symtab->table[i]); elt != NULL; elt = nelt) { 212 unsigned int hv; 213 214 nelt = NEXT(elt, link); 215 216 UNLINK(symtab->table[i], elt, link); 217 hv = hash(elt->key, symtab->case_sensitive); 218 APPEND(newtable[hv % newsize], elt, link); 219 } 220 } 221 222 isc_mem_put(symtab->mctx, symtab->table, 223 symtab->size * sizeof(eltlist_t)); 224 225 symtab->table = newtable; 226 symtab->size = newsize; 227 symtab->maxload = newmax; 228} 229 230isc_result_t 231isc_symtab_define(isc_symtab_t *symtab, const char *key, unsigned int type, 232 isc_symvalue_t value, isc_symexists_t exists_policy) 233{ 234 unsigned int bucket; 235 elt_t *elt; 236 237 REQUIRE(VALID_SYMTAB(symtab)); 238 REQUIRE(key != NULL); 239 REQUIRE(type != 0); 240 241 FIND(symtab, key, type, bucket, elt); 242 243 if (exists_policy != isc_symexists_add && elt != NULL) { 244 if (exists_policy == isc_symexists_reject) 245 return (ISC_R_EXISTS); 246 INSIST(exists_policy == isc_symexists_replace); 247 UNLINK(symtab->table[bucket], elt, link); 248 if (symtab->undefine_action != NULL) 249 (symtab->undefine_action)(elt->key, elt->type, 250 elt->value, 251 symtab->undefine_arg); 252 } else { 253 elt = (elt_t *)isc_mem_get(symtab->mctx, sizeof(*elt)); 254 if (elt == NULL) 255 return (ISC_R_NOMEMORY); 256 ISC_LINK_INIT(elt, link); 257 symtab->count++; 258 } 259 260 /* 261 * Though the "key" can be const coming in, it is not stored as const 262 * so that the calling program can easily have writable access to 263 * it in its undefine_action function. In the event that it *was* 264 * truly const coming in and then the caller modified it anyway ... 265 * well, don't do that! 266 */ 267 DE_CONST(key, elt->key); 268 elt->type = type; 269 elt->value = value; 270 271 /* 272 * We prepend so that the most recent definition will be found. 273 */ 274 PREPEND(symtab->table[bucket], elt, link); 275 276 if (symtab->count > symtab->maxload) 277 grow_table(symtab); 278 279 return (ISC_R_SUCCESS); 280} 281 282isc_result_t 283isc_symtab_undefine(isc_symtab_t *symtab, const char *key, unsigned int type) { 284 unsigned int bucket; 285 elt_t *elt; 286 287 REQUIRE(VALID_SYMTAB(symtab)); 288 REQUIRE(key != NULL); 289 290 FIND(symtab, key, type, bucket, elt); 291 292 if (elt == NULL) 293 return (ISC_R_NOTFOUND); 294 295 if (symtab->undefine_action != NULL) 296 (symtab->undefine_action)(elt->key, elt->type, 297 elt->value, symtab->undefine_arg); 298 UNLINK(symtab->table[bucket], elt, link); 299 isc_mem_put(symtab->mctx, elt, sizeof(*elt)); 300 symtab->count--; 301 302 return (ISC_R_SUCCESS); 303} 304