1 /* $NetBSD: symtab.c,v 1.5 2021/02/19 16:42:19 christos Exp $ */ 2 3 /* 4 * Copyright (C) Internet Systems Consortium, Inc. ("ISC") 5 * 6 * This Source Code Form is subject to the terms of the Mozilla Public 7 * License, v. 2.0. If a copy of the MPL was not distributed with this 8 * file, you can obtain one at https://mozilla.org/MPL/2.0/. 9 * 10 * See the COPYRIGHT file distributed with this work for additional 11 * information regarding copyright ownership. 12 */ 13 14 /*! \file */ 15 16 #include <ctype.h> 17 #include <stdbool.h> 18 19 #include <isc/magic.h> 20 #include <isc/mem.h> 21 #include <isc/string.h> 22 #include <isc/symtab.h> 23 #include <isc/util.h> 24 25 typedef struct elt { 26 char *key; 27 unsigned int type; 28 isc_symvalue_t value; 29 LINK(struct elt) link; 30 } elt_t; 31 32 typedef LIST(elt_t) eltlist_t; 33 34 #define SYMTAB_MAGIC ISC_MAGIC('S', 'y', 'm', 'T') 35 #define VALID_SYMTAB(st) ISC_MAGIC_VALID(st, SYMTAB_MAGIC) 36 37 struct isc_symtab { 38 /* Unlocked. */ 39 unsigned int magic; 40 isc_mem_t *mctx; 41 unsigned int size; 42 unsigned int count; 43 unsigned int maxload; 44 eltlist_t *table; 45 isc_symtabaction_t undefine_action; 46 void *undefine_arg; 47 bool case_sensitive; 48 }; 49 50 isc_result_t 51 isc_symtab_create(isc_mem_t *mctx, unsigned int size, 52 isc_symtabaction_t undefine_action, void *undefine_arg, 53 bool case_sensitive, isc_symtab_t **symtabp) { 54 isc_symtab_t *symtab; 55 unsigned int i; 56 57 REQUIRE(mctx != NULL); 58 REQUIRE(symtabp != NULL && *symtabp == NULL); 59 REQUIRE(size > 0); /* Should be prime. */ 60 61 symtab = isc_mem_get(mctx, sizeof(*symtab)); 62 63 symtab->mctx = NULL; 64 isc_mem_attach(mctx, &symtab->mctx); 65 symtab->table = isc_mem_get(mctx, size * sizeof(eltlist_t)); 66 for (i = 0; i < size; i++) { 67 INIT_LIST(symtab->table[i]); 68 } 69 symtab->size = size; 70 symtab->count = 0; 71 symtab->maxload = size * 3 / 4; 72 symtab->undefine_action = undefine_action; 73 symtab->undefine_arg = undefine_arg; 74 symtab->case_sensitive = case_sensitive; 75 symtab->magic = SYMTAB_MAGIC; 76 77 *symtabp = symtab; 78 79 return (ISC_R_SUCCESS); 80 } 81 82 void 83 isc_symtab_destroy(isc_symtab_t **symtabp) { 84 isc_symtab_t *symtab; 85 unsigned int i; 86 elt_t *elt, *nelt; 87 88 REQUIRE(symtabp != NULL); 89 symtab = *symtabp; 90 *symtabp = NULL; 91 REQUIRE(VALID_SYMTAB(symtab)); 92 93 for (i = 0; i < symtab->size; i++) { 94 for (elt = HEAD(symtab->table[i]); elt != NULL; elt = nelt) { 95 nelt = NEXT(elt, link); 96 if (symtab->undefine_action != NULL) { 97 (symtab->undefine_action)(elt->key, elt->type, 98 elt->value, 99 symtab->undefine_arg); 100 } 101 isc_mem_put(symtab->mctx, elt, sizeof(*elt)); 102 } 103 } 104 isc_mem_put(symtab->mctx, symtab->table, 105 symtab->size * sizeof(eltlist_t)); 106 symtab->magic = 0; 107 isc_mem_putanddetach(&symtab->mctx, symtab, sizeof(*symtab)); 108 } 109 110 static inline unsigned int 111 hash(const char *key, bool case_sensitive) { 112 const char *s; 113 unsigned int h = 0; 114 int c; 115 116 /* 117 * This hash function is similar to the one Ousterhout 118 * uses in Tcl. 119 */ 120 121 if (case_sensitive) { 122 for (s = key; *s != '\0'; s++) { 123 h += (h << 3) + *s; 124 } 125 } else { 126 for (s = key; *s != '\0'; s++) { 127 c = *s; 128 c = tolower((unsigned char)c); 129 h += (h << 3) + c; 130 } 131 } 132 133 return (h); 134 } 135 136 #define FIND(s, k, t, b, e) \ 137 b = hash((k), (s)->case_sensitive) % (s)->size; \ 138 if ((s)->case_sensitive) { \ 139 for (e = HEAD((s)->table[b]); e != NULL; e = NEXT(e, link)) { \ 140 if (((t) == 0 || e->type == (t)) && \ 141 strcmp(e->key, (k)) == 0) \ 142 break; \ 143 } \ 144 } else { \ 145 for (e = HEAD((s)->table[b]); e != NULL; e = NEXT(e, link)) { \ 146 if (((t) == 0 || e->type == (t)) && \ 147 strcasecmp(e->key, (k)) == 0) \ 148 break; \ 149 } \ 150 } 151 152 isc_result_t 153 isc_symtab_lookup(isc_symtab_t *symtab, const char *key, unsigned int type, 154 isc_symvalue_t *value) { 155 unsigned int bucket; 156 elt_t *elt; 157 158 REQUIRE(VALID_SYMTAB(symtab)); 159 REQUIRE(key != NULL); 160 161 FIND(symtab, key, type, bucket, elt); 162 163 if (elt == NULL) { 164 return (ISC_R_NOTFOUND); 165 } 166 167 if (value != NULL) { 168 *value = elt->value; 169 } 170 171 return (ISC_R_SUCCESS); 172 } 173 174 static void 175 grow_table(isc_symtab_t *symtab) { 176 eltlist_t *newtable; 177 unsigned int i, newsize, newmax; 178 179 REQUIRE(symtab != NULL); 180 181 newsize = symtab->size * 2; 182 newmax = newsize * 3 / 4; 183 INSIST(newsize > 0U && newmax > 0U); 184 185 newtable = isc_mem_get(symtab->mctx, newsize * sizeof(eltlist_t)); 186 187 for (i = 0; i < newsize; i++) { 188 INIT_LIST(newtable[i]); 189 } 190 191 for (i = 0; i < symtab->size; i++) { 192 elt_t *elt, *nelt; 193 194 for (elt = HEAD(symtab->table[i]); elt != NULL; elt = nelt) { 195 unsigned int hv; 196 197 nelt = NEXT(elt, link); 198 199 UNLINK(symtab->table[i], elt, link); 200 hv = hash(elt->key, symtab->case_sensitive); 201 APPEND(newtable[hv % newsize], elt, link); 202 } 203 } 204 205 isc_mem_put(symtab->mctx, symtab->table, 206 symtab->size * sizeof(eltlist_t)); 207 208 symtab->table = newtable; 209 symtab->size = newsize; 210 symtab->maxload = newmax; 211 } 212 213 isc_result_t 214 isc_symtab_define(isc_symtab_t *symtab, const char *key, unsigned int type, 215 isc_symvalue_t value, isc_symexists_t exists_policy) { 216 unsigned int bucket; 217 elt_t *elt; 218 219 REQUIRE(VALID_SYMTAB(symtab)); 220 REQUIRE(key != NULL); 221 REQUIRE(type != 0); 222 223 FIND(symtab, key, type, bucket, elt); 224 225 if (exists_policy != isc_symexists_add && elt != NULL) { 226 if (exists_policy == isc_symexists_reject) { 227 return (ISC_R_EXISTS); 228 } 229 INSIST(exists_policy == isc_symexists_replace); 230 UNLINK(symtab->table[bucket], elt, link); 231 if (symtab->undefine_action != NULL) { 232 (symtab->undefine_action)(elt->key, elt->type, 233 elt->value, 234 symtab->undefine_arg); 235 } 236 } else { 237 elt = isc_mem_get(symtab->mctx, sizeof(*elt)); 238 ISC_LINK_INIT(elt, link); 239 symtab->count++; 240 } 241 242 /* 243 * Though the "key" can be const coming in, it is not stored as const 244 * so that the calling program can easily have writable access to 245 * it in its undefine_action function. In the event that it *was* 246 * truly const coming in and then the caller modified it anyway ... 247 * well, don't do that! 248 */ 249 DE_CONST(key, elt->key); 250 elt->type = type; 251 elt->value = value; 252 253 /* 254 * We prepend so that the most recent definition will be found. 255 */ 256 PREPEND(symtab->table[bucket], elt, link); 257 258 if (symtab->count > symtab->maxload) { 259 grow_table(symtab); 260 } 261 262 return (ISC_R_SUCCESS); 263 } 264 265 isc_result_t 266 isc_symtab_undefine(isc_symtab_t *symtab, const char *key, unsigned int type) { 267 unsigned int bucket; 268 elt_t *elt; 269 270 REQUIRE(VALID_SYMTAB(symtab)); 271 REQUIRE(key != NULL); 272 273 FIND(symtab, key, type, bucket, elt); 274 275 if (elt == NULL) { 276 return (ISC_R_NOTFOUND); 277 } 278 279 if (symtab->undefine_action != NULL) { 280 (symtab->undefine_action)(elt->key, elt->type, elt->value, 281 symtab->undefine_arg); 282 } 283 UNLINK(symtab->table[bucket], elt, link); 284 isc_mem_put(symtab->mctx, elt, sizeof(*elt)); 285 symtab->count--; 286 287 return (ISC_R_SUCCESS); 288 } 289 290 unsigned int 291 isc_symtab_count(isc_symtab_t *symtab) { 292 REQUIRE(VALID_SYMTAB(symtab)); 293 return (symtab->count); 294 } 295