1 /* $NetBSD: symtab.c,v 1.7 2023/01/25 21:43:32 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 <ctype.h> 35 #include <stdbool.h> 36 #include <stdlib.h> 37 38 #include <isc/assertions.h> 39 #include <isc/magic.h> 40 #include <isc/string.h> 41 42 #include <isccc/result.h> 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 = malloc(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 int c; 141 142 /* 143 * P. J. Weinberger's hash function, adapted from p. 436 of 144 * _Compilers: Principles, Techniques, and Tools_, Aho, Sethi 145 * and Ullman, Addison-Wesley, 1986, ISBN 0-201-10088-6. 146 */ 147 148 if (case_sensitive) { 149 for (s = key; *s != '\0'; s++) { 150 h = (h << 4) + *s; 151 if ((g = (h & 0xf0000000)) != 0) { 152 h = h ^ (g >> 24); 153 h = h ^ g; 154 } 155 } 156 } else { 157 for (s = key; *s != '\0'; s++) { 158 c = *s; 159 c = tolower((unsigned char)c); 160 h = (h << 4) + c; 161 if ((g = (h & 0xf0000000)) != 0) { 162 h = h ^ (g >> 24); 163 h = h ^ g; 164 } 165 } 166 } 167 168 return (h); 169 } 170 171 #define FIND(s, k, t, b, e) \ 172 b = hash((k), (s)->case_sensitive) % (s)->size; \ 173 if ((s)->case_sensitive) { \ 174 for (e = ISC_LIST_HEAD((s)->table[b]); e != NULL; \ 175 e = ISC_LIST_NEXT(e, link)) \ 176 { \ 177 if (((t) == 0 || e->type == (t)) && \ 178 strcmp(e->key, (k)) == 0) \ 179 break; \ 180 } \ 181 } else { \ 182 for (e = ISC_LIST_HEAD((s)->table[b]); e != NULL; \ 183 e = ISC_LIST_NEXT(e, link)) \ 184 { \ 185 if (((t) == 0 || e->type == (t)) && \ 186 strcasecmp(e->key, (k)) == 0) \ 187 break; \ 188 } \ 189 } 190 191 isc_result_t 192 isccc_symtab_lookup(isccc_symtab_t *symtab, const char *key, unsigned int type, 193 isccc_symvalue_t *value) { 194 unsigned int bucket; 195 elt_t *elt; 196 197 REQUIRE(VALID_SYMTAB(symtab)); 198 REQUIRE(key != NULL); 199 200 FIND(symtab, key, type, bucket, elt); 201 202 if (elt == NULL) { 203 return (ISC_R_NOTFOUND); 204 } 205 206 if (value != NULL) { 207 *value = elt->value; 208 } 209 210 return (ISC_R_SUCCESS); 211 } 212 213 isc_result_t 214 isccc_symtab_define(isccc_symtab_t *symtab, char *key, unsigned int type, 215 isccc_symvalue_t value, isccc_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 != isccc_symexists_add && elt != NULL) { 226 if (exists_policy == isccc_symexists_reject) { 227 return (ISC_R_EXISTS); 228 } 229 INSIST(exists_policy == isccc_symexists_replace); 230 ISC_LIST_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 = malloc(sizeof(*elt)); 238 if (elt == NULL) { 239 return (ISC_R_NOMEMORY); 240 } 241 ISC_LINK_INIT(elt, link); 242 } 243 244 elt->key = key; 245 elt->type = type; 246 elt->value = value; 247 248 /* 249 * We prepend so that the most recent definition will be found. 250 */ 251 ISC_LIST_PREPEND(symtab->table[bucket], elt, link); 252 253 return (ISC_R_SUCCESS); 254 } 255 256 isc_result_t 257 isccc_symtab_undefine(isccc_symtab_t *symtab, const char *key, 258 unsigned int type) { 259 unsigned int bucket; 260 elt_t *elt; 261 262 REQUIRE(VALID_SYMTAB(symtab)); 263 REQUIRE(key != NULL); 264 265 FIND(symtab, key, type, bucket, elt); 266 267 if (elt == NULL) { 268 return (ISC_R_NOTFOUND); 269 } 270 271 free_elt(symtab, bucket, elt); 272 273 return (ISC_R_SUCCESS); 274 } 275 276 void 277 isccc_symtab_foreach(isccc_symtab_t *symtab, isccc_symtabforeachaction_t action, 278 void *arg) { 279 unsigned int i; 280 elt_t *elt, *nelt; 281 282 REQUIRE(VALID_SYMTAB(symtab)); 283 REQUIRE(action != NULL); 284 285 for (i = 0; i < symtab->size; i++) { 286 for (elt = ISC_LIST_HEAD(symtab->table[i]); elt != NULL; 287 elt = nelt) 288 { 289 nelt = ISC_LIST_NEXT(elt, link); 290 if ((action)(elt->key, elt->type, elt->value, arg)) { 291 free_elt(symtab, i, elt); 292 } 293 } 294 } 295 } 296