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