/*
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 library is free software; you can redistribute it and/or
- modify it under the terms of the GNU Lesser 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 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 library is distributed in the hope that it will be useful,
+ 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
- Lesser General Public License for more details.
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
- You should have received a copy of the GNU Lesser General Public
- License along with this library; if not, write to the Free Software
- Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
Original AVL tree library by Michael H. Buselli <cosine@cosine.org>.
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.1 2001/01/05 23:50:56 guus Exp $
+ $Id: avl_tree.c,v 1.1.2.6 2001/02/20 21:53:18 wsl 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;
+ case 0:
+ 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;