1/*	$NetBSD$	*/
2
3/*
4 * Copyright (C) 2004, 2005, 2007, 2011, 2012  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
34typedef struct elt {
35	char *				key;
36	unsigned int			type;
37	isc_symvalue_t			value;
38	LINK(struct elt)		link;
39} elt_t;
40
41typedef 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
46struct 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
59isc_result_t
60isc_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	symtab->table = (eltlist_t *)isc_mem_get(mctx,
77						 size * sizeof(eltlist_t));
78	if (symtab->table == NULL) {
79		isc_mem_put(mctx, symtab, sizeof(*symtab));
80		return (ISC_R_NOMEMORY);
81	}
82	for (i = 0; i < size; i++)
83		INIT_LIST(symtab->table[i]);
84	symtab->mctx = mctx;
85	symtab->size = size;
86	symtab->count = 0;
87	symtab->maxload = size * 3 / 4;
88	symtab->undefine_action = undefine_action;
89	symtab->undefine_arg = undefine_arg;
90	symtab->case_sensitive = case_sensitive;
91	symtab->magic = SYMTAB_MAGIC;
92
93	*symtabp = symtab;
94
95	return (ISC_R_SUCCESS);
96}
97
98void
99isc_symtab_destroy(isc_symtab_t **symtabp) {
100	isc_symtab_t *symtab;
101	unsigned int i;
102	elt_t *elt, *nelt;
103
104	REQUIRE(symtabp != NULL);
105	symtab = *symtabp;
106	REQUIRE(VALID_SYMTAB(symtab));
107
108	for (i = 0; i < symtab->size; i++) {
109		for (elt = HEAD(symtab->table[i]); elt != NULL; elt = nelt) {
110			nelt = NEXT(elt, link);
111			if (symtab->undefine_action != NULL)
112			       (symtab->undefine_action)(elt->key,
113							 elt->type,
114							 elt->value,
115							 symtab->undefine_arg);
116			isc_mem_put(symtab->mctx, elt, sizeof(*elt));
117		}
118	}
119	isc_mem_put(symtab->mctx, symtab->table,
120		    symtab->size * sizeof(eltlist_t));
121	symtab->magic = 0;
122	isc_mem_put(symtab->mctx, symtab, sizeof(*symtab));
123
124	*symtabp = NULL;
125}
126
127static inline unsigned int
128hash(const char *key, isc_boolean_t case_sensitive) {
129	const char *s;
130	unsigned int h = 0;
131	int c;
132
133	/*
134	 * This hash function is similar to the one Ousterhout
135	 * uses in Tcl.
136	 */
137
138	if (case_sensitive) {
139		for (s = key; *s != '\0'; s++) {
140			h += (h << 3) + *s;
141		}
142	} else {
143		for (s = key; *s != '\0'; s++) {
144			c = *s;
145			c = tolower((unsigned char)c);
146			h += (h << 3) + c;
147		}
148	}
149
150	return (h);
151}
152
153#define FIND(s, k, t, b, e) \
154	b = hash((k), (s)->case_sensitive) % (s)->size; \
155	if ((s)->case_sensitive) { \
156		for (e = HEAD((s)->table[b]); e != NULL; e = NEXT(e, link)) { \
157			if (((t) == 0 || e->type == (t)) && \
158			    strcmp(e->key, (k)) == 0) \
159				break; \
160		} \
161	} else { \
162		for (e = HEAD((s)->table[b]); e != NULL; e = NEXT(e, link)) { \
163			if (((t) == 0 || e->type == (t)) && \
164			    strcasecmp(e->key, (k)) == 0) \
165				break; \
166		} \
167	}
168
169isc_result_t
170isc_symtab_lookup(isc_symtab_t *symtab, const char *key, unsigned int type,
171		  isc_symvalue_t *value)
172{
173	unsigned int bucket;
174	elt_t *elt;
175
176	REQUIRE(VALID_SYMTAB(symtab));
177	REQUIRE(key != NULL);
178
179	FIND(symtab, key, type, bucket, elt);
180
181	if (elt == NULL)
182		return (ISC_R_NOTFOUND);
183
184	if (value != NULL)
185		*value = elt->value;
186
187	return (ISC_R_SUCCESS);
188}
189
190static void
191grow_table(isc_symtab_t *symtab) {
192	eltlist_t *newtable;
193	unsigned int i, newsize, newmax;
194
195	REQUIRE(symtab != NULL);
196
197	newsize = symtab->size * 2;
198	newmax = newsize * 3 / 4;
199	INSIST(newsize > 0U && newmax > 0U);
200
201	newtable = isc_mem_get(symtab->mctx, newsize * sizeof(eltlist_t));
202	if (newtable == NULL)
203		return;
204
205	for (i = 0; i < newsize; i++)
206		INIT_LIST(newtable[i]);
207
208	for (i = 0; i < symtab->size; i++) {
209		elt_t *elt, *nelt;
210
211		for (elt = HEAD(symtab->table[i]); elt != NULL; elt = nelt) {
212			unsigned int hv;
213
214			nelt = NEXT(elt, link);
215
216			UNLINK(symtab->table[i], elt, link);
217			hv = hash(elt->key, symtab->case_sensitive);
218			APPEND(newtable[hv % newsize], elt, link);
219		}
220	}
221
222	isc_mem_put(symtab->mctx, symtab->table,
223		    symtab->size * sizeof(eltlist_t));
224
225	symtab->table = newtable;
226	symtab->size = newsize;
227	symtab->maxload = newmax;
228}
229
230isc_result_t
231isc_symtab_define(isc_symtab_t *symtab, const char *key, unsigned int type,
232		  isc_symvalue_t value, isc_symexists_t exists_policy)
233{
234	unsigned int bucket;
235	elt_t *elt;
236
237	REQUIRE(VALID_SYMTAB(symtab));
238	REQUIRE(key != NULL);
239	REQUIRE(type != 0);
240
241	FIND(symtab, key, type, bucket, elt);
242
243	if (exists_policy != isc_symexists_add && elt != NULL) {
244		if (exists_policy == isc_symexists_reject)
245			return (ISC_R_EXISTS);
246		INSIST(exists_policy == isc_symexists_replace);
247		UNLINK(symtab->table[bucket], elt, link);
248		if (symtab->undefine_action != NULL)
249			(symtab->undefine_action)(elt->key, elt->type,
250						  elt->value,
251						  symtab->undefine_arg);
252	} else {
253		elt = (elt_t *)isc_mem_get(symtab->mctx, sizeof(*elt));
254		if (elt == NULL)
255			return (ISC_R_NOMEMORY);
256		ISC_LINK_INIT(elt, link);
257		symtab->count++;
258	}
259
260	/*
261	 * Though the "key" can be const coming in, it is not stored as const
262	 * so that the calling program can easily have writable access to
263	 * it in its undefine_action function.  In the event that it *was*
264	 * truly const coming in and then the caller modified it anyway ...
265	 * well, don't do that!
266	 */
267	DE_CONST(key, elt->key);
268	elt->type = type;
269	elt->value = value;
270
271	/*
272	 * We prepend so that the most recent definition will be found.
273	 */
274	PREPEND(symtab->table[bucket], elt, link);
275
276	if (symtab->count > symtab->maxload)
277		grow_table(symtab);
278
279	return (ISC_R_SUCCESS);
280}
281
282isc_result_t
283isc_symtab_undefine(isc_symtab_t *symtab, const char *key, unsigned int type) {
284	unsigned int bucket;
285	elt_t *elt;
286
287	REQUIRE(VALID_SYMTAB(symtab));
288	REQUIRE(key != NULL);
289
290	FIND(symtab, key, type, bucket, elt);
291
292	if (elt == NULL)
293		return (ISC_R_NOTFOUND);
294
295	if (symtab->undefine_action != NULL)
296		(symtab->undefine_action)(elt->key, elt->type,
297					  elt->value, symtab->undefine_arg);
298	UNLINK(symtab->table[bucket], elt, link);
299	isc_mem_put(symtab->mctx, elt, sizeof(*elt));
300	symtab->count--;
301
302	return (ISC_R_SUCCESS);
303}
304