X-Git-Url: https://www.tinc-vpn.org/git/browse?p=tinc;a=blobdiff_plain;f=lib%2Frbl.c;h=cf0316b77c376ebb52ab23220a7a43af9390893f;hp=0edc0ffbcb73b01221b4c0522e2dd0336c532ca1;hb=8f273f0ee265c75dd8eea65b2f1cd60a79691cd6;hpb=4f68e5b6133480478edba0959cb87d4eb149a8e7

diff --git a/lib/rbl.c b/lib/rbl.c
index 0edc0ffb..cf0316b7 100644
--- a/lib/rbl.c
+++ b/lib/rbl.c
@@ -17,14 +17,17 @@
     along with this program; if not, write to the Free Software
     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 
-    $Id: rbl.c,v 1.1.2.4 2000/11/18 23:22:44 guus Exp $
+    $Id: rbl.c,v 1.1.2.7 2000/11/19 22:12:46 guus Exp $
 */
 
+#include <xalloc.h>
+
+#include "rbl.h"
 
 /* Allocate a new rbl node */
 rbl_t *new_rbl()
 {
-  return (rbl_t *)xmalloc_and_zero(sizeof(*rbl));
+  return (rbl_t *)xmalloc_and_zero(sizeof(rbl_t));
 }
 
 /* Free a rbl node */
@@ -34,7 +37,7 @@ void free_rbl(rbl_t *rbl)
 }
 
 /* Allocate a new rbltree header */
-rbltree_t *new_rbltree(rbl_compare_t *compare, rbl_action_t *delete)
+rbltree_t *new_rbltree(rbl_compare_t compare, rbl_action_t delete)
 {
   rbltree_t *tree;
 
@@ -55,7 +58,7 @@ void free_rbltree(rbltree_t *tree)
 }
 
 /* Search closest match in the tree */
