From: Guus Sliepen <guus@tinc-vpn.org>
Date: Sat, 18 Nov 2000 18:14:57 +0000 (+0000)
Subject: - Fixed searching
X-Git-Tag: release-1.0pre4~165
X-Git-Url: https://tinc-vpn.org/git/browse?p=tinc;a=commitdiff_plain;h=00e5d572621ad5f0263999dbfbfcb11e023bf48b;hp=7fcc0c6415488ed6ce0089a67ab7cfdd5d0d83ca

- Fixed searching
- Insertion implemented
---

diff --git a/lib/rbl.c b/lib/rbl.c
index 765236c2..88027e86 100644
--- a/lib/rbl.c
+++ b/lib/rbl.c
@@ -17,37 +17,57 @@
     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.1 2000/11/16 09:18:38 guus Exp $
+    $Id: rbl.c,v 1.1.2.2 2000/11/18 18:14:57 guus Exp $
 */
 
-rbl_t *new_rbl(rbltree_t *tree)
+
+/* Allocate a new rbl node */
+rbl_t *new_rbl()
 {
-  rbl_t *rbl;
+  return (rbl_t *)xmalloc_and_zero(sizeof(*rbl));
+}
+
+/* Free a rbl node */
+void free_rbl(rbl_t *rbl)
+{
+  free(rbl);
+}
 
-  rbl = xmalloc(sizeof(*rbl));
+/* Allocate a new rbltree header */
+rbltree_t *new_rbltree(rbl_compare_t *compare, rbl_delete_t *delete)
+{
+  rbltree_t *tree;
 
-  if(rbl)
+  tree = (rbltree_t *)xmalloc_and_zero(sizeof(rbltree_t));
+  if(tree)
     {
-      memset(rbl, 0, sizeof(*rbl));
-      rbl->tree = tree;
+      tree->compare = compare;
+      tree->delete = delete;
     }
-    
-  return rbl;
+  
+  return tree;
 }
 
-void free_rbl(rbl_t *rbl)
+/* Free a rbltree header */
+void free_rbltree(rbltree_t *tree)
 {
-  free(rbl);
+  free(tree);
 }
 
