From 129bcfb52322c2e27fc0e63605bc04c99ac40f8c Mon Sep 17 00:00:00 2001 From: David Robillard Date: Fri, 10 Sep 2021 20:11:33 -0400 Subject: Remove destroy field of BTree and add zix_btree_clear() If this is used, it is only when clearing or freeing a tree. Allowing it to be given as a parameter directly there is clearer and avoids bloating the tree itself with information that isn't needed. --- benchmark/tree_bench.c | 4 ++-- include/zix/btree.h | 21 +++++++++++++--- src/btree.c | 65 ++++++++++++++++++++++++++++---------------------- test/btree_test.c | 63 ++++++++++++++++++++++++++++++++++++++++-------- 4 files changed, 109 insertions(+), 44 deletions(-) diff --git a/benchmark/tree_bench.c b/benchmark/tree_bench.c index f57538d..e01b64f 100644 --- a/benchmark/tree_bench.c +++ b/benchmark/tree_bench.c @@ -156,7 +156,7 @@ bench_zix_btree(size_t n_elems, uintptr_t r = 0u; ZixBTreeIter* ti = NULL; - ZixBTree* t = zix_btree_new(int_cmp, NULL, NULL); + ZixBTree* t = zix_btree_new(int_cmp, NULL); // Insert n_elems elements struct timespec insert_start = bench_start(); @@ -205,7 +205,7 @@ bench_zix_btree(size_t n_elems, } fprintf(del_dat, "\t%lf", bench_end(&del_start)); - zix_btree_free(t); + zix_btree_free(t, NULL); return EXIT_SUCCESS; } diff --git a/include/zix/btree.h b/include/zix/btree.h index bce3068..5472eca 100644 --- a/include/zix/btree.h +++ b/include/zix/btree.h @@ -50,12 +50,27 @@ typedef struct ZixBTreeIterImpl ZixBTreeIter; /// Create a new (empty) B-Tree ZIX_API ZixBTree* -zix_btree_new(ZixComparator cmp, const void* cmp_data, ZixDestroyFunc destroy); +zix_btree_new(ZixComparator cmp, const void* cmp_data); -/// Free `t` +/** + Free `t` and all the nodes it contains. + + @param destroy Function to call once for every value in the tree. This can + be used to free values if they are dynamically allocated. +*/ +ZIX_API +void +zix_btree_free(ZixBTree* t, ZixDestroyFunc destroy); + +/** + Clear everything from `t`, leaving it empty. + + @param destroy Function called exactly once for every value in the tree, + just before that value is removed from the tree. +*/ ZIX_API void -zix_btree_free(ZixBTree* t); +zix_btree_clear(ZixBTree* t, ZixDestroyFunc destroy); /// Return the number of elements in `t` ZIX_PURE_API diff --git a/src/btree.c b/src/btree.c index 65c6e7b..eb5a5f5 100644 --- a/src/btree.c +++ b/src/btree.c @@ -39,12 +39,11 @@ typedef uint16_t ZixShort; #define ZIX_BTREE_INODE_VALS (ZIX_BTREE_LEAF_VALS / 2u) struct ZixBTreeImpl { - ZixBTreeNode* root; - ZixDestroyFunc destroy; - ZixComparator cmp; - const void* cmp_data; - size_t size; - unsigned height; ///< Number of levels, i.e. root only has height 1 + ZixBTreeNode* root; + ZixComparator cmp; + const void* cmp_data; + size_t size; + unsigned height; ///< Number of levels, i.e. root only has height 1 }; struct ZixBTreeNodeImpl { @@ -113,14 +112,11 @@ zix_btree_child(const ZixBTreeNode* const node, const unsigned i) } ZixBTree* -zix_btree_new(const ZixComparator cmp, - const void* const cmp_data, - const ZixDestroyFunc destroy) +zix_btree_new(const ZixComparator cmp, const void* const cmp_data) { ZixBTree* t = (ZixBTree*)malloc(sizeof(ZixBTree)); if (t) { t->root = zix_btree_node_new(true); - t->destroy = destroy; t->cmp = cmp; t->cmp_data = cmp_data; t->size = 0; @@ -134,40 +130,51 @@ zix_btree_new(const ZixComparator cmp, } static void -zix_btree_free_rec(ZixBTree* const t, ZixBTreeNode* const n) -{ - if (n) { +zix_btree_free_children(ZixBTree* const t, + ZixBTreeNode* const n, + ZixDestroyFunc destroy) +{ + if (!n->is_leaf) { + for (ZixShort i = 0; i < n->n_vals + 1u; ++i) { + zix_btree_free_children(t, zix_btree_child(n, i), destroy); + free(zix_btree_child(n, i)); + } + } + + if (destroy) { if (n->is_leaf) { - if (t->destroy) { - for (ZixShort i = 0u; i < n->n_vals; ++i) { - t->destroy(n->data.leaf.vals[i]); - } + for (ZixShort i = 0u; i < n->n_vals; ++i) { + destroy(n->data.leaf.vals[i]); } } else { - if (t->destroy) { - for (ZixShort i = 0u; i < n->n_vals; ++i) { - t->destroy(n->data.inode.vals[i]); - } - } - - for (ZixShort i = 0u; i < n->n_vals + 1u; ++i) { - zix_btree_free_rec(t, zix_btree_child(n, i)); + for (ZixShort i = 0u; i < n->n_vals; ++i) { + destroy(n->data.inode.vals[i]); } } - - free(n); } } void -zix_btree_free(ZixBTree* const t) +zix_btree_free(ZixBTree* const t, ZixDestroyFunc destroy) { if (t) { - zix_btree_free_rec(t, t->root); + zix_btree_clear(t, destroy); + free(t->root); free(t); } } +void +zix_btree_clear(ZixBTree* const t, ZixDestroyFunc destroy) +{ + zix_btree_free_children(t, t->root, destroy); + + memset(t->root, 0, sizeof(ZixBTreeNode)); + t->root->is_leaf = true; + t->size = 0u; + t->height = 1u; +} + size_t zix_btree_size(const ZixBTree* const t) { diff --git a/test/btree_test.c b/test/btree_test.c index 6914053..4e84ac4 100644 --- a/test/btree_test.c +++ b/test/btree_test.c @@ -55,11 +55,6 @@ ith_elem(const unsigned test_num, const size_t n_elems, const size_t i) } } -static void -destroy(void* ZIX_UNUSED(ptr)) -{ -} - typedef struct { unsigned test_num; size_t n_elems; @@ -104,10 +99,11 @@ ZIX_LOG_FUNC(2, 3) static int test_fail(ZixBTree* t, const char* fmt, ...) { - zix_btree_free(t); + zix_btree_free(t, NULL); if (expect_failure) { return EXIT_SUCCESS; } + va_list args; va_start(args, fmt); fprintf(stderr, "error: "); @@ -116,6 +112,50 @@ test_fail(ZixBTree* t, const char* fmt, ...) return EXIT_FAILURE; } +static const size_t n_clear_insertions = 1024u; + +static void +destroy(void* const ptr) +{ + assert(ptr); + assert((uintptr_t)ptr <= n_clear_insertions); +} + +static void +no_destroy(void* const ptr) +{ + assert(!ptr); +} + +static void +test_clear(void) +{ + ZixBTree* t = zix_btree_new(int_cmp, NULL); + + for (uintptr_t r = 0u; r < n_clear_insertions; ++r) { + assert(!zix_btree_insert(t, (void*)(r + 1u))); + } + + zix_btree_clear(t, destroy); + assert(zix_btree_size(t) == 0); + + zix_btree_free(t, no_destroy); +} + +static void +test_free(void) +{ + ZixBTree* t = zix_btree_new(int_cmp, NULL); + + for (uintptr_t r = 0u; r < n_clear_insertions; ++r) { + assert(!zix_btree_insert(t, (void*)(r + 1u))); + } + + assert(zix_btree_size(t) == n_clear_insertions); + + zix_btree_free(t, destroy); +} + static int stress(const unsigned test_num, const size_t n_elems) { @@ -124,7 +164,7 @@ stress(const unsigned test_num, const size_t n_elems) } uintptr_t r = 0; - ZixBTree* t = zix_btree_new(int_cmp, NULL, NULL); + ZixBTree* t = zix_btree_new(int_cmp, NULL); ZixStatus st = ZIX_STATUS_SUCCESS; if (!t) { @@ -441,12 +481,12 @@ stress(const unsigned test_num, const size_t n_elems) zix_btree_iter_free(next); next = NULL; - zix_btree_free(t); + zix_btree_free(t, NULL); // Test lower_bound with wildcard comparator TestContext ctx = {test_num, n_elems}; - if (!(t = zix_btree_new(wildcard_cmp, &ctx, destroy))) { + if (!(t = zix_btree_new(wildcard_cmp, &ctx))) { return test_fail(t, "Failed to allocate tree\n"); } @@ -499,7 +539,7 @@ stress(const unsigned test_num, const size_t n_elems) } zix_btree_iter_free(ti); - zix_btree_free(t); + zix_btree_free(t, NULL); return EXIT_SUCCESS; } @@ -512,6 +552,9 @@ main(int argc, char** argv) return EXIT_FAILURE; } + test_clear(); + test_free(); + const unsigned n_tests = 3u; const size_t n_elems = (argc > 1) ? strtoul(argv[1], NULL, 10) : 524288u; -- cgit v1.2.1