1 /* dict-splay.c - Abstract dictionary type
2 * Copyright 2000-2004 srvx Development Team
4 * This file is part of srvx.
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.
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.
21 * Create new dictionary.
26 dict_t dict = calloc(1, sizeof(*dict));
31 * Return number of entries in the dictionary.
34 dict_size(dict_t dict)
40 * Set the function to be called when freeing a key structure.
41 * If the function is NULL, just forget about the pointer.
44 dict_set_free_keys(dict_t dict, free_f free_keys)
46 dict->free_keys = free_keys;
50 * Set the function to free data.
51 * If the function is NULL, just forget about the pointer.
54 dict_set_free_data(dict_t dict, free_f free_data)
56 dict->free_data = free_data;
60 dict_foreach(dict_t dict, dict_iterator_f it_f, void *extra)
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);
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.
74 static struct dict_node*
75 dict_splay(struct dict_node *node, const char *key)
77 struct dict_node N, *l, *r, *y;
78 if (!node) return NULL;
83 int res = irccasecmp(key, node->key);
87 res = irccasecmp(key, node->l->key);
98 } else { /* res > 0 */
100 res = irccasecmp(key, node->r->key);
121 * Free node. Free data/key using free_f functions.
124 dict_dispose_node(struct dict_node *node, free_f free_keys, free_f free_data)
126 if (free_keys && node->key) {
127 if (free_keys == free)
128 free((void*)node->key);
130 free_keys((void*)node->key);
132 if (free_data && node->data) {
133 if (free_data == free)
136 free_data(node->data);
142 * Insert an entry into the dictionary.
143 * Key ordering (and uniqueness) is determined by case-insensitive
147 dict_insert(dict_t dict, const char *key, void *data)
149 struct dict_node *new_node;
152 new_node = malloc(sizeof(struct dict_node));
154 new_node->data = data;
157 dict->root = dict_splay(dict->root, key);
158 res = irccasecmp(key, dict->root->key);
160 /* insert just "before" current root */
161 new_node->l = dict->root->l;
162 new_node->r = dict->root;
163 dict->root->l = NULL;
164 if (dict->root->prev) {
165 dict->root->prev->next = new_node;
167 dict->first = new_node;
169 new_node->prev = dict->root->prev;
170 new_node->next = dict->root;
171 dict->root->prev = new_node;
172 dict->root = new_node;
173 } else if (res > 0) {
174 /* insert just "after" current root */
175 new_node->r = dict->root->r;
176 new_node->l = dict->root;
177 dict->root->r = NULL;
178 if (dict->root->next) {
179 dict->root->next->prev = new_node;
181 dict->last = new_node;
183 new_node->next = dict->root->next;
184 new_node->prev = dict->root;
185 dict->root->next = new_node;
186 dict->root = new_node;
188 /* maybe we don't want to overwrite it .. oh well */
189 if (dict->free_data) {
190 if (dict->free_data == free)
191 free(dict->root->data);
193 dict->free_data(dict->root->data);
195 if (dict->free_keys) {
196 if (dict->free_keys == free)
197 free((void*)dict->root->key);
199 dict->free_keys((void*)dict->root->key);
202 dict->root->key = key;
203 dict->root->data = data;
204 /* decrement the count since we dropped the node */
208 new_node->l = new_node->r = NULL;
209 new_node->next = new_node->prev = NULL;
210 dict->root = dict->first = dict->last = new_node;
216 * Remove an entry from the dictionary.
217 * Return non-zero if it was found, or zero if the key was not in the
221 dict_remove2(dict_t dict, const char *key, int no_dispose)
223 struct dict_node *new_root, *old_root;
227 dict->root = dict_splay(dict->root, key);
228 if (irccasecmp(key, dict->root->key))
231 if (!dict->root->l) {
232 new_root = dict->root->r;
234 new_root = dict_splay(dict->root->l, key);
235 new_root->r = dict->root->r;
237 if (dict->root->prev) dict->root->prev->next = dict->root->next;
238 if (dict->first == dict->root) dict->first = dict->first->next;
239 if (dict->root->next) dict->root->next->prev = dict->root->prev;
240 if (dict->last == dict->root) dict->last = dict->last->prev;
241 old_root = dict->root;
242 dict->root = new_root;
247 dict_dispose_node(old_root, dict->free_keys, dict->free_data);
253 * Find an entry in the dictionary.
254 * If "found" is non-NULL, set it to non-zero if the key was found.
255 * Return the data associated with the key (or NULL if the key was
259 dict_find(dict_t dict, const char *key, int *found)
262 if (!dict || !dict->root || !key) {
267 dict->root = dict_splay(dict->root, key);
268 was_found = !irccasecmp(key, dict->root->key);
271 return was_found ? dict->root->data : NULL;
275 * Delete an entire dictionary.
278 dict_delete(dict_t dict)
280 dict_iterator_t it, next;
283 for (it=dict_first(dict); it; it=next) {
284 next = iter_next(it);
285 dict_dispose_node(it, dict->free_keys, dict->free_data);
290 struct dict_sanity_struct {
291 unsigned int node_count;
292 struct dict_node *bad_node;
297 dict_sanity_check_node(struct dict_node *node, struct dict_sanity_struct *dss)
300 snprintf(dss->error, sizeof(dss->error), "Node %p had null key", node);
304 if (dict_sanity_check_node(node->l, dss)) return 1;
305 if (irccasecmp(node->l->key, node->key) >= 0) {
306 snprintf(dss->error, sizeof(dss->error), "Node %p's left child's key '%s' >= its key '%s'", node, node->l->key, node->key);
311 if (dict_sanity_check_node(node->r, dss)) return 1;
312 if (irccasecmp(node->key, node->r->key) >= 0) {
313 snprintf(dss->error, sizeof(dss->error), "Node %p's right child's key '%s' <= its key '%s'", node, node->r->key, node->key);
322 * Perform sanity checks on the dict's internal structure.
325 dict_sanity_check(dict_t dict)
327 struct dict_sanity_struct dss;
331 if (dict->root && dict_sanity_check_node(dict->root, &dss)) {
332 return strdup(dss.error);
333 } else if (dss.node_count != dict->count) {
334 snprintf(dss.error, sizeof(dss.error), "Counted %d nodes but expected %d.", dss.node_count, dict->count);
335 return strdup(dss.error);