From: Paul <redacted>
Date: Tue, 28 Oct 2008 23:28:06 +0000 (+0000)
Subject: Add a variant of WALK trie to use when clearing nodes from the trie
X-Git-Url: https://jfr.im/git/irc/quakenet/newserv.git/commitdiff_plain/801fd068aeae19c057be0a4421e9b93b6ae4815b

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 049f993a..2f0e510d 100644
--- 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 2f6b66c4..ab709362 100644
--- 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 460685c1..738929a0 100644
--- 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;
     }
 }