]>
Commit | Line | Data |
---|---|---|
d76ed9a9 AS |
1 | /* dict-splay.c - Abstract dictionary type |
2 | * Copyright 2000-2004 srvx Development Team | |
3 | * | |
83ff05c3 | 4 | * This file is part of x3. |
d76ed9a9 | 5 | * |
d0f04f71 | 6 | * x3 is free software; you can redistribute it and/or modify |
d76ed9a9 | 7 | * it under the terms of the GNU General Public License as published by |
348683aa | 8 | * the Free Software Foundation; either version 3 of the License, or |
d76ed9a9 AS |
9 | * (at your option) any later version. |
10 | * | |
11 | * This program is distributed in the hope that it will be useful, | |
12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | * GNU General Public License for more details. | |
15 | */ | |
16 | ||
17 | #include "common.h" | |
18 | #include "dict.h" | |
19 | ||
20 | /* | |
21 | * Create new dictionary. | |
22 | */ | |
23 | dict_t | |
24 | dict_new(void) | |
25 | { | |
26 | dict_t dict = calloc(1, sizeof(*dict)); | |
27 | return dict; | |
28 | } | |
29 | ||
30 | /* | |
31 | * Return number of entries in the dictionary. | |
32 | */ | |
33 | unsigned int | |
34 | dict_size(dict_t dict) | |
35 | { | |
36 | return dict->count; | |
37 | } | |
38 | ||
39 | /* | |
40 | * Set the function to be called when freeing a key structure. | |
41 | * If the function is NULL, just forget about the pointer. | |
42 | */ | |
43 | void | |
44 | dict_set_free_keys(dict_t dict, free_f free_keys) | |
45 | { | |
46 | dict->free_keys = free_keys; | |
47 | } | |
48 | ||
49 | /* | |
50 | * Set the function to free data. | |
51 | * If the function is NULL, just forget about the pointer. | |
52 | */ | |
53 | void | |
54 | dict_set_free_data(dict_t dict, free_f free_data) | |
55 | { | |
56 | dict->free_data = free_data; | |
57 | } | |
58 | ||
59 | const char * | |
60 | dict_foreach(dict_t dict, dict_iterator_f it_f, void *extra) | |
61 | { | |
62 | dict_iterator_t it; | |
63 | ||
64 | for (it=dict_first(dict); it; it=iter_next(it)) { | |
65 | if (it_f(iter_key(it), iter_data(it), extra)) return iter_key(it); | |
66 | } | |
67 | return NULL; | |
68 | } | |
69 | ||
70 | /* | |
71 | * This function finds a node and pulls it to the top of the tree. | |
72 | * This helps balance the tree and auto-cache things you search for. | |
73 | */ | |
74 | static struct dict_node* | |
75 | dict_splay(struct dict_node *node, const char *key) | |
76 | { | |
77 | struct dict_node N, *l, *r, *y; | |
ec1a68c8 | 78 | int res; |
79 | ||
d76ed9a9 | 80 | if (!node) return NULL; |
cf945df8 | 81 | if (!key) return NULL; |
d76ed9a9 AS |
82 | N.l = N.r = NULL; |
83 | l = r = &N; | |
84 | ||
85 | while (1) { | |
ec1a68c8 | 86 | verify(node); |
87 | res = irccasecmp(key, node->key); | |
d76ed9a9 AS |
88 | if (!res) break; |
89 | if (res < 0) { | |
90 | if (!node->l) break; | |
91 | res = irccasecmp(key, node->l->key); | |
92 | if (res < 0) { | |
93 | y = node->l; | |
94 | node->l = y->r; | |
95 | y->r = node; | |
96 | node = y; | |
97 | if (!node->l) break; | |
98 | } | |
99 | r->l = node; | |
100 | r = node; | |
101 | node = node->l; | |
102 | } else { /* res > 0 */ | |
103 | if (!node->r) break; | |
104 | res = irccasecmp(key, node->r->key); | |
105 | if (res > 0) { | |
106 | y = node->r; | |
107 | node->r = y->l; | |
108 | y->l = node; | |
109 | node = y; | |
110 | if (!node->r) break; | |
111 | } | |
112 | l->r = node; | |
113 | l = node; | |
114 | node = node->r; | |
115 | } | |
116 | } | |
117 | l->r = node->l; | |
118 | r->l = node->r; | |
119 | node->l = N.r; | |
120 | node->r = N.l; | |
121 | return node; | |
122 | } | |
123 | ||
124 | /* | |
125 | * Free node. Free data/key using free_f functions. | |
126 | */ | |
127 | static void | |
128 | dict_dispose_node(struct dict_node *node, free_f free_keys, free_f free_data) | |
129 | { | |
ec1a68c8 | 130 | if (free_keys && node->key) { |
131 | if (free_keys == free) | |
132 | free((void*)node->key); | |
133 | else | |
134 | free_keys((void*)node->key); | |
135 | } | |
136 | if (free_data && node->data) { | |
137 | if (free_data == free) | |
138 | free(node->data); | |
139 | else | |
140 | free_data(node->data); | |
141 | } | |
d76ed9a9 AS |
142 | free(node); |
143 | } | |
144 | ||
145 | /* | |
146 | * Insert an entry into the dictionary. | |
147 | * Key ordering (and uniqueness) is determined by case-insensitive | |
148 | * string comparison. | |
149 | */ | |
150 | void | |
151 | dict_insert(dict_t dict, const char *key, void *data) | |
152 | { | |
153 | struct dict_node *new_node; | |
154 | if (!key) | |
155 | return; | |
ec1a68c8 | 156 | verify(dict); |
d76ed9a9 AS |
157 | new_node = malloc(sizeof(struct dict_node)); |
158 | new_node->key = key; | |
159 | new_node->data = data; | |
160 | if (dict->root) { | |
161 | int res; | |
162 | dict->root = dict_splay(dict->root, key); | |
163 | res = irccasecmp(key, dict->root->key); | |
164 | if (res < 0) { | |
165 | /* insert just "before" current root */ | |
166 | new_node->l = dict->root->l; | |
167 | new_node->r = dict->root; | |
168 | dict->root->l = NULL; | |
169 | if (dict->root->prev) { | |
170 | dict->root->prev->next = new_node; | |
171 | } else { | |
172 | dict->first = new_node; | |
173 | } | |
174 | new_node->prev = dict->root->prev; | |
175 | new_node->next = dict->root; | |
176 | dict->root->prev = new_node; | |
177 | dict->root = new_node; | |
178 | } else if (res > 0) { | |
179 | /* insert just "after" current root */ | |
180 | new_node->r = dict->root->r; | |
181 | new_node->l = dict->root; | |
182 | dict->root->r = NULL; | |
183 | if (dict->root->next) { | |
184 | dict->root->next->prev = new_node; | |
185 | } else { | |
186 | dict->last = new_node; | |
187 | } | |
188 | new_node->next = dict->root->next; | |
189 | new_node->prev = dict->root; | |
190 | dict->root->next = new_node; | |
191 | dict->root = new_node; | |
192 | } else { | |
193 | /* maybe we don't want to overwrite it .. oh well */ | |
ec1a68c8 | 194 | if (dict->free_data) { |
195 | if (dict->free_data == free) | |
196 | free(dict->root->data); | |
197 | else | |
198 | dict->free_data(dict->root->data); | |
199 | } | |
200 | if (dict->free_keys) { | |
201 | if (dict->free_keys == free) | |
202 | free((void*)dict->root->key); | |
203 | else | |
204 | dict->free_keys((void*)dict->root->key); | |
205 | } | |
d76ed9a9 AS |
206 | free(new_node); |
207 | dict->root->key = key; | |
208 | dict->root->data = data; | |
209 | /* decrement the count since we dropped the node */ | |
210 | dict->count--; | |
211 | } | |
212 | } else { | |
213 | new_node->l = new_node->r = NULL; | |
214 | new_node->next = new_node->prev = NULL; | |
215 | dict->root = dict->first = dict->last = new_node; | |
216 | } | |
217 | dict->count++; | |
218 | } | |
219 | ||
220 | /* | |
221 | * Remove an entry from the dictionary. | |
222 | * Return non-zero if it was found, or zero if the key was not in the | |
223 | * dictionary. | |
224 | */ | |
225 | int | |
226 | dict_remove2(dict_t dict, const char *key, int no_dispose) | |
227 | { | |
1117fc5a | 228 | struct dict_node *new_root, *old_root; |
d76ed9a9 AS |
229 | |
230 | if (!dict->root) | |
231 | return 0; | |
cf945df8 | 232 | if (!key) return 0; |
ec1a68c8 | 233 | verify(dict); |
d76ed9a9 AS |
234 | dict->root = dict_splay(dict->root, key); |
235 | if (irccasecmp(key, dict->root->key)) | |
236 | return 0; | |
237 | ||
238 | if (!dict->root->l) { | |
239 | new_root = dict->root->r; | |
240 | } else { | |
241 | new_root = dict_splay(dict->root->l, key); | |
242 | new_root->r = dict->root->r; | |
243 | } | |
244 | if (dict->root->prev) dict->root->prev->next = dict->root->next; | |
245 | if (dict->first == dict->root) dict->first = dict->first->next; | |
246 | if (dict->root->next) dict->root->next->prev = dict->root->prev; | |
247 | if (dict->last == dict->root) dict->last = dict->last->prev; | |
1117fc5a | 248 | old_root = dict->root; |
249 | dict->root = new_root; | |
250 | dict->count--; | |
d76ed9a9 | 251 | if (no_dispose) { |
1117fc5a | 252 | free(old_root); |
d76ed9a9 | 253 | } else { |
1117fc5a | 254 | dict_dispose_node(old_root, dict->free_keys, dict->free_data); |
d76ed9a9 | 255 | } |
d76ed9a9 AS |
256 | return 1; |
257 | } | |
258 | ||
259 | /* | |
260 | * Find an entry in the dictionary. | |
261 | * If "found" is non-NULL, set it to non-zero if the key was found. | |
262 | * Return the data associated with the key (or NULL if the key was | |
263 | * not found). | |
264 | */ | |
265 | void* | |
266 | dict_find(dict_t dict, const char *key, int *found) | |
267 | { | |
268 | int was_found; | |
269 | if (!dict || !dict->root || !key) { | |
270 | if (found) | |
271 | *found = 0; | |
272 | return NULL; | |
273 | } | |
ec1a68c8 | 274 | verify(dict); |
d76ed9a9 AS |
275 | dict->root = dict_splay(dict->root, key); |
276 | was_found = !irccasecmp(key, dict->root->key); | |
277 | if (found) | |
278 | *found = was_found; | |
279 | return was_found ? dict->root->data : NULL; | |
280 | } | |
281 | ||
282 | /* | |
283 | * Delete an entire dictionary. | |
284 | */ | |
285 | void | |
286 | dict_delete(dict_t dict) | |
287 | { | |
288 | dict_iterator_t it, next; | |
289 | if (!dict) | |
290 | return; | |
291 | for (it=dict_first(dict); it; it=next) { | |
292 | next = iter_next(it); | |
293 | dict_dispose_node(it, dict->free_keys, dict->free_data); | |
294 | } | |
295 | free(dict); | |
296 | } | |
297 | ||
298 | struct dict_sanity_struct { | |
299 | unsigned int node_count; | |
300 | struct dict_node *bad_node; | |
301 | char error[128]; | |
302 | }; | |
303 | ||
304 | static int | |
305 | dict_sanity_check_node(struct dict_node *node, struct dict_sanity_struct *dss) | |
306 | { | |
ec1a68c8 | 307 | verify(node); |
d76ed9a9 | 308 | if (!node->key) { |
1136f709 | 309 | snprintf(dss->error, sizeof(dss->error), "Node %p had null key", (void*)node); |
d76ed9a9 AS |
310 | return 1; |
311 | } | |
312 | if (node->l) { | |
313 | if (dict_sanity_check_node(node->l, dss)) return 1; | |
314 | if (irccasecmp(node->l->key, node->key) >= 0) { | |
1136f709 | 315 | snprintf(dss->error, sizeof(dss->error), "Node %p's left child's key '%s' >= its key '%s'", (void*)node, node->l->key, node->key); |
d76ed9a9 AS |
316 | return 1; |
317 | } | |
318 | } | |
319 | if (node->r) { | |
320 | if (dict_sanity_check_node(node->r, dss)) return 1; | |
321 | if (irccasecmp(node->key, node->r->key) >= 0) { | |
1136f709 | 322 | snprintf(dss->error, sizeof(dss->error), "Node %p's right child's key '%s' <= its key '%s'", (void*)node, node->r->key, node->key); |
d76ed9a9 AS |
323 | return 1; |
324 | } | |
325 | } | |
326 | dss->node_count++; | |
327 | return 0; | |
328 | } | |
329 | ||
330 | /* | |
331 | * Perform sanity checks on the dict's internal structure. | |
332 | */ | |
333 | char * | |
334 | dict_sanity_check(dict_t dict) | |
335 | { | |
336 | struct dict_sanity_struct dss; | |
337 | dss.node_count = 0; | |
338 | dss.bad_node = 0; | |
339 | dss.error[0] = 0; | |
ec1a68c8 | 340 | verify(dict); |
d76ed9a9 AS |
341 | if (dict->root && dict_sanity_check_node(dict->root, &dss)) { |
342 | return strdup(dss.error); | |
343 | } else if (dss.node_count != dict->count) { | |
344 | snprintf(dss.error, sizeof(dss.error), "Counted %d nodes but expected %d.", dss.node_count, dict->count); | |
345 | return strdup(dss.error); | |
346 | } else { | |
347 | return 0; | |
348 | } | |
349 | } |