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