From bb9d3ce25dd09b96cdf232477c90414270c503e8 Mon Sep 17 00:00:00 2001 From: David Robillard Date: Fri, 10 Sep 2021 20:11:34 -0400 Subject: Allow ZixBTreeIter to be allocated on the stack --- benchmark/tree_bench.c | 11 +- include/.clang-tidy | 1 + include/zix/btree.h | 90 ++++++++-------- include/zix/common.h | 5 +- meson.build | 4 +- src/btree.c | 274 +++++++++++++++++++------------------------------ test/btree_test.c | 57 ++-------- 7 files changed, 174 insertions(+), 268 deletions(-) diff --git a/benchmark/tree_bench.c b/benchmark/tree_bench.c index e01b64f..d27c506 100644 --- a/benchmark/tree_bench.c +++ b/benchmark/tree_bench.c @@ -154,9 +154,9 @@ bench_zix_btree(size_t n_elems, { start_test("ZixBTree"); - uintptr_t r = 0u; - ZixBTreeIter* ti = NULL; - ZixBTree* t = zix_btree_new(int_cmp, NULL); + uintptr_t r = 0u; + ZixBTreeIter ti = zix_btree_end_iter; + ZixBTree* t = zix_btree_new(int_cmp, NULL); // Insert n_elems elements struct timespec insert_start = bench_start(); @@ -185,12 +185,11 @@ bench_zix_btree(size_t n_elems, // Iterate over all elements struct timespec iter_start = bench_start(); - ZixBTreeIter* iter = zix_btree_begin(t); - for (; !zix_btree_iter_is_end(iter); zix_btree_iter_increment(iter)) { + ZixBTreeIter iter = zix_btree_begin(t); + for (; !zix_btree_iter_is_end(iter); zix_btree_iter_increment(&iter)) { volatile void* const value = zix_btree_get(iter); (void)value; } - zix_btree_iter_free(iter); fprintf(iter_dat, "\t%lf", bench_end(&iter_start)); // Delete all elements diff --git a/include/.clang-tidy b/include/.clang-tidy index 8399cae..fec15b8 100644 --- a/include/.clang-tidy +++ b/include/.clang-tidy @@ -1,5 +1,6 @@ Checks: > *, + -*-uppercase-literal-suffix, -altera-struct-pack-align, -clang-diagnostic-unused-function, -clang-diagnostic-unused-macros, diff --git a/include/zix/btree.h b/include/zix/btree.h index 5472eca..5212ec7 100644 --- a/include/zix/btree.h +++ b/include/zix/btree.h @@ -21,6 +21,7 @@ #include #include +#include #ifdef __cplusplus extern "C" { @@ -33,6 +34,19 @@ extern "C" { @{ */ +/** + The maximum height of a ZixBTree. + + This is exposed because it determines the size of iterators, which are + statically sized so they can used on the stack. The usual degree (or + "fanout") of a B-Tree is high enough that a relatively short tree can + contain many elements. With the default page size of 4 KiB, the default + height of 6 is enough to store trillions. +*/ +#ifndef ZIX_BTREE_MAX_HEIGHT +# define ZIX_BTREE_MAX_HEIGHT 6u +#endif + /// A B-Tree typedef struct ZixBTreeImpl ZixBTree; @@ -42,10 +56,23 @@ typedef struct ZixBTreeNodeImpl ZixBTreeNode; /** An iterator over a B-Tree. - Note that modifying the trees invalidates all iterators, so all iterators - are const iterators. + Note that modifying the tree invalidates all iterators. + + The contents of this type are considered an implementation detail and should + not be used directly by clients. They are nevertheless exposed here so that + iterators can be allocated on the stack. */ -typedef struct ZixBTreeIterImpl ZixBTreeIter; +typedef struct { + ZixBTreeNode* nodes[ZIX_BTREE_MAX_HEIGHT]; ///< Parallel node pointer stack + uint16_t indexes[ZIX_BTREE_MAX_HEIGHT]; ///< Parallel child index stack + uint16_t level; ///< Current level in stack +} ZixBTreeIter; + +/// A static end iterator for convenience +static const ZixBTreeIter zix_btree_end_iter = { + {NULL, NULL, NULL, NULL, NULL, NULL}, + {0u, 0u, 0u, 0u, 0u, 0u}, + 0u}; /// Create a new (empty) B-Tree ZIX_API @@ -91,22 +118,21 @@ zix_btree_insert(ZixBTree* t, void* e); @param out Set to point to the removed pointer (which may not equal `e`). - @param next If non-NULL, pointed to the value following `e`. If *next is - also non-NULL, the iterator is reused, otherwise a new one is allocated. To - reuse an iterator, no items may have been added since its creation. + @param next On successful return, set to point at the value that immediately + followed `e`. */ ZIX_API ZixStatus -zix_btree_remove(ZixBTree* t, const void* e, void** out, ZixBTreeIter** next); +zix_btree_remove(ZixBTree* t, const void* e, void** out, ZixBTreeIter* next); /** Set `ti` to an element equal to `e` in `t`. - If no such item exists, `ti` is set to NULL. + If no such item exists, `ti` is set to the end. */ ZIX_API ZixStatus -zix_btree_find(const ZixBTree* t, const void* e, ZixBTreeIter** ti); +zix_btree_find(const ZixBTree* t, const void* e, ZixBTreeIter* ti); /** Set `ti` to the smallest element in `t` that is not less than `e`. @@ -117,56 +143,40 @@ zix_btree_find(const ZixBTree* t, const void* e, ZixBTreeIter** ti); */ ZIX_API ZixStatus -zix_btree_lower_bound(const ZixBTree* t, const void* e, ZixBTreeIter** ti); +zix_btree_lower_bound(const ZixBTree* t, const void* e, ZixBTreeIter* ti); /// Return the data associated with the given tree item ZIX_PURE_API void* -zix_btree_get(const ZixBTreeIter* ti); +zix_btree_get(ZixBTreeIter ti); -/** - Return an iterator to the first (smallest) element in `t`. - - The returned iterator must be freed with zix_btree_iter_free(). -*/ +/// Return an iterator to the first (smallest) element in `t` ZIX_PURE_API -ZixBTreeIter* +ZixBTreeIter zix_btree_begin(const ZixBTree* t); -/** - Return an iterator to the end of `t` (one past the last element). - - The returned iterator must be freed with zix_btree_iter_free(). -*/ -ZIX_API -ZixBTreeIter* +/// Return an iterator to the end of `t` (one past the last element) +ZIX_CONST_API +ZixBTreeIter zix_btree_end(const ZixBTree* t); -/// Return a new copy of `i` -ZIX_API -ZixBTreeIter* -zix_btree_iter_copy(const ZixBTreeIter* i); - /// Return true iff `lhs` is equal to `rhs` ZIX_PURE_API bool -zix_btree_iter_equals(const ZixBTreeIter* lhs, const ZixBTreeIter* rhs); +zix_btree_iter_equals(ZixBTreeIter lhs, ZixBTreeIter rhs); -/// Return true iff `i` is an iterator to the end of its tree -ZIX_PURE_API -bool -zix_btree_iter_is_end(const ZixBTreeIter* i); +/// Return true iff `i` is an iterator at the end of a tree +static inline bool +zix_btree_iter_is_end(const ZixBTreeIter i) +{ + return i.level == 0 && !i.nodes[0]; +} /// Increment `i` to point to the next element in the tree ZIX_API -void +ZixStatus zix_btree_iter_increment(ZixBTreeIter* i); -/// Free `i` -ZIX_API -void -zix_btree_iter_free(ZixBTreeIter* i); - /** @} @} diff --git a/include/zix/common.h b/include/zix/common.h index 926e281..02f00b4 100644 --- a/include/zix/common.h +++ b/include/zix/common.h @@ -87,7 +87,8 @@ typedef enum { ZIX_STATUS_NOT_FOUND, ZIX_STATUS_EXISTS, ZIX_STATUS_BAD_ARG, - ZIX_STATUS_BAD_PERMS + ZIX_STATUS_BAD_PERMS, + ZIX_STATUS_REACHED_END } ZixStatus; static inline const char* @@ -108,6 +109,8 @@ zix_strerror(const ZixStatus status) return "Bad argument"; case ZIX_STATUS_BAD_PERMS: return "Bad permissions"; + case ZIX_STATUS_REACHED_END: + return "Reached end"; } return "Unknown error"; } diff --git a/meson.build b/meson.build index 8be6321..cdde084 100644 --- a/meson.build +++ b/meson.build @@ -54,7 +54,7 @@ if get_option('strict') '-Wformat-signedness', '-Wformat-truncation=2', '-Wformat=2', - '-Wframe-larger-than=512', + '-Wframe-larger-than=1024', '-Wimplicit-fallthrough=2', '-Winit-self', # '-Winline', @@ -74,7 +74,7 @@ if get_option('strict') '-Wshift-overflow=2', '-Wsizeof-array-argument', '-Wstack-protector', - '-Wstack-usage=512', + '-Wstack-usage=1024', '-Wstrict-aliasing=3', # '-Wstrict-overflow=5', '-Wstringop-overflow=3', diff --git a/src/btree.c b/src/btree.c index eb5a5f5..483cfa8 100644 --- a/src/btree.c +++ b/src/btree.c @@ -43,7 +43,6 @@ struct ZixBTreeImpl { ZixComparator cmp; const void* cmp_data; size_t size; - unsigned height; ///< Number of levels, i.e. root only has height 1 }; struct ZixBTreeNodeImpl { @@ -83,7 +82,9 @@ zix_btree_node_new(const bool leaf) { #if !((defined(__STDC_VERSION__) && __STDC_VERSION__ >= 201112l) || \ (defined(__cplusplus) && __cplusplus >= 201103L)) - assert(sizeof(ZixBTreeNode) == ZIX_BTREE_PAGE_SIZE); + assert(sizeof(ZixBTreeNode) <= ZIX_BTREE_PAGE_SIZE); + assert(sizeof(ZixBTreeNode) >= + ZIX_BTREE_PAGE_SIZE - 2u * sizeof(ZixBTreeNode*)); #endif ZixBTreeNode* node = (ZixBTreeNode*)malloc(sizeof(ZixBTreeNode)); @@ -120,7 +121,6 @@ zix_btree_new(const ZixComparator cmp, const void* const cmp_data) t->cmp = cmp; t->cmp_data = cmp_data; t->size = 0; - t->height = 1; if (!t->root) { free(t); return NULL; @@ -172,7 +172,6 @@ zix_btree_clear(ZixBTree* const t, ZixDestroyFunc destroy) memset(t->root, 0, sizeof(ZixBTreeNode)); t->root->is_leaf = true; t->size = 0u; - t->height = 1u; } size_t @@ -336,7 +335,6 @@ zix_btree_insert(ZixBTree* const t, void* const e) } t->root = parent; parent->data.inode.children[0] = n; - ++t->height; } ZixBTreeNode* const rhs = zix_btree_split_child(parent, i, n); @@ -380,27 +378,35 @@ zix_btree_insert(ZixBTree* const t, void* const e) return ZIX_STATUS_SUCCESS; } -static ZixBTreeIter* -zix_btree_iter_new(const ZixBTree* const t) +static void +zix_btree_iter_set_frame(ZixBTreeIter* const ti, + ZixBTreeNode* const n, + const ZixShort i) { - const size_t s = t->height * sizeof(ZixBTreeIterFrame); + assert(i <= ZIX_BTREE_LEAF_VALS); - ZixBTreeIter* i = (ZixBTreeIter*)calloc(1, sizeof(ZixBTreeIter) + s); - if (i) { - i->n_levels = t->height; - } - return i; + ti->nodes[ti->level] = n; + ti->indexes[ti->level] = (uint16_t)i; } static void -zix_btree_iter_set_frame(ZixBTreeIter* const ti, - ZixBTreeNode* const n, - const unsigned i) +zix_btree_iter_push(ZixBTreeIter* const ti, + ZixBTreeNode* const n, + const ZixShort i) { - if (ti) { - ti->stack[ti->level].node = n; - ti->stack[ti->level].index = i; - } + assert(ti->level < ZIX_BTREE_MAX_HEIGHT); + ++ti->level; + ti->nodes[ti->level] = n; + ti->indexes[ti->level] = (uint16_t)i; +} + +static void +zix_btree_iter_pop(ZixBTreeIter* const ti) +{ + assert(ti->level > 0u); + ti->nodes[ti->level] = NULL; + ti->indexes[ti->level] = 0u; + --ti->level; } ZIX_PURE_FUNC @@ -574,21 +580,15 @@ zix_btree_remove_max(ZixBTree* const t, ZixBTreeNode* n) } ZixStatus -zix_btree_remove(ZixBTree* const t, - const void* const e, - void** const out, - ZixBTreeIter** const next) -{ - ZixBTreeNode* n = t->root; - ZixBTreeIter* ti = NULL; - const bool user_iter = next && *next; - if (next) { - if (!*next && !(*next = zix_btree_iter_new(t))) { - return ZIX_STATUS_NO_MEM; - } - ti = *next; - ti->level = 0; - } +zix_btree_remove(ZixBTree* const t, + const void* const e, + void** const out, + ZixBTreeIter* const next) +{ + ZixBTreeNode* n = t->root; + ZixBTreeIter* ti = next; + + *ti = zix_btree_end_iter; while (true) { /* To remove in a single walk down, the tree is adjusted along the way @@ -606,10 +606,10 @@ zix_btree_remove(ZixBTree* const t, *out = zix_btree_aerase(n->data.leaf.vals, --n->n_vals, i); if (ti && i == n->n_vals) { if (i == 0) { - ti->level = 0; - ti->stack[0].node = NULL; + ti->level = 0; + ti->nodes[0] = NULL; } else { - --ti->stack[ti->level].index; + --ti->indexes[ti->level]; zix_btree_iter_increment(ti); } } @@ -618,11 +618,7 @@ zix_btree_remove(ZixBTree* const t, } // Not found in leaf node, or tree - if (ti && !user_iter) { - zix_btree_iter_free(ti); - *next = NULL; - } - + *next = zix_btree_end_iter; return ZIX_STATUS_NOT_FOUND; } @@ -666,11 +662,9 @@ zix_btree_remove(ZixBTree* const t, const ZixShort counts[2] = {zix_btree_child(n, 0)->n_vals, zix_btree_child(n, 1)->n_vals}; - n = zix_btree_merge(t, n, 0); - if (ti) { - ti->stack[ti->level].node = n; - ti->stack[ti->level].index = counts[i]; - } + n = zix_btree_merge(t, n, 0); + ti->nodes[ti->level] = n; + ti->indexes[ti->level] = (uint16_t)counts[i]; } else { // Both child's siblings are minimal, merge them if (i < n->n_vals) { @@ -678,7 +672,7 @@ zix_btree_remove(ZixBTree* const t, } else { n = zix_btree_merge(t, n, i - 1U); if (ti) { - --ti->stack[ti->level].index; + --ti->indexes[ti->level]; } } } @@ -698,18 +692,17 @@ zix_btree_remove(ZixBTree* const t, ZixStatus zix_btree_find(const ZixBTree* const t, const void* const e, - ZixBTreeIter** const ti) + ZixBTreeIter* const ti) { ZixBTreeNode* n = t->root; - if (!(*ti = zix_btree_iter_new(t))) { - return ZIX_STATUS_NO_MEM; - } + + *ti = zix_btree_end_iter; while (n) { bool equal = false; const unsigned i = zix_btree_node_find(t, n, e, &equal); - zix_btree_iter_set_frame(*ti, n, i); + zix_btree_iter_set_frame(ti, n, (uint16_t)i); if (equal) { return ZIX_STATUS_SUCCESS; @@ -719,45 +712,33 @@ zix_btree_find(const ZixBTree* const t, break; } - ++(*ti)->level; + ++ti->level; n = zix_btree_child(n, i); } - zix_btree_iter_free(*ti); - *ti = NULL; + *ti = zix_btree_end_iter; return ZIX_STATUS_NOT_FOUND; } ZixStatus zix_btree_lower_bound(const ZixBTree* const t, const void* const e, - ZixBTreeIter** const ti) + ZixBTreeIter* const ti) { - if (!t) { - *ti = NULL; - return ZIX_STATUS_BAD_ARG; - } - - if (!t->root) { - *ti = NULL; - return ZIX_STATUS_SUCCESS; - } - ZixBTreeNode* n = t->root; bool found = false; unsigned found_level = 0; - if (!(*ti = zix_btree_iter_new(t))) { - return ZIX_STATUS_NO_MEM; - } + + *ti = zix_btree_end_iter; while (n) { bool equal = false; const unsigned i = zix_btree_node_find(t, n, e, &equal); - zix_btree_iter_set_frame(*ti, n, i); + zix_btree_iter_set_frame(ti, n, (uint16_t)i); if (equal) { - found_level = (*ti)->level; + found_level = ti->level; found = true; } @@ -765,21 +746,18 @@ zix_btree_lower_bound(const ZixBTree* const t, break; } - ++(*ti)->level; + ++ti->level; n = zix_btree_child(n, i); assert(n); } - const ZixBTreeIterFrame* const frame = &(*ti)->stack[(*ti)->level]; - assert(frame->node); - if (frame->index == frame->node->n_vals) { + if (ti->indexes[ti->level] == ti->nodes[ti->level]->n_vals) { if (found) { // Found on a previous level but went too far - (*ti)->level = found_level; + ti->level = (uint16_t)found_level; } else { // Reached end (key is greater than everything in tree) - (*ti)->level = 0; - (*ti)->stack[0].node = NULL; + *ti = zix_btree_end_iter; } } @@ -787,130 +765,86 @@ zix_btree_lower_bound(const ZixBTree* const t, } void* -zix_btree_get(const ZixBTreeIter* const ti) +zix_btree_get(const ZixBTreeIter ti) { - const ZixBTreeIterFrame* const frame = &ti->stack[ti->level]; - assert(frame->node); - assert(frame->index < frame->node->n_vals); - return zix_btree_value(frame->node, frame->index); + const ZixBTreeNode* const node = ti.nodes[ti.level]; + const unsigned index = ti.indexes[ti.level]; + + assert(node); + assert(index < node->n_vals); + + return node->is_leaf ? node->data.leaf.vals[index] + : node->data.inode.vals[index]; } -ZixBTreeIter* +ZixBTreeIter zix_btree_begin(const ZixBTree* const t) { - ZixBTreeIter* const i = zix_btree_iter_new(t); - if (!i) { - return NULL; - } + ZixBTreeIter iter = zix_btree_end_iter; + + if (t->size > 0u) { + ZixBTreeNode* n = t->root; + zix_btree_iter_set_frame(&iter, n, 0u); - if (t->size == 0) { - i->level = 0; - i->stack[0].node = NULL; - } else { - ZixBTreeNode* n = t->root; - i->stack[0].node = n; - i->stack[0].index = 0; while (!n->is_leaf) { n = zix_btree_child(n, 0); - ++i->level; - i->stack[i->level].node = n; - i->stack[i->level].index = 0; + zix_btree_iter_push(&iter, n, 0u); } } - return i; + return iter; } -ZixBTreeIter* +ZixBTreeIter zix_btree_end(const ZixBTree* const t) { - return zix_btree_iter_new(t); -} - -ZixBTreeIter* -zix_btree_iter_copy(const ZixBTreeIter* const i) -{ - if (!i) { - return NULL; - } - - const size_t s = i->n_levels * sizeof(ZixBTreeIterFrame); - ZixBTreeIter* j = (ZixBTreeIter*)calloc(1, sizeof(ZixBTreeIter) + s); - if (j) { - memcpy(j, i, sizeof(ZixBTreeIter) + s); - } + (void)t; - return j; -} - -bool -zix_btree_iter_is_end(const ZixBTreeIter* const i) -{ - return !i || (i->level == 0 && i->stack[0].node == NULL); + return zix_btree_end_iter; } bool -zix_btree_iter_equals(const ZixBTreeIter* const lhs, - const ZixBTreeIter* const rhs) +zix_btree_iter_equals(const ZixBTreeIter lhs, const ZixBTreeIter rhs) { - if (zix_btree_iter_is_end(lhs) && zix_btree_iter_is_end(rhs)) { - return true; - } - - if (zix_btree_iter_is_end(lhs) || zix_btree_iter_is_end(rhs) || - lhs->level != rhs->level) { - return false; - } + const size_t indexes_size = (lhs.level + 1u) * sizeof(uint16_t); - return !memcmp(lhs, - rhs, - sizeof(ZixBTreeIter) + - (lhs->level + 1) * sizeof(ZixBTreeIterFrame)); + return (lhs.level == rhs.level) && (lhs.nodes[0] == rhs.nodes[0]) && + (!lhs.nodes[0] || !memcmp(lhs.indexes, rhs.indexes, indexes_size)); } -void +ZixStatus zix_btree_iter_increment(ZixBTreeIter* const i) { - ZixBTreeIterFrame* f = &i->stack[i->level]; - if (f->node->is_leaf) { - // Leaf, move right - assert(f->index < f->node->n_vals); - if (++f->index == f->node->n_vals) { - // Reached end of leaf, move up - f = &i->stack[i->level]; - while (i->level > 0 && f->index == f->node->n_vals) { - f = &i->stack[--i->level]; - assert(f->index <= f->node->n_vals); - } + assert(!zix_btree_iter_is_end(*i)); - if (f->index == f->node->n_vals) { - // Reached end of tree - assert(i->level == 0); - f->node = NULL; - f->index = 0; + // Move to the next value in the current node + const uint16_t index = ++i->indexes[i->level]; + + if (i->nodes[i->level]->is_leaf) { + // Leaf, move up if necessary until we're not at the end of the node + while (i->indexes[i->level] >= i->nodes[i->level]->n_vals) { + if (i->level == 0) { + // End of root, end of tree + i->nodes[0] = NULL; + return ZIX_STATUS_REACHED_END; } + + // At end of internal node, move up + zix_btree_iter_pop(i); } + } else { // Internal node, move down to next child - assert(f->index < f->node->n_vals); - ZixBTreeNode* child = zix_btree_child(f->node, ++f->index); + const ZixBTreeNode* const node = i->nodes[i->level]; + ZixBTreeNode* const child = node->data.inode.children[index]; - f = &i->stack[++i->level]; - f->node = child; - f->index = 0; + zix_btree_iter_push(i, child, 0u); // Move down and left until we hit a leaf - while (!f->node->is_leaf) { - child = zix_btree_child(f->node, 0); - f = &i->stack[++i->level]; - f->node = child; - f->index = 0; + while (!i->nodes[i->level]->is_leaf) { + zix_btree_iter_push(i, i->nodes[i->level]->data.inode.children[0], 0u); } } -} -void -zix_btree_iter_free(ZixBTreeIter* const i) -{ - free(i); + return ZIX_STATUS_SUCCESS; } diff --git a/test/btree_test.c b/test/btree_test.c index 4e84ac4..c5b575d 100644 --- a/test/btree_test.c +++ b/test/btree_test.c @@ -172,11 +172,8 @@ stress(const unsigned test_num, const size_t n_elems) } // Ensure begin iterator is end on empty tree - ZixBTreeIter* ti = zix_btree_begin(t); - ZixBTreeIter* end = zix_btree_end(t); - if (!ti) { - return test_fail(t, "Failed to allocate iterator\n"); - } + ZixBTreeIter ti = zix_btree_begin(t); + ZixBTreeIter end = zix_btree_end(t); if (!zix_btree_iter_is_end(ti)) { return test_fail(t, "Begin iterator on empty tree is not end\n"); @@ -186,13 +183,6 @@ stress(const unsigned test_num, const size_t n_elems) return test_fail(t, "Begin and end of empty tree are not equal\n"); } - zix_btree_iter_free(end); - zix_btree_iter_free(ti); - - if (zix_btree_iter_copy(NULL)) { - return test_fail(t, "Copy of null iterator returned non-null\n"); - } - // Insert n_elems elements for (size_t i = 0; i < n_elems; ++i) { r = ith_elem(test_num, n_elems, i); @@ -220,15 +210,6 @@ stress(const unsigned test_num, const size_t n_elems) if (zix_btree_iter_equals(ti, end)) { return test_fail(t, "Begin and end of non-empty tree are equal\n"); } - zix_btree_iter_free(end); - - // Ensure non-null iterator copying works - ZixBTreeIter* begin_copy = zix_btree_iter_copy(ti); - if (!zix_btree_iter_equals(ti, begin_copy)) { - return test_fail(t, "Iterator copy is not equal to original\n"); - } - zix_btree_iter_free(begin_copy); - zix_btree_iter_free(ti); // Search for all elements for (size_t i = 0; i < n_elems; ++i) { @@ -244,12 +225,6 @@ stress(const unsigned test_num, const size_t n_elems) (uintptr_t)zix_btree_get(ti), r); } - - zix_btree_iter_free(ti); - } - - if (zix_btree_lower_bound(NULL, (void*)r, &ti) != ZIX_STATUS_BAD_ARG) { - return test_fail(t, "Lower bound on NULL tree succeeded\n"); } // Find the lower bound of all elements and ensure it's exact @@ -273,8 +248,6 @@ stress(const unsigned test_num, const size_t n_elems) (uintptr_t)zix_btree_get(ti), r); } - - zix_btree_iter_free(ti); } // Search for elements that don't exist @@ -289,7 +262,7 @@ stress(const unsigned test_num, const size_t n_elems) size_t i = 0; uintptr_t last = 0; for (ti = zix_btree_begin(t); !zix_btree_iter_is_end(ti); - zix_btree_iter_increment(ti), ++i) { + zix_btree_iter_increment(&ti), ++i) { const uintptr_t iter_data = (uintptr_t)zix_btree_get(ti); if (iter_data < last) { return test_fail(t, @@ -301,7 +274,7 @@ stress(const unsigned test_num, const size_t n_elems) } last = iter_data; } - zix_btree_iter_free(ti); + if (i != n_elems) { return test_fail(t, "Iteration stopped at %" PRIuPTR "/%" PRIuPTR @@ -324,18 +297,17 @@ stress(const unsigned test_num, const size_t n_elems) return test_fail(t, "Find %" PRIuPTR " failed\n", (uintptr_t)r); } last = (uintptr_t)zix_btree_get(ti); - zix_btree_iter_increment(ti); - for (i = 1; !zix_btree_iter_is_end(ti); zix_btree_iter_increment(ti), ++i) { + zix_btree_iter_increment(&ti); + for (i = 1; !zix_btree_iter_is_end(ti); zix_btree_iter_increment(&ti), ++i) { if ((uintptr_t)zix_btree_get(ti) == last) { return test_fail( t, "Duplicate element @ %" PRIuPTR " %" PRIuPTR "\n", i, last); } last = (uintptr_t)zix_btree_get(ti); } - zix_btree_iter_free(ti); // Delete all elements - ZixBTreeIter* next = NULL; + ZixBTreeIter next = zix_btree_end_iter; for (size_t e = 0; e < n_elems; e++) { r = ith_elem(test_num, n_elems, e); @@ -363,8 +335,6 @@ stress(const unsigned test_num, const size_t n_elems) } } } - zix_btree_iter_free(next); - next = NULL; // Ensure the tree is empty if (zix_btree_size(t) != 0) { @@ -388,8 +358,6 @@ stress(const unsigned test_num, const size_t n_elems) t, "Non-existant deletion of %" PRIuPTR " succeeded\n", (uintptr_t)r); } } - zix_btree_iter_free(next); - next = NULL; // Ensure tree size is still correct if (zix_btree_size(t) != n_elems) { @@ -425,8 +393,6 @@ stress(const unsigned test_num, const size_t n_elems) } } } - zix_btree_iter_free(next); - next = NULL; // Check tree size if (zix_btree_size(t) != n_elems - (n_elems / 4)) { @@ -446,8 +412,6 @@ stress(const unsigned test_num, const size_t n_elems) return test_fail(t, "Error deleting %" PRIuPTR "\n", (uintptr_t)r); } } - zix_btree_iter_free(next); - next = NULL; // Delete all remaining elements via next iterator next = zix_btree_begin(t); @@ -477,10 +441,8 @@ stress(const unsigned test_num, const size_t n_elems) last_value = removed; } - assert(!next || zix_btree_size(t) == 0); - zix_btree_iter_free(next); - next = NULL; + assert(zix_btree_size(t) == 0); zix_btree_free(t, NULL); // Test lower_bound with wildcard comparator @@ -526,8 +488,6 @@ stress(const unsigned test_num, const size_t n_elems) t, "Wildcard lower bound %" PRIuPTR " != %" PRIuPTR "\n", iter_data, cut); } - zix_btree_iter_free(ti); - // Find lower bound of value past end const uintptr_t max = (uintptr_t)-1; if (zix_btree_lower_bound(t, (void*)max, &ti)) { @@ -538,7 +498,6 @@ stress(const unsigned test_num, const size_t n_elems) return test_fail(t, "Lower bound of maximum value is not end\n"); } - zix_btree_iter_free(ti); zix_btree_free(t, NULL); return EXIT_SUCCESS; -- cgit v1.2.1