-rbl_t rbl_search_closest(rbltree_t *tree, void *data)
+rbl_t *rbl_search_closest_rbl(rbltree_t *tree, void *data)
 {
   rbl_t *rbl, *next;
   int result;
@@ -66,7 +69,7 @@ rbl_t rbl_search_closest(rbltree_t *tree, void *data)
     {
       rbl = next;
       
-      result = tree->compare(rbl->data, data);
+      result = tree->compare(data, rbl->data);
 
       if(result < 0)
         next = rbl->left;
@@ -79,8 +82,13 @@ rbl_t rbl_search_closest(rbltree_t *tree, void *data)
   return rbl;
 }
 
+void *rbl_search_closest(rbltree_t *tree, void *data)
+{
+  return rbl_search_closest_rbl(tree, data)->data;
+}
+
 /* Search exact match or return NULL pointer */
-rbl_t rbl_search(rbltree_t *tree, void *data)
+rbl_t *rbl_search_rbl(rbltree_t *tree, void *data)
 {
   rbl_t *rbl, *next;
   int result;
@@ -91,7 +99,7 @@ rbl_t rbl_search(rbltree_t *tree, void *data)
     {
       rbl = next;
       
-      result = tree->compare(rbl->data, data);
+      result = tree->compare(data, rbl->data);
 
       if(result < 0)
         next = rbl->left;
@@ -104,6 +112,18 @@ rbl_t rbl_search(rbltree_t *tree, void *data)
   return NULL;
 }
 
+void *rbl_search(rbltree_t *tree, void *data)
+{
+  rbl_t *rbl;
+
+  rbl = rbl_search_rbl(tree, data);
+
+  if(rbl)
+    return rbl->data;
+  else
+    return NULL;  
+}
+
 /* Red-black tree operations taken from Introduction to Algorithms,
    Cormen, Leiserson & Rivest, chapter 14.
 */
@@ -127,7 +147,7 @@ void rbl_left_rotate(rbl_t *x)
       x->parent->left = y;
     else
       x->parent->right = y;
-  
+
   y->left = x;
   x->parent = y;      
 }
@@ -135,7 +155,7 @@ void rbl_left_rotate(rbl_t *x)
 void rbl_right_rotate(rbl_t *y)
 {
   rbl_t *x;
-  
+
   x = y->left;
   y->left = x->right;
 
@@ -157,113 +177,129 @@ void rbl_right_rotate(rbl_t *y)
 }
 
 /* Insert a node into the rbl tree */
-rbl_t rbl_insert_rbl(rbltree_t *tree, rbl_t *rbl)
+rbl_t *rbl_insert_rbl(rbltree_t *tree, rbl_t *rbl)
 {
-   rbl_t *closest, y;
-   int result;
+  rbl_t *closest, *x, *y;
+  int result;
   
+  rbl->tree = tree;
+
   /* Binary tree and linked list insert */
   
   if(tree->top)
     {
-      closest = rbl_search_closest(tree, rbl->data);
-      result = tree->compare(rbl->data, data);
+      closest = rbl_search_closest_rbl(tree, rbl->data);
+      result = tree->compare(rbl->data, closest->data);
       if(result < 0)
         {
           closest->left = rbl;
+
           rbl->prev = closest->prev;
           rbl->next = closest;
           closest->prev = rbl;
-          rbl->prev->next = rbl;
+
+          if(rbl->prev)
+            rbl->prev->next = rbl;
+          else
+            tree->head = rbl;
         }
       else if(result > 0)
         {
           closest->right = rbl;
-          rbl->next = closest->right;
+
+          rbl->next = closest->next;
           rbl->prev = closest;
           closest->next = rbl;
-          rbl->next->prev = rbl;
+
+          if(rbl->next)
+            rbl->next->prev = rbl;
+          else
+            tree->tail = rbl;
         }
       else
         return closest;		/* Ofcourse, we cannot add two identical things */
+
+      rbl->parent = closest;
     }
   else
-    tree->top = rbl;
-
-  /* Linked list fixup */
-  
-  if(!rbl->prev)
-    tree->head = rbl;
-    
-  if(!rbl->next)
-    tree->tail = rbl;
+    {
+      tree->top = rbl;
+      tree->head = rbl;
+      tree->tail = rbl;
+    }
 
   /* Red-black part of insert */
   
-  rbl->color = RBL_RED;
+  x = rbl;
+  x->color = RBL_RED;
   
-  while(rbl->parent && rbl->parent->color == RBL_RED)
+  while(x != tree->top && x->parent->color == RBL_RED)
     {
-      if(rbl->parent == rbl->parent->parent->left)
+      if(x->parent == x->parent->parent->left)
         {
-          y = rbl->parent->parent->right;
-          if(y->color == RBL_RED)
+          y = x->parent->parent->right;
+          if(y && y->color == RBL_RED)
             {
-              rbl->parent->color = RBL_BLACK;
+              x->parent->color = RBL_BLACK;
               y->color = RBL_BLACK;
-              rbl->parent->parent->color = RBL_RED;
-              rbl = rbl->parent->parent;
+              x->parent->parent->color = RBL_RED;
+              x = x->parent->parent;
             }
           else          
             {
-              if(rbl == rbl->parent->right)
+              if(x == x->parent->right)
                 {
-                  rbl = rbl->parent;
-                  rbl_left_rotate(rbl);
+                  x = x->parent;
+                  rbl_left_rotate(x);
                 }
-              rbl->parent->color = RBL_BLACK;
-              rbl->parent->parent->color = RBL_RED;
-              rbl_right_rotate(rbl->parent->parent);
+              x->parent->color = RBL_BLACK;
+              x->parent->parent->color = RBL_RED;
+              rbl_right_rotate(x->parent->parent);
             }
         }
       else
         {
-          y = rbl->parent->parent->left;
-          if(y->color == RBL_RED)
+          y = x->parent->parent->left;
+          if(y && y->color == RBL_RED)
             {
-              rbl->parent->color = RBL_BLACK;
+              x->parent->color = RBL_BLACK;
               y->color = RBL_BLACK;
-              rbl->parent->parent->color = RBL_RED;
-              rbl = rbl->parent->parent;
+              x->parent->parent->color = RBL_RED;
+              x = x->parent->parent;
             }
           else          
             {
-              if(rbl == rbl->parent->left)
+              if(x == x->parent->left)
                 {
-                  rbl = rbl->parent;
-                  rbl_right_rotate(rbl);
+                  x = x->parent;
+                  rbl_right_rotate(x);
                 }
-              rbl->parent->color = RBL_BLACK;
-              rbl->parent->parent->color = RBL_RED;
-              rbl_left_rotate(rbl->parent->parent);
+              x->parent->color = RBL_BLACK;
+              x->parent->parent->color = RBL_RED;
+              rbl_left_rotate(x->parent->parent);
             }
         }
     }
   
   tree->top->color = RBL_BLACK;
-
   return rbl;
 }
 
 /* Create a new node and insert it into the tree */
-rbl_t rbl_insert(rbltree_t *tree, void *data)
+rbl_t *rbl_insert(rbltree_t *tree, void *data)
 {
   rbl_t *rbl;
   
   rbl = new_rbl();
   rbl->data = data;
 
-  return rbl_insert_rbl(tree, rbl);
+  if(rbl_insert_rbl(tree, rbl) == rbl)
+    return rbl;
+  else
+    {
+      free_rbl(rbl);
+      return NULL;
+    }
 }
 
 /* Restore red-black property after violation due to a deletion */
@@ -279,7 +315,7 @@ void rbl_delete_fixup(rbl_t *x)
           if(w->color == RBL_RED)
             {
               w->color = RBL_BLACK;
-              x->partent->color = RBL_RED;
+              x->parent->color = RBL_RED;
               rbl_left_rotate(x->parent);
               w = x->parent->right;
             }
@@ -310,7 +346,7 @@ void rbl_delete_fixup(rbl_t *x)
           if(w->color == RBL_RED)
             {
               w->color = RBL_BLACK;
-              x->partent->color = RBL_RED;
+              x->parent->color = RBL_RED;
               rbl_right_rotate(x->parent);
               w = x->parent->left;
             }
@@ -341,12 +377,12 @@ void rbl_delete_fixup(rbl_t *x)
 }
 
 /* Unlink node from the tree, but keep the node intact. */
-rbl_t rbl_unlink_rbl(rbl_t *rbl)
+rbl_t *rbl_unlink_rbl(rbl_t *rbl)
 {
   rbl_t *x, *y;
 
   /* Binary tree delete */
-  
+
   if(rbl->left && rbl->right)
     y = rbl->next;
   else
@@ -393,18 +429,18 @@ rbl_t rbl_unlink_rbl(rbl_t *rbl)
 
   /* Red-black part of delete */
   
-  if(y->color == RBL_BLACK)
+  if(y->color == RBL_BLACK && x)
     rbl_delete_fixup(x);
     
   return rbl;
 }
 
 /* Search node in tree and unlink it */
-rbl_t rbl_unlink(rbltree_t *tree, void *data)
+rbl_t *rbl_unlink(rbltree_t *tree, void *data)
 {
   rbl_t *rbl;
   
-  rbl = rbl_search(tree, data);
+  rbl = rbl_search_rbl(tree, data);
   
   if(rbl)
     return rbl_unlink_rbl(rbl);
@@ -424,14 +460,79 @@ void rbl_delete(rbltree_t *tree, void *data)
   free_rbl(rbl_unlink(tree, data));
 }
 
+rbl_unlink_rbltree_branch(rbl_t *rbl)
+{
+  if(rbl->left)
+    rbl_unlink_rbltree_branch(rbl->left);
+
+  if(rbl->right)
+    rbl_unlink_rbltree_branch(rbl->right);
+
+  if(rbl->parent)
+    {
+      if(rbl == rbl->parent->left)
+        rbl->parent->left = NULL;
+      else
+        rbl->parent->right = NULL;
+    }
+}
+
+/* Optimized unlinking for a complete tree */
+void rbl_unlink_rbltree(rbltree_t *tree)
+{
+  rbl_t *rbl, *next;
+  
+  for(rbl = tree->head; rbl; rbl = next)
+    {
+      next = rbl->next;
+      rbl->tree = NULL;
+      rbl->parent = NULL;
+      rbl->left = NULL;
+      rbl->right = NULL;
+      rbl->prev = NULL;
+      rbl->next = NULL;
+    }
+    
+  tree->top = NULL;
+  tree->head = NULL;
+  tree->tail = NULL;
+}
+
+/* Optimized deletion for a complete tree */
+void rbl_delete_rbltree(rbltree_t *tree)
+{
+  rbl_t *rbl, *next;
+  
+  for(rbl = tree->head; rbl; rbl = next)
+    {
+      next = rbl->next;
+      tree->delete(rbl->data);
+    }
+
+  tree->top = NULL;
+  tree->head = NULL;
+  tree->tail = NULL;
+}
+
 /* Do action for each list entry (in order)
    Deletion of entry for which action is called is allowed.
  */
-void rbl_foreach(rbltree_t *tree, rbl_action_t *action)
+void rbl_foreach(rbltree_t *tree, rbl_action_t action)
+{
+  rbl_t *rbl, *next;
+  
+  for(rbl = tree->head; rbl; rbl = next)
+    {
+      next = rbl->next;
+      action(rbl->data);
+    }
+}
+
+void rbl_foreach_rbl(rbltree_t *tree, rbl_action_rbl_t action)
 {
   rbl_t *rbl, *next;
   
-  for(rbl = tree->head; rbl; rbl = next);
+  for(rbl = tree->head; rbl; rbl = next)
     {
       next = rbl->next;
       action(rbl);