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