1258945Sroberto/* 2280849Scy * Copyright (C) 2004, 2005, 2007, 2011, 2012 Internet Systems Consortium, Inc. ("ISC") 3258945Sroberto * Copyright (C) 1996-2001 Internet Software Consortium. 4258945Sroberto * 5258945Sroberto * Permission to use, copy, modify, and/or distribute this software for any 6258945Sroberto * purpose with or without fee is hereby granted, provided that the above 7258945Sroberto * copyright notice and this permission notice appear in all copies. 8258945Sroberto * 9258945Sroberto * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 10258945Sroberto * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 11258945Sroberto * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 12258945Sroberto * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 13258945Sroberto * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 14258945Sroberto * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 15258945Sroberto * PERFORMANCE OF THIS SOFTWARE. 16258945Sroberto */ 17258945Sroberto 18280849Scy/* $Id$ */ 19258945Sroberto 20258945Sroberto/*! \file */ 21258945Sroberto 22258945Sroberto#include <config.h> 23258945Sroberto 24258945Sroberto#include <ctype.h> 25258945Sroberto 26258945Sroberto#include <isc/magic.h> 27258945Sroberto#include <isc/mem.h> 28258945Sroberto#include <isc/string.h> 29258945Sroberto#include <isc/symtab.h> 30258945Sroberto#include <isc/util.h> 31258945Sroberto 32258945Srobertotypedef struct elt { 33258945Sroberto char * key; 34258945Sroberto unsigned int type; 35258945Sroberto isc_symvalue_t value; 36258945Sroberto LINK(struct elt) link; 37258945Sroberto} elt_t; 38258945Sroberto 39258945Srobertotypedef LIST(elt_t) eltlist_t; 40258945Sroberto 41258945Sroberto#define SYMTAB_MAGIC ISC_MAGIC('S', 'y', 'm', 'T') 42258945Sroberto#define VALID_SYMTAB(st) ISC_MAGIC_VALID(st, SYMTAB_MAGIC) 43258945Sroberto 44258945Srobertostruct isc_symtab { 45258945Sroberto /* Unlocked. */ 46258945Sroberto unsigned int magic; 47258945Sroberto isc_mem_t * mctx; 48258945Sroberto unsigned int size; 49280849Scy unsigned int count; 50280849Scy unsigned int maxload; 51258945Sroberto eltlist_t * table; 52258945Sroberto isc_symtabaction_t undefine_action; 53258945Sroberto void * undefine_arg; 54258945Sroberto isc_boolean_t case_sensitive; 55258945Sroberto}; 56258945Sroberto 57258945Srobertoisc_result_t 58258945Srobertoisc_symtab_create(isc_mem_t *mctx, unsigned int size, 59258945Sroberto isc_symtabaction_t undefine_action, 60258945Sroberto void *undefine_arg, 61258945Sroberto isc_boolean_t case_sensitive, 62258945Sroberto isc_symtab_t **symtabp) 63258945Sroberto{ 64258945Sroberto isc_symtab_t *symtab; 65258945Sroberto unsigned int i; 66258945Sroberto 67258945Sroberto REQUIRE(mctx != NULL); 68258945Sroberto REQUIRE(symtabp != NULL && *symtabp == NULL); 69258945Sroberto REQUIRE(size > 0); /* Should be prime. */ 70258945Sroberto 71258945Sroberto symtab = (isc_symtab_t *)isc_mem_get(mctx, sizeof(*symtab)); 72258945Sroberto if (symtab == NULL) 73258945Sroberto return (ISC_R_NOMEMORY); 74258945Sroberto symtab->table = (eltlist_t *)isc_mem_get(mctx, 75258945Sroberto size * sizeof(eltlist_t)); 76258945Sroberto if (symtab->table == NULL) { 77258945Sroberto isc_mem_put(mctx, symtab, sizeof(*symtab)); 78258945Sroberto return (ISC_R_NOMEMORY); 79258945Sroberto } 80258945Sroberto for (i = 0; i < size; i++) 81258945Sroberto INIT_LIST(symtab->table[i]); 82258945Sroberto symtab->mctx = mctx; 83258945Sroberto symtab->size = size; 84280849Scy symtab->count = 0; 85280849Scy symtab->maxload = size * 3 / 4; 86258945Sroberto symtab->undefine_action = undefine_action; 87258945Sroberto symtab->undefine_arg = undefine_arg; 88258945Sroberto symtab->case_sensitive = case_sensitive; 89258945Sroberto symtab->magic = SYMTAB_MAGIC; 90258945Sroberto 91258945Sroberto *symtabp = symtab; 92258945Sroberto 93258945Sroberto return (ISC_R_SUCCESS); 94258945Sroberto} 95258945Sroberto 96258945Srobertovoid 97258945Srobertoisc_symtab_destroy(isc_symtab_t **symtabp) { 98258945Sroberto isc_symtab_t *symtab; 99258945Sroberto unsigned int i; 100258945Sroberto elt_t *elt, *nelt; 101258945Sroberto 102258945Sroberto REQUIRE(symtabp != NULL); 103258945Sroberto symtab = *symtabp; 104258945Sroberto REQUIRE(VALID_SYMTAB(symtab)); 105258945Sroberto 106258945Sroberto for (i = 0; i < symtab->size; i++) { 107258945Sroberto for (elt = HEAD(symtab->table[i]); elt != NULL; elt = nelt) { 108258945Sroberto nelt = NEXT(elt, link); 109258945Sroberto if (symtab->undefine_action != NULL) 110258945Sroberto (symtab->undefine_action)(elt->key, 111258945Sroberto elt->type, 112258945Sroberto elt->value, 113258945Sroberto symtab->undefine_arg); 114258945Sroberto isc_mem_put(symtab->mctx, elt, sizeof(*elt)); 115258945Sroberto } 116258945Sroberto } 117258945Sroberto isc_mem_put(symtab->mctx, symtab->table, 118258945Sroberto symtab->size * sizeof(eltlist_t)); 119258945Sroberto symtab->magic = 0; 120258945Sroberto isc_mem_put(symtab->mctx, symtab, sizeof(*symtab)); 121258945Sroberto 122258945Sroberto *symtabp = NULL; 123258945Sroberto} 124258945Sroberto 125258945Srobertostatic inline unsigned int 126258945Srobertohash(const char *key, isc_boolean_t case_sensitive) { 127258945Sroberto const char *s; 128258945Sroberto unsigned int h = 0; 129258945Sroberto int c; 130258945Sroberto 131258945Sroberto /* 132258945Sroberto * This hash function is similar to the one Ousterhout 133258945Sroberto * uses in Tcl. 134258945Sroberto */ 135258945Sroberto 136258945Sroberto if (case_sensitive) { 137258945Sroberto for (s = key; *s != '\0'; s++) { 138258945Sroberto h += (h << 3) + *s; 139258945Sroberto } 140258945Sroberto } else { 141258945Sroberto for (s = key; *s != '\0'; s++) { 142258945Sroberto c = *s; 143258945Sroberto c = tolower((unsigned char)c); 144258945Sroberto h += (h << 3) + c; 145258945Sroberto } 146258945Sroberto } 147258945Sroberto 148258945Sroberto return (h); 149258945Sroberto} 150258945Sroberto 151258945Sroberto#define FIND(s, k, t, b, e) \ 152258945Sroberto b = hash((k), (s)->case_sensitive) % (s)->size; \ 153258945Sroberto if ((s)->case_sensitive) { \ 154258945Sroberto for (e = HEAD((s)->table[b]); e != NULL; e = NEXT(e, link)) { \ 155258945Sroberto if (((t) == 0 || e->type == (t)) && \ 156258945Sroberto strcmp(e->key, (k)) == 0) \ 157258945Sroberto break; \ 158258945Sroberto } \ 159258945Sroberto } else { \ 160258945Sroberto for (e = HEAD((s)->table[b]); e != NULL; e = NEXT(e, link)) { \ 161258945Sroberto if (((t) == 0 || e->type == (t)) && \ 162258945Sroberto strcasecmp(e->key, (k)) == 0) \ 163258945Sroberto break; \ 164258945Sroberto } \ 165258945Sroberto } 166258945Sroberto 167258945Srobertoisc_result_t 168258945Srobertoisc_symtab_lookup(isc_symtab_t *symtab, const char *key, unsigned int type, 169258945Sroberto isc_symvalue_t *value) 170258945Sroberto{ 171258945Sroberto unsigned int bucket; 172258945Sroberto elt_t *elt; 173258945Sroberto 174258945Sroberto REQUIRE(VALID_SYMTAB(symtab)); 175258945Sroberto REQUIRE(key != NULL); 176258945Sroberto 177258945Sroberto FIND(symtab, key, type, bucket, elt); 178258945Sroberto 179258945Sroberto if (elt == NULL) 180258945Sroberto return (ISC_R_NOTFOUND); 181258945Sroberto 182258945Sroberto if (value != NULL) 183258945Sroberto *value = elt->value; 184258945Sroberto 185258945Sroberto return (ISC_R_SUCCESS); 186258945Sroberto} 187258945Sroberto 188280849Scystatic void 189280849Scygrow_table(isc_symtab_t *symtab) { 190280849Scy eltlist_t *newtable; 191280849Scy unsigned int i, newsize, newmax; 192280849Scy 193280849Scy REQUIRE(symtab != NULL); 194280849Scy 195280849Scy newsize = symtab->size * 2; 196280849Scy newmax = newsize * 3 / 4; 197280849Scy INSIST(newsize > 0U && newmax > 0U); 198280849Scy 199280849Scy newtable = isc_mem_get(symtab->mctx, newsize * sizeof(eltlist_t)); 200280849Scy if (newtable == NULL) 201280849Scy return; 202280849Scy 203280849Scy for (i = 0; i < newsize; i++) 204280849Scy INIT_LIST(newtable[i]); 205280849Scy 206280849Scy for (i = 0; i < symtab->size; i++) { 207280849Scy elt_t *elt, *nelt; 208280849Scy 209280849Scy for (elt = HEAD(symtab->table[i]); elt != NULL; elt = nelt) { 210280849Scy unsigned int hv; 211280849Scy 212280849Scy nelt = NEXT(elt, link); 213280849Scy 214280849Scy UNLINK(symtab->table[i], elt, link); 215280849Scy hv = hash(elt->key, symtab->case_sensitive); 216280849Scy APPEND(newtable[hv % newsize], elt, link); 217280849Scy } 218280849Scy } 219280849Scy 220280849Scy isc_mem_put(symtab->mctx, symtab->table, 221280849Scy symtab->size * sizeof(eltlist_t)); 222280849Scy 223280849Scy symtab->table = newtable; 224280849Scy symtab->size = newsize; 225280849Scy symtab->maxload = newmax; 226280849Scy} 227280849Scy 228258945Srobertoisc_result_t 229258945Srobertoisc_symtab_define(isc_symtab_t *symtab, const char *key, unsigned int type, 230258945Sroberto isc_symvalue_t value, isc_symexists_t exists_policy) 231258945Sroberto{ 232258945Sroberto unsigned int bucket; 233258945Sroberto elt_t *elt; 234258945Sroberto 235258945Sroberto REQUIRE(VALID_SYMTAB(symtab)); 236258945Sroberto REQUIRE(key != NULL); 237258945Sroberto REQUIRE(type != 0); 238258945Sroberto 239258945Sroberto FIND(symtab, key, type, bucket, elt); 240258945Sroberto 241258945Sroberto if (exists_policy != isc_symexists_add && elt != NULL) { 242258945Sroberto if (exists_policy == isc_symexists_reject) 243258945Sroberto return (ISC_R_EXISTS); 244258945Sroberto INSIST(exists_policy == isc_symexists_replace); 245258945Sroberto UNLINK(symtab->table[bucket], elt, link); 246258945Sroberto if (symtab->undefine_action != NULL) 247258945Sroberto (symtab->undefine_action)(elt->key, elt->type, 248258945Sroberto elt->value, 249258945Sroberto symtab->undefine_arg); 250258945Sroberto } else { 251258945Sroberto elt = (elt_t *)isc_mem_get(symtab->mctx, sizeof(*elt)); 252258945Sroberto if (elt == NULL) 253258945Sroberto return (ISC_R_NOMEMORY); 254258945Sroberto ISC_LINK_INIT(elt, link); 255280849Scy symtab->count++; 256258945Sroberto } 257258945Sroberto 258258945Sroberto /* 259258945Sroberto * Though the "key" can be const coming in, it is not stored as const 260258945Sroberto * so that the calling program can easily have writable access to 261258945Sroberto * it in its undefine_action function. In the event that it *was* 262258945Sroberto * truly const coming in and then the caller modified it anyway ... 263258945Sroberto * well, don't do that! 264258945Sroberto */ 265258945Sroberto DE_CONST(key, elt->key); 266258945Sroberto elt->type = type; 267258945Sroberto elt->value = value; 268258945Sroberto 269258945Sroberto /* 270258945Sroberto * We prepend so that the most recent definition will be found. 271258945Sroberto */ 272258945Sroberto PREPEND(symtab->table[bucket], elt, link); 273258945Sroberto 274280849Scy if (symtab->count > symtab->maxload) 275280849Scy grow_table(symtab); 276280849Scy 277258945Sroberto return (ISC_R_SUCCESS); 278258945Sroberto} 279258945Sroberto 280258945Srobertoisc_result_t 281258945Srobertoisc_symtab_undefine(isc_symtab_t *symtab, const char *key, unsigned int type) { 282258945Sroberto unsigned int bucket; 283258945Sroberto elt_t *elt; 284258945Sroberto 285258945Sroberto REQUIRE(VALID_SYMTAB(symtab)); 286258945Sroberto REQUIRE(key != NULL); 287258945Sroberto 288258945Sroberto FIND(symtab, key, type, bucket, elt); 289258945Sroberto 290258945Sroberto if (elt == NULL) 291258945Sroberto return (ISC_R_NOTFOUND); 292258945Sroberto 293258945Sroberto if (symtab->undefine_action != NULL) 294258945Sroberto (symtab->undefine_action)(elt->key, elt->type, 295258945Sroberto elt->value, symtab->undefine_arg); 296258945Sroberto UNLINK(symtab->table[bucket], elt, link); 297258945Sroberto isc_mem_put(symtab->mctx, elt, sizeof(*elt)); 298280849Scy symtab->count--; 299258945Sroberto 300258945Sroberto return (ISC_R_SUCCESS); 301258945Sroberto} 302