[libqb] [PATCH] map: free unused leaf nodes

[Angus Salkeld]

So if a node has no children and no value or notifier
then it is freed.

Signed-off-by: Angus Salkeld <asalkeld(a)redhat.com&gt;
---
 lib/trie.c        |   24 +++++++++++++++++++++++-
 tests/check_map.c |    7 +++++--
 2 files changed, 28 insertions(+), 3 deletions(-)

diff --git a/lib/trie.c b/lib/trie.c
index 62761cf..9561b99 100644
--- a/lib/trie.c
+++ b/lib/trie.c
@@ -333,6 +333,26 @@ trie_lookup(struct trie *t, const char *key, int exact_match)
 }
 
 static void
+trie_node_release(struct trie *t, struct trie_node *node)
+{
+	if (node->num_children == 0 &&
+	    node->refcount == 0 &&
+	    node->parent != NULL &&
+	    qb_list_empty(&node->notifier_head)) {
+		struct trie_node *p = node->parent;
+		/*
+		 * unlink the node from the parent
+		 */
+		p->children[node->idx] = NULL;
+		free(node);
+		t->num_nodes--;
+		t->mem_used -= sizeof(struct trie_node);
+
+		trie_node_release(t, p);
+	}
+}
+
+static void
 trie_node_destroy(struct trie *t, struct trie_node *n)
 {
 	if (n->value == NULL) {
@@ -342,6 +362,8 @@ trie_node_destroy(struct trie *t, struct trie_node *n)
 
 	n->key = NULL;
 	n->value = NULL;
+
+	trie_node_release(t, n);
 }
 
 static void
@@ -367,7 +389,6 @@ trie_print_node(struct trie_node *n, struct trie_node *r, const char
*suffix)
 	}
 }
 
-
 static void
 trie_node_ref(struct trie *t, struct trie_node *node)
 {
@@ -628,6 +649,7 @@ trie_notify_del(qb_map_t * m, const char *key,
 		}
 	}
 	if (found) {
+		trie_node_release(t, n);
 		return 0;
 	} else {
 		return -ENOENT;
diff --git a/tests/check_map.c b/tests/check_map.c
index 50c6317..23f005e 100644
--- a/tests/check_map.c
+++ b/tests/check_map.c
@@ -97,15 +97,18 @@ static int32_t
 check_order(const char *key, void *value, void *data)
 {
 	int *o = (int*)data;
-	ck_assert(chars[*o][0] == key[0]);
+	ck_assert_str_eq(chars[*o], key);
+	ck_assert_str_eq(chars[*o], value);
 	(*o)++;
 	return QB_FALSE;
 }
+
 static int32_t
 check_order2(const char *key, void *value, void *data)
 {
 	int *o = (int*)data;
-	ck_assert(chars2[*o][0] == key[0]);
+	ck_assert_str_eq(chars2[*o], key);
+	ck_assert_str_eq(chars2[*o], value);
 	(*o)++;
 	return QB_FALSE;
 }
-- 
1.7.7.4