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