/*
avl_tree.c -- avl_ tree and linked list convenience
Copyright (C) 1998 Michael H. Buselli
- 2000 Ivo Timmermans <itimmermans@bigfoot.com>,
- 2000 Guus Sliepen <guus@sliepen.warande.net>
- 2000 Wessel Dankers <wsl@nl.linux.org>
+ 2000,2001 Ivo Timmermans <itimmermans@bigfoot.com>,
+ 2000,2001 Guus Sliepen <guus@sliepen.warande.net>
+ 2000,2001 Wessel Dankers <wsl@nl.linux.org>
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the code. Mail me if you found a bug.
Cleaned up and incorporated some of the ideas from the red-black tree
- library for inclusion into tinc (http://tinc.nl.linux.org) by
+ library for inclusion into tinc (http://tinc.nl.linux.org/) by
Guus Sliepen <guus@sliepen.warande.net>.
- $Id: avl_tree.c,v 1.1.2.2 2001/01/06 18:21:17 guus Exp $
+ $Id: avl_tree.c,v 1.1.2.7 2001/02/27 16:50:29 guus Exp $
*/
#include <stdio.h>
node = avl_search_closest_node(tree, data, &result);
- if(result > 0)
+ if(result < 0)
node = node->prev;
return node;
node = avl_search_closest_node(tree, data, &result);
- if(result < 0)
+ if(result > 0)
node = node->next;
return node;
avl_node_t *avl_insert(avl_tree_t *tree, void *data)
{
- avl_node_t *node;
+ avl_node_t *closest, *new;
+ int result;
- node = avl_alloc_node();
- node->data = data;
+ if (!tree->root)
+ {
+ new = avl_alloc_node();
+ new->data = data;
+ avl_insert_top(tree, new);
+ }
+ else
+ {
+ closest = avl_search_closest_node(tree, data, &result);
+ switch(result)
+ {
+ case -1:
+ new = avl_alloc_node();
+ new->data = data;
+ avl_insert_before(tree, closest, new);
+ break;
+ case 1:
+ new = avl_alloc_node();
+ new->data = data;
+ avl_insert_after(tree, closest, new);
+ break;
+ default:
+ return NULL;
+ }
+ }
+
+#ifdef AVL_COUNT
+ new->count = 1;
+#endif
+#ifdef AVL_DEPTH
+ new->depth = 1;
+#endif
- return avl_insert_node(tree, node);
+ return new;
}
avl_node_t *avl_insert_node(avl_tree_t *tree, avl_node_t *node)
avl_insert_after(tree, closest, node);
break;
case 0:
- return closest;
+ return NULL;
}
}
node->parent = before;
node->prev = before->prev;
+ if(before->left)
+ return avl_insert_after(tree, before->prev, node);
+
if (before->prev)
before->prev->next = node;
else
if (!after)
return tree->head ? avl_insert_before(tree, tree->head, node) : avl_insert_top(tree, node);
+ if(after->right)
+ return avl_insert_before(tree, after->next, node);
+
node->prev = after;
node->parent = after;
node->next = after->next;