]>
Commit | Line | Data |
---|---|---|
d76ed9a9 AS |
1 | /* dict-splay.c - Abstract dictionary type |
2 | * Copyright 2000-2004 srvx Development Team | |
3 | * | |
4 | * This file is part of srvx. | |
5 | * | |
6 | * srvx is free software; you can redistribute it and/or modify | |
7 | * it under the terms of the GNU General Public License as published by | |
8 | * the Free Software Foundation; either version 2 of the License, or | |
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; | |
78 | if (!node) return NULL; | |
79 | N.l = N.r = NULL; | |
80 | l = r = &N; | |
81 | ||
82 | while (1) { | |
83 | int res = irccasecmp(key, node->key); | |
84 | if (!res) break; | |
85 | if (res < 0) { | |
86 | if (!node->l) break; | |
87 | res = irccasecmp(key, node->l->key); | |
88 | if (res < 0) { | |
89 | y = node->l; | |
90 | node->l = y->r; | |
91 | y->r = node; | |
92 | node = y; | |
93 | if (!node->l) break; | |
94 | } | |
95 | r->l = node; | |
96 | r = node; | |
97 | node = node->l; | |
98 | } else { /* res > 0 */ | |
99 | if (!node->r) break; | |
100 | res = irccasecmp(key, node->r->key); | |
101 | if (res > 0) { | |
102 | y = node->r; | |
103 | node->r = y->l; | |
104 | y->l = node; | |
105 | node = y; | |
106 | if (!node->r) break; | |
107 | } | |
108 | l->r = node; | |
109 | l = node; | |
110 | node = node->r; | |
111 | } | |
112 | } | |
113 | l->r = node->l; | |
114 | r->l = node->r; | |
115 | node->l = N.r; | |
116 | node->r = N.l; | |
117 | return node; | |
118 | } | |
119 | ||
120 | /* | |
121 | * Free node. Free data/key using free_f functions. | |
122 | */ | |
123 | static void | |
124 | dict_dispose_node(struct dict_node *node, free_f free_keys, free_f free_data) | |
125 | { | |
126 | if (free_keys && node->key) | |
127 | free_keys((void*)node->key); | |
128 | if (free_data && node->data) | |
129 | free_data(node->data); | |
130 | free(node); | |
131 | } | |
132 | ||
133 | /* | |
134 | * Insert an entry into the dictionary. | |
135 | * Key ordering (and uniqueness) is determined by case-insensitive | |
136 | * string comparison. | |
137 | */ | |
138 | void | |
139 | dict_insert(dict_t dict, const char *key, void *data) | |
140 | { | |
141 | struct dict_node *new_node; | |
142 | if (!key) | |
143 | return; | |
144 | new_node = malloc(sizeof(struct dict_node)); | |
145 | new_node->key = key; | |
146 | new_node->data = data; | |
147 | if (dict->root) { | |
148 | int res; | |
149 | dict->root = dict_splay(dict->root, key); | |
150 | res = irccasecmp(key, dict->root->key); | |
151 | if (res < 0) { | |
152 | /* insert just "before" current root */ | |
153 | new_node->l = dict->root->l; | |
154 | new_node->r = dict->root; | |
155 | dict->root->l = NULL; | |
156 | if (dict->root->prev) { | |
157 | dict->root->prev->next = new_node; | |
158 | } else { | |
159 | dict->first = new_node; | |
160 | } | |
161 | new_node->prev = dict->root->prev; | |
162 | new_node->next = dict->root; | |
163 | dict->root->prev = new_node; | |
164 | dict->root = new_node; | |
165 | } else if (res > 0) { | |
166 | /* insert just "after" current root */ | |
167 | new_node->r = dict->root->r; | |
168 | new_node->l = dict->root; | |
169 | dict->root->r = NULL; | |
170 | if (dict->root->next) { | |
171 | dict->root->next->prev = new_node; | |
172 | } else { | |
173 | dict->last = new_node; | |
174 | } | |
175 | new_node->next = dict->root->next; | |
176 | new_node->prev = dict->root; | |
177 | dict->root->next = new_node; | |
178 | dict->root = new_node; | |
179 | } else { | |
180 | /* maybe we don't want to overwrite it .. oh well */ | |
181 | if (dict->free_data) dict->free_data(dict->root->data); | |
182 | if (dict->free_keys) dict->free_keys((void*)dict->root->key); | |
183 | free(new_node); | |
184 | dict->root->key = key; | |
185 | dict->root->data = data; | |
186 | /* decrement the count since we dropped the node */ | |
187 | dict->count--; | |
188 | } | |
189 | } else { | |
190 | new_node->l = new_node->r = NULL; | |
191 | new_node->next = new_node->prev = NULL; | |
192 | dict->root = dict->first = dict->last = new_node; | |
193 | } | |
194 | dict->count++; | |
195 | } | |
196 | ||
197 | /* | |
198 | * Remove an entry from the dictionary. | |
199 | * Return non-zero if it was found, or zero if the key was not in the | |
200 | * dictionary. | |
201 | */ | |
202 | int | |
203 | dict_remove2(dict_t dict, const char *key, int no_dispose) | |
204 | { | |
1117fc5a | 205 | struct dict_node *new_root, *old_root; |
d76ed9a9 AS |
206 | |
207 | if (!dict->root) | |
208 | return 0; | |
209 | dict->root = dict_splay(dict->root, key); | |
210 | if (irccasecmp(key, dict->root->key)) | |
211 | return 0; | |
212 | ||
213 | if (!dict->root->l) { | |
214 | new_root = dict->root->r; | |
215 | } else { | |
216 | new_root = dict_splay(dict->root->l, key); | |
217 | new_root->r = dict->root->r; | |
218 | } | |
219 | if (dict->root->prev) dict->root->prev->next = dict->root->next; | |
220 | if (dict->first == dict->root) dict->first = dict->first->next; | |
221 | if (dict->root->next) dict->root->next->prev = dict->root->prev; | |
222 | if (dict->last == dict->root) dict->last = dict->last->prev; | |
1117fc5a | 223 | old_root = dict->root; |
224 | dict->root = new_root; | |
225 | dict->count--; | |
d76ed9a9 | 226 | if (no_dispose) { |
1117fc5a | 227 | free(old_root); |
d76ed9a9 | 228 | } else { |
1117fc5a | 229 | dict_dispose_node(old_root, dict->free_keys, dict->free_data); |
d76ed9a9 | 230 | } |
d76ed9a9 AS |
231 | return 1; |
232 | } | |
233 | ||
234 | /* | |
235 | * Find an entry in the dictionary. | |
236 | * If "found" is non-NULL, set it to non-zero if the key was found. | |
237 | * Return the data associated with the key (or NULL if the key was | |
238 | * not found). | |
239 | */ | |
240 | void* | |
241 | dict_find(dict_t dict, const char *key, int *found) | |
242 | { | |
243 | int was_found; | |
244 | if (!dict || !dict->root || !key) { | |
245 | if (found) | |
246 | *found = 0; | |
247 | return NULL; | |
248 | } | |
249 | dict->root = dict_splay(dict->root, key); | |
250 | was_found = !irccasecmp(key, dict->root->key); | |
251 | if (found) | |
252 | *found = was_found; | |
253 | return was_found ? dict->root->data : NULL; | |
254 | } | |
255 | ||
256 | /* | |
257 | * Delete an entire dictionary. | |
258 | */ | |
259 | void | |
260 | dict_delete(dict_t dict) | |
261 | { | |
262 | dict_iterator_t it, next; | |
263 | if (!dict) | |
264 | return; | |
265 | for (it=dict_first(dict); it; it=next) { | |
266 | next = iter_next(it); | |
267 | dict_dispose_node(it, dict->free_keys, dict->free_data); | |
268 | } | |
269 | free(dict); | |
270 | } | |
271 | ||
272 | struct dict_sanity_struct { | |
273 | unsigned int node_count; | |
274 | struct dict_node *bad_node; | |
275 | char error[128]; | |
276 | }; | |
277 | ||
278 | static int | |
279 | dict_sanity_check_node(struct dict_node *node, struct dict_sanity_struct *dss) | |
280 | { | |
281 | if (!node->key) { | |
282 | snprintf(dss->error, sizeof(dss->error), "Node %p had null key", node); | |
283 | return 1; | |
284 | } | |
285 | if (node->l) { | |
286 | if (dict_sanity_check_node(node->l, dss)) return 1; | |
287 | if (irccasecmp(node->l->key, node->key) >= 0) { | |
288 | snprintf(dss->error, sizeof(dss->error), "Node %p's left child's key '%s' >= its key '%s'", node, node->l->key, node->key); | |
289 | return 1; | |
290 | } | |
291 | } | |
292 | if (node->r) { | |
293 | if (dict_sanity_check_node(node->r, dss)) return 1; | |
294 | if (irccasecmp(node->key, node->r->key) >= 0) { | |
295 | snprintf(dss->error, sizeof(dss->error), "Node %p's right child's key '%s' <= its key '%s'", node, node->r->key, node->key); | |
296 | return 1; | |
297 | } | |
298 | } | |
299 | dss->node_count++; | |
300 | return 0; | |
301 | } | |
302 | ||
303 | /* | |
304 | * Perform sanity checks on the dict's internal structure. | |
305 | */ | |
306 | char * | |
307 | dict_sanity_check(dict_t dict) | |
308 | { | |
309 | struct dict_sanity_struct dss; | |
310 | dss.node_count = 0; | |
311 | dss.bad_node = 0; | |
312 | dss.error[0] = 0; | |
313 | if (dict->root && dict_sanity_check_node(dict->root, &dss)) { | |
314 | return strdup(dss.error); | |
315 | } else if (dss.node_count != dict->count) { | |
316 | snprintf(dss.error, sizeof(dss.error), "Counted %d nodes but expected %d.", dss.node_count, dict->count); | |
317 | return strdup(dss.error); | |
318 | } else { | |
319 | return 0; | |
320 | } | |
321 | } |