From a4d9629afc0859d674d466c20b9e316fe6adebc3 Mon Sep 17 00:00:00 2001
From: Yuri Schaeffer <yuri@nlnetlabs.nl>
Date: Fri, 18 Oct 2013 14:37:40 +0000
Subject: [PATCH] keep size of tree as state. With each insert lruhash needs a
 new quote on the size which is relatively expensive.

git-svn-id: file:///svn/unbound/branches/edns-subnet@2990 be551aaa-1e26-0410-a405-d3ace91eadb9
---
 edns-subnet/addrtree.c | 37 +++++++++++++++++++++++++------------
 edns-subnet/addrtree.h |  2 ++
 2 files changed, 27 insertions(+), 12 deletions(-)

diff --git a/edns-subnet/addrtree.c b/edns-subnet/addrtree.c
index 5afb91963..3e4094432 100644
--- a/edns-subnet/addrtree.c
+++ b/edns-subnet/addrtree.c
@@ -43,6 +43,7 @@ edge_create(struct addrnode *node, const addrkey_t *addr,
 	memcpy(edge->str, addr, n * sizeof (addrkey_t));
 	/* Only manipulate other objects after successful alloc */
 	node->parent_edge = edge;
+	log_assert(parent_node->edge[parent_index] == NULL);
 	parent_node->edge[parent_index] = edge;
 	return edge;
 }
@@ -74,6 +75,18 @@ node_create(struct addrtree *tree, void *elem, addrlen_t scope,
 	return node;
 }
 
+/** Size in bytes of node and parent edge
+ * @param tree: tree the node lives in
+ * @param node: node which size must be calculated 
+ * @return size in bytes.
+ **/
+static inline size_t 
+node_size(const struct addrtree *tree, const struct addrnode *n)
+{
+	return sizeof *n + sizeof *n->parent_edge + strlen(n->parent_edge->str) + 
+		(n->elem?tree->sizefunc(n->elem):0);
+}
+
 struct addrtree * 
 addrtree_create(addrlen_t max_depth, void (*delfunc)(void *, void *), 
 	size_t (*sizefunc)(void *), void *env, unsigned int max_node_count)
@@ -89,6 +102,7 @@ addrtree_create(addrlen_t max_depth, void (*delfunc)(void *, void *),
 		free(tree);
 		return NULL;
 	}
+	tree->size_bytes = sizeof *tree + sizeof *tree->root;
 	tree->first = NULL;
 	tree->last = NULL;
 	tree->max_depth = max_depth;
@@ -109,6 +123,7 @@ static void
 clean_node(struct addrtree *tree, struct addrnode *node)
 {
 	if (!node->elem) return;
+	tree->size_bytes -= tree->sizefunc(node->elem);
 	tree->delfunc(tree->env, node->elem);
 	node->elem = NULL;
 }
@@ -181,6 +196,7 @@ purge_node(struct addrtree *tree, struct addrnode *node)
 		child_edge->parent_index = index;
 	}
 	parent_edge->parent_node->edge[index] = child_edge;
+	tree->size_bytes -= node_size(tree, node);
 	free(parent_edge->str);
 	free(parent_edge);
 	lru_pop(tree, node);
@@ -216,19 +232,10 @@ lru_cleanup(struct addrtree *tree)
 	}
 }
 
-size_t addrtree_size(const struct addrtree *tree)
+inline size_t
+addrtree_size(const struct addrtree *tree)
 {
-	struct addrnode *n;
-	size_t s;
-
-	if (!tree) return 0;
-	s = sizeof (struct addrnode); /* root always exists but not in LRU */
-	if (tree->root->elem) s += tree->sizefunc(tree->root->elem);
-	for (n = tree->first; n; n = n->next) {
-		s += sizeof (struct addredge) + sizeof (struct addrnode);
-		if (n->elem) s += tree->sizefunc(n->elem);
-	}
-	return s;
+	return tree?tree->size_bytes:0;
 }
 
 void addrtree_delete(struct addrtree *tree)
@@ -240,10 +247,12 @@ void addrtree_delete(struct addrtree *tree)
 	while ((n = tree->first)) {
 		tree->first = n->next;
 		clean_node(tree, n);
+		tree->size_bytes -= node_size(tree, n);
 		free(n->parent_edge->str);
 		free(n->parent_edge);
 		free(n);
 	}
+	log_assert(sizeof *tree == addrtree_size(tree));
 	free(tree);
 }
 
@@ -335,6 +344,7 @@ addrtree_insert(struct addrtree *tree, const addrkey_t *addr,
 			clean_node(tree, node);
 			node->elem = elem;
 			node->scope = scope;
+			tree->size_bytes += tree->sizefunc(elem);
 			return;
 		}
 		index = getbit(addr, sourcemask, depth);
@@ -357,6 +367,7 @@ addrtree_insert(struct addrtree *tree, const addrkey_t *addr,
 				free(newnode);
 				return;
 			}
+			tree->size_bytes += node_size(tree, newnode);
 			lru_push(tree, newnode);
 			lru_cleanup(tree);
 			return;
@@ -381,6 +392,7 @@ addrtree_insert(struct addrtree *tree, const addrkey_t *addr,
 			free(newnode);
 			return;
 		}
+		tree->size_bytes += node_size(tree, newnode);
 		lru_push(tree, newnode);
 		/* connect existing child to our new node */
 		index = getbit(edge->str, edge->len, common);
@@ -403,6 +415,7 @@ addrtree_insert(struct addrtree *tree, const addrkey_t *addr,
 				free(newnode);
 				return;
 			}
+			tree->size_bytes += node_size(tree, newnode);
 			lru_push(tree, newnode);
 		}
 		lru_cleanup(tree);
diff --git a/edns-subnet/addrtree.h b/edns-subnet/addrtree.h
index 43985c698..8c3000fe4 100644
--- a/edns-subnet/addrtree.h
+++ b/edns-subnet/addrtree.h
@@ -41,6 +41,8 @@ struct addrtree {
 	/** Maximum number of allowed nodes, will be enforced by LRU list.
 	 * Excluding the root node, 0 for unlimited */
 	unsigned int max_node_count;
+	/** Size of tree in bytes */
+	size_t size_bytes;
 	/** Maximum prefix length we are willing to cache. */
 	addrlen_t max_depth;
 	/** External function to delete elem. Called as 
-- 
2.47.2