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