[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 x3.
 *
 * x3 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 3 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;
    int res;

    if (!node) return NULL;
    if (!key) return NULL;
    N.l = N.r = NULL;
    l = r = &N;

    while (1) {
        verify(node);
        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) {
        if (free_keys == free)
            free((void*)node->key);
        else
            free_keys((void*)node->key);
    }
    if (free_data && node->data) {
        if (free_data == free)
            free(node->data);
        else
            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;
    verify(dict);
    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) {
                if (dict->free_data == free)
                    free(dict->root->data);
                else
                    dict->free_data(dict->root->data);
            }
            if (dict->free_keys) {
                if (dict->free_keys == free)
                    free((void*)dict->root->key);
                else
                    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;
    if (!key) return 0;
    verify(dict);
    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;
    }
    verify(dict);
    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)
{
    verify(node);
    if (!node->key) {
        snprintf(dss->error, sizeof(dss->error), "Node %p had null key", (void*)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'", (void*)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'", (void*)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;
    verify(dict);
    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	*
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	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;
ec1a68c8	79
d76ed9a9	80	if (!node) return NULL;
cf945df8	81	if (!key) return NULL;
d76ed9a9	82	N.l = N.r = NULL;
	83	l = r = &N;
	84
	85	while (1) {
ec1a68c8	86	verify(node);
ec1a68c8	87	res = irccasecmp(key, node->key);
d76ed9a9	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	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	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	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	229
	230	if (!dict->root)
	231	return 0;
cf945df8	232	if (!key) return 0;
ec1a68c8	233	verify(dict);
d76ed9a9	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	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	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	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	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	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	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	}