From be24944a8a24aca28b54dafb6a1385507e5ca67c Mon Sep 17 00:00:00 2001 From: Sebastian Harl Date: Fri, 11 Jul 2014 17:42:33 +0200 Subject: [PATCH] avltree: Iterate through the tree depth-first when clearing it. Else, we cannot simple delete each node but we'd have to actually remove it from the tree because we'd be removing non-leaf nodes. Don't use recursion for iterating the tree. It's not needed and would consume stack-space unnecessarily. The current approach limits the size of the tree by heap memory only. --- src/utils/avltree.c | 25 +++++++++++++++++++++++-- 1 file changed, 23 insertions(+), 2 deletions(-) diff --git a/src/utils/avltree.c b/src/utils/avltree.c index 7397a34..aad2b9a 100644 --- a/src/utils/avltree.c +++ b/src/utils/avltree.c @@ -154,9 +154,30 @@ tree_clear(sdb_avltree_t *tree) { node_t *n; - n = node_smallest(tree); + if ((! tree) || (! tree->root)) + return; + + /* do a depth-first iteration and delete the leafs */ + n = tree->root; while (n) { - node_t *tmp = node_next(n); + node_t *tmp; + + if (n->left) { + n = n->left; + continue; + } + else if (n->right) { + n = n->right; + continue; + } + + tmp = n->parent; + if (tmp) { + if (tmp->left == n) + tmp->left = NULL; + else + tmp->right = NULL; + } node_destroy(n); n = tmp; -- 2.30.2