[irc/evilnet/x3.git] / src / dict-splay.c

/* dict-splay.c - Abstract dictionary type
 * Copyright 2000-2004 srvx Development Team
 *
 * This file is part of srvx.
 *
 * srvx is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 */

#include "common.h"
#include "dict.h"

/*
 *    Create new dictionary.
 */
dict_t
dict_new(void)
{
    dict_t dict = calloc(1, sizeof(*dict));
    return dict;
}

/*
 *    Return number of entries in the dictionary.
 */
unsigned int
dict_size(dict_t dict)
{
    return dict->count;
}

/*
 *    Set the function to be called when freeing a key structure.
 *    If the function is NULL, just forget about the pointer.
 */
void
dict_set_free_keys(dict_t dict, free_f free_keys)
{
    dict->free_keys = free_keys;
}

/*
 *    Set the function to free data.
 * If the function is NULL, just forget about the pointer.
 */
void
dict_set_free_data(dict_t dict, free_f free_data)
{
    dict->free_data = free_data;
}

const char *
dict_foreach(dict_t dict, dict_iterator_f it_f, void *extra)
{
    dict_iterator_t it;

    for (it=dict_first(dict); it; it=iter_next(it)) {
        if (it_f(iter_key(it), iter_data(it), extra)) return iter_key(it);
    }
    return NULL;
}

/*
 *   This function finds a node and pulls it to the top of the tree.
 *   This helps balance the tree and auto-cache things you search for.
 */
static struct dict_node*
dict_splay(struct dict_node *node, const char *key)
{
    struct dict_node N, *l, *r, *y;
    if (!node) return NULL;
    N.l = N.r = NULL;
    l = r = &N;

    while (1) {
	int res = irccasecmp(key, node->key);
	if (!res) break;
	if (res < 0) {
	    if (!node->l) break;
	    res = irccasecmp(key, node->l->key);
	    if (res < 0) {
		y = node->l;
		node->l = y->r;
		y->r = node;
		node = y;
		if (!node->l) break;
	    }
	    r->l = node;
	    r = node;
	    node = node->l;
	} else { /* res > 0 */
	    if (!node->r) break;
	    res = irccasecmp(key, node->r->key);
	    if (res > 0) {
		y = node->r;
		node->r = y->l;
		y->l = node;
		node = y;
		if (!node->r) break;
	    }
	    l->r = node;
	    l = node;
	    node = node->r;
	}
    }
    l->r = node->l;
    r->l = node->r;
    node->l = N.r;
    node->r = N.l;
    return node;
}

/*
 *    Free node.  Free data/key using free_f functions.
 */
static void
dict_dispose_node(struct dict_node *node, free_f free_keys, free_f free_data)
{
    if (free_keys && node->key)
        free_keys((void*)node->key);
    if (free_data && node->data)
        free_data(node->data);
    free(node);
}

/*
 *    Insert an entry into the dictionary.
 *    Key ordering (and uniqueness) is determined by case-insensitive
 *    string comparison.
 */
void
dict_insert(dict_t dict, const char *key, void *data)
{
    struct dict_node *new_node;
    if (!key)
        return;
    new_node = malloc(sizeof(struct dict_node));
    new_node->key = key;
    new_node->data = data;
    if (dict->root) {
	int res;
	dict->root = dict_splay(dict->root, key);
	res = irccasecmp(key, dict->root->key);
	if (res < 0) {
            /* insert just "before" current root */
	    new_node->l = dict->root->l;
	    new_node->r = dict->root;
	    dict->root->l = NULL;
            if (dict->root->prev) {
                dict->root->prev->next = new_node;
            } else {
                dict->first = new_node;
            }
            new_node->prev = dict->root->prev;
            new_node->next = dict->root;
            dict->root->prev = new_node;
	    dict->root = new_node;
	} else if (res > 0) {
            /* insert just "after" current root */
	    new_node->r = dict->root->r;
	    new_node->l = dict->root;
	    dict->root->r = NULL;
            if (dict->root->next) {
                dict->root->next->prev = new_node;
            } else {
                dict->last = new_node;
            }
            new_node->next = dict->root->next;
            new_node->prev = dict->root;
            dict->root->next = new_node;
	    dict->root = new_node;
	} else {
	    /* maybe we don't want to overwrite it .. oh well */
	    if (dict->free_data) dict->free_data(dict->root->data);
            if (dict->free_keys) dict->free_keys((void*)dict->root->key);
            free(new_node);
            dict->root->key = key;
	    dict->root->data = data;
	    /* decrement the count since we dropped the node */
	    dict->count--;
	}
    } else {
	new_node->l = new_node->r = NULL;
        new_node->next = new_node->prev = NULL;
	dict->root = dict->first = dict->last = new_node;
    }
    dict->count++;
}

