s/sliepen.warande.net/sliepen.eu.org/g

[tinc] / lib / avl_tree.c

diff --git a/lib/avl_tree.c b/lib/avl_tree.c
index 34ce2a3..8ec680b 100644 (file)
--- a/lib/avl_tree.c
+++ b/lib/avl_tree.c
@@ -1,8 +1,8 @@
 /*
     avl_tree.c -- avl_ tree and linked list convenience
     Copyright (C) 1998 Michael H. Buselli
-                  2000,2001 Ivo Timmermans <itimmermans@bigfoot.com>,
-                  2000,2001 Guus Sliepen <guus@sliepen.warande.net>
+                  2000,2001 Ivo Timmermans <ivo@o2w.nl>,
+                  2000,2001 Guus Sliepen <guus@sliepen.eu.org>
                   2000,2001 Wessel Dankers <wsl@nl.linux.org>
 
     This program is free software; you can redistribute it and/or modify
@@ -26,10 +26,10 @@
     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
-    Guus Sliepen <guus@sliepen.warande.net>.
+    library for inclusion into tinc (http://tinc.nl.linux.org/) by
+    Guus Sliepen <guus@sliepen.eu.org>.
 
-    $Id: avl_tree.c,v 1.1.2.3 2001/01/07 17:08:49 guus Exp $
+    $Id: avl_tree.c,v 1.1.2.9 2002/06/21 10:11:11 guus Exp $
 */
 
 #include <stdio.h>
@@ -383,7 +383,7 @@ avl_node_t *avl_search_closest_smaller_node(const avl_tree_t *tree, const void *
   
   node = avl_search_closest_node(tree, data, &result);
   
-  if(result > 0)
+  if(result < 0)
     node = node->prev;
   
   return node;
@@ -396,7 +396,7 @@ avl_node_t *avl_search_closest_greater_node(const avl_tree_t *tree, const void *
   
   node = avl_search_closest_node(tree, data, &result);
   
-  if(result < 0)
+  if(result > 0)
     node = node->next;
   
   return node;
@@ -406,12 +406,43 @@ avl_node_t *avl_search_closest_greater_node(const avl_tree_t *tree, const void *
 
 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)
@@ -433,7 +464,7 @@ 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;
     }
   }
   
@@ -462,6 +493,9 @@ void avl_insert_before(avl_tree_t *tree, avl_node_t *before, avl_node_t *node)
   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
@@ -478,6 +512,9 @@ void avl_insert_after(avl_tree_t *tree, avl_node_t *after, avl_node_t *node)
   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;
@@ -560,6 +597,15 @@ void avl_unlink_node(avl_tree_t *tree, avl_node_t *node)
   }
 
   avl_rebalance(tree, balnode);
+  
+  node->next = node->prev = node->parent = node->left = node->right = NULL;
+
+#ifdef AVL_COUNT
+  node->count = 0;
+#endif
+#ifdef AVL_DEPTH
+  node->depth = 0;
+#endif
 }
 
 void avl_delete_node(avl_tree_t *tree, avl_node_t *node)