1 /* $NetBSD: symtab.c,v 1.9 2025/01/26 16:25:44 christos Exp $ */ 2 3 /* 4 * Copyright (C) Internet Systems Consortium, Inc. ("ISC") 5 * 6 * SPDX-License-Identifier: MPL-2.0 AND ISC 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 /* 17 * Copyright (C) 2001 Nominum, Inc. 18 * 19 * Permission to use, copy, modify, and/or distribute this software for any 20 * purpose with or without fee is hereby granted, provided that the above 21 * copyright notice and this permission notice appear in all copies. 22 * 23 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC AND NOMINUM DISCLAIMS ALL 24 * WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES 25 * OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY 26 * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 27 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 28 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 29 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 30 */ 31 32 /*! \file */ 33 34 #include <stdbool.h> 35 #include <stdlib.h> 36 37 #include <isc/ascii.h> 38 #include <isc/assertions.h> 39 #include <isc/magic.h> 40 #include <isc/result.h> 41 #include <isc/string.h> 42 43 #include <isccc/symtab.h> 44 #include <isccc/util.h> 45 46 typedef struct elt { 47 char *key; 48 unsigned int type; 49 isccc_symvalue_t value; 50 ISC_LINK(struct elt) link; 51 } elt_t; 52 53 typedef ISC_LIST(elt_t) eltlist_t; 54 55 #define SYMTAB_MAGIC ISC_MAGIC('S', 'y', 'm', 'T') 56 #define VALID_SYMTAB(st) ISC_MAGIC_VALID(st, SYMTAB_MAGIC) 57 58 struct isccc_symtab { 59 unsigned int magic; 60 unsigned int size; 61 eltlist_t *table; 62 isccc_symtabundefaction_t undefine_action; 63 void *undefine_arg; 64 bool case_sensitive; 65 }; 66 67 isc_result_t 68 isccc_symtab_create(unsigned int size, 69 isccc_symtabundefaction_t undefine_action, 70 void *undefine_arg, bool case_sensitive, 71 isccc_symtab_t **symtabp) { 72 isccc_symtab_t *symtab; 73 unsigned int i; 74 75 REQUIRE(symtabp != NULL && *symtabp == NULL); 76 REQUIRE(size > 0); /* Should be prime. */ 77 78 symtab = malloc(sizeof(*symtab)); 79 if (symtab == NULL) { 80 return ISC_R_NOMEMORY; 81 } 82 symtab->table = calloc(size, sizeof(eltlist_t)); 83 if (symtab->table == NULL) { 84 free(symtab); 85 return ISC_R_NOMEMORY; 86 } 87 for (i = 0; i < size; i++) { 88 ISC_LIST_INIT(symtab->table[i]); 89 } 90 symtab->size = size; 91 symtab->undefine_action = undefine_action; 92 symtab->undefine_arg = undefine_arg; 93 symtab->case_sensitive = case_sensitive; 94 symtab->magic = SYMTAB_MAGIC; 95 96 *symtabp = symtab; 97 98 return ISC_R_SUCCESS; 99 } 100 101 static void 102 free_elt(isccc_symtab_t *symtab, unsigned int bucket, elt_t *elt) { 103 ISC_LIST_UNLINK(symtab->table[bucket], elt, link); 104 if (symtab->undefine_action != NULL) { 105 (symtab->undefine_action)(elt->key, elt->type, elt->value, 106 symtab->undefine_arg); 107 } 108 free(elt); 109 } 110 111 void 112 isccc_symtab_destroy(isccc_symtab_t **symtabp) { 113 isccc_symtab_t *symtab; 114 unsigned int i; 115 elt_t *elt, *nelt; 116 117 REQUIRE(symtabp != NULL); 118 symtab = *symtabp; 119 *symtabp = NULL; 120 REQUIRE(VALID_SYMTAB(symtab)); 121 122 for (i = 0; i < symtab->size; i++) { 123 for (elt = ISC_LIST_HEAD(symtab->table[i]); elt != NULL; 124 elt = nelt) 125 { 126 nelt = ISC_LIST_NEXT(elt, link); 127 free_elt(symtab, i, elt); 128 } 129 } 130 free(symtab->table); 131 symtab->magic = 0; 132 free(symtab); 133 } 134 135 static unsigned int 136 hash(const char *key, bool case_sensitive) { 137 const char *s; 138 unsigned int h = 0; 139 unsigned int g; 140 141 /* 142 * P. J. Weinberger's hash function, adapted from p. 436 of 143 * _Compilers: Principles, Techniques, and Tools_, Aho, Sethi 144 * and Ullman, Addison-Wesley, 1986, ISBN 0-201-10088-6. 145 */ 146 147 if (case_sensitive) { 148 for (s = key; *s != '\0'; s++) { 149 h = (h << 4) + *s; 150 if ((g = (h & 0xf0000000)) != 0) { 151 h = h ^ (g >> 24); 152 h = h ^ g; 153 } 154 } 155 } else { 156 for (s = key; *s != '\0'; s++) { 157 h = (h << 4) + isc_ascii_tolower(*s); 158 if ((g = (h & 0xf0000000)) != 0) { 159 h = h ^ (g >> 24); 160 h = h ^ g; 161 } 162 } 163 } 164 165 return h; 166 } 167 168 #define FIND(s, k, t, b, e) \ 169 b = hash((k), (s)->case_sensitive) % (s)->size; \ 170 if ((s)->case_sensitive) { \ 171 for (e = ISC_LIST_HEAD((s)->table[b]); e != NULL; \ 172 e = ISC_LIST_NEXT(e, link)) \ 173 { \ 174 if (((t) == 0 || e->type == (t)) && \ 175 strcmp(e->key, (k)) == 0) \ 176 break; \ 177 } \ 178 } else { \ 179 for (e = ISC_LIST_HEAD((s)->table[b]); e != NULL; \ 180 e = ISC_LIST_NEXT(e, link)) \ 181 { \ 182 if (((t) == 0 || e->type == (t)) && \ 183 strcasecmp(e->key, (k)) == 0) \ 184 break; \ 185 } \ 186 } 187 188 isc_result_t 189 isccc_symtab_lookup(isccc_symtab_t *symtab, const char *key, unsigned int type, 190 isccc_symvalue_t *value) { 191 unsigned int bucket; 192 elt_t *elt; 193 194 REQUIRE(VALID_SYMTAB(symtab)); 195 REQUIRE(key != NULL); 196 197 FIND(symtab, key, type, bucket, elt); 198 199 if (elt == NULL) { 200 return ISC_R_NOTFOUND; 201 } 202 203 SET_IF_NOT_NULL(value, elt->value); 204 205 return ISC_R_SUCCESS; 206 } 207 208 isc_result_t 209 isccc_symtab_define(isccc_symtab_t *symtab, char *key, unsigned int type, 210 isccc_symvalue_t value, isccc_symexists_t exists_policy) { 211 unsigned int bucket; 212 elt_t *elt; 213 214 REQUIRE(VALID_SYMTAB(symtab)); 215 REQUIRE(key != NULL); 216 REQUIRE(type != 0); 217 218 FIND(symtab, key, type, bucket, elt); 219 220 if (exists_policy != isccc_symexists_add && elt != NULL) { 221 if (exists_policy == isccc_symexists_reject) { 222 return ISC_R_EXISTS; 223 } 224 INSIST(exists_policy == isccc_symexists_replace); 225 ISC_LIST_UNLINK(symtab->table[bucket], elt, link); 226 if (symtab->undefine_action != NULL) { 227 (symtab->undefine_action)(elt->key, elt->type, 228 elt->value, 229 symtab->undefine_arg); 230 } 231 } else { 232 elt = malloc(sizeof(*elt)); 233 if (elt == NULL) { 234 return ISC_R_NOMEMORY; 235 } 236 ISC_LINK_INIT(elt, link); 237 } 238 239 elt->key = key; 240 elt->type = type; 241 elt->value = value; 242 243 /* 244 * We prepend so that the most recent definition will be found. 245 */ 246 ISC_LIST_PREPEND(symtab->table[bucket], elt, link); 247 248 return ISC_R_SUCCESS; 249 } 250 251 isc_result_t 252 isccc_symtab_undefine(isccc_symtab_t *symtab, const char *key, 253 unsigned int type) { 254 unsigned int bucket; 255 elt_t *elt; 256 257 REQUIRE(VALID_SYMTAB(symtab)); 258 REQUIRE(key != NULL); 259 260 FIND(symtab, key, type, bucket, elt); 261 262 if (elt == NULL) { 263 return ISC_R_NOTFOUND; 264 } 265 266 free_elt(symtab, bucket, elt); 267 268 return ISC_R_SUCCESS; 269 } 270 271 void 272 isccc_symtab_foreach(isccc_symtab_t *symtab, isccc_symtabforeachaction_t action, 273 void *arg) { 274 unsigned int i; 275 elt_t *elt, *nelt; 276 277 REQUIRE(VALID_SYMTAB(symtab)); 278 REQUIRE(action != NULL); 279 280 for (i = 0; i < symtab->size; i++) { 281 for (elt = ISC_LIST_HEAD(symtab->table[i]); elt != NULL; 282 elt = nelt) 283 { 284 nelt = ISC_LIST_NEXT(elt, link); 285 if ((action)(elt->key, elt->type, elt->value, arg)) { 286 free_elt(symtab, i, elt); 287 } 288 } 289 } 290 } 291