diff options
author | David Robillard <d@drobilla.net> | 2023-09-22 23:12:28 -0400 |
---|---|---|
committer | David Robillard <d@drobilla.net> | 2023-09-22 23:12:28 -0400 |
commit | e2e65a8c8b816a066da1f7a4843ca7f504c2b3d9 (patch) | |
tree | 5ba3dcd7dcf753067b5ee45e1ce42b30aca2e090 /test/test_btree.c | |
parent | 9f2e5b963c17a13303456dd46e13fc7c2ef32039 (diff) | |
download | zix-e2e65a8c8b816a066da1f7a4843ca7f504c2b3d9.tar.gz zix-e2e65a8c8b816a066da1f7a4843ca7f504c2b3d9.tar.bz2 zix-e2e65a8c8b816a066da1f7a4843ca7f504c2b3d9.zip |
Improve test suite code coverage
Diffstat (limited to 'test/test_btree.c')
-rw-r--r-- | test/test_btree.c | 427 |
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; } |