Add a variant of WALK trie to use when clearing nodes from the trie

--HG--
branch : paul

diff --git a/patricia/patricia.c b/patricia/patricia.c
index 049f993a6330b85238ec087a237280a77f0287a2..2f0e510dfc39b7257768382d9cd8734b78390526 100644 (file)
--- a/patricia/patricia.c
+++ b/patricia/patricia.c
@@ -121,9 +121,18 @@ void releasenodeext(int index) {
 
   head = iptree->head;
 
-  PATRICIA_WALK_ALL(head, node)
+  PATRICIA_WALK_CLEAR(head, node)
   {
-      node->exts[index]=NULL;
-  } PATRICIA_WALK_END;
+    if ( node->exts[index] ) { 
+      if (node->prefix) {
+        if (node->prefix->ref_count == 1) {
+          patricia_remove(iptree, node);
+        } else {
+          patricia_deref_prefix(node->prefix);
+        }
+      }
+    }
+    node->exts[index]=NULL;
+  } PATRICIA_WALK_CLEAR_END;
 }
 

diff --git a/patricia/patricia.h b/patricia/patricia.h
index 2f6b66c4035d73654adc10a27224c8c90ed220d8..ab7093625b95783da32ef92488bd533fcd2d9b5b 100644 (file)
--- a/patricia/patricia.h
+++ b/patricia/patricia.h
@@ -156,4 +156,27 @@ do { \
         } \
     } while (0)
 
+#define PATRICIA_WALK_CLEAR(Xhead, Xnode) \
+    patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \
+    patricia_node_t **Xsp = Xstack; \
+    patricia_node_t *Xrn = (Xhead); \
+    while ((Xnode = Xrn)) { \
+      patricia_node_t *l = Xrn->l; \
+      patricia_node_t *r = Xrn->r; \
+
+#define PATRICIA_WALK_CLEAR_END \
+            if (l) { \
+                if (r) { \
+                    *Xsp++ = r; \
+                } \
+                Xrn = l; \
+            } else if (r) { \
+                Xrn = r; \
+            } else if (Xsp != Xstack) { \
+                Xrn = *(--Xsp); \
+            } else { \
+                Xrn = (patricia_node_t *) 0; \
+            } \
+        } 
+   
 #endif /* _PATRICIA_H */

diff --git a/patricia/patricialib.c b/patricia/patricialib.c
index 460685c10440a2e74fe8359442df026a2e7cf679..738929a0c601e294e4aa84a0b285d7105cffae06 100644 (file)
--- a/patricia/patricialib.c
+++ b/patricia/patricialib.c
@@ -90,8 +90,8 @@ patricia_deref_prefix (prefix_t * prefix)
 
     prefix->ref_count--;
     if (prefix->ref_count <= 0) {
-       freeprefix(prefix);
-       return;
+      freeprefix(prefix);
+      return;
     }
 }