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>
---
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
Show replies by date