1 /* $OpenBSD$ */
2
3 /*
4 * Copyright (c) 2012 Gilles Chehade <gilles@poolp.org>
5 * Copyright (c) 2012 Eric Faurot <eric@openbsd.org>
6 *
7 * Permission to use, copy, modify, and 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 THE AUTHOR DISCLAIMS ALL WARRANTIES
12 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
14 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
17 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
18 */
19
20 #include <sys/types.h>
21 #include <sys/tree.h>
22
23 #include <err.h>
24 #include <stdio.h>
25 #include <stdlib.h>
26 #include <string.h>
27
28 #include <smtpd-api.h>
29
30 struct dictentry {
31 SPLAY_ENTRY(dictentry) entry;
32 const char *key;
33 void *data;
34 };
35
36 static int dictentry_cmp(struct dictentry *, struct dictentry *);
37
38 SPLAY_PROTOTYPE(_dict, dictentry, entry, dictentry_cmp);
39
40 int
dict_check(struct dict * d,const char * k)41 dict_check(struct dict *d, const char *k)
42 {
43 struct dictentry key;
44
45 key.key = k;
46 return (SPLAY_FIND(_dict, &d->dict, &key) != NULL);
47 }
48
49 static inline struct dictentry *
dict_alloc(const char * k,void * data)50 dict_alloc(const char *k, void *data)
51 {
52 struct dictentry *e;
53 size_t s = strlen(k) + 1;
54 void *t;
55
56 if ((e = malloc(sizeof(*e) + s)) == NULL)
57 return NULL;
58
59 e->key = t = (char*)(e) + sizeof(*e);
60 e->data = data;
61 memmove(t, k, s);
62
63 return (e);
64 }
65
66 void *
dict_set(struct dict * d,const char * k,void * data)67 dict_set(struct dict *d, const char *k, void *data)
68 {
69 struct dictentry *entry, key;
70 char *old;
71
72 key.key = k;
73 if ((entry = SPLAY_FIND(_dict, &d->dict, &key)) == NULL) {
74 if ((entry = dict_alloc(k, data)) == NULL)
75 err(1, "dict_set: malloc");
76 SPLAY_INSERT(_dict, &d->dict, entry);
77 old = NULL;
78 d->count += 1;
79 } else {
80 old = entry->data;
81 entry->data = data;
82 }
83
84 return (old);
85 }
86
87 void
dict_xset(struct dict * d,const char * k,void * data)88 dict_xset(struct dict *d, const char * k, void *data)
89 {
90 struct dictentry *entry;
91
92 if ((entry = dict_alloc(k, data)) == NULL)
93 err(1, "dict_xset: malloc");
94 if (SPLAY_INSERT(_dict, &d->dict, entry))
95 errx(1, "dict_xset(%p, %s)", d, k);
96 d->count += 1;
97 }
98
99 void *
dict_get(struct dict * d,const char * k)100 dict_get(struct dict *d, const char *k)
101 {
102 struct dictentry key, *entry;
103
104 key.key = k;
105 if ((entry = SPLAY_FIND(_dict, &d->dict, &key)) == NULL)
106 return (NULL);
107
108 return (entry->data);
109 }
110
111 void *
dict_xget(struct dict * d,const char * k)112 dict_xget(struct dict *d, const char *k)
113 {
114 struct dictentry key, *entry;
115
116 key.key = k;
117 if ((entry = SPLAY_FIND(_dict, &d->dict, &key)) == NULL)
118 errx(1, "dict_xget(%p, %s)", d, k);
119
120 return (entry->data);
121 }
122
123 void *
dict_pop(struct dict * d,const char * k)124 dict_pop(struct dict *d, const char *k)
125 {
126 struct dictentry key, *entry;
127 void *data;
128
129 key.key = k;
130 if ((entry = SPLAY_FIND(_dict, &d->dict, &key)) == NULL)
131 return (NULL);
132
133 data = entry->data;
134 SPLAY_REMOVE(_dict, &d->dict, entry);
135 free(entry);
136 d->count -= 1;
137
138 return (data);
139 }
140
141 void *
dict_xpop(struct dict * d,const char * k)142 dict_xpop(struct dict *d, const char *k)
143 {
144 struct dictentry key, *entry;
145 void *data;
146
147 key.key = k;
148 if ((entry = SPLAY_FIND(_dict, &d->dict, &key)) == NULL)
149 errx(1, "dict_xpop(%p, %s)", d, k);
150
151 data = entry->data;
152 SPLAY_REMOVE(_dict, &d->dict, entry);
153 free(entry);
154 d->count -= 1;
155
156 return (data);
157 }
158
159 int
dict_poproot(struct dict * d,void ** data)160 dict_poproot(struct dict *d, void **data)
161 {
162 struct dictentry *entry;
163
164 entry = SPLAY_ROOT(&d->dict);
165 if (entry == NULL)
166 return (0);
167 if (data)
168 *data = entry->data;
169 SPLAY_REMOVE(_dict, &d->dict, entry);
170 free(entry);
171 d->count -= 1;
172
173 return (1);
174 }
175
176 int
dict_root(struct dict * d,const char ** k,void ** data)177 dict_root(struct dict *d, const char **k, void **data)
178 {
179 struct dictentry *entry;
180
181 entry = SPLAY_ROOT(&d->dict);
182 if (entry == NULL)
183 return (0);
184 if (k)
185 *k = entry->key;
186 if (data)
187 *data = entry->data;
188 return (1);
189 }
190
191 int
dict_iter(struct dict * d,void ** hdl,const char ** k,void ** data)192 dict_iter(struct dict *d, void **hdl, const char **k, void **data)
193 {
194 struct dictentry *curr = *hdl;
195
196 if (curr == NULL)
197 curr = SPLAY_MIN(_dict, &d->dict);
198 else
199 curr = SPLAY_NEXT(_dict, &d->dict, curr);
200
201 if (curr) {
202 *hdl = curr;
203 if (k)
204 *k = curr->key;
205 if (data)
206 *data = curr->data;
207 return (1);
208 }
209
210 return (0);
211 }
212
213 int
dict_iterfrom(struct dict * d,void ** hdl,const char * kfrom,const char ** k,void ** data)214 dict_iterfrom(struct dict *d, void **hdl, const char *kfrom, const char **k,
215 void **data)
216 {
217 struct dictentry *curr = *hdl, key;
218
219 if (curr == NULL) {
220 if (kfrom == NULL)
221 curr = SPLAY_MIN(_dict, &d->dict);
222 else {
223 key.key = kfrom;
224 curr = SPLAY_FIND(_dict, &d->dict, &key);
225 if (curr == NULL) {
226 SPLAY_INSERT(_dict, &d->dict, &key);
227 curr = SPLAY_NEXT(_dict, &d->dict, &key);
228 SPLAY_REMOVE(_dict, &d->dict, &key);
229 }
230 }
231 } else
232 curr = SPLAY_NEXT(_dict, &d->dict, curr);
233
234 if (curr) {
235 *hdl = curr;
236 if (k)
237 *k = curr->key;
238 if (data)
239 *data = curr->data;
240 return (1);
241 }
242
243 return (0);
244 }
245
246 void
dict_merge(struct dict * dst,struct dict * src)247 dict_merge(struct dict *dst, struct dict *src)
248 {
249 struct dictentry *entry;
250
251 while (!SPLAY_EMPTY(&src->dict)) {
252 entry = SPLAY_ROOT(&src->dict);
253 SPLAY_REMOVE(_dict, &src->dict, entry);
254 if (SPLAY_INSERT(_dict, &dst->dict, entry))
255 errx(1, "dict_merge: duplicate");
256 }
257 dst->count += src->count;
258 src->count = 0;
259 }
260
261 static int
dictentry_cmp(struct dictentry * a,struct dictentry * b)262 dictentry_cmp(struct dictentry *a, struct dictentry *b)
263 {
264 return strcmp(a->key, b->key);
265 }
266
267 SPLAY_GENERATE(_dict, dictentry, entry, dictentry_cmp);
268