2 * Portions Copyright (C) 2004, 2005, 2007 Internet Systems Consortium, Inc. ("ISC")
3 * Portions Copyright (C) 2001 Internet Software Consortium.
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.
9 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC AND NOMINUM DISCLAIMS ALL
10 * WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES
11 * OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY
12 * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 * Portions Copyright (C) 2001 Nominum, Inc.
19 * Permission to use, copy, modify, and/or distribute this software for any
20 * purpose with or without fee is hereby granted, provided that the above
21 * copyright notice and this permission notice appear in all copies.
23 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC AND NOMINUM DISCLAIMS ALL
24 * WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES
25 * OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY
26 * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
27 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
28 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
29 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
32 /* $Id: symtab.c,v 1.11 2007/09/13 04:45:18 each Exp $ */
41 #include <isc/assertions.h>
42 #include <isc/magic.h>
43 #include <isc/string.h>
45 #include <isccc/result.h>
46 #include <isccc/symtab.h>
47 #include <isccc/util.h>
52 isccc_symvalue_t value
;
53 ISC_LINK(struct elt
) link
;
56 typedef ISC_LIST(elt_t
) eltlist_t
;
58 #define SYMTAB_MAGIC ISC_MAGIC('S', 'y', 'm', 'T')
59 #define VALID_SYMTAB(st) ISC_MAGIC_VALID(st, SYMTAB_MAGIC)
65 isccc_symtabundefaction_t undefine_action
;
67 isc_boolean_t case_sensitive
;
71 isccc_symtab_create(unsigned int size
,
72 isccc_symtabundefaction_t undefine_action
,
74 isc_boolean_t case_sensitive
,
75 isccc_symtab_t
**symtabp
)
77 isccc_symtab_t
*symtab
;
80 REQUIRE(symtabp
!= NULL
&& *symtabp
== NULL
);
81 REQUIRE(size
> 0); /* Should be prime. */
83 symtab
= malloc(sizeof(*symtab
));
85 return (ISC_R_NOMEMORY
);
86 symtab
->table
= malloc(size
* sizeof(eltlist_t
));
87 if (symtab
->table
== NULL
) {
89 return (ISC_R_NOMEMORY
);
91 for (i
= 0; i
< size
; i
++)
92 ISC_LIST_INIT(symtab
->table
[i
]);
94 symtab
->undefine_action
= undefine_action
;
95 symtab
->undefine_arg
= undefine_arg
;
96 symtab
->case_sensitive
= case_sensitive
;
97 symtab
->magic
= SYMTAB_MAGIC
;
101 return (ISC_R_SUCCESS
);
105 free_elt(isccc_symtab_t
*symtab
, unsigned int bucket
, elt_t
*elt
) {
106 ISC_LIST_UNLINK(symtab
->table
[bucket
], elt
, link
);
107 if (symtab
->undefine_action
!= NULL
)
108 (symtab
->undefine_action
)(elt
->key
, elt
->type
, elt
->value
,
109 symtab
->undefine_arg
);
114 isccc_symtab_destroy(isccc_symtab_t
**symtabp
) {
115 isccc_symtab_t
*symtab
;
119 REQUIRE(symtabp
!= NULL
);
121 REQUIRE(VALID_SYMTAB(symtab
));
123 for (i
= 0; i
< symtab
->size
; i
++) {
124 for (elt
= ISC_LIST_HEAD(symtab
->table
[i
]);
127 nelt
= ISC_LIST_NEXT(elt
, link
);
128 free_elt(symtab
, i
, elt
);
138 static inline unsigned int
139 hash(const char *key
, isc_boolean_t case_sensitive
) {
146 * P. J. Weinberger's hash function, adapted from p. 436 of
147 * _Compilers: Principles, Techniques, and Tools_, Aho, Sethi
148 * and Ullman, Addison-Wesley, 1986, ISBN 0-201-10088-6.
151 if (case_sensitive
) {
152 for (s
= key
; *s
!= '\0'; s
++) {
154 if ((g
= ( h
& 0xf0000000 )) != 0) {
160 for (s
= key
; *s
!= '\0'; s
++) {
162 c
= tolower((unsigned char)c
);
164 if ((g
= ( h
& 0xf0000000 )) != 0) {
174 #define FIND(s, k, t, b, e) \
175 b = hash((k), (s)->case_sensitive) % (s)->size; \
176 if ((s)->case_sensitive) { \
177 for (e = ISC_LIST_HEAD((s)->table[b]); \
179 e = ISC_LIST_NEXT(e, link)) { \
180 if (((t) == 0 || e->type == (t)) && \
181 strcmp(e->key, (k)) == 0) \
185 for (e = ISC_LIST_HEAD((s)->table[b]); \
187 e = ISC_LIST_NEXT(e, link)) { \
188 if (((t) == 0 || e->type == (t)) && \
189 strcasecmp(e->key, (k)) == 0) \
195 isccc_symtab_lookup(isccc_symtab_t
*symtab
, const char *key
, unsigned int type
,
196 isccc_symvalue_t
*value
)
201 REQUIRE(VALID_SYMTAB(symtab
));
202 REQUIRE(key
!= NULL
);
204 FIND(symtab
, key
, type
, bucket
, elt
);
207 return (ISC_R_NOTFOUND
);
212 return (ISC_R_SUCCESS
);
216 isccc_symtab_define(isccc_symtab_t
*symtab
, char *key
, unsigned int type
,
217 isccc_symvalue_t value
, isccc_symexists_t exists_policy
)
222 REQUIRE(VALID_SYMTAB(symtab
));
223 REQUIRE(key
!= NULL
);
226 FIND(symtab
, key
, type
, bucket
, elt
);
228 if (exists_policy
!= isccc_symexists_add
&& elt
!= NULL
) {
229 if (exists_policy
== isccc_symexists_reject
)
230 return (ISC_R_EXISTS
);
231 INSIST(exists_policy
== isccc_symexists_replace
);
232 ISC_LIST_UNLINK(symtab
->table
[bucket
], elt
, link
);
233 if (symtab
->undefine_action
!= NULL
)
234 (symtab
->undefine_action
)(elt
->key
, elt
->type
,
236 symtab
->undefine_arg
);
238 elt
= malloc(sizeof(*elt
));
240 return (ISC_R_NOMEMORY
);
241 ISC_LINK_INIT(elt
, link
);
249 * We prepend so that the most recent definition will be found.
251 ISC_LIST_PREPEND(symtab
->table
[bucket
], elt
, link
);
253 return (ISC_R_SUCCESS
);
257 isccc_symtab_undefine(isccc_symtab_t
*symtab
, const char *key
, unsigned int type
) {
261 REQUIRE(VALID_SYMTAB(symtab
));
262 REQUIRE(key
!= NULL
);
264 FIND(symtab
, key
, type
, bucket
, elt
);
267 return (ISC_R_NOTFOUND
);
269 free_elt(symtab
, bucket
, elt
);
271 return (ISC_R_SUCCESS
);
275 isccc_symtab_foreach(isccc_symtab_t
*symtab
, isccc_symtabforeachaction_t action
,
281 REQUIRE(VALID_SYMTAB(symtab
));
282 REQUIRE(action
!= NULL
);
284 for (i
= 0; i
< symtab
->size
; i
++) {
285 for (elt
= ISC_LIST_HEAD(symtab
->table
[i
]);
288 nelt
= ISC_LIST_NEXT(elt
, link
);
289 if ((action
)(elt
->key
, elt
->type
, elt
->value
, arg
))
290 free_elt(symtab
, i
, elt
);