/*
 *    Remove an entry from the dictionary.
 *    Return non-zero if it was found, or zero if the key was not in the
 *    dictionary.
 */
int
dict_remove2(dict_t dict, const char *key, int no_dispose)
{
    struct dict_node *new_root, *old_root;

    if (!dict->root)
        return 0;
    dict->root = dict_splay(dict->root, key);
    if (irccasecmp(key, dict->root->key))
        return 0;

    if (!dict->root->l) {
        new_root = dict->root->r;
    } else {
        new_root = dict_splay(dict->root->l, key);
        new_root->r = dict->root->r;
    }
    if (dict->root->prev) dict->root->prev->next = dict->root->next;
    if (dict->first == dict->root) dict->first = dict->first->next;
    if (dict->root->next) dict->root->next->prev = dict->root->prev;
    if (dict->last == dict->root) dict->last = dict->last->prev;
    old_root = dict->root;
    dict->root = new_root;
    dict->count--;
    if (no_dispose) {
        free(old_root);
    } else {
        dict_dispose_node(old_root, dict->free_keys, dict->free_data);
    }
    return 1;
}

/*
 *    Find an entry in the dictionary.
 *    If "found" is non-NULL, set it to non-zero if the key was found.
 *    Return the data associated with the key (or NULL if the key was
 *    not found).
 */
void*
dict_find(dict_t dict, const char *key, int *found)
{
    int was_found;
    if (!dict || !dict->root || !key) {
	if (found)
            *found = 0;
	return NULL;
    }
    dict->root = dict_splay(dict->root, key);
    was_found = !irccasecmp(key, dict->root->key);
    if (found)
        *found = was_found;
    return was_found ? dict->root->data : NULL;
}

/*
 *    Delete an entire dictionary.
 */
void
dict_delete(dict_t dict)
{
    dict_iterator_t it, next;
    if (!dict)
        return;
    for (it=dict_first(dict); it; it=next) {
        next = iter_next(it);
        dict_dispose_node(it, dict->free_keys, dict->free_data);
    }
    free(dict);
}

struct dict_sanity_struct {
    unsigned int node_count;
    struct dict_node *bad_node;
    char error[128];
};

static int
dict_sanity_check_node(struct dict_node *node, struct dict_sanity_struct *dss)
{
    if (!node->key) {
        snprintf(dss->error, sizeof(dss->error), "Node %p had null key", node);
        return 1;
    }
    if (node->l) {
        if (dict_sanity_check_node(node->l, dss)) return 1;
        if (irccasecmp(node->l->key, node->key) >= 0) {
            snprintf(dss->error, sizeof(dss->error), "Node %p's left child's key '%s' >= its key '%s'", node, node->l->key, node->key);
            return 1;
        }
    }
    if (node->r) {
        if (dict_sanity_check_node(node->r, dss)) return 1;
        if (irccasecmp(node->key, node->r->key) >= 0) {
            snprintf(dss->error, sizeof(dss->error), "Node %p's right child's key '%s' <= its key '%s'", node, node->r->key, node->key);
            return 1;
        }
    }
    dss->node_count++;
    return 0;
}

/*
 *    Perform sanity checks on the dict's internal structure.
 */
char *
dict_sanity_check(dict_t dict)
{
    struct dict_sanity_struct dss;
    dss.node_count = 0;
    dss.bad_node = 0;
    dss.error[0] = 0;
    if (dict->root && dict_sanity_check_node(dict->root, &dss)) {
        return strdup(dss.error);
    } else if (dss.node_count != dict->count) {
        snprintf(dss.error, sizeof(dss.error), "Counted %d nodes but expected %d.", dss.node_count, dict->count);
        return strdup(dss.error);
    } else {
        return 0;
    }
}
Commit	Line	Data
d76ed9a9	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	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	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	}