+/* Search closest match in the tree */
 rbl_t rbl_search_closest(rbltree_t *tree, void *data)
 {
   rbl_t *rbl, *next;
   int result;
   
-  for(next = rbltree->head; next; next = rbl)
+  next = rbl = tree->head;
+  
+  while(next)
     {
-      result = rbltree->compare(rbl->data, data)
+      rbl = next;
+      
+      result = tree->compare(rbl->data, data);
+
       if(result < 0)
         next = rbl->left;
       else if(result > 0)
@@ -59,14 +79,20 @@ rbl_t rbl_search_closest(rbltree_t *tree, void *data)
   return rbl;
 }
 
+/* Search exact match or return NULL pointer */
 rbl_t rbl_search(rbltree_t *tree, void *data)
 {
   rbl_t *rbl, *next;
   int result;
   
-  for(next = rbltree->head; next; next = rbl)
+  next = rbl = tree->head;
+  
+  while(next)
     {
-      result = rbltree->compare(rbl->data, data)
+      rbl = next;
+      
+      result = tree->compare(rbl->data, data);
+
       if(result < 0)
         next = rbl->left;
       else if(result > 0)
@@ -78,8 +104,186 @@ rbl_t rbl_search(rbltree_t *tree, void *data)
   return NULL;
 }
 
+/* Red-black tree operations taken from Introduction to Algorithms,
+   Cormen, Leiserson & Rivest, chapter 14.
+*/
+
+void rbl_left_rotate(rbl_t *x)
+{
+  rbl_t *y;
+  
+  y = x->right;
+  x->right = y->left;
+
+  if(y->left)
+    y->left->parent = x;
+
+  y->parent = x->parent;
+  
+  if(!x->parent)
+    x->tree->head = y;
+  else
+    if(x == x->parent->left)
+      x->parent->left = y;
+    else
+      x->parent->right = y;
+  
+  y->left = x;
+  x->parent = y;      
+}
+
+void rbl_right_rotate(rbl_t *y)
+{
+  rbl_t *x;
+  
+  x = y->left;
+  y->left = x->right;
+
+  if(x->right)
+    x->right->parent = y;
+
+  x->parent = y->parent;
+  
+  if(!y->parent)
+    y->tree->head = x;
+  else
+    if(y == y->parent->right)
+      y->parent->right = x;
+    else
+      y->parent->left = x;
+  
+  x->right = y;
+  y->parent = x;      
+}
+
+/* Insert a node into the rbl tree */
+rbl_t rbl_insert_rbl(rbltree_t *tree, rbl_t *rbl)
+{
+   rbl_t *closest, y;
+   int result;
+  
+  /* Binary tree and linked list insert */
+  
+  if(tree->head)
+    {
+      closest = rbl_search_closest(tree, rbl->data);
+      result = tree->compare(rbl->data, data);
+      if(result < 0)
+        {
+          closest->left = rbl;
+          rbl->prev = closest->prev;
+          rbl->next = closest;
+          closest->prev = rbl;
+          rbl->prev->next = rbl;
+        }
+      else if(result > 0)
+        {
+          closest->right = rbl;
+          rbl->next = closest->right;
+          rbl->prev = closest;
+          closest->next = rbl;
+          rbl->next->prev = rbl;
+        }
+      else
+        return closest;		/* Ofcourse, we cannot add two identical things */
+    }
+  else
+    tree->head = rbl;
+
+  /* Red-black part of insert */
+  
+  rbl->color = RBL_RED;
+  
+  while(rbl->parent && rbl->parent->color == RBL_RED)
+    {
+      if(rbl->parent == rbl->parent->parent->left)
+        {
+          y = rbl->parent->parent->right;
+          if(y->color == RBL_RED)
+            {
+              rbl->parent->color = RBL_BLACK;
+              y->color = RBL_BLACK;
+              rbl->parent->parent->color = RBL_RED;
+              rbl = rbl->parent->parent;
+            }
+          else          
+            {
+              if(rbl == rbl->parent->right)
+                {
+                  rbl = rbl->parent;
+                  rbl_left_rotate(rbl);
+                }
+              rbl->parent->color = RBL_BLACK;
+              rbl->parent->parent->color = RBL_RED;
+              rbl_right_rotate(rbl->parent->parent);
+            }
+        }
+      else
+        {
+          y = rbl->parent->parent->left;
+          if(y->color == RBL_RED)
+            {
+              rbl->parent->color = RBL_BLACK;
+              y->color = RBL_BLACK;
+              rbl->parent->parent->color = RBL_RED;
+              rbl = rbl->parent->parent;
+            }
+          else          
+            {
+              if(rbl == rbl->parent->left)
+                {
+                  rbl = rbl->parent;
+                  rbl_right_rotate(rbl);
+                }
+              rbl->parent->color = RBL_BLACK;
+              rbl->parent->parent->color = RBL_RED;
+              rbl_left_rotate(rbl->parent->parent);
+            }
+        }
+    }
+  
+  tree->head->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;
   
+  rbl = new_rbl();
+  rbl->data = data;
+
+  return rbl_insert_rbl(tree, rbl);
+}
+
+/* Unlink node from the tree, but keep the node intact */
+rbl_t rbl_unlink_rbl(rbl_t *rbl)
+{
+}
+
+/* Search node in tree and unlink it */
+rbl_t rbl_unlink(rbltree_t *tree, void *data)
+{
+  rbl_t *rbl;
+  
+  rbl = rbl_search(tree, data);
+  
+  if(rbl)
+    return rbl_unlink_rbl(rbl);
+  else
+    return NULL;
+}
+
+/* Unlink node and free it */
+void rbl_delete_rbl(rbl_t *rbl)
+{
+  free_rbl(rbl_unlink_rbl(rbl));
+}
+
+/* Search node in tree, unlink and free it */
+void rbl_delete(rbltree_t *tree, void *data)
+{
+  free_rbl(rbl_unlink(tree, data));
 }
diff --git a/lib/rbl.h b/lib/rbl.h
index 40a1c69d..bd9ecda3 100644
--- a/lib/rbl.h
+++ b/lib/rbl.h
@@ -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.h,v 1.1.2.1 2000/11/16 09:18:38 guus Exp $
+    $Id: rbl.h,v 1.1.2.2 2000/11/18 18:14:57 guus Exp $
 */
 
 typedef int (*rbl_compare_t) (const void *, const void *);
@@ -59,13 +59,16 @@ enum
   RBL_BLACK;
 };
 
-extern rbl_t rbl_search(rbltree_t *, void *);
-extern rbl_t rbl_search_closest(rbltree_t *, void *);
-extern rbl_t rbl_insert(rbltree_t *, void *);
-extern rbl_t rbl_unlink(rbltree_t *, void *);
-extern rbl_t rbl_delete(rbltree_t *, void *);
-extern rbl_t rbl_insert_rbl(rbltree_t *, rbl_t *);
-extern rbl_t rbl_unlink_rbl(rbltree_t *, rbl_t *);
-extern rbl_t rbl_delete_rbl(rbltree_t *, rbl_t *);
-extern rbl_t rbl_prev(rbl_t *);
-extern rbl_t rbl_next(rbl_t *);
+extern rbl_t *new_rbltree(rbl_compare_t *, rbl_delete_t *);
+extern void free_rbltree(rbltree_t *);
+extern rbl_t *new_rbl(void);
+extern void free_rbl(rbl_t *);
+
+extern rbl_t *rbl_search(rbltree_t *, void *);
+extern rbl_t *rbl_search_closest(rbltree_t *, void *);
+extern rbl_t *rbl_insert(rbltree_t *, void *);
+extern rbl_t *rbl_unlink(rbltree_t *, void *);
+extern rbl_t *rbl_delete(rbltree_t *, void *);
+extern rbl_t *rbl_insert_rbl(rbltree_t *, rbl_t *);
+extern rbl_t *rbl_unlink_rbl(rbltree_t *, rbl_t *);
+extern rbl_t *rbl_delete_rbl(rbltree_t *, rbl_t *);