Change the kernel dev_t, representing a pointer to a specinfo structure,
[dragonfly.git] / contrib / bind-9.2.4rc7 / lib / isccc / symtab.c
1 /*
2  * Portions Copyright (C) 2004  Internet Systems Consortium, Inc. ("ISC")
3  * Portions Copyright (C) 2001  Internet Software Consortium.
4  * Portions Copyright (C) 2001  Nominum, Inc.
5  *
6  * Permission to use, copy, modify, and distribute this software for any
7  * purpose with or without fee is hereby granted, provided that the above
8  * copyright notice and this permission notice appear in all copies.
9  *
10  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC AND NOMINUM DISCLAIMS ALL
11  * WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES
12  * OF MERCHANTABILITY AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY
13  * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17  */
18
19 /* $Id: symtab.c,v 1.3.2.1 2004/03/09 06:12:26 marka Exp $ */
20
21 #include <config.h>
22
23 #include <ctype.h>
24 #include <stdlib.h>
25 #include <string.h>
26
27 #include <isc/assertions.h>
28 #include <isc/magic.h>
29
30 #include <isccc/result.h>
31 #include <isccc/symtab.h>
32 #include <isccc/util.h>
33
34 typedef struct elt {
35         char *                          key;
36         unsigned int                    type;
37         isccc_symvalue_t                        value;
38         ISC_LINK(struct elt)            link;
39 } elt_t;
40
41 typedef ISC_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 isccc_symtab {
47         unsigned int                    magic;
48         unsigned int                    size;
49         eltlist_t *                     table;
50         isccc_symtabundefaction_t               undefine_action;
51         void *                          undefine_arg;
52         isc_boolean_t                   case_sensitive;
53 };
54
55 isc_result_t
56 isccc_symtab_create(unsigned int size,
57                   isccc_symtabundefaction_t undefine_action,
58                   void *undefine_arg,
59                   isc_boolean_t case_sensitive,
60                   isccc_symtab_t **symtabp)
61 {
62         isccc_symtab_t *symtab;
63         unsigned int i;
64
65         REQUIRE(symtabp != NULL && *symtabp == NULL);
66         REQUIRE(size > 0);      /* Should be prime. */
67
68         symtab = malloc(sizeof *symtab);
69         if (symtab == NULL)
70                 return (ISC_R_NOMEMORY);
71         symtab->table = malloc(size * sizeof (eltlist_t));
72         if (symtab->table == NULL) {
73                 free(symtab);
74                 return (ISC_R_NOMEMORY);
75         }
76         for (i = 0; i < size; i++)
77                 ISC_LIST_INIT(symtab->table[i]);
78         symtab->size = size;
79         symtab->undefine_action = undefine_action;
80         symtab->undefine_arg = undefine_arg;
81         symtab->case_sensitive = case_sensitive;
82         symtab->magic = SYMTAB_MAGIC;
83
84         *symtabp = symtab;
85
86         return (ISC_R_SUCCESS);
87 }
88
89 static inline void
90 free_elt(isccc_symtab_t *symtab, unsigned int bucket, elt_t *elt) {
91         ISC_LIST_UNLINK(symtab->table[bucket], elt, link);
92         if (symtab->undefine_action != NULL)
93                 (symtab->undefine_action)(elt->key, elt->type, elt->value,
94                                           symtab->undefine_arg);
95         free(elt);
96 }
97
98 void
99 isccc_symtab_destroy(isccc_symtab_t **symtabp) {
100         isccc_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 = ISC_LIST_HEAD(symtab->table[i]);
110                      elt != NULL;
111                      elt = nelt) {
112                         nelt = ISC_LIST_NEXT(elt, link);
113                         free_elt(symtab, i, elt);
114                 }
115         }
116         free(symtab->table);
117         symtab->magic = 0;
118         free(symtab);
119
120         *symtabp = NULL;
121 }
122
123 static inline unsigned int
124 hash(const char *key, isc_boolean_t case_sensitive) {
125         const char *s;
126         unsigned int h = 0;
127         unsigned int g;
128         int c;
129
130         /*
131          * P. J. Weinberger's hash function, adapted from p. 436 of
132          * _Compilers: Principles, Techniques, and Tools_, Aho, Sethi
133          * and Ullman, Addison-Wesley, 1986, ISBN 0-201-10088-6.
134          */
135
136         if (case_sensitive) {
137                 for (s = key; *s != '\0'; s++) {
138                         h = ( h << 4 ) + *s;
139                         if ((g = ( h & 0xf0000000 )) != 0) {
140                                 h = h ^ (g >> 24);
141                                 h = h ^ g;
142                         }
143                 }
144         } else {
145                 for (s = key; *s != '\0'; s++) {
146                         c = *s;
147                         c = tolower((unsigned char)c);
148                         h = ( h << 4 ) + c;
149                         if ((g = ( h & 0xf0000000 )) != 0) {
150                                 h = h ^ (g >> 24);
151                                 h = h ^ g;
152                         }
153                 }
154         }
155
156         return (h);
157 }
158
159 #define FIND(s, k, t, b, e) \
160         b = hash((k), (s)->case_sensitive) % (s)->size; \
161         if ((s)->case_sensitive) { \
162                 for (e = ISC_LIST_HEAD((s)->table[b]); \
163                      e != NULL; \
164                      e = ISC_LIST_NEXT(e, link)) { \
165                         if (((t) == 0 || e->type == (t)) && \
166                             strcmp(e->key, (k)) == 0) \
167                                 break; \
168                 } \
169         } else { \
170                 for (e = ISC_LIST_HEAD((s)->table[b]); \
171                      e != NULL; \
172                      e = ISC_LIST_NEXT(e, link)) { \
173                         if (((t) == 0 || e->type == (t)) && \
174                             strcasecmp(e->key, (k)) == 0) \
175                                 break; \
176                 } \
177         }
178
179 isc_result_t
180 isccc_symtab_lookup(isccc_symtab_t *symtab, const char *key, unsigned int type,
181                   isccc_symvalue_t *value)
182 {
183         unsigned int bucket;
184         elt_t *elt;
185
186         REQUIRE(VALID_SYMTAB(symtab));
187         REQUIRE(key != NULL);
188
189         FIND(symtab, key, type, bucket, elt);
190
191         if (elt == NULL)
192                 return (ISC_R_NOTFOUND);
193
194         if (value != NULL)
195                 *value = elt->value;
196
197         return (ISC_R_SUCCESS);
198 }
199
200 isc_result_t
201 isccc_symtab_define(isccc_symtab_t *symtab, char *key, unsigned int type,
202                   isccc_symvalue_t value, isccc_symexists_t exists_policy)
203 {
204         unsigned int bucket;
205         elt_t *elt;
206
207         REQUIRE(VALID_SYMTAB(symtab));
208         REQUIRE(key != NULL);
209         REQUIRE(type != 0);
210
211         FIND(symtab, key, type, bucket, elt);
212
213         if (exists_policy != isccc_symexists_add && elt != NULL) {
214                 if (exists_policy == isccc_symexists_reject)
215                         return (ISC_R_EXISTS);
216                 INSIST(exists_policy == isccc_symexists_replace);
217                 ISC_LIST_UNLINK(symtab->table[bucket], elt, link);
218                 if (symtab->undefine_action != NULL)
219                         (symtab->undefine_action)(elt->key, elt->type,
220                                                   elt->value,
221                                                   symtab->undefine_arg);
222         } else {
223                 elt = malloc(sizeof *elt);
224                 if (elt == NULL)
225                         return (ISC_R_NOMEMORY);
226                 ISC_LINK_INIT(elt, link);
227         }
228
229         elt->key = key;
230         elt->type = type;
231         elt->value = value;
232
233         /*
234          * We prepend so that the most recent definition will be found.
235          */
236         ISC_LIST_PREPEND(symtab->table[bucket], elt, link);
237
238         return (ISC_R_SUCCESS);
239 }
240
241 isc_result_t
242 isccc_symtab_undefine(isccc_symtab_t *symtab, const char *key, unsigned int type) {
243         unsigned int bucket;
244         elt_t *elt;
245
246         REQUIRE(VALID_SYMTAB(symtab));
247         REQUIRE(key != NULL);
248
249         FIND(symtab, key, type, bucket, elt);
250
251         if (elt == NULL)
252                 return (ISC_R_NOTFOUND);
253
254         free_elt(symtab, bucket, elt);
255
256         return (ISC_R_SUCCESS);
257 }
258
259 void
260 isccc_symtab_foreach(isccc_symtab_t *symtab, isccc_symtabforeachaction_t action,
261                    void *arg)
262 {
263         unsigned int i;
264         elt_t *elt, *nelt;
265
266         REQUIRE(VALID_SYMTAB(symtab));
267         REQUIRE(action != NULL);
268
269         for (i = 0; i < symtab->size; i++) {
270                 for (elt = ISC_LIST_HEAD(symtab->table[i]);
271                      elt != NULL;
272                      elt = nelt) {
273                         nelt = ISC_LIST_NEXT(elt, link);
274                         if ((action)(elt->key, elt->type, elt->value, arg))
275                                 free_elt(symtab, i, elt);
276                 }
277         }
278 }