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