summaryrefslogtreecommitdiffstats
path: root/test/test_btree.c
diff options
context:
space:
mode:
Diffstat (limited to 'test/test_btree.c')
-rw-r--r--test/test_btree.c427
1 files changed, 192 insertions, 235 deletions
diff --git a/test/test_btree.c b/test/test_btree.c
index 7392ff8..e918799 100644
--- a/test/test_btree.c
+++ b/test/test_btree.c
@@ -1,10 +1,11 @@
-// Copyright 2011-2021 David Robillard <d@drobilla.net>
+// Copyright 2011-2023 David Robillard <d@drobilla.net>
// SPDX-License-Identifier: ISC
#undef NDEBUG
#include "zix/btree.h"
+#include "ensure.h"
#include "failing_allocator.h"
#include "test_args.h"
#include "test_data.h"
@@ -16,12 +17,9 @@
#include <assert.h>
#include <inttypes.h>
#include <stdarg.h>
-#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
-static bool expect_failure = false;
-
ZIX_PURE_FUNC
static int
int_cmp(const void* a, const void* b, const void* ZIX_UNUSED(user_data))
@@ -69,23 +67,13 @@ wildcard_cmp(const void* a, const void* b, const void* user_data)
const uintptr_t ia = (uintptr_t)a;
const uintptr_t ib = (uintptr_t)b;
- if (ia == 0) {
- if (ib >= wildcard_cut(test_num, n_elems)) {
- return 0; // Wildcard match
- }
-
- return 1; // Wildcard a > b
- }
-
- if (ib == 0) {
- if (ia >= wildcard_cut(test_num, n_elems)) {
- return 0; // Wildcard match
- }
-
- return -1; // Wildcard b > a
- }
-
- return int_cmp(a, b, user_data);
+ return (ia == 0)
+ ? ((ib >= wildcard_cut(test_num, n_elems)) ? 0 // Wildcard match
+ : 1) // Wildcard a > b
+ : (ib == 0)
+ ? ((ia >= wildcard_cut(test_num, n_elems)) ? 0 // Wildcard match
+ : -1) // Wildcard b > a
+ : int_cmp(a, b, user_data);
}
ZIX_LOG_FUNC(2, 3)
@@ -93,9 +81,6 @@ static int
test_fail(ZixBTree* t, const char* fmt, ...)
{
zix_btree_free(t, NULL, NULL);
- if (expect_failure) {
- return EXIT_SUCCESS;
- }
va_list args; // NOLINT(cppcoreguidelines-init-variables)
va_start(args, fmt);
@@ -106,24 +91,18 @@ test_fail(ZixBTree* t, const char* fmt, ...)
}
static const size_t n_clear_insertions = 1024U;
+static size_t n_destroy_calls = 0U;
static void
destroy(void* const ptr, const void* const user_data)
{
(void)user_data;
+ ++n_destroy_calls;
assert(ptr);
assert((uintptr_t)ptr <= n_clear_insertions);
}
static void
-no_destroy(void* const ptr, const void* const user_data)
-{
- (void)ptr;
- (void)user_data;
- assert(!ptr);
-}
-
-static void
test_clear(void)
{
ZixBTree* t = zix_btree_new(NULL, int_cmp, NULL);
@@ -132,10 +111,17 @@ test_clear(void)
assert(!zix_btree_insert(t, (void*)(r + 1U)));
}
+ // Clear and check that destroy is called once for each element
+ assert(n_destroy_calls == 0U);
+ zix_btree_clear(t, destroy, &n_destroy_calls);
+ assert(zix_btree_size(t) == 0U);
+ assert(n_destroy_calls == n_clear_insertions);
+
+ // Clear the now-empty tree and check that destroy isn't called again
zix_btree_clear(t, destroy, NULL);
- assert(zix_btree_size(t) == 0);
+ assert(n_destroy_calls == n_clear_insertions);
- zix_btree_free(t, no_destroy, NULL);
+ zix_btree_free(t, destroy, NULL);
}
static void
@@ -257,103 +243,91 @@ stress(ZixAllocator* const allocator,
const unsigned test_num,
const size_t n_elems)
{
- if (n_elems == 0) {
- return 0;
- }
+ assert(n_elems > 0U);
uintptr_t r = 0;
ZixBTree* t = zix_btree_new(allocator, int_cmp, NULL);
ZixStatus st = ZIX_STATUS_SUCCESS;
- if (!t) {
- return test_fail(t, "Failed to allocate tree\n");
- }
+ ENSURE(t, t, "Failed to allocate tree\n");
// Ensure begin iterator is end on empty tree
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");
- }
+ ENSURE(
+ t, zix_btree_iter_is_end(ti), "Begin iterator on empty tree is not end\n");
- if (!zix_btree_iter_equals(ti, end)) {
- return test_fail(t, "Begin and end of empty tree are not equal\n");
- }
+ ENSURE(t,
+ zix_btree_iter_equals(ti, end),
+ "Begin and end of empty tree are not equal\n");
// Insert n_elems elements
for (size_t i = 0; i < n_elems; ++i) {
- r = ith_elem(test_num, n_elems, i);
- if (!zix_btree_find(t, (void*)r, &ti)) {
- return test_fail(t, "%" PRIuPTR " already in tree\n", (uintptr_t)r);
- }
-
- if ((st = zix_btree_insert(t, (void*)r))) {
- return test_fail(
- t, "Insert %" PRIuPTR " failed (%s)\n", (uintptr_t)r, zix_strerror(st));
- }
+ r = ith_elem(test_num, n_elems, i);
+ st = zix_btree_insert(t, (void*)r);
+ ENSUREV(t, !st, "Insert %" PRIuPTR " failed (%s)\n", r, zix_strerror(st));
}
// Ensure tree size is correct
- if (zix_btree_size(t) != n_elems) {
- return test_fail(t,
- "Tree size %" PRIuPTR " != %" PRIuPTR "\n",
- zix_btree_size(t),
- n_elems);
- }
+ ENSUREV(t,
+ zix_btree_size(t) == n_elems,
+ "Tree size %" PRIuPTR " != %" PRIuPTR "\n",
+ zix_btree_size(t),
+ n_elems);
// Ensure begin no longer equals end
ti = zix_btree_begin(t);
end = zix_btree_end(t);
- if (zix_btree_iter_equals(ti, end)) {
- return test_fail(t, "Begin and end of non-empty tree are equal\n");
- }
+ ENSURE(t,
+ !zix_btree_iter_equals(ti, end),
+ "Begin and end of non-empty tree are equal\n");
// Search for all elements
for (size_t i = 0; i < n_elems; ++i) {
r = ith_elem(test_num, n_elems, i);
- if (zix_btree_find(t, (void*)r, &ti)) {
- return test_fail(
- t, "Find %" PRIuPTR " @ %" PRIuPTR " failed\n", (uintptr_t)r, i);
- }
+ ENSUREV(t,
+ !zix_btree_find(t, (void*)r, &ti),
+ "Find %" PRIuPTR " @ %" PRIuPTR " failed\n",
+ r,
+ i);
- if ((uintptr_t)zix_btree_get(ti) != r) {
- return test_fail(t,
- "Search data corrupt (%" PRIuPTR " != %" PRIuPTR ")\n",
- (uintptr_t)zix_btree_get(ti),
- r);
- }
+ ENSUREV(t,
+ (uintptr_t)zix_btree_get(ti) == r,
+ "Search data corrupt (%" PRIuPTR " != %" PRIuPTR ")\n",
+ (uintptr_t)zix_btree_get(ti),
+ r);
}
// Find the lower bound of all elements and ensure it's exact
for (size_t i = 0; i < n_elems; ++i) {
r = ith_elem(test_num, n_elems, i);
- if (zix_btree_lower_bound(t, int_cmp, NULL, (void*)r, &ti)) {
- return test_fail(
- t, "Lower bound %" PRIuPTR " @ %" PRIuPTR " failed\n", (uintptr_t)r, i);
- }
+ ENSUREV(t,
+ !zix_btree_lower_bound(t, int_cmp, NULL, (void*)r, &ti),
+ "Lower bound %" PRIuPTR " @ %" PRIuPTR " failed\n",
+ r,
+ i);
- if (zix_btree_iter_is_end(ti)) {
- return test_fail(t,
- "Lower bound %" PRIuPTR " @ %" PRIuPTR " hit end\n",
- (uintptr_t)r,
- i);
- }
+ ENSUREV(t,
+ !zix_btree_iter_is_end(ti),
+ "Lower bound %" PRIuPTR " @ %" PRIuPTR " hit end\n",
+ r,
+ i);
- if ((uintptr_t)zix_btree_get(ti) != r) {
- return test_fail(t,
- "Lower bound corrupt (%" PRIuPTR " != %" PRIuPTR "\n",
- (uintptr_t)zix_btree_get(ti),
- r);
- }
+ ENSUREV(t,
+ (uintptr_t)zix_btree_get(ti) == r,
+ "Lower bound corrupt (%" PRIuPTR " != %" PRIuPTR "\n",
+ (uintptr_t)zix_btree_get(ti),
+ r);
}
// Search for elements that don't exist
for (size_t i = 0; i < n_elems; ++i) {
r = ith_elem(test_num, n_elems * 3, n_elems + i);
- if (!zix_btree_find(t, (void*)r, &ti)) {
- return test_fail(t, "Unexpectedly found %" PRIuPTR "\n", (uintptr_t)r);
- }
+ ENSUREV(t,
+ zix_btree_find(t, (void*)r, &ti),
+ "Unexpectedly found %" PRIuPTR "\n",
+ r);
}
// Iterate over all elements
@@ -362,143 +336,132 @@ stress(ZixAllocator* const allocator,
for (ti = zix_btree_begin(t); !zix_btree_iter_is_end(ti);
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,
- "Iter @ %" PRIuPTR " corrupt (%" PRIuPTR " < %" PRIuPTR
- ")\n",
- i,
- iter_data,
- last);
- }
+ ENSUREV(t,
+ iter_data >= last,
+ "Iter @ %" PRIuPTR " corrupt (%" PRIuPTR " < %" PRIuPTR ")\n",
+ i,
+ iter_data,
+ last);
+
last = iter_data;
}
- if (i != n_elems) {
- return test_fail(t,
- "Iteration stopped at %" PRIuPTR "/%" PRIuPTR
- " elements\n",
- i,
- n_elems);
- }
+ ENSUREV(t,
+ i == n_elems,
+ "Iteration stopped at %" PRIuPTR "/%" PRIuPTR " elements\n",
+ i,
+ n_elems);
// Insert n_elems elements again, ensuring duplicates fail
for (i = 0; i < n_elems; ++i) {
r = ith_elem(test_num, n_elems, i);
- if (!zix_btree_insert(t, (void*)r)) {
- return test_fail(t, "Duplicate insert succeeded\n");
- }
+ ENSURE(t, zix_btree_insert(t, (void*)r), "Duplicate insert succeeded\n");
}
// Search for the middle element then iterate from there
r = ith_elem(test_num, n_elems, n_elems / 2);
- if (zix_btree_find(t, (void*)r, &ti)) {
- return test_fail(t, "Find %" PRIuPTR " failed\n", (uintptr_t)r);
- }
+ ENSUREV(
+ t, !zix_btree_find(t, (void*)r, &ti), "Find %" PRIuPTR " failed\n", 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) {
- if ((uintptr_t)zix_btree_get(ti) == last) {
- return test_fail(
- t, "Duplicate element @ %" PRIuPTR " %" PRIuPTR "\n", i, last);
- }
+ ENSUREV(t,
+ (uintptr_t)zix_btree_get(ti) != last,
+ "Duplicate element @ %" PRIuPTR " %" PRIuPTR "\n",
+ i,
+ last);
last = (uintptr_t)zix_btree_get(ti);
}
- // Delete all elements
+ // Remove all elements
ZixBTreeIter next = zix_btree_end_iter;
for (size_t e = 0; e < n_elems; e++) {
r = ith_elem(test_num, n_elems, e);
uintptr_t removed = 0;
- if (zix_btree_remove(t, (void*)r, (void**)&removed, &next)) {
- return test_fail(t, "Error removing item %" PRIuPTR "\n", (uintptr_t)r);
- }
+ ENSUREV(t,
+ !zix_btree_remove(t, (void*)r, (void**)&removed, &next),
+ "Error removing item %" PRIuPTR "\n",
+ r);
- if (removed != r) {
- return test_fail(t,
- "Removed wrong item %" PRIuPTR " != %" PRIuPTR "\n",
- removed,
- (uintptr_t)r);
- }
+ ENSUREV(t,
+ removed == r,
+ "Removed wrong item %" PRIuPTR " != %" PRIuPTR "\n",
+ removed,
+ r);
if (test_num == 0) {
const uintptr_t next_value = ith_elem(test_num, n_elems, e + 1);
- if (!((zix_btree_iter_is_end(next) && e == n_elems - 1) ||
- (uintptr_t)zix_btree_get(next) == next_value)) {
- return test_fail(t,
- "Delete all next iterator %" PRIuPTR " != %" PRIuPTR
- "\n",
- (uintptr_t)zix_btree_get(next),
- next_value);
- }
+ ENSUREV(t,
+ (zix_btree_iter_is_end(next) && e == n_elems - 1) ||
+ ((uintptr_t)zix_btree_get(next) == next_value),
+ "Remove-all next value %" PRIuPTR " != %" PRIuPTR "\n",
+ (uintptr_t)zix_btree_get(next),
+ next_value);
}
}
// Ensure the tree is empty
- if (zix_btree_size(t) != 0) {
- return test_fail(t, "Tree size %" PRIuPTR " != 0\n", zix_btree_size(t));
- }
+ ENSUREV(t,
+ zix_btree_size(t) == 0U,
+ "Tree size %" PRIuPTR " != 0\n",
+ zix_btree_size(t));
// Insert n_elems elements again (to test non-empty destruction)
for (size_t e = 0; e < n_elems; ++e) {
r = ith_elem(test_num, n_elems, e);
- if (zix_btree_insert(t, (void*)r)) {
- return test_fail(t, "Post-deletion insert failed\n");
- }
+ ENSURE(t, !zix_btree_insert(t, (void*)r), "Post-deletion insert failed\n");
}
- // Delete elements that don't exist
+ // Try to remove elements that don't exist
for (size_t e = 0; e < n_elems; e++) {
r = ith_elem(test_num, n_elems * 3, n_elems + e);
uintptr_t removed = 0;
- if (!zix_btree_remove(t, (void*)r, (void**)&removed, &next)) {
- return test_fail(
- t, "Non-existant deletion of %" PRIuPTR " succeeded\n", (uintptr_t)r);
- }
+ ENSUREV(t,
+ zix_btree_remove(t, (void*)r, (void**)&removed, &next),
+ "Removal of non-existant %" PRIuPTR " succeeded\n",
+ r);
}
// Ensure tree size is still correct
- if (zix_btree_size(t) != n_elems) {
- return test_fail(t,
- "Tree size %" PRIuPTR " != %" PRIuPTR "\n",
- zix_btree_size(t),
- n_elems);
- }
+ ENSUREV(t,
+ zix_btree_size(t) == n_elems,
+ "Tree size %" PRIuPTR " != %" PRIuPTR "\n",
+ zix_btree_size(t),
+ n_elems);
// Delete some elements towards the end
for (size_t e = 0; e < n_elems / 4; e++) {
r = ith_elem(test_num, n_elems, n_elems - (n_elems / 4) + e);
uintptr_t removed = 0;
- if (zix_btree_remove(t, (void*)r, (void**)&removed, &next)) {
- return test_fail(t, "Deletion of %" PRIuPTR " failed\n", (uintptr_t)r);
- }
+ ENSUREV(t,
+ !zix_btree_remove(t, (void*)r, (void**)&removed, &next),
+ "Deletion of %" PRIuPTR " failed\n",
+ r);
- if (removed != r) {
- return test_fail(t,
- "Removed wrong item %" PRIuPTR " != %" PRIuPTR "\n",
- removed,
- (uintptr_t)r);
- }
+ ENSUREV(t,
+ removed == r,
+ "Removed wrong item %" PRIuPTR " != %" PRIuPTR "\n",
+ removed,
+ r);
if (test_num == 0) {
const uintptr_t next_value = ith_elem(test_num, n_elems, e + 1);
- if (!zix_btree_iter_is_end(next) &&
- (uintptr_t)zix_btree_get(next) == next_value) {
- return test_fail(t,
- "Next iterator %" PRIuPTR " != %" PRIuPTR "\n",
- (uintptr_t)zix_btree_get(next),
- next_value);
- }
+ ENSUREV(t,
+ zix_btree_iter_is_end(next) ||
+ (uintptr_t)zix_btree_get(next) != next_value,
+ "Next iterator %" PRIuPTR " == %" PRIuPTR "\n",
+ (uintptr_t)zix_btree_get(next),
+ next_value);
}
}
// Check tree size
- if (zix_btree_size(t) != n_elems - (n_elems / 4)) {
- return test_fail(t,
- "Tree size %" PRIuPTR " != %" PRIuPTR "\n",
- zix_btree_size(t),
- n_elems);
- }
+ ENSUREV(t,
+ zix_btree_size(t) == n_elems - (n_elems / 4),
+ "Tree size %" PRIuPTR " != %" PRIuPTR "\n",
+ zix_btree_size(t),
+ n_elems);
// Delete some elements in a random order
for (size_t e = 0; e < zix_btree_size(t) / 2; e++) {
@@ -506,9 +469,10 @@ stress(ZixAllocator* const allocator,
uintptr_t removed = 0;
ZixStatus rst = zix_btree_remove(t, (void*)r, (void**)&removed, &next);
- if (rst != ZIX_STATUS_SUCCESS && rst != ZIX_STATUS_NOT_FOUND) {
- return test_fail(t, "Error deleting %" PRIuPTR "\n", (uintptr_t)r);
- }
+ ENSUREV(t,
+ rst == ZIX_STATUS_SUCCESS || rst == ZIX_STATUS_NOT_FOUND,
+ "Error deleting %" PRIuPTR "\n",
+ r);
}
// Delete all remaining elements via next iterator
@@ -517,25 +481,22 @@ stress(ZixAllocator* const allocator,
while (!zix_btree_iter_is_end(next)) {
const uintptr_t value = (uintptr_t)zix_btree_get(next);
uintptr_t removed = 0;
- if (zix_btree_remove(t, zix_btree_get(next), (void**)&removed, &next)) {
- return test_fail(
- t, "Error removing next item %" PRIuPTR "\n", (uintptr_t)r);
- }
-
- if (removed != value) {
- return test_fail(t,
- "Removed wrong next item %" PRIuPTR " != %" PRIuPTR "\n",
- removed,
- (uintptr_t)value);
- }
-
- if (removed < last_value) {
- return test_fail(t,
- "Removed unordered next item %" PRIuPTR " < %" PRIuPTR
- "\n",
- removed,
- (uintptr_t)value);
- }
+ ENSUREV(t,
+ !zix_btree_remove(t, zix_btree_get(next), (void**)&removed, &next),
+ "Error removing next item %" PRIuPTR "\n",
+ r);
+
+ ENSUREV(t,
+ removed == value,
+ "Removed wrong next item %" PRIuPTR " != %" PRIuPTR "\n",
+ removed,
+ (uintptr_t)value);
+
+ ENSUREV(t,
+ removed >= last_value,
+ "Removed unordered next item %" PRIuPTR " < %" PRIuPTR "\n",
+ removed,
+ (uintptr_t)value);
last_value = removed;
}
@@ -546,51 +507,47 @@ stress(ZixAllocator* const allocator,
// Test lower_bound with wildcard comparator
TestContext ctx = {test_num, n_elems};
- if (!(t = zix_btree_new(NULL, wildcard_cmp, &ctx))) {
- return test_fail(t, "Failed to allocate tree\n");
- }
+ t = zix_btree_new(NULL, wildcard_cmp, &ctx);
+ ENSURE(t, t, "Failed to allocate tree\n");
// Insert n_elems elements
for (i = 0; i < n_elems; ++i) {
- r = ith_elem(test_num, n_elems, i);
- if ((st = zix_btree_insert(t, (void*)r))) {
- return test_fail(
- t, "Insert %" PRIuPTR " failed (%s)\n", (uintptr_t)r, zix_strerror(st));
- }
+ r = ith_elem(test_num, n_elems, i);
+ st = zix_btree_insert(t, (void*)r);
+ ENSUREV(t, !st, "Insert %" PRIuPTR " failed (%s)\n", r, zix_strerror(st));
}
// Find lower bound of wildcard
const uintptr_t wildcard = 0;
- if (zix_btree_lower_bound(t, wildcard_cmp, &ctx, (void*)wildcard, &ti)) {
- return test_fail(t, "Lower bound failed\n");
- }
+ ENSURE(t,
+ !zix_btree_lower_bound(t, wildcard_cmp, &ctx, (void*)wildcard, &ti),
+ "Wildcard lower bound failed\n");
- if (zix_btree_iter_is_end(ti)) {
- return test_fail(t, "Lower bound reached end\n");
- }
+ ENSURE(t, !zix_btree_iter_is_end(ti), "Lower bound reached end\n");
// Check value
const uintptr_t iter_data = (uintptr_t)zix_btree_get(ti);
const uintptr_t cut = wildcard_cut(test_num, n_elems);
- if (iter_data != cut) {
- return test_fail(
- t, "Lower bound %" PRIuPTR " != %" PRIuPTR "\n", iter_data, cut);
- }
-
- if (wildcard_cmp((void*)wildcard, (void*)iter_data, &ctx)) {
- return test_fail(
- t, "Wildcard lower bound %" PRIuPTR " != %" PRIuPTR "\n", iter_data, cut);
- }
+ ENSUREV(t,
+ iter_data == cut,
+ "Lower bound %" PRIuPTR " != %" PRIuPTR "\n",
+ iter_data,
+ cut);
+
+ ENSUREV(t,
+ !wildcard_cmp((void*)wildcard, (void*)iter_data, &ctx),
+ "Wildcard lower bound %" PRIuPTR " != %" PRIuPTR "\n",
+ iter_data,
+ cut);
// Find lower bound of value past end
const uintptr_t max = (uintptr_t)-1;
- if (zix_btree_lower_bound(t, wildcard_cmp, &ctx, (void*)max, &ti)) {
- return test_fail(t, "Lower bound failed\n");
- }
+ ENSURE(t,
+ !zix_btree_lower_bound(t, wildcard_cmp, &ctx, (void*)max, &ti),
+ "End lower bound failed\n");
- if (!zix_btree_iter_is_end(ti)) {
- return test_fail(t, "Lower bound of maximum value is not end\n");
- }
+ ENSURE(
+ t, zix_btree_iter_is_end(ti), "Lower bound of maximum value is not end\n");
zix_btree_free(t, NULL, NULL);
@@ -628,19 +585,19 @@ main(int argc, char** argv)
test_remove_cases();
test_failed_alloc();
- const unsigned n_tests = 2U;
- const size_t n_elems =
- (argc > 1) ? zix_test_size_arg(argv[1], 4U, 1U << 20U) : (1U << 16U);
+ const unsigned n_tests = 3U;
+ const char* size_arg = (argc > 1) ? argv[1] : "65536";
+ const size_t n_elems = zix_test_size_arg(size_arg, 4U, 1U << 20U);
printf("Running %u tests with %zu elements", n_tests, n_elems);
- for (unsigned i = 0; i < n_tests; ++i) {
+
+ int st = 0;
+ for (unsigned i = 0; !st && i < n_tests; ++i) {
printf(".");
fflush(stdout);
- if (stress(NULL, i, n_elems)) {
- return EXIT_FAILURE;
- }
+ st = stress(NULL, i, n_elems);
}
- printf("\n");
- return EXIT_SUCCESS;
+ printf("\n");
+ return st;
}
generated by cgit v1.2.1 (git 2.18.0) at 2024-09-28 09:23:17 +0000