X-Git-Url: https://tinc-vpn.org/git/browse?p=tinc;a=blobdiff_plain;f=lib%2Frbl.c;h=1a40535051a5b3704ff9fe0d5882cf3272555c00;hp=1c661d0600d1c08caf6ab0cadbdd6a4496f11412;hb=394ed3fb174bb629bfb4b441fe58842562f955de;hpb=3526f1e151b7a189f075d88c9d88cacaece31d02

diff --git a/lib/rbl.c b/lib/rbl.c
index 1c661d06..1a405350 100644
--- a/lib/rbl.c
+++ b/lib/rbl.c
@@ -17,12 +17,16 @@
     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.5 2000/11/19 02:04:29 guus Exp $
+    $Id: rbl.c,v 1.1.2.11 2000/11/22 19:14:08 guus Exp $
 */
 
+#include "config.h"
+
+#include <stdlib.h>
 #include <xalloc.h>
 
 #include "rbl.h"
+#include <system.h>
 
 /* Allocate a new rbl node */
 rbl_t *new_rbl()
@@ -33,6 +37,8 @@ rbl_t *new_rbl()
 /* Free a rbl node */
 void free_rbl(rbl_t *rbl)
 {
+  if(rbl->data && rbl->tree->delete)
+    rbl->tree->delete(rbl->data);
   free(rbl);
 }
 
@@ -58,11 +64,11 @@ 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;
-  
+
   next = rbl = tree->top;
   
   while(next)
@@ -71,8 +77,6 @@ rbl_t *rbl_search_closest(rbltree_t *tree, void *data)
       
       result = tree->compare(data, rbl->data);
 
-// fprintf(stderr, "comparing %s     with %s        = %d\n", rbl->data, data, result);
-
       if(result < 0)
         next = rbl->left;
       else if(result > 0)
@@ -84,31 +88,53 @@ rbl_t *rbl_search_closest(rbltree_t *tree, void *data)
   return rbl;
 }
 
+void *rbl_search_closest(rbltree_t *tree, void *data)
+{
+  rbl_t *rbl;
+  
+  rbl = rbl_search_closest_rbl(tree, data);
+
+  if(rbl)
+    return rbl->data;
+  else
+    return NULL;
+}
+
 /* 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;
+  rbl_t *rbl;
   int result;
+
+  rbl = tree->top;
   
-  next = rbl = tree->top;
-  
-  while(next)
+  while(rbl)
     {
-      rbl = next;
-      
-      result = tree->compare(rbl->data, data);
+      result = tree->compare(data, rbl->data);
 
       if(result < 0)
-        next = rbl->left;
+        rbl = rbl->left;
       else if(result > 0)
-        next = rbl->right;
+        rbl = rbl->right;
       else
         return rbl;
     }
-    
+
   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.
 */
@@ -173,7 +199,7 @@ rbl_t *rbl_insert_rbl(rbltree_t *tree, rbl_t *rbl)
   
   if(tree->top)
     {
-      closest = rbl_search_closest(tree, rbl->data);
+      closest = rbl_search_closest_rbl(tree, rbl->data);
       result = tree->compare(rbl->data, closest->data);
       if(result < 0)
         {
@@ -367,7 +393,7 @@ rbl_t *rbl_unlink_rbl(rbl_t *rbl)
   rbl_t *x, *y;
 
   /* Binary tree delete */
-  
+
   if(rbl->left && rbl->right)
     y = rbl->next;
   else
@@ -414,9 +440,9 @@ 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;
 }
 
@@ -425,24 +451,67 @@ 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);
-  else
-    return NULL;
+    rbl_unlink_rbl(rbl);
+
+  return rbl;
 }
 
 /* Unlink node and free it */
 void rbl_delete_rbl(rbl_t *rbl)
 {
-  free_rbl(rbl_unlink_rbl(rbl));
+  rbl_unlink_rbl(rbl);
+  free_rbl(rbl);
 }
 
 /* Search node in tree, unlink and free it */
 void rbl_delete(rbltree_t *tree, void *data)
 {
-  free_rbl(rbl_unlink(tree, data));
+  rbl_t *rbl;
+
+  rbl = rbl_unlink(tree, data);
+
+  if(rbl)
+    free_rbl(rbl);
+}
+
+/* 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;
+      free_rbl(rbl);
+    }
+
+  tree->top = NULL;
+  tree->head = NULL;
+  tree->tail = NULL;
 }
 
 /* Do action for each list entry (in order)
@@ -452,6 +521,17 @@ 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)
     {
       next = rbl->next;