X-Git-Url: https://jfr.im/git/irc/quakenet/newserv.git/blobdiff_plain/7a25133f306ebaee3ecb00a79cf7c51d03d3acf0..daf8fe8757ed4fb89c39e381ddb68ea813db7205:/patricia/patricialib.c

diff --git a/patricia/patricialib.c b/patricia/patricialib.c
index 44b4e6c3..86584c34 100644
--- a/patricia/patricialib.c
+++ b/patricia/patricialib.c
@@ -27,6 +27,18 @@ char patricia_copyright[] =
 
 #include "patricia.h"
 
+//#define LEAK_DETECTION
+
+#ifdef LEAK_DETECTION
+#define MAGIC 0x6a3b4ef3
+
+struct fake_node {
+  patricia_node_t node;
+  uint32_t magic;
+  patricia_node_t *real_node;
+};
+#endif
+
 /* prefix_tochar
  * convert prefix information to bytes
  */
@@ -53,6 +65,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 +102,8 @@ patricia_deref_prefix (prefix_t * prefix)
 
     prefix->ref_count--;
     if (prefix->ref_count <= 0) {
-	freeprefix(prefix);
-	return;
+      freeprefix(prefix);
+      return;
     }
 }
 
@@ -212,7 +225,7 @@ patricia_search_exact (patricia_tree_t *patricia, struct irc_in_addr *sin, unsig
     addr = (u_char *)sin;
 
     while (node->bit < bitlen) {
-	if (BIT_TEST (addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
+        if (is_bit_set(addr,node->bit))
 	    node = node->r;
 	else
 	    node = node->l;
@@ -225,7 +238,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);
@@ -257,7 +270,7 @@ patricia_search_best2 (patricia_tree_t *patricia, struct irc_in_addr *sin, unsig
 	    stack[cnt++] = node;
 	}
 
-	if (BIT_TEST (addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) {
+        if (is_bit_set(addr,node->bit)) {
 	    node = node->r;
 	}
 	else {
@@ -320,7 +333,7 @@ patricia_lookup (patricia_tree_t *patricia, prefix_t *prefix)
     while (node->bit < bitlen || node->prefix == NULL) {
         /* check that we're not at the lowest leaf i.e. node->bit is less than max bits */
 	if (node->bit < patricia->maxbits &&
-	    (addr[node->bit >> 3]) & (0x80 >> (node->bit & 0x07))) {
+            (is_bit_set(addr,node->bit))) {
 	    if (node->r == NULL)
 		break;
 	    node = node->r;
@@ -346,7 +359,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;
 	}
@@ -366,19 +379,17 @@ patricia_lookup (patricia_tree_t *patricia, prefix_t *prefix)
     }
 
     if (differ_bit == bitlen && node->bit == bitlen) {
-	if (node->prefix) {
-	    return (node);
-	}
-	node->prefix = patricia_ref_prefix (prefix);
+	if (!node->prefix) {
+	    node->prefix = patricia_ref_prefix (prefix);
+        }
 	return (node);
     }
 
     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 &&
-	    (addr[node->bit >> 3]) & (0x80 >> (node->bit & 0x07))) {
+	    (is_bit_set(addr, node->bit))) {
 	    assert (node->r == NULL);
 	    node->r = new_node;
 	}
@@ -391,7 +402,7 @@ patricia_lookup (patricia_tree_t *patricia, prefix_t *prefix)
 
     if (bitlen == differ_bit) {
 	if (bitlen < patricia->maxbits &&
-	    (test_addr[bitlen >> 3]) & (0x80 >> (bitlen & 0x07))) {
+	    (is_bit_set(test_addr,bitlen))) {
 	    new_node->r = node;
 	}
 	else {
@@ -409,13 +420,13 @@ 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 &&
-	    (addr[differ_bit >> 3]) & (0x80 >> (differ_bit & 0x07))) {
+	    (is_bit_set(addr, differ_bit))) {
 	    glue->r = new_node;
 	    glue->l = node;
 	}
@@ -436,7 +447,9 @@ patricia_lookup (patricia_tree_t *patricia, prefix_t *prefix)
 	    node->parent->l = glue;
 	}
 	node->parent = glue;
+        glue->usercount = node->usercount;
     }
+
     return (new_node);
 }
 
@@ -530,6 +543,16 @@ patricia_remove (patricia_tree_t *patricia, patricia_node_t *node)
     }
 }
 
+#ifdef LEAK_DETECTION
+static patricia_node_t *getrealnode(patricia_node_t *node) {
+  struct fake_node *f = (struct fake_node *)node;
+  if(f->magic != MAGIC) {
+    printf("magic failure\n");
+    abort();
+  }
+  return f->real_node;
+}
+#endif
 
 patricia_node_t *
 refnode(patricia_tree_t *tree, struct irc_in_addr *sin, int bitlen) {
@@ -546,6 +569,14 @@ refnode(patricia_tree_t *tree, struct irc_in_addr *sin, int bitlen) {
     patricia_ref_prefix(node->prefix);
   }
 
+#ifdef LEAK_DETECTION
+  struct fake_node *f = malloc(sizeof(struct fake_node));
+  f->magic = MAGIC;
+  f->node = *node;
+  f->real_node = node;
+  node = (patricia_node_t *)f;
+#endif
+
   return node;
 }
 
@@ -554,6 +585,15 @@ derefnode(patricia_tree_t *tree, patricia_node_t *node) {
   if (!node || !node->prefix)
     return;
 
+#ifdef LEAK_DETECTION
+  patricia_node_t *real_node = getrealnode(node);
+  free(node);
+  node = real_node;
+
+  if (!node || !node->prefix)
+    return;
+#endif
+
   if (node->prefix->ref_count == 1) {
     patricia_remove(tree, node);
   } else
@@ -572,3 +612,35 @@ patricia_node_t *patricia_new_node(patricia_tree_t *patricia, unsigned char bit,
   return new_node;  
 }
 
+void node_increment_usercount( patricia_node_t *node) {
+#ifdef LEAK_DETECTION
+  node = getrealnode(node);
+#endif
+
+  while(node) {
+    node->usercount++;
+    node=node->parent;
+  }
+}
+
+void node_decrement_usercount( patricia_node_t *node) {
+#ifdef LEAK_DETECTION
+  node = getrealnode(node);
+#endif
+
+  while(node) {
+    node->usercount--;
+    node=node->parent;
+  }
+}
+
+int is_normalized_ipmask( struct irc_in_addr *sin, unsigned char bitlen ) {
+  u_char *addr = (u_char *)sin;
+
+  while (bitlen < PATRICIA_MAXBITS) {
+    if (is_bit_set(addr,bitlen))
+       return 0;
+    bitlen++;
+  }
+  return 1;
+}