So if a node has no children and no value or notifier then it is freed.
Signed-off-by: Angus Salkeld asalkeld@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; }