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

[irc/quakenet/newserv.git] / patricia / patricialib.c

diff --git a/patricia/patricialib.c b/patricia/patricialib.c
index a68fa552271a8ec94209598ea49155f4b407b904..738929a0c601e294e4aa84a0b285d7105cffae06 100644 (file)
--- a/patricia/patricialib.c
+++ b/patricia/patricialib.c
@@ -53,6 +53,7 @@ comp_with_mask (void *addr, void *dest, u_int mask)
     return (0);
 }
 
+
 prefix_t *
 patricia_new_prefix (struct irc_in_addr *dest, int bitlen)
 {
@@ -89,8 +90,8 @@ patricia_deref_prefix (prefix_t * prefix)
 
     prefix->ref_count--;
     if (prefix->ref_count <= 0) {
-       freeprefix(prefix);
-       return;
+      freeprefix(prefix);
+      return;
     }
 }
 
@@ -225,7 +226,7 @@ patricia_search_exact (patricia_tree_t *patricia, struct irc_in_addr *sin, unsig
        return (NULL);
     assert (node->bit == bitlen);
     assert (node->bit == node->prefix->bitlen);
-    if (comp_with_mask (prefix_tochar (node->prefix), addr,    bitlen)) {
+    if (comp_with_mask (prefix_tochar (node->prefix), addr, bitlen)) {
        return (node);
     }
     return (NULL);
@@ -346,7 +347,7 @@ patricia_lookup (patricia_tree_t *patricia, prefix_t *prefix)
            continue;
        }
        /* I know the better way, but for now */
-       for (j = 0; j < 8; j++) {
+        for (j = 0; j < 8; j++) {
            if ((r) & ((0x80 >> j)))
                break;
        }
@@ -373,7 +374,6 @@ patricia_lookup (patricia_tree_t *patricia, prefix_t *prefix)
     }
 
     new_node = patricia_new_node(patricia, prefix->bitlen, patricia_ref_prefix (prefix));
-
     if (node->bit == differ_bit) {
        new_node->parent = node;
        if (node->bit < patricia->maxbits &&
@@ -390,7 +390,7 @@ patricia_lookup (patricia_tree_t *patricia, prefix_t *prefix)
 
     if (bitlen == differ_bit) {
        if (bitlen < patricia->maxbits &&
-           (is_bit_set(addr,bitlen))) {
+           (is_bit_set(test_addr,bitlen))) {
            new_node->r = node;
        }
        else {
@@ -408,11 +408,11 @@ patricia_lookup (patricia_tree_t *patricia, prefix_t *prefix)
            node->parent->l = new_node;
        }
        node->parent = new_node;
+        new_node->usercount = node->usercount;
     }
     else {
         glue = patricia_new_node(patricia, differ_bit, NULL);
         glue->parent = node->parent;
-        
        if (differ_bit < patricia->maxbits &&
            (is_bit_set(addr, differ_bit))) {
            glue->r = new_node;
@@ -435,7 +435,9 @@ patricia_lookup (patricia_tree_t *patricia, prefix_t *prefix)
            node->parent->l = glue;
        }
        node->parent = glue;
+        glue->usercount = node->usercount;
     }
+
     return (new_node);
 }
 
@@ -571,3 +573,16 @@ patricia_node_t *patricia_new_node(patricia_tree_t *patricia, unsigned char bit,
   return new_node;  
 }
 
+void node_increment_usercount( patricia_node_t *node) {
+  while(node) {
+    node->usercount++;
+    node=node->parent;
+  }
+}
+
+void node_decrement_usercount( patricia_node_t *node) {
+  while(node) {
+    node->usercount--;
+    node=node->parent;
+  }
+}