]>
jfr.im git - irc/evilnet/x3.git/blob - src/dict-splay.c
1 /* dict-splay.c - Abstract dictionary type
2 * Copyright 2000-2004 srvx Development Team
4 * This file is part of x3.
6 * x3 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 3 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
;
80 if (!node
) return NULL
;
81 if (!key
) return NULL
;
87 res
= irccasecmp(key
, node
->key
);
91 res
= irccasecmp(key
, node
->l
->key
);
102 } else { /* res > 0 */
104 res
= irccasecmp(key
, node
->r
->key
);
125 * Free node. Free data/key using free_f functions.
128 dict_dispose_node(struct dict_node
*node
, free_f free_keys
, free_f free_data
)
130 if (free_keys
&& node
->key
) {
131 if (free_keys
== free
)
132 free((void*)node
->key
);
134 free_keys((void*)node
->key
);
136 if (free_data
&& node
->data
) {
137 if (free_data
== free
)
140 free_data(node
->data
);
146 * Insert an entry into the dictionary.
147 * Key ordering (and uniqueness) is determined by case-insensitive
151 dict_insert(dict_t dict
, const char *key
, void *data
)
153 struct dict_node
*new_node
;
157 new_node
= malloc(sizeof(struct dict_node
));
159 new_node
->data
= data
;
162 dict
->root
= dict_splay(dict
->root
, key
);
163 res
= irccasecmp(key
, dict
->root
->key
);
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
;
172 dict
->first
= new_node
;
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
;
186 dict
->last
= new_node
;
188 new_node
->next
= dict
->root
->next
;
189 new_node
->prev
= dict
->root
;
190 dict
->root
->next
= new_node
;
191 dict
->root
= new_node
;
193 /* maybe we don't want to overwrite it .. oh well */
194 if (dict
->free_data
) {
195 if (dict
->free_data
== free
)
196 free(dict
->root
->data
);
198 dict
->free_data(dict
->root
->data
);
200 if (dict
->free_keys
) {
201 if (dict
->free_keys
== free
)
202 free((void*)dict
->root
->key
);
204 dict
->free_keys((void*)dict
->root
->key
);
207 dict
->root
->key
= key
;
208 dict
->root
->data
= data
;
209 /* decrement the count since we dropped the node */
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
;
221 * Remove an entry from the dictionary.
222 * Return non-zero if it was found, or zero if the key was not in the
226 dict_remove2(dict_t dict
, const char *key
, int no_dispose
)
228 struct dict_node
*new_root
, *old_root
;
234 dict
->root
= dict_splay(dict
->root
, key
);
235 if (irccasecmp(key
, dict
->root
->key
))
238 if (!dict
->root
->l
) {
239 new_root
= dict
->root
->r
;
241 new_root
= dict_splay(dict
->root
->l
, key
);
242 new_root
->r
= dict
->root
->r
;
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
;
248 old_root
= dict
->root
;
249 dict
->root
= new_root
;
254 dict_dispose_node(old_root
, dict
->free_keys
, dict
->free_data
);
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
266 dict_find(dict_t dict
, const char *key
, int *found
)
269 if (!dict
|| !dict
->root
|| !key
) {
275 dict
->root
= dict_splay(dict
->root
, key
);
276 was_found
= !irccasecmp(key
, dict
->root
->key
);
279 return was_found
? dict
->root
->data
: NULL
;
283 * Delete an entire dictionary.
286 dict_delete(dict_t dict
)
288 dict_iterator_t it
, next
;
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
);
298 struct dict_sanity_struct
{
299 unsigned int node_count
;
300 struct dict_node
*bad_node
;
305 dict_sanity_check_node(struct dict_node
*node
, struct dict_sanity_struct
*dss
)
309 snprintf(dss
->error
, sizeof(dss
->error
), "Node %p had null key", (void*)node
);
313 if (dict_sanity_check_node(node
->l
, dss
)) return 1;
314 if (irccasecmp(node
->l
->key
, node
->key
) >= 0) {
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
);
320 if (dict_sanity_check_node(node
->r
, dss
)) return 1;
321 if (irccasecmp(node
->key
, node
->r
->key
) >= 0) {
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
);
331 * Perform sanity checks on the dict's internal structure.
334 dict_sanity_check(dict_t dict
)
336 struct dict_sanity_struct dss
;
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
);