1 /*
2 * Copyright (C) Internet Systems Consortium, Inc. ("ISC")
3 *
4 * Permission to use, copy, modify, and/or distribute this software for any
5 * purpose with or without fee is hereby granted, provided that the above
6 * copyright notice and this permission notice appear in all copies.
7 *
8 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
9 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
10 * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
11 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
12 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
13 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
14 * PERFORMANCE OF THIS SOFTWARE.
15 */
16
17 /* $Id: symtab.c,v 1.6 2020/09/14 08:40:44 florian Exp $ */
18
19 /*! \file */
20
21 #include <ctype.h>
22 #include <stdlib.h>
23 #include <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 struct isc_symtab {
37 /* Unlocked. */
38 unsigned int size;
39 unsigned int count;
40 unsigned int maxload;
41 eltlist_t * table;
42 isc_symtabaction_t undefine_action;
43 void * undefine_arg;
44 int case_sensitive;
45 };
46
47 isc_result_t
isc_symtab_create(unsigned int size,isc_symtabaction_t undefine_action,void * undefine_arg,int case_sensitive,isc_symtab_t ** symtabp)48 isc_symtab_create(unsigned int size,
49 isc_symtabaction_t undefine_action,
50 void *undefine_arg,
51 int case_sensitive,
52 isc_symtab_t **symtabp)
53 {
54 isc_symtab_t *symtab;
55 unsigned int i;
56
57 REQUIRE(symtabp != NULL && *symtabp == NULL);
58 REQUIRE(size > 0); /* Should be prime. */
59
60 symtab = (isc_symtab_t *)malloc(sizeof(*symtab));
61 if (symtab == NULL)
62 return (ISC_R_NOMEMORY);
63
64 symtab->table = (eltlist_t *)reallocarray(NULL, size, sizeof(eltlist_t));
65 if (symtab->table == NULL) {
66 free(symtab);
67 return (ISC_R_NOMEMORY);
68 }
69 for (i = 0; i < size; i++)
70 INIT_LIST(symtab->table[i]);
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 *symtabp = symtab;
78 return (ISC_R_SUCCESS);
79 }
80
81 void
isc_symtab_destroy(isc_symtab_t ** symtabp)82 isc_symtab_destroy(isc_symtab_t **symtabp) {
83 isc_symtab_t *symtab;
84 unsigned int i;
85 elt_t *elt, *nelt;
86
87 REQUIRE(symtabp != NULL);
88 symtab = *symtabp;
89
90 for (i = 0; i < symtab->size; i++) {
91 for (elt = HEAD(symtab->table[i]); elt != NULL; elt = nelt) {
92 nelt = NEXT(elt, link);
93 if (symtab->undefine_action != NULL)
94 (symtab->undefine_action)(elt->key,
95 elt->type,
96 elt->value,
97 symtab->undefine_arg);
98 free(elt);
99 }
100 }
101 free(symtab->table);
102 free(symtab);
103 *symtabp = NULL;
104 }
105
106 static inline unsigned int
hash(const char * key,int case_sensitive)107 hash(const char *key, int case_sensitive) {
108 const char *s;
109 unsigned int h = 0;
110 int c;
111
112 /*
113 * This hash function is similar to the one Ousterhout
114 * uses in Tcl.
115 */
116
117 if (case_sensitive) {
118 for (s = key; *s != '\0'; s++) {
119 h += (h << 3) + *s;
120 }
121 } else {
122 for (s = key; *s != '\0'; s++) {
123 c = *s;
124 c = tolower((unsigned char)c);
125 h += (h << 3) + c;
126 }
127 }
128
129 return (h);
130 }
131
132 #define FIND(s, k, t, b, e) \
133 b = hash((k), (s)->case_sensitive) % (s)->size; \
134 if ((s)->case_sensitive) { \
135 for (e = HEAD((s)->table[b]); e != NULL; e = NEXT(e, link)) { \
136 if (((t) == 0 || e->type == (t)) && \
137 strcmp(e->key, (k)) == 0) \
138 break; \
139 } \
140 } else { \
141 for (e = HEAD((s)->table[b]); e != NULL; e = NEXT(e, link)) { \
142 if (((t) == 0 || e->type == (t)) && \
143 strcasecmp(e->key, (k)) == 0) \
144 break; \
145 } \
146 }
147
148 isc_result_t
isc_symtab_lookup(isc_symtab_t * symtab,const char * key,unsigned int type,isc_symvalue_t * value)149 isc_symtab_lookup(isc_symtab_t *symtab, const char *key, unsigned int type,
150 isc_symvalue_t *value)
151 {
152 unsigned int bucket;
153 elt_t *elt;
154
155 REQUIRE(key != NULL);
156
157 FIND(symtab, key, type, bucket, elt);
158
159 if (elt == NULL)
160 return (ISC_R_NOTFOUND);
161
162 if (value != NULL)
163 *value = elt->value;
164
165 return (ISC_R_SUCCESS);
166 }
167
168 static void
grow_table(isc_symtab_t * symtab)169 grow_table(isc_symtab_t *symtab) {
170 eltlist_t *newtable;
171 unsigned int i, newsize, newmax;
172
173 REQUIRE(symtab != NULL);
174
175 newsize = symtab->size * 2;
176 newmax = newsize * 3 / 4;
177 INSIST(newsize > 0U && newmax > 0U);
178
179 newtable = reallocarray(NULL, newsize, sizeof(eltlist_t));
180 if (newtable == NULL)
181 return;
182
183 for (i = 0; i < newsize; i++)
184 INIT_LIST(newtable[i]);
185
186 for (i = 0; i < symtab->size; i++) {
187 elt_t *elt, *nelt;
188
189 for (elt = HEAD(symtab->table[i]); elt != NULL; elt = nelt) {
190 unsigned int hv;
191
192 nelt = NEXT(elt, link);
193
194 UNLINK(symtab->table[i], elt, link);
195 hv = hash(elt->key, symtab->case_sensitive);
196 APPEND(newtable[hv % newsize], elt, link);
197 }
198 }
199
200 free(symtab->table);
201
202 symtab->table = newtable;
203 symtab->size = newsize;
204 symtab->maxload = newmax;
205 }
206
207 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)208 isc_symtab_define(isc_symtab_t *symtab, const char *key, unsigned int type,
209 isc_symvalue_t value, isc_symexists_t exists_policy)
210 {
211 unsigned int bucket;
212 elt_t *elt;
213
214 REQUIRE(key != NULL);
215 REQUIRE(type != 0);
216
217 FIND(symtab, key, type, bucket, elt);
218
219 if (exists_policy != isc_symexists_add && elt != NULL) {
220 if (exists_policy == isc_symexists_reject)
221 return (ISC_R_EXISTS);
222 INSIST(exists_policy == isc_symexists_replace);
223 UNLINK(symtab->table[bucket], elt, link);
224 if (symtab->undefine_action != NULL)
225 (symtab->undefine_action)(elt->key, elt->type,
226 elt->value,
227 symtab->undefine_arg);
228 } else {
229 elt = (elt_t *)malloc(sizeof(*elt));
230 if (elt == NULL)
231 return (ISC_R_NOMEMORY);
232 ISC_LINK_INIT(elt, link);
233 symtab->count++;
234 }
235
236 /*
237 * Though the "key" can be const coming in, it is not stored as const
238 * so that the calling program can easily have writable access to
239 * it in its undefine_action function. In the event that it *was*
240 * truly const coming in and then the caller modified it anyway ...
241 * well, don't do that!
242 */
243 DE_CONST(key, elt->key);
244 elt->type = type;
245 elt->value = value;
246
247 /*
248 * We prepend so that the most recent definition will be found.
249 */
250 PREPEND(symtab->table[bucket], elt, link);
251
252 if (symtab->count > symtab->maxload)
253 grow_table(symtab);
254
255 return (ISC_R_SUCCESS);
256 }
257