- Implemented deletions

[tinc] / lib / rbl.c

diff --git a/lib/rbl.c b/lib/rbl.c
index 88027e8..32e87bb 100644 (file)
--- a/lib/rbl.c
+++ b/lib/rbl.c
@@ -17,7 +17,7 @@
     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.2 2000/11/18 18:14:57 guus Exp $
+    $Id: rbl.c,v 1.1.2.3 2000/11/18 23:21:00 guus Exp $
 */
 
 
@@ -34,7 +34,7 @@ void free_rbl(rbl_t *rbl)
 }
 
 /* Allocate a new rbltree header */
-rbltree_t *new_rbltree(rbl_compare_t *compare, rbl_delete_t *delete)
+rbltree_t *new_rbltree(rbl_compare_t *compare, rbl_action_t *delete)
 {
   rbltree_t *tree;
 
@@ -60,7 +60,7 @@ rbl_t rbl_search_closest(rbltree_t *tree, void *data)
   rbl_t *rbl, *next;
   int result;
   
-  next = rbl = tree->head;
+  next = rbl = tree->top;
   
   while(next)
     {
@@ -85,7 +85,7 @@ rbl_t rbl_search(rbltree_t *tree, void *data)
   rbl_t *rbl, *next;
   int result;
   
-  next = rbl = tree->head;
+  next = rbl = tree->top;
   
   while(next)
     {
@@ -121,7 +121,7 @@ void rbl_left_rotate(rbl_t *x)
   y->parent = x->parent;
   
   if(!x->parent)
-    x->tree->head = y;
+    x->tree->top = y;
   else
     if(x == x->parent->left)
       x->parent->left = y;
@@ -145,7 +145,7 @@ void rbl_right_rotate(rbl_t *y)
   x->parent = y->parent;
   
   if(!y->parent)
-    y->tree->head = x;
+    y->tree->top = x;
   else
     if(y == y->parent->right)
       y->parent->right = x;
@@ -164,7 +164,7 @@ rbl_t rbl_insert_rbl(rbltree_t *tree, rbl_t *rbl)
   
   /* Binary tree and linked list insert */
   
-  if(tree->head)
+  if(tree->top)
     {
       closest = rbl_search_closest(tree, rbl->data);
       result = tree->compare(rbl->data, data);
@@ -188,7 +188,7 @@ rbl_t rbl_insert_rbl(rbltree_t *tree, rbl_t *rbl)
         return closest;                /* Ofcourse, we cannot add two identical things */
     }
   else
-    tree->head = rbl;
+    tree->top = rbl;
 
   /* Red-black part of insert */
   
@@ -242,7 +242,7 @@ rbl_t rbl_insert_rbl(rbltree_t *tree, rbl_t *rbl)
         }
     }
   
-  tree->head->color = RBL_BLACK;
+  tree->top->color = RBL_BLACK;
 
   return rbl;
 }
@@ -258,9 +258,137 @@ rbl_t rbl_insert(rbltree_t *tree, void *data)
   return rbl_insert_rbl(tree, rbl);
 }
 
-/* Unlink node from the tree, but keep the node intact */
+/* Restore red-black property after violation due to a deletion */
+void rbl_delete_fixup(rbl_t *x)
+{
+  rbl_t *w;
+  
+  while(x != x->tree->top && x->color == RBL_BLACK)
+    {
+      if(x == x->parent->left)
+        {
+          w = x->parent->right;
+          if(w->color == RBL_RED)
+            {
+              w->color = RBL_BLACK;
+              x->partent->color = RBL_RED;
+              rbl_left_rotate(x->parent);
+              w = x->parent->right;
+            }
+          if(w->left->color == RBL_BLACK && w->right->color == RBL_BLACK)
+            {
+              w->color = RBL_RED;
+              x = x->parent;
+            }
+          else
+            {
+              if(w->right->color == RBL_BLACK)
+                {
+                  w->left->color = RBL_BLACK;
+                  w->color = RBL_RED;
+                  rbl_right_rotate(w);
+                  w = x->parent->right;
+                }
+              w->color = x->parent->color;
+              x->parent->color = RBL_BLACK;
+              w->right->color = RBL_BLACK;
+              rbl_left_rotate(x->parent);
+              x = x->tree->top;
+            }
+        }
+      else
+        {
+          w = x->parent->left;
+          if(w->color == RBL_RED)
+            {
+              w->color = RBL_BLACK;
+              x->partent->color = RBL_RED;
+              rbl_right_rotate(x->parent);
+              w = x->parent->left;
+            }
+          if(w->right->color == RBL_BLACK && w->left->color == RBL_BLACK)
+            {
+              w->color = RBL_RED;
+              x = x->parent;
+            }
+          else
+            {
+              if(w->left->color == RBL_BLACK)
+                {
+                  w->right->color = RBL_BLACK;
+                  w->color = RBL_RED;
+                  rbl_left_rotate(w);
+                  w = x->parent->left;
+                }
+              w->color = x->parent->color;
+              x->parent->color = RBL_BLACK;
+              w->left->color = RBL_BLACK;
+              rbl_right_rotate(x->parent);
+              x = x->tree->top;
+            }
+        }
+    }
+  
+  x->color = RBL_BLACK;
+}
+
+/* Unlink node from the tree, but keep the node intact. */
 rbl_t rbl_unlink_rbl(rbl_t *rbl)
 {
+  rbl_t *x, *y;
+
+  /* Binary tree delete */
+  
+  if(rbl->left && rbl->right)
+    y = rbl->next;
+  else
+    y = rbl;
+    
+  if(y->left)
+    x = y->left;
+  else
+    x = y->right;
+    
+  if(x)
+    x->parent = y->parent;
+    
+  if(!y->parent)
+    rbl->tree->top = x;
+  else
+    if(y == y->parent->left)
+      y->parent->left = x;
+    else
+      y->parent->right = x;
+  
+  if(y != rbl)
+    {
+      y->left = rbl->left;
+      y->right = rbl->right;
+      y->parent = rbl->parent;
+      if(rbl == rbl->parent->left)
+        rbl->parent->left = y;
+      else
+        rbl->parent->right = y;
+    }
+
+  /* Linked list delete */
+  
+  if(rbl->prev)
+    rbl->prev->next = rbl->next;
+  else
+    rbl->tree->head = rbl->next;
+  
+  if(rbl->next)
+    rbl->next->prev = rbl->prev;
+  else
+    rbl->tree->tail = rbl->prev;
+
+  /* Red-black part of delete */
+  
+  if(y->color == RBL_BLACK)
+    rbl_delete_fixup(x);
+    
+  return rbl;
 }
 
 /* Search node in tree and unlink it */
@@ -287,3 +415,17 @@ void rbl_delete(rbltree_t *tree, void *data)
 {
   free_rbl(rbl_unlink(tree, data));
 }
+
+/* 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)
+{
+  rbl_t *rbl, *next;
+  
+  for(rbl = tree->head; rbl; rbl = next);
+    {
+      next = rbl->next;
+      action(rbl);
+    }
+}