From f65912600fc301cbdbb613f1df0dc29820f1da35 Mon Sep 17 00:00:00 2001 From: David Robillard Date: Thu, 18 Aug 2022 13:18:52 -0400 Subject: Use conventional test executable names --- meson.build | 18 +- test/allocator_test.c | 121 ---------- test/bitset_test.c | 70 ------ test/btree_test.c | 642 ------------------------------------------------- test/digest_test.c | 129 ---------- test/hash_test.c | 421 --------------------------------- test/ring_test.c | 195 --------------- test/sem_test.c | 70 ------ test/strerror_test.c | 31 --- test/test_allocator.c | 121 ++++++++++ test/test_bitset.c | 71 ++++++ test/test_btree.c | 643 ++++++++++++++++++++++++++++++++++++++++++++++++++ test/test_digest.c | 131 ++++++++++ test/test_hash.c | 421 +++++++++++++++++++++++++++++++++ test/test_ring.c | 195 +++++++++++++++ test/test_sem.c | 70 ++++++ test/test_strerror.c | 31 +++ test/test_tree.c | 224 ++++++++++++++++++ test/tree_test.c | 224 ------------------ 19 files changed, 1916 insertions(+), 1912 deletions(-) delete mode 100644 test/allocator_test.c delete mode 100644 test/bitset_test.c delete mode 100644 test/btree_test.c delete mode 100644 test/digest_test.c delete mode 100644 test/hash_test.c delete mode 100644 test/ring_test.c delete mode 100644 test/sem_test.c delete mode 100644 test/strerror_test.c create mode 100644 test/test_allocator.c create mode 100644 test/test_bitset.c create mode 100644 test/test_btree.c create mode 100644 test/test_digest.c create mode 100644 test/test_hash.c create mode 100644 test/test_ring.c create mode 100644 test/test_sem.c create mode 100644 test/test_strerror.c create mode 100644 test/test_tree.c delete mode 100644 test/tree_test.c diff --git a/meson.build b/meson.build index 7d2ab27..45f8b88 100644 --- a/meson.build +++ b/meson.build @@ -172,18 +172,18 @@ install_headers(c_headers, subdir: versioned_name / 'zix') ######### sequential_tests = [ - 'allocator_test', - 'bitset_test', - 'btree_test', - 'digest_test', - 'hash_test', - 'strerror_test', - 'tree_test', + 'test_allocator', + 'test_bitset', + 'test_btree', + 'test_digest', + 'test_hash', + 'test_strerror', + 'test_tree', ] threaded_tests = [ - 'ring_test', - 'sem_test', + 'test_ring', + 'test_sem', ] if not get_option('tests').disabled() and not meson.is_subproject() diff --git a/test/allocator_test.c b/test/allocator_test.c deleted file mode 100644 index e146de6..0000000 --- a/test/allocator_test.c +++ /dev/null @@ -1,121 +0,0 @@ -// Copyright 2014-2021 David Robillard -// SPDX-License-Identifier: ISC - -#undef NDEBUG - -#include "zix/allocator.h" -#include "zix/bump_allocator.h" - -#include -#include - -static void -test_allocator(void) -{ - // Just a basic smoke test to check that things seem to be working - - ZixAllocator* const allocator = zix_default_allocator(); - - char* const malloced = (char*)zix_malloc(allocator, 4); - malloced[0] = 0; - malloced[3] = 3; - assert(malloced[0] == 0); - assert(malloced[3] == 3); - - char* const calloced = (char*)zix_calloc(allocator, 4, 1); - assert(calloced[0] == 0); - assert(calloced[1] == 0); - assert(calloced[2] == 0); - assert(calloced[3] == 0); - - char* const realloced = (char*)zix_realloc(allocator, calloced, 8); - assert(realloced[0] == 0); - assert(realloced[1] == 0); - assert(realloced[2] == 0); - assert(realloced[3] == 0); - realloced[4] = 4; - realloced[5] = 5; - realloced[6] = 6; - realloced[7] = 7; - assert(realloced[4] == 4); - assert(realloced[5] == 5); - assert(realloced[6] == 6); - assert(realloced[7] == 7); - - char* const aligned = (char*)zix_aligned_alloc(allocator, 4096, 4096); - assert((uintptr_t)aligned % 4096 == 0); - aligned[0] = 0; - aligned[3] = 3; - assert(aligned[0] == 0); - assert(aligned[3] == 3); - - zix_aligned_free(allocator, aligned); - zix_free(allocator, realloced); - zix_free(allocator, malloced); -} - -static void -test_bump_allocator(void) -{ - char buffer[1024] = {0}; - ZixBumpAllocator allocator = zix_bump_allocator(sizeof(buffer), buffer); - - assert(!zix_malloc(&allocator.base, 1025)); - - char* const malloced = (char*)zix_malloc(&allocator.base, 3); - assert(malloced >= buffer); - assert(malloced <= buffer + sizeof(buffer)); - assert((uintptr_t)malloced % sizeof(uintmax_t) == 0U); - - assert(!zix_calloc(&allocator.base, 1017, 1)); - - char* const calloced = (char*)zix_calloc(&allocator.base, 4, 1); - assert(calloced > malloced); - assert(calloced <= buffer + sizeof(buffer)); - assert((uintptr_t)calloced % sizeof(uintmax_t) == 0U); - assert(!calloced[0]); - assert(!calloced[1]); - assert(!calloced[2]); - assert(!calloced[3]); - - char* const realloced = (char*)zix_realloc(&allocator.base, calloced, 8); - assert(realloced == calloced); - - assert(!zix_realloc(&allocator.base, malloced, 8)); // Not the top - assert(!zix_realloc(&allocator.base, realloced, 4089)); // No space - - zix_free(&allocator.base, realloced); - - char* const reclaimed = (char*)zix_malloc(&allocator.base, 512); - assert(reclaimed); - assert(reclaimed == realloced); - - assert(!zix_aligned_alloc(&allocator.base, sizeof(uintmax_t), 1024)); - assert(!zix_aligned_alloc(&allocator.base, 1024, 1024)); - assert(!zix_aligned_alloc(&allocator.base, 2048, 2048)); - assert(!zix_aligned_alloc(&allocator.base, 4096, 4096)); - assert(!zix_aligned_alloc(&allocator.base, 8192, 8192)); - assert(!zix_aligned_alloc(&allocator.base, 4096, 4096)); - assert(!zix_aligned_alloc(&allocator.base, 2048, 2048)); - assert(!zix_aligned_alloc(&allocator.base, 1024, 1024)); - assert(!zix_aligned_alloc(&allocator.base, 512, 512)); - - char* const aligned = (char*)zix_aligned_alloc(&allocator.base, 128, 128); - assert(aligned); - assert(aligned >= reclaimed); - assert(aligned <= buffer + sizeof(buffer)); - assert((uintptr_t)aligned % 128 == 0U); - - zix_aligned_free(&allocator.base, aligned); - zix_free(&allocator.base, reclaimed); // Correct, but a noop - zix_free(&allocator.base, malloced); // Correct, but a noop -} - -int -main(void) -{ - test_allocator(); - test_bump_allocator(); - - return 0; -} diff --git a/test/bitset_test.c b/test/bitset_test.c deleted file mode 100644 index ef0528f..0000000 --- a/test/bitset_test.c +++ /dev/null @@ -1,70 +0,0 @@ -// Copyright 2014-2020 David Robillard -// SPDX-License-Identifier: ISC - -#undef NDEBUG - -#include "zix/bitset.h" - -#include - -#define N_BITS 256U -#define N_ELEMS (ZIX_BITSET_ELEMS(N_BITS)) - -#define MIN(a, b) (((a) < (b)) ? (a) : (b)) - -int -main(void) -{ - ZixBitset b[N_ELEMS]; - ZixBitsetTally t[N_ELEMS]; - - zix_bitset_clear(b, t, N_BITS); - assert(zix_bitset_count_up_to(b, t, N_BITS) == 0); - - for (size_t i = 0; i < N_BITS; ++i) { - zix_bitset_set(b, t, i); - assert(zix_bitset_get(b, i)); - - const size_t count = zix_bitset_count_up_to(b, t, N_BITS); - assert(count == i + 1); - } - - for (size_t i = 0; i <= N_BITS; ++i) { - const size_t count = zix_bitset_count_up_to(b, t, i); - assert(count == i); - } - - for (size_t i = 0; i <= N_BITS; ++i) { - if (i < N_BITS) { - zix_bitset_reset(b, t, i); - } - - const size_t count = zix_bitset_count_up_to(b, t, i); - assert(count == 0); - } - - zix_bitset_clear(b, t, N_BITS); - for (size_t i = 0; i < N_BITS; i += 2) { - zix_bitset_set(b, t, i); - - const size_t count = zix_bitset_count_up_to(b, t, i + 1); - const size_t result = MIN(N_BITS / 2, i / 2 + 1); - - assert(count == result); - } - - zix_bitset_clear(b, t, N_BITS); - for (size_t i = 0; i < N_BITS; ++i) { - if (i % 2 == 0) { - zix_bitset_set(b, t, i); - - const size_t count = zix_bitset_count_up_to_if(b, t, i); - const size_t result = MIN(N_BITS / 2, i / 2); - assert(count == result); - } else { - assert(zix_bitset_count_up_to_if(b, t, i) == (size_t)-1); - } - } - - return 0; -} diff --git a/test/btree_test.c b/test/btree_test.c deleted file mode 100644 index 878eef9..0000000 --- a/test/btree_test.c +++ /dev/null @@ -1,642 +0,0 @@ -// Copyright 2011-2021 David Robillard -// SPDX-License-Identifier: ISC - -#undef NDEBUG - -#include "zix/btree.h" - -#include "failing_allocator.h" -#include "test_data.h" - -#include "zix/common.h" - -#include -#include -#include -#include -#include -#include -#include - -static bool expect_failure = false; - -ZIX_PURE_FUNC -static int -int_cmp(const void* a, const void* b, const void* ZIX_UNUSED(user_data)) -{ - const uintptr_t ia = (uintptr_t)a; - const uintptr_t ib = (uintptr_t)b; - - assert(ia != 0U); // No wildcards - assert(ib != 0U); // No wildcards - - return ia < ib ? -1 : ia > ib ? 1 : 0; -} - -static uintptr_t -ith_elem(const unsigned test_num, const size_t n_elems, const size_t i) -{ - switch (test_num % 3) { - case 0: - return i + 1; // Increasing - case 1: - return n_elems - i; // Decreasing - default: - return 1U + unique_rand(i); // Pseudo-random - } -} - -typedef struct { - unsigned test_num; - size_t n_elems; -} TestContext; - -static uintptr_t -wildcard_cut(unsigned test_num, size_t n_elems) -{ - return ith_elem(test_num, n_elems, n_elems / 3); -} - -/// Wildcard comparator where 0 matches anything >= wildcard_cut(n_elems) -static int -wildcard_cmp(const void* a, const void* b, const void* user_data) -{ - const TestContext* ctx = (const TestContext*)user_data; - const size_t n_elems = ctx->n_elems; - const unsigned test_num = ctx->test_num; - 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); -} - -ZIX_LOG_FUNC(2, 3) -static int -test_fail(ZixBTree* t, const char* fmt, ...) -{ - zix_btree_free(t, NULL, NULL); - if (expect_failure) { - return EXIT_SUCCESS; - } - - va_list args; - va_start(args, fmt); - fprintf(stderr, "error: "); - vfprintf(stderr, fmt, args); - va_end(args); - return EXIT_FAILURE; -} - -static const size_t n_clear_insertions = 1024U; - -static void -destroy(void* const ptr, const void* const user_data) -{ - (void)user_data; - assert(ptr); - assert((uintptr_t)ptr <= n_clear_insertions); -} - -static void -no_destroy(void* const ptr, const void* const user_data) -{ - (void)user_data; - assert(!ptr); -} - -static void -test_clear(void) -{ - ZixBTree* t = zix_btree_new(NULL, 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, NULL); - assert(zix_btree_size(t) == 0); - - zix_btree_free(t, no_destroy, NULL); -} - -static void -test_free(void) -{ - ZixBTree* t = zix_btree_new(NULL, 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, NULL); -} - -static void -test_iter_comparison(void) -{ - static const size_t n_elems = 4096U; - - ZixBTree* const t = zix_btree_new(NULL, int_cmp, NULL); - - // Store increasing numbers from 1 (jammed into the pointers themselves) - for (uintptr_t r = 1U; r < n_elems; ++r) { - assert(!zix_btree_insert(t, (void*)r)); - } - - // Check that begin and end work sensibly - const ZixBTreeIter begin = zix_btree_begin(t); - const ZixBTreeIter end = zix_btree_end(t); - assert(!zix_btree_iter_is_end(begin)); - assert(zix_btree_iter_is_end(end)); - assert(!zix_btree_iter_equals(begin, end)); - assert(!zix_btree_iter_equals(end, begin)); - - // Make another begin iterator - ZixBTreeIter j = zix_btree_begin(t); - assert(zix_btree_iter_equals(begin, j)); - - // Advance it and check that they are no longer equal - for (size_t r = 1U; r < n_elems - 1U; ++r) { - j = zix_btree_iter_next(j); - assert(!zix_btree_iter_is_end(j)); - assert(!zix_btree_iter_equals(begin, j)); - assert(!zix_btree_iter_equals(end, j)); - assert(!zix_btree_iter_equals(j, end)); - } - - // Advance it to the end - zix_btree_iter_increment(&j); - assert(zix_btree_iter_is_end(j)); - assert(!zix_btree_iter_equals(begin, j)); - assert(zix_btree_iter_equals(end, j)); - assert(zix_btree_iter_equals(j, end)); - - zix_btree_free(t, NULL, NULL); -} - -static void -test_insert_split_value(void) -{ - static const size_t n_insertions = 767U; // Number of insertions to split - static const uintptr_t split_value = 512U; // Value that will be pulled up - - ZixBTree* const t = zix_btree_new(NULL, int_cmp, NULL); - - // Insert right up until it would cause a split - for (uintptr_t r = 1U; r < n_insertions; ++r) { - assert(!zix_btree_insert(t, (void*)r)); - } - - // Insert the element that will be chosen as the split pivot - assert(zix_btree_insert(t, (void*)split_value) == ZIX_STATUS_EXISTS); - - zix_btree_free(t, NULL, NULL); -} - -static void -test_remove_cases(void) -{ - /* Insert and remove in several "phases" with different strides that are not - even multiples. This spreads the load around to hit as many cases as - possible. */ - - static const uintptr_t s1 = 2U; - static const uintptr_t s2 = 255U; - const size_t n_insertions = s1 * s2 * 1000U; - - ZixBTree* const t = zix_btree_new(NULL, int_cmp, NULL); - - // Insert in s1-sized chunks - for (uintptr_t phase = 0U; phase < s1; ++phase) { - for (uintptr_t r = 0U; r < n_insertions / s1; ++r) { - const uintptr_t value = (s1 * r) + phase + 1U; - - assert(!zix_btree_insert(t, (void*)value)); - } - } - - // Remove in s2-sized chunks - ZixBTreeIter next = zix_btree_end(t); - for (uintptr_t phase = 0U; phase < s2; ++phase) { - for (uintptr_t r = 0U; r < n_insertions / s2; ++r) { - const uintptr_t value = (s2 * r) + phase + 1U; - void* out = NULL; - - assert(!zix_btree_remove(t, (void*)value, &out, &next)); - assert((uintptr_t)out == value); - } - } - - assert(!zix_btree_size(t)); - zix_btree_free(t, NULL, NULL); -} - -static int -stress(ZixAllocator* const allocator, - const unsigned test_num, - const size_t n_elems) -{ - if (n_elems == 0) { - return 0; - } - - 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 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"); - } - - if (!zix_btree_iter_equals(ti, end)) { - return test_fail(t, "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)); - } - } - - // 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); - } - - // 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"); - } - - // 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); - } - - 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); - } - } - - // 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); - } - - if (zix_btree_iter_is_end(ti)) { - return test_fail(t, - "Lower bound %" PRIuPTR " @ %" PRIuPTR " hit end\n", - (uintptr_t)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); - } - } - - // 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); - } - } - - // Iterate over all elements - 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) { - 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); - } - last = iter_data; - } - - if (i != n_elems) { - return test_fail(t, - "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"); - } - } - - // 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); - } - 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); - } - last = (uintptr_t)zix_btree_get(ti); - } - - // Delete 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); - } - - if (removed != r) { - return test_fail(t, - "Removed wrong item %" PRIuPTR " != %" PRIuPTR "\n", - removed, - (uintptr_t)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); - } - } - } - - // Ensure the tree is empty - if (zix_btree_size(t) != 0) { - return test_fail(t, "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"); - } - } - - // Delete 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); - } - } - - // 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); - } - - // 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); - } - - if (removed != r) { - return test_fail(t, - "Removed wrong item %" PRIuPTR " != %" PRIuPTR "\n", - removed, - (uintptr_t)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); - } - } - } - - // 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); - } - - // Delete some elements in a random order - for (size_t e = 0; e < zix_btree_size(t) / 2; e++) { - r = ith_elem(test_num, n_elems, unique_rand(e) % n_elems); - - 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); - } - } - - // Delete all remaining elements via next iterator - next = zix_btree_begin(t); - uintptr_t last_value = 0; - 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); - } - - last_value = removed; - } - - assert(zix_btree_size(t) == 0); - zix_btree_free(t, NULL, NULL); - - // 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"); - } - - // 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)); - } - } - - // 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"); - } - - if (zix_btree_iter_is_end(ti)) { - return test_fail(t, "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); - } - - // 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"); - } - - if (!zix_btree_iter_is_end(ti)) { - return test_fail(t, "Lower bound of maximum value is not end\n"); - } - - zix_btree_free(t, NULL, NULL); - - return EXIT_SUCCESS; -} - -static void -test_failed_alloc(void) -{ - ZixFailingAllocator allocator = zix_failing_allocator(); - - // Successfully stress test the tree to count the number of allocations - assert(!stress(&allocator.base, 0, 4096)); - - // Test that each allocation failing is handled gracefully - const size_t n_new_allocs = allocator.n_allocations; - for (size_t i = 0U; i < n_new_allocs; ++i) { - allocator.n_remaining = i; - assert(stress(&allocator.base, 0, 4096)); - } -} - -int -main(int argc, char** argv) -{ - if (argc > 2) { - fprintf(stderr, "Usage: %s [N_ELEMS]\n", argv[0]); - return EXIT_FAILURE; - } - - test_clear(); - test_free(); - test_iter_comparison(); - test_insert_split_value(); - test_remove_cases(); - test_failed_alloc(); - - const unsigned n_tests = 3U; - const size_t n_elems = (argc > 1) ? strtoul(argv[1], NULL, 10) : 131072U; - - printf("Running %u tests with %" PRIuPTR " elements", n_tests, n_elems); - for (unsigned i = 0; i < n_tests; ++i) { - printf("."); - fflush(stdout); - if (stress(NULL, i, n_elems)) { - return EXIT_FAILURE; - } - } - printf("\n"); - - return EXIT_SUCCESS; -} diff --git a/test/digest_test.c b/test/digest_test.c deleted file mode 100644 index c1a16a8..0000000 --- a/test/digest_test.c +++ /dev/null @@ -1,129 +0,0 @@ -// Copyright 2020-2021 David Robillard -// SPDX-License-Identifier: ISC - -#undef NDEBUG - -#include "zix/digest.h" - -#include -#include - -// Just basic smoke tests to ensure the hash functions are reacting to data - -static void -test_digest(void) -{ - static const uint8_t data[] = { - 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}; - - size_t last = 0U; - - for (size_t offset = 0; offset < 7; ++offset) { - const size_t len = 8U - offset; - for (size_t i = offset; i < 8; ++i) { - const size_t h = zix_digest(0U, &data[i], len); - assert(h != last); - last = h; - } - } -} - -static void -test_digest32(void) -{ - static const uint8_t data[] = {1, 2, 3, 4, 5, 6, 7, 8}; - - uint32_t last = 0U; - - for (size_t offset = 0; offset < 3; ++offset) { - for (size_t i = offset; i < 4; ++i) { - const uint32_t h = zix_digest32(0U, &data[i], 4); - assert(h != last); - last = h; - } - } -} - -static void -test_digest64(void) -{ - static const uint8_t data[] = { - 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}; - - uint64_t last = 0U; - - for (size_t offset = 0; offset < 7; ++offset) { - for (size_t i = offset; i < 8; ++i) { - const uint64_t h = zix_digest64(0U, &data[i], 8); - assert(h != last); - last = h; - } - } -} - -static void -test_digest32_aligned(void) -{ - static const uint32_t data[] = {1, 2, 3, 4, 5, 6, 7, 8}; - - uint32_t last = 0U; - - for (size_t offset = 0; offset < 3; ++offset) { - const size_t len = 4U - offset; - for (size_t i = offset; i < 4; ++i) { - const uint32_t h = - zix_digest32_aligned(0U, &data[i], len * sizeof(uint32_t)); - assert(h != last); - last = h; - } - } -} - -static void -test_digest64_aligned(void) -{ - static const uint64_t data[] = {1, 2, 3, 4, 5, 6, 7, 8}; - - uint64_t last = 0U; - - for (size_t offset = 0; offset < 3; ++offset) { - const size_t len = 4U - offset; - for (size_t i = offset; i < 4; ++i) { - const uint64_t h = - zix_digest64_aligned(0U, &data[i], len * sizeof(uint64_t)); - assert(h != last); - last = h; - } - } -} - -static void -test_digest_aligned(void) -{ - static const size_t data[] = {1, 2, 3, 4, 5, 6, 7, 8}; - - size_t last = 0U; - - for (size_t offset = 0; offset < 3; ++offset) { - const size_t len = 4U - offset; - for (size_t i = offset; i < 4; ++i) { - const size_t h = zix_digest_aligned(0U, &data[i], len * sizeof(size_t)); - assert(h != last); - last = h; - } - } -} - -ZIX_PURE_FUNC int -main(void) -{ - test_digest32(); - test_digest64(); - test_digest(); - - test_digest32_aligned(); - test_digest64_aligned(); - test_digest_aligned(); - - return 0; -} diff --git a/test/hash_test.c b/test/hash_test.c deleted file mode 100644 index 287dbaa..0000000 --- a/test/hash_test.c +++ /dev/null @@ -1,421 +0,0 @@ -// Copyright 2011-2021 David Robillard -// SPDX-License-Identifier: ISC - -#undef NDEBUG - -#define ZIX_HASH_KEY_TYPE const char -#define ZIX_HASH_RECORD_TYPE const char - -#include "failing_allocator.h" -#include "test_data.h" - -#include "zix/allocator.h" -#include "zix/attributes.h" -#include "zix/common.h" -#include "zix/digest.h" -#include "zix/hash.h" - -#include -#include -#include -#include -#include -#include -#include -#include - -static bool expect_failure = false; - -ZIX_LOG_FUNC(4, 5) -static int -test_fail(ZixHash* const hash, - char* const buffer, - char** const strings, - const char* fmt, - ...) -{ - if (!expect_failure) { - va_list args; - va_start(args, fmt); - fprintf(stderr, "error: "); - vfprintf(stderr, fmt, args); - va_end(args); - } - - zix_hash_free(hash); - free(buffer); - free(strings); - - return expect_failure ? 0 : 1; -} - -ZIX_PURE_FUNC static const char* -identity(const char* record) -{ - return record; -} - -/// Decent hash function using zix_digest (murmur2) -ZIX_PURE_FUNC static size_t -decent_string_hash(const char* const str) -{ - return zix_digest(0U, str, strlen(str)); -} - -/// Terrible hash function from K&R first edition -ZIX_PURE_FUNC static size_t -terrible_string_hash(const char* str) -{ - size_t hash = 0U; - uint8_t c = 0U; - - while ((c = (uint8_t)*str++)) { - hash += c; - } - - return hash; -} - -ZIX_PURE_FUNC static size_t -string_hash_aligned(const char* const str) -{ - size_t length = strlen(str); - - length = (length + (sizeof(size_t) - 1)) / sizeof(size_t) * sizeof(size_t); - return zix_digest_aligned(0U, str, length); -} - -ZIX_PURE_FUNC static size_t -string_hash32(const char* const str) -{ - return (size_t)zix_digest32(0U, str, strlen(str)); -} - -ZIX_PURE_FUNC static size_t -string_hash64(const char* const str) -{ - return (size_t)zix_digest64(0U, str, strlen(str)); -} - -ZIX_PURE_FUNC static size_t -string_hash32_aligned(const char* const str) -{ - size_t length = strlen(str); - - length = (length + 3U) / 4U * 4U; - return (size_t)zix_digest32_aligned(0U, str, length); -} - -#if UINTPTR_MAX >= UINT64_MAX - -ZIX_PURE_FUNC static size_t -string_hash64_aligned(const char* const str) -{ - size_t length = strlen(str); - - length = (length + 7U) / 8U * 8U; - return (size_t)zix_digest64_aligned(0U, str, length); -} - -#endif - -static bool -string_equal(const char* const a, const char* const b) -{ - return !strcmp(a, b); -} - -static int -stress_with(ZixAllocator* const allocator, - const ZixHashFunc hash_func, - const size_t n_elems) -{ - ZixHash* hash = zix_hash_new(allocator, identity, hash_func, string_equal); - if (!hash) { - return test_fail(hash, NULL, NULL, "Failed to allocate hash\n"); - } - - static const size_t string_length = 15; - - char* const buffer = (char*)calloc(1, n_elems * (string_length + 1)); - char** const strings = (char**)calloc(sizeof(char*), n_elems); - if (!buffer || !strings) { - return test_fail(hash, buffer, strings, "Failed to allocate strings\n"); - } - - uint32_t seed = 1U; - for (size_t i = 0U; i < n_elems; ++i) { - strings[i] = buffer + i * (string_length + 1); - assert((uintptr_t)strings[i] % sizeof(size_t) == 0); - assert((uintptr_t)strings[i] % sizeof(uint32_t) == 0); - - for (size_t j = 0U; j < string_length; ++j) { - seed = lcg32(seed); - strings[i][j] = (char)('!' + (seed % 92)); - } - } - - // Insert each string - for (size_t i = 0; i < n_elems; ++i) { - ZixStatus st = zix_hash_insert(hash, strings[i]); - if (st) { - return test_fail( - hash, buffer, strings, "Failed to insert `%s'\n", strings[i]); - } - } - - // Ensure hash size is correct - if (zix_hash_size(hash) != n_elems) { - return test_fail(hash, - buffer, - strings, - "Hash size %" PRIuPTR " != %" PRIuPTR "\n", - zix_hash_size(hash), - n_elems); - } - - // Attempt to insert each string again - for (size_t i = 0; i < n_elems; ++i) { - ZixStatus st = zix_hash_insert(hash, strings[i]); - if (st != ZIX_STATUS_EXISTS) { - return test_fail(hash, - buffer, - strings, - "Double inserted `%s' (%s)\n", - strings[i], - zix_strerror(st)); - } - } - - // Search for each string - for (size_t i = 0; i < n_elems; ++i) { - const char* match = (const char*)zix_hash_find_record(hash, strings[i]); - if (!match) { - return test_fail( - hash, buffer, strings, "Failed to find `%s'\n", strings[i]); - } - if (match != strings[i]) { - return test_fail( - hash, buffer, strings, "Bad match for `%s': `%s'\n", strings[i], match); - } - } - - static const char* const not_indexed_string = "__not__indexed__"; - - // Do a quick smoke test to ensure that false matches don't succeed - char* const not_indexed = (char*)calloc(1, strlen(not_indexed_string) + 1); - if (not_indexed) { - memcpy(not_indexed, not_indexed_string, strlen(not_indexed_string) + 1); - const char* match = (const char*)zix_hash_find_record(hash, not_indexed); - if (match) { - return test_fail( - hash, buffer, strings, "Unexpectedly found `%s'\n", not_indexed); - } - free(not_indexed); - } - - // Remove strings - for (size_t i = 0; i < n_elems; ++i) { - const size_t initial_size = zix_hash_size(hash); - - // Remove string - const char* removed = NULL; - ZixStatus st = zix_hash_remove(hash, strings[i], &removed); - if (st) { - return test_fail( - hash, buffer, strings, "Failed to remove `%s'\n", strings[i]); - } - - // Ensure the removed value is what we expected - if (removed != strings[i]) { - return test_fail(hash, - buffer, - strings, - "Removed `%s` instead of `%s`\n", - removed, - strings[i]); - } - - // Ensure size is updated - if (zix_hash_size(hash) != initial_size - 1) { - return test_fail( - hash, buffer, strings, "Removing node did not decrease hash size\n"); - } - - // Ensure second removal fails - st = zix_hash_remove(hash, strings[i], &removed); - if (st != ZIX_STATUS_NOT_FOUND) { - return test_fail( - hash, buffer, strings, "Unexpectedly removed `%s' twice\n", strings[i]); - } - - // Ensure value can no longer be found - assert(zix_hash_find(hash, strings[i]) == zix_hash_end(hash)); - - // Check to ensure remaining strings are still present - for (size_t j = i + 1; j < n_elems; ++j) { - const char* match = (const char*)zix_hash_find_record(hash, strings[j]); - if (!match) { - return test_fail(hash, - buffer, - strings, - "Failed to find `%s' after remove\n", - strings[j]); - } - if (match != strings[j]) { - return test_fail(hash, - buffer, - strings, - "Bad match for `%s' after remove\n", - strings[j]); - } - } - } - - // Insert each string again (to check non-empty destruction) - for (size_t i = 0; i < n_elems; ++i) { - ZixHashInsertPlan plan = zix_hash_plan_insert(hash, strings[i]); - - assert(!zix_hash_record_at(hash, plan)); - ZixStatus st = zix_hash_insert_at(hash, plan, strings[i]); - if (st) { - return test_fail( - hash, buffer, strings, "Failed to insert `%s'\n", strings[i]); - } - } - - // Check key == value (and test zix_hash_foreach) - size_t n_checked = 0U; - for (ZixHashIter i = zix_hash_begin(hash); i != zix_hash_end(hash); - i = zix_hash_next(hash, i)) { - const char* const string = (const char*)zix_hash_get(hash, i); - assert(string); - if (strlen(string) < 3) { - return test_fail(hash, buffer, strings, "Corrupt value `%s'\n", string); - } - - ++n_checked; - } - if (n_checked != n_elems) { - return test_fail(hash, buffer, strings, "Check failed\n"); - } - - free(strings); - free(buffer); - zix_hash_free(hash); - - return 0; -} - -static int -stress(ZixAllocator* const allocator, const size_t n_elems) -{ - if (stress_with(allocator, decent_string_hash, n_elems) || - stress_with(allocator, terrible_string_hash, n_elems / 4) || - stress_with(allocator, string_hash_aligned, n_elems / 4) || - stress_with(allocator, string_hash32, n_elems / 4) || - stress_with(allocator, string_hash64, n_elems / 4) || - stress_with(allocator, string_hash32_aligned, n_elems / 4)) { - return 1; - } - -#if UINTPTR_MAX >= UINT64_MAX - if (stress_with(allocator, string_hash64_aligned, n_elems / 4)) { - return 1; - } -#endif - - return 0; -} - -/// Identity hash function for numeric strings for explicitly hitting cases -ZIX_PURE_FUNC static size_t -identity_index_hash(const char* const str) -{ - return strtoul(str, NULL, 10); -} - -static void -test_all_tombstones(void) -{ - /* This tests an edge case where a minimum-sized table can be entirely full - of tombstones. If the search loop is not written carefully, then this can - result in a hang. This has been seen to occur in real code, though it's - very hard to hit with a decent hash function. So, we use the above - degenerate index hashing function to explicitly place elements exactly - where we want to hit this case. */ - -#define N_STRINGS 4 - - static const char* original_strings[N_STRINGS] = { - "0 a", - "1 a", - "2 a", - "3 a", - }; - - static const char* collision_strings[N_STRINGS] = { - "0 b", - "1 b", - "2 b", - "3 b", - }; - - ZixStatus st = ZIX_STATUS_SUCCESS; - ZixHash* hash = - zix_hash_new(NULL, identity, identity_index_hash, string_equal); - - // Insert each element then immediately remove it - for (unsigned i = 0U; i < N_STRINGS; ++i) { - const char* removed = NULL; - - assert(!zix_hash_insert(hash, original_strings[i])); - assert(!zix_hash_remove(hash, original_strings[i], &removed)); - } - - // Now the table should be "empty" but contain tombstones - assert(zix_hash_size(hash) == 0); - - // Insert clashing elements which should hit the "all tombstones" case - for (unsigned i = 0U; i < N_STRINGS; ++i) { - assert(!zix_hash_insert(hash, collision_strings[i])); - assert(!st); - } - - zix_hash_free(hash); - -#undef N_STRINGS -} - -static void -test_failed_alloc(void) -{ - ZixFailingAllocator allocator = zix_failing_allocator(); - - // Successfully stress test the tree to count the number of allocations - assert(!stress(&allocator.base, 16)); - - // Test that each allocation failing is handled gracefully - const size_t n_new_allocs = allocator.n_allocations; - for (size_t i = 0U; i < n_new_allocs; ++i) { - allocator.n_remaining = i; - assert(stress(&allocator.base, 16)); - } -} - -int -main(void) -{ - zix_hash_free(NULL); - - test_all_tombstones(); - test_failed_alloc(); - - static const size_t n_elems = 1024U; - - if (stress(NULL, n_elems)) { - return 1; - } - - return 0; -} diff --git a/test/ring_test.c b/test/ring_test.c deleted file mode 100644 index 79aa0f1..0000000 --- a/test/ring_test.c +++ /dev/null @@ -1,195 +0,0 @@ -// Copyright 2011-2021 David Robillard -// SPDX-License-Identifier: ISC - -#undef NDEBUG - -#include "failing_allocator.h" - -#include "zix/attributes.h" -#include "zix/ring.h" -#include "zix/thread.h" - -#include -#include -#include -#include -#include -#include - -#define MSG_SIZE 20U - -static ZixRing* ring = 0; -static unsigned n_writes = 0; -static bool read_error = false; - -static int -gen_msg(int* const msg, int start) -{ - for (unsigned i = 0U; i < MSG_SIZE; ++i) { - msg[i] = start; - start = (start + 1) % INT_MAX; - } - return start; -} - -ZIX_PURE_FUNC -static int -cmp_msg(const int* const msg1, const int* const msg2) -{ - for (unsigned i = 0U; i < MSG_SIZE; ++i) { - assert(msg1[i] == msg2[i]); - } - - return 1; -} - -static void* -reader(void* ZIX_UNUSED(arg)) -{ - printf("Reader starting\n"); - - int ref_msg[MSG_SIZE]; // Reference generated for comparison - int read_msg[MSG_SIZE]; // Read from ring - unsigned count = 0; - int start = gen_msg(ref_msg, 0); - for (unsigned i = 0; i < n_writes; ++i) { - if (zix_ring_read_space(ring) >= MSG_SIZE * sizeof(int)) { - if (zix_ring_read(ring, read_msg, MSG_SIZE * sizeof(int))) { - assert(cmp_msg(ref_msg, read_msg)); - start = gen_msg(ref_msg, start); - ++count; - } - } - } - - printf("Reader finished\n"); - return NULL; -} - -static void* -writer(void* ZIX_UNUSED(arg)) -{ - printf("Writer starting\n"); - - int write_msg[MSG_SIZE]; // Written to ring - int start = gen_msg(write_msg, 0); - for (unsigned i = 0; i < n_writes; ++i) { - if (zix_ring_write_space(ring) >= MSG_SIZE * sizeof(int)) { - if (zix_ring_write(ring, write_msg, MSG_SIZE * sizeof(int))) { - start = gen_msg(write_msg, start); - } - } - } - - printf("Writer finished\n"); - return NULL; -} - -static int -test_ring(const unsigned size) -{ - zix_ring_free(NULL); - - printf("Testing %u writes of %u ints to a %u int ring...\n", - n_writes, - MSG_SIZE, - size); - - ring = zix_ring_new(NULL, size); - assert(ring); - assert(zix_ring_read_space(ring) == 0); - assert(zix_ring_write_space(ring) == zix_ring_capacity(ring)); - - zix_ring_mlock(ring); - - ZixThread reader_thread; // NOLINT - assert(!zix_thread_create(&reader_thread, MSG_SIZE * 4UL, reader, NULL)); - - ZixThread writer_thread; // NOLINT - assert(!zix_thread_create(&writer_thread, MSG_SIZE * 4UL, writer, NULL)); - - zix_thread_join(reader_thread, NULL); - zix_thread_join(writer_thread, NULL); - - assert(!read_error); - assert(ring); - zix_ring_reset(ring); - assert(zix_ring_read_space(ring) == 0); - assert(zix_ring_write_space(ring) == zix_ring_capacity(ring)); - - zix_ring_write(ring, "a", 1); - zix_ring_write(ring, "b", 1); - - char buf = 0; - uint32_t n = zix_ring_peek(ring, &buf, 1); - assert(n == 1); - assert(buf == 'a'); - - n = zix_ring_skip(ring, 1); - assert(n == 1); - - assert(zix_ring_read_space(ring) == 1); - - n = zix_ring_read(ring, &buf, 1); - assert(n == 1); - assert(buf == 'b'); - - assert(zix_ring_read_space(ring) == 0); - - n = zix_ring_peek(ring, &buf, 1); - assert(n == 0); - - n = zix_ring_read(ring, &buf, 1); - assert(n == 0); - - n = zix_ring_skip(ring, 1); - assert(n == 0); - - char* big_buf = (char*)calloc(size, 1); - n = zix_ring_write(ring, big_buf, size - 1); - assert(n == (uint32_t)size - 1); - - n = zix_ring_write(ring, big_buf, size); - assert(n == 0); - - free(big_buf); - zix_ring_free(ring); - return 0; -} - -static void -test_failed_alloc(void) -{ - ZixFailingAllocator allocator = zix_failing_allocator(); - - // Successfully allocate a ring to count the number of allocations - ring = zix_ring_new(&allocator.base, 512); - assert(ring); - - // Test that each allocation failing is handled gracefully - const size_t n_new_allocs = allocator.n_allocations; - for (size_t i = 0U; i < n_new_allocs; ++i) { - allocator.n_remaining = i; - assert(!zix_ring_new(&allocator.base, 512)); - } - - zix_ring_free(ring); -} - -int -main(int argc, char** argv) -{ - if (argc > 1 && argv[1][0] == '-') { - printf("Usage: %s SIZE N_WRITES\n", argv[0]); - return 1; - } - - const unsigned size = - (argc > 1) ? (unsigned)strtoul(argv[1], NULL, 10) : 1024; - - n_writes = (argc > 2) ? (unsigned)strtoul(argv[2], NULL, 10) : size * 1024; - - test_failed_alloc(); - test_ring(size); - return 0; -} diff --git a/test/sem_test.c b/test/sem_test.c deleted file mode 100644 index 33859f1..0000000 --- a/test/sem_test.c +++ /dev/null @@ -1,70 +0,0 @@ -// Copyright 2012-2021 David Robillard -// SPDX-License-Identifier: ISC - -#undef NDEBUG - -#include "zix/attributes.h" -#include "zix/sem.h" -#include "zix/thread.h" - -#include -#include -#include - -static ZixSem sem; -static unsigned n_signals = 1024; - -static void* -reader(void* ZIX_UNUSED(arg)) -{ - printf("Reader starting\n"); - - for (unsigned i = 0; i < n_signals; ++i) { - zix_sem_wait(&sem); - } - - printf("Reader finished\n"); - return NULL; -} - -static void* -writer(void* ZIX_UNUSED(arg)) -{ - printf("Writer starting\n"); - - for (unsigned i = 0; i < n_signals; ++i) { - zix_sem_post(&sem); - } - - printf("Writer finished\n"); - return NULL; -} - -int -main(int argc, char** argv) -{ - if (argc > 2) { - printf("Usage: %s N_SIGNALS\n", argv[0]); - return 1; - } - - if (argc > 1) { - n_signals = (unsigned)strtol(argv[1], NULL, 10); - } - - printf("Testing %u signals...\n", n_signals); - - assert(!zix_sem_init(&sem, 0)); - - ZixThread reader_thread; // NOLINT - assert(!zix_thread_create(&reader_thread, 128, reader, NULL)); - - ZixThread writer_thread; // NOLINT - assert(!zix_thread_create(&writer_thread, 128, writer, NULL)); - - zix_thread_join(reader_thread, NULL); - zix_thread_join(writer_thread, NULL); - - zix_sem_destroy(&sem); - return 0; -} diff --git a/test/strerror_test.c b/test/strerror_test.c deleted file mode 100644 index 2f4c090..0000000 --- a/test/strerror_test.c +++ /dev/null @@ -1,31 +0,0 @@ -// Copyright 2021 David Robillard -// SPDX-License-Identifier: ISC - -#undef NDEBUG - -#include "zix/common.h" - -#include -#include -#include - -int -main(void) -{ - const char* msg = zix_strerror(ZIX_STATUS_SUCCESS); - assert(!strcmp(msg, "Success")); - - for (int i = ZIX_STATUS_ERROR; i <= ZIX_STATUS_REACHED_END; ++i) { - msg = zix_strerror((ZixStatus)i); - assert(strcmp(msg, "Success")); - } - - msg = zix_strerror((ZixStatus)-1); - assert(!strcmp(msg, "Unknown error")); - - msg = zix_strerror((ZixStatus)1000000); - assert(!strcmp(msg, "Unknown error")); - - printf("Success\n"); - return 0; -} diff --git a/test/test_allocator.c b/test/test_allocator.c new file mode 100644 index 0000000..e146de6 --- /dev/null +++ b/test/test_allocator.c @@ -0,0 +1,121 @@ +// Copyright 2014-2021 David Robillard +// SPDX-License-Identifier: ISC + +#undef NDEBUG + +#include "zix/allocator.h" +#include "zix/bump_allocator.h" + +#include +#include + +static void +test_allocator(void) +{ + // Just a basic smoke test to check that things seem to be working + + ZixAllocator* const allocator = zix_default_allocator(); + + char* const malloced = (char*)zix_malloc(allocator, 4); + malloced[0] = 0; + malloced[3] = 3; + assert(malloced[0] == 0); + assert(malloced[3] == 3); + + char* const calloced = (char*)zix_calloc(allocator, 4, 1); + assert(calloced[0] == 0); + assert(calloced[1] == 0); + assert(calloced[2] == 0); + assert(calloced[3] == 0); + + char* const realloced = (char*)zix_realloc(allocator, calloced, 8); + assert(realloced[0] == 0); + assert(realloced[1] == 0); + assert(realloced[2] == 0); + assert(realloced[3] == 0); + realloced[4] = 4; + realloced[5] = 5; + realloced[6] = 6; + realloced[7] = 7; + assert(realloced[4] == 4); + assert(realloced[5] == 5); + assert(realloced[6] == 6); + assert(realloced[7] == 7); + + char* const aligned = (char*)zix_aligned_alloc(allocator, 4096, 4096); + assert((uintptr_t)aligned % 4096 == 0); + aligned[0] = 0; + aligned[3] = 3; + assert(aligned[0] == 0); + assert(aligned[3] == 3); + + zix_aligned_free(allocator, aligned); + zix_free(allocator, realloced); + zix_free(allocator, malloced); +} + +static void +test_bump_allocator(void) +{ + char buffer[1024] = {0}; + ZixBumpAllocator allocator = zix_bump_allocator(sizeof(buffer), buffer); + + assert(!zix_malloc(&allocator.base, 1025)); + + char* const malloced = (char*)zix_malloc(&allocator.base, 3); + assert(malloced >= buffer); + assert(malloced <= buffer + sizeof(buffer)); + assert((uintptr_t)malloced % sizeof(uintmax_t) == 0U); + + assert(!zix_calloc(&allocator.base, 1017, 1)); + + char* const calloced = (char*)zix_calloc(&allocator.base, 4, 1); + assert(calloced > malloced); + assert(calloced <= buffer + sizeof(buffer)); + assert((uintptr_t)calloced % sizeof(uintmax_t) == 0U); + assert(!calloced[0]); + assert(!calloced[1]); + assert(!calloced[2]); + assert(!calloced[3]); + + char* const realloced = (char*)zix_realloc(&allocator.base, calloced, 8); + assert(realloced == calloced); + + assert(!zix_realloc(&allocator.base, malloced, 8)); // Not the top + assert(!zix_realloc(&allocator.base, realloced, 4089)); // No space + + zix_free(&allocator.base, realloced); + + char* const reclaimed = (char*)zix_malloc(&allocator.base, 512); + assert(reclaimed); + assert(reclaimed == realloced); + + assert(!zix_aligned_alloc(&allocator.base, sizeof(uintmax_t), 1024)); + assert(!zix_aligned_alloc(&allocator.base, 1024, 1024)); + assert(!zix_aligned_alloc(&allocator.base, 2048, 2048)); + assert(!zix_aligned_alloc(&allocator.base, 4096, 4096)); + assert(!zix_aligned_alloc(&allocator.base, 8192, 8192)); + assert(!zix_aligned_alloc(&allocator.base, 4096, 4096)); + assert(!zix_aligned_alloc(&allocator.base, 2048, 2048)); + assert(!zix_aligned_alloc(&allocator.base, 1024, 1024)); + assert(!zix_aligned_alloc(&allocator.base, 512, 512)); + + char* const aligned = (char*)zix_aligned_alloc(&allocator.base, 128, 128); + assert(aligned); + assert(aligned >= reclaimed); + assert(aligned <= buffer + sizeof(buffer)); + assert((uintptr_t)aligned % 128 == 0U); + + zix_aligned_free(&allocator.base, aligned); + zix_free(&allocator.base, reclaimed); // Correct, but a noop + zix_free(&allocator.base, malloced); // Correct, but a noop +} + +int +main(void) +{ + test_allocator(); + test_bump_allocator(); + + return 0; +} diff --git a/test/test_bitset.c b/test/test_bitset.c new file mode 100644 index 0000000..67f6567 --- /dev/null +++ b/test/test_bitset.c @@ -0,0 +1,71 @@ +// Copyright 2014-2020 David Robillard +// SPDX-License-Identifier: ISC + +#undef NDEBUG + +#include "zix/bitset.h" + +#include +#include + +#define N_BITS 256U +#define N_ELEMS (ZIX_BITSET_ELEMS(N_BITS)) + +#define MIN(a, b) (((a) < (b)) ? (a) : (b)) + +int +main(void) +{ + ZixBitset b[N_ELEMS]; + ZixBitsetTally t[N_ELEMS]; + + zix_bitset_clear(b, t, N_BITS); + assert(zix_bitset_count_up_to(b, t, N_BITS) == 0); + + for (size_t i = 0; i < N_BITS; ++i) { + zix_bitset_set(b, t, i); + assert(zix_bitset_get(b, i)); + + const size_t count = zix_bitset_count_up_to(b, t, N_BITS); + assert(count == i + 1); + } + + for (size_t i = 0; i <= N_BITS; ++i) { + const size_t count = zix_bitset_count_up_to(b, t, i); + assert(count == i); + } + + for (size_t i = 0; i <= N_BITS; ++i) { + if (i < N_BITS) { + zix_bitset_reset(b, t, i); + } + + const size_t count = zix_bitset_count_up_to(b, t, i); + assert(count == 0); + } + + zix_bitset_clear(b, t, N_BITS); + for (size_t i = 0; i < N_BITS; i += 2) { + zix_bitset_set(b, t, i); + + const size_t count = zix_bitset_count_up_to(b, t, i + 1); + const size_t result = MIN(N_BITS / 2, i / 2 + 1); + + assert(count == result); + } + + zix_bitset_clear(b, t, N_BITS); + for (size_t i = 0; i < N_BITS; ++i) { + if (i % 2 == 0) { + zix_bitset_set(b, t, i); + + const size_t count = zix_bitset_count_up_to_if(b, t, i); + const size_t result = MIN(N_BITS / 2, i / 2); + assert(count == result); + } else { + assert(zix_bitset_count_up_to_if(b, t, i) == (size_t)-1); + } + } + + return 0; +} diff --git a/test/test_btree.c b/test/test_btree.c new file mode 100644 index 0000000..3820f56 --- /dev/null +++ b/test/test_btree.c @@ -0,0 +1,643 @@ +// Copyright 2011-2021 David Robillard +// SPDX-License-Identifier: ISC + +#undef NDEBUG + +#include "zix/btree.h" + +#include "failing_allocator.h" +#include "test_data.h" + +#include "zix/allocator.h" +#include "zix/attributes.h" +#include "zix/common.h" + +#include +#include +#include +#include +#include +#include + +static bool expect_failure = false; + +ZIX_PURE_FUNC +static int +int_cmp(const void* a, const void* b, const void* ZIX_UNUSED(user_data)) +{ + const uintptr_t ia = (uintptr_t)a; + const uintptr_t ib = (uintptr_t)b; + + assert(ia != 0U); // No wildcards + assert(ib != 0U); // No wildcards + + return ia < ib ? -1 : ia > ib ? 1 : 0; +} + +static uintptr_t +ith_elem(const unsigned test_num, const size_t n_elems, const size_t i) +{ + switch (test_num % 3) { + case 0: + return i + 1; // Increasing + case 1: + return n_elems - i; // Decreasing + default: + return 1U + unique_rand(i); // Pseudo-random + } +} + +typedef struct { + unsigned test_num; + size_t n_elems; +} TestContext; + +static uintptr_t +wildcard_cut(unsigned test_num, size_t n_elems) +{ + return ith_elem(test_num, n_elems, n_elems / 3); +} + +/// Wildcard comparator where 0 matches anything >= wildcard_cut(n_elems) +static int +wildcard_cmp(const void* a, const void* b, const void* user_data) +{ + const TestContext* ctx = (const TestContext*)user_data; + const size_t n_elems = ctx->n_elems; + const unsigned test_num = ctx->test_num; + 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); +} + +ZIX_LOG_FUNC(2, 3) +static int +test_fail(ZixBTree* t, const char* fmt, ...) +{ + zix_btree_free(t, NULL, NULL); + if (expect_failure) { + return EXIT_SUCCESS; + } + + va_list args; + va_start(args, fmt); + fprintf(stderr, "error: "); + vfprintf(stderr, fmt, args); + va_end(args); + return EXIT_FAILURE; +} + +static const size_t n_clear_insertions = 1024U; + +static void +destroy(void* const ptr, const void* const user_data) +{ + (void)user_data; + assert(ptr); + assert((uintptr_t)ptr <= n_clear_insertions); +} + +static void +no_destroy(void* const ptr, const void* const user_data) +{ + (void)user_data; + assert(!ptr); +} + +static void +test_clear(void) +{ + ZixBTree* t = zix_btree_new(NULL, 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, NULL); + assert(zix_btree_size(t) == 0); + + zix_btree_free(t, no_destroy, NULL); +} + +static void +test_free(void) +{ + ZixBTree* t = zix_btree_new(NULL, 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, NULL); +} + +static void +test_iter_comparison(void) +{ + static const size_t n_elems = 4096U; + + ZixBTree* const t = zix_btree_new(NULL, int_cmp, NULL); + + // Store increasing numbers from 1 (jammed into the pointers themselves) + for (uintptr_t r = 1U; r < n_elems; ++r) { + assert(!zix_btree_insert(t, (void*)r)); + } + + // Check that begin and end work sensibly + const ZixBTreeIter begin = zix_btree_begin(t); + const ZixBTreeIter end = zix_btree_end(t); + assert(!zix_btree_iter_is_end(begin)); + assert(zix_btree_iter_is_end(end)); + assert(!zix_btree_iter_equals(begin, end)); + assert(!zix_btree_iter_equals(end, begin)); + + // Make another begin iterator + ZixBTreeIter j = zix_btree_begin(t); + assert(zix_btree_iter_equals(begin, j)); + + // Advance it and check that they are no longer equal + for (size_t r = 1U; r < n_elems - 1U; ++r) { + j = zix_btree_iter_next(j); + assert(!zix_btree_iter_is_end(j)); + assert(!zix_btree_iter_equals(begin, j)); + assert(!zix_btree_iter_equals(end, j)); + assert(!zix_btree_iter_equals(j, end)); + } + + // Advance it to the end + zix_btree_iter_increment(&j); + assert(zix_btree_iter_is_end(j)); + assert(!zix_btree_iter_equals(begin, j)); + assert(zix_btree_iter_equals(end, j)); + assert(zix_btree_iter_equals(j, end)); + + zix_btree_free(t, NULL, NULL); +} + +static void +test_insert_split_value(void) +{ + static const size_t n_insertions = 767U; // Number of insertions to split + static const uintptr_t split_value = 512U; // Value that will be pulled up + + ZixBTree* const t = zix_btree_new(NULL, int_cmp, NULL); + + // Insert right up until it would cause a split + for (uintptr_t r = 1U; r < n_insertions; ++r) { + assert(!zix_btree_insert(t, (void*)r)); + } + + // Insert the element that will be chosen as the split pivot + assert(zix_btree_insert(t, (void*)split_value) == ZIX_STATUS_EXISTS); + + zix_btree_free(t, NULL, NULL); +} + +static void +test_remove_cases(void) +{ + /* Insert and remove in several "phases" with different strides that are not + even multiples. This spreads the load around to hit as many cases as + possible. */ + + static const uintptr_t s1 = 2U; + static const uintptr_t s2 = 255U; + const size_t n_insertions = s1 * s2 * 1000U; + + ZixBTree* const t = zix_btree_new(NULL, int_cmp, NULL); + + // Insert in s1-sized chunks + for (uintptr_t phase = 0U; phase < s1; ++phase) { + for (uintptr_t r = 0U; r < n_insertions / s1; ++r) { + const uintptr_t value = (s1 * r) + phase + 1U; + + assert(!zix_btree_insert(t, (void*)value)); + } + } + + // Remove in s2-sized chunks + ZixBTreeIter next = zix_btree_end(t); + for (uintptr_t phase = 0U; phase < s2; ++phase) { + for (uintptr_t r = 0U; r < n_insertions / s2; ++r) { + const uintptr_t value = (s2 * r) + phase + 1U; + void* out = NULL; + + assert(!zix_btree_remove(t, (void*)value, &out, &next)); + assert((uintptr_t)out == value); + } + } + + assert(!zix_btree_size(t)); + zix_btree_free(t, NULL, NULL); +} + +static int +stress(ZixAllocator* const allocator, + const unsigned test_num, + const size_t n_elems) +{ + if (n_elems == 0) { + return 0; + } + + 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 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"); + } + + if (!zix_btree_iter_equals(ti, end)) { + return test_fail(t, "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)); + } + } + + // 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); + } + + // 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"); + } + + // 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); + } + + 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); + } + } + + // 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); + } + + if (zix_btree_iter_is_end(ti)) { + return test_fail(t, + "Lower bound %" PRIuPTR " @ %" PRIuPTR " hit end\n", + (uintptr_t)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); + } + } + + // 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); + } + } + + // Iterate over all elements + 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) { + 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); + } + last = iter_data; + } + + if (i != n_elems) { + return test_fail(t, + "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"); + } + } + + // 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); + } + 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); + } + last = (uintptr_t)zix_btree_get(ti); + } + + // Delete 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); + } + + if (removed != r) { + return test_fail(t, + "Removed wrong item %" PRIuPTR " != %" PRIuPTR "\n", + removed, + (uintptr_t)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); + } + } + } + + // Ensure the tree is empty + if (zix_btree_size(t) != 0) { + return test_fail(t, "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"); + } + } + + // Delete 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); + } + } + + // 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); + } + + // 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); + } + + if (removed != r) { + return test_fail(t, + "Removed wrong item %" PRIuPTR " != %" PRIuPTR "\n", + removed, + (uintptr_t)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); + } + } + } + + // 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); + } + + // Delete some elements in a random order + for (size_t e = 0; e < zix_btree_size(t) / 2; e++) { + r = ith_elem(test_num, n_elems, unique_rand(e) % n_elems); + + 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); + } + } + + // Delete all remaining elements via next iterator + next = zix_btree_begin(t); + uintptr_t last_value = 0; + 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); + } + + last_value = removed; + } + + assert(zix_btree_size(t) == 0); + zix_btree_free(t, NULL, NULL); + + // 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"); + } + + // 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)); + } + } + + // 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"); + } + + if (zix_btree_iter_is_end(ti)) { + return test_fail(t, "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); + } + + // 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"); + } + + if (!zix_btree_iter_is_end(ti)) { + return test_fail(t, "Lower bound of maximum value is not end\n"); + } + + zix_btree_free(t, NULL, NULL); + + return EXIT_SUCCESS; +} + +static void +test_failed_alloc(void) +{ + ZixFailingAllocator allocator = zix_failing_allocator(); + + // Successfully stress test the tree to count the number of allocations + assert(!stress(&allocator.base, 0, 4096)); + + // Test that each allocation failing is handled gracefully + const size_t n_new_allocs = allocator.n_allocations; + for (size_t i = 0U; i < n_new_allocs; ++i) { + allocator.n_remaining = i; + assert(stress(&allocator.base, 0, 4096)); + } +} + +int +main(int argc, char** argv) +{ + if (argc > 2) { + fprintf(stderr, "Usage: %s [N_ELEMS]\n", argv[0]); + return EXIT_FAILURE; + } + + test_clear(); + test_free(); + test_iter_comparison(); + test_insert_split_value(); + test_remove_cases(); + test_failed_alloc(); + + const unsigned n_tests = 3U; + const size_t n_elems = (argc > 1) ? strtoul(argv[1], NULL, 10) : 131072U; + + printf("Running %u tests with %" PRIuPTR " elements", n_tests, n_elems); + for (unsigned i = 0; i < n_tests; ++i) { + printf("."); + fflush(stdout); + if (stress(NULL, i, n_elems)) { + return EXIT_FAILURE; + } + } + printf("\n"); + + return EXIT_SUCCESS; +} diff --git a/test/test_digest.c b/test/test_digest.c new file mode 100644 index 0000000..7e7e77a --- /dev/null +++ b/test/test_digest.c @@ -0,0 +1,131 @@ +// Copyright 2020-2021 David Robillard +// SPDX-License-Identifier: ISC + +#undef NDEBUG + +#include "zix/attributes.h" +#include "zix/digest.h" + +#include +#include +#include + +// Just basic smoke tests to ensure the hash functions are reacting to data + +static void +test_digest(void) +{ + static const uint8_t data[] = { + 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}; + + size_t last = 0U; + + for (size_t offset = 0; offset < 7; ++offset) { + const size_t len = 8U - offset; + for (size_t i = offset; i < 8; ++i) { + const size_t h = zix_digest(0U, &data[i], len); + assert(h != last); + last = h; + } + } +} + +static void +test_digest32(void) +{ + static const uint8_t data[] = {1, 2, 3, 4, 5, 6, 7, 8}; + + uint32_t last = 0U; + + for (size_t offset = 0; offset < 3; ++offset) { + for (size_t i = offset; i < 4; ++i) { + const uint32_t h = zix_digest32(0U, &data[i], 4); + assert(h != last); + last = h; + } + } +} + +static void +test_digest64(void) +{ + static const uint8_t data[] = { + 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}; + + uint64_t last = 0U; + + for (size_t offset = 0; offset < 7; ++offset) { + for (size_t i = offset; i < 8; ++i) { + const uint64_t h = zix_digest64(0U, &data[i], 8); + assert(h != last); + last = h; + } + } +} + +static void +test_digest32_aligned(void) +{ + static const uint32_t data[] = {1, 2, 3, 4, 5, 6, 7, 8}; + + uint32_t last = 0U; + + for (size_t offset = 0; offset < 3; ++offset) { + const size_t len = 4U - offset; + for (size_t i = offset; i < 4; ++i) { + const uint32_t h = + zix_digest32_aligned(0U, &data[i], len * sizeof(uint32_t)); + assert(h != last); + last = h; + } + } +} + +static void +test_digest64_aligned(void) +{ + static const uint64_t data[] = {1, 2, 3, 4, 5, 6, 7, 8}; + + uint64_t last = 0U; + + for (size_t offset = 0; offset < 3; ++offset) { + const size_t len = 4U - offset; + for (size_t i = offset; i < 4; ++i) { + const uint64_t h = + zix_digest64_aligned(0U, &data[i], len * sizeof(uint64_t)); + assert(h != last); + last = h; + } + } +} + +static void +test_digest_aligned(void) +{ + static const size_t data[] = {1, 2, 3, 4, 5, 6, 7, 8}; + + size_t last = 0U; + + for (size_t offset = 0; offset < 3; ++offset) { + const size_t len = 4U - offset; + for (size_t i = offset; i < 4; ++i) { + const size_t h = zix_digest_aligned(0U, &data[i], len * sizeof(size_t)); + assert(h != last); + last = h; + } + } +} + +ZIX_PURE_FUNC int +main(void) +{ + test_digest32(); + test_digest64(); + test_digest(); + + test_digest32_aligned(); + test_digest64_aligned(); + test_digest_aligned(); + + return 0; +} diff --git a/test/test_hash.c b/test/test_hash.c new file mode 100644 index 0000000..287dbaa --- /dev/null +++ b/test/test_hash.c @@ -0,0 +1,421 @@ +// Copyright 2011-2021 David Robillard +// SPDX-License-Identifier: ISC + +#undef NDEBUG + +#define ZIX_HASH_KEY_TYPE const char +#define ZIX_HASH_RECORD_TYPE const char + +#include "failing_allocator.h" +#include "test_data.h" + +#include "zix/allocator.h" +#include "zix/attributes.h" +#include "zix/common.h" +#include "zix/digest.h" +#include "zix/hash.h" + +#include +#include +#include +#include +#include +#include +#include +#include + +static bool expect_failure = false; + +ZIX_LOG_FUNC(4, 5) +static int +test_fail(ZixHash* const hash, + char* const buffer, + char** const strings, + const char* fmt, + ...) +{ + if (!expect_failure) { + va_list args; + va_start(args, fmt); + fprintf(stderr, "error: "); + vfprintf(stderr, fmt, args); + va_end(args); + } + + zix_hash_free(hash); + free(buffer); + free(strings); + + return expect_failure ? 0 : 1; +} + +ZIX_PURE_FUNC static const char* +identity(const char* record) +{ + return record; +} + +/// Decent hash function using zix_digest (murmur2) +ZIX_PURE_FUNC static size_t +decent_string_hash(const char* const str) +{ + return zix_digest(0U, str, strlen(str)); +} + +/// Terrible hash function from K&R first edition +ZIX_PURE_FUNC static size_t +terrible_string_hash(const char* str) +{ + size_t hash = 0U; + uint8_t c = 0U; + + while ((c = (uint8_t)*str++)) { + hash += c; + } + + return hash; +} + +ZIX_PURE_FUNC static size_t +string_hash_aligned(const char* const str) +{ + size_t length = strlen(str); + + length = (length + (sizeof(size_t) - 1)) / sizeof(size_t) * sizeof(size_t); + return zix_digest_aligned(0U, str, length); +} + +ZIX_PURE_FUNC static size_t +string_hash32(const char* const str) +{ + return (size_t)zix_digest32(0U, str, strlen(str)); +} + +ZIX_PURE_FUNC static size_t +string_hash64(const char* const str) +{ + return (size_t)zix_digest64(0U, str, strlen(str)); +} + +ZIX_PURE_FUNC static size_t +string_hash32_aligned(const char* const str) +{ + size_t length = strlen(str); + + length = (length + 3U) / 4U * 4U; + return (size_t)zix_digest32_aligned(0U, str, length); +} + +#if UINTPTR_MAX >= UINT64_MAX + +ZIX_PURE_FUNC static size_t +string_hash64_aligned(const char* const str) +{ + size_t length = strlen(str); + + length = (length + 7U) / 8U * 8U; + return (size_t)zix_digest64_aligned(0U, str, length); +} + +#endif + +static bool +string_equal(const char* const a, const char* const b) +{ + return !strcmp(a, b); +} + +static int +stress_with(ZixAllocator* const allocator, + const ZixHashFunc hash_func, + const size_t n_elems) +{ + ZixHash* hash = zix_hash_new(allocator, identity, hash_func, string_equal); + if (!hash) { + return test_fail(hash, NULL, NULL, "Failed to allocate hash\n"); + } + + static const size_t string_length = 15; + + char* const buffer = (char*)calloc(1, n_elems * (string_length + 1)); + char** const strings = (char**)calloc(sizeof(char*), n_elems); + if (!buffer || !strings) { + return test_fail(hash, buffer, strings, "Failed to allocate strings\n"); + } + + uint32_t seed = 1U; + for (size_t i = 0U; i < n_elems; ++i) { + strings[i] = buffer + i * (string_length + 1); + assert((uintptr_t)strings[i] % sizeof(size_t) == 0); + assert((uintptr_t)strings[i] % sizeof(uint32_t) == 0); + + for (size_t j = 0U; j < string_length; ++j) { + seed = lcg32(seed); + strings[i][j] = (char)('!' + (seed % 92)); + } + } + + // Insert each string + for (size_t i = 0; i < n_elems; ++i) { + ZixStatus st = zix_hash_insert(hash, strings[i]); + if (st) { + return test_fail( + hash, buffer, strings, "Failed to insert `%s'\n", strings[i]); + } + } + + // Ensure hash size is correct + if (zix_hash_size(hash) != n_elems) { + return test_fail(hash, + buffer, + strings, + "Hash size %" PRIuPTR " != %" PRIuPTR "\n", + zix_hash_size(hash), + n_elems); + } + + // Attempt to insert each string again + for (size_t i = 0; i < n_elems; ++i) { + ZixStatus st = zix_hash_insert(hash, strings[i]); + if (st != ZIX_STATUS_EXISTS) { + return test_fail(hash, + buffer, + strings, + "Double inserted `%s' (%s)\n", + strings[i], + zix_strerror(st)); + } + } + + // Search for each string + for (size_t i = 0; i < n_elems; ++i) { + const char* match = (const char*)zix_hash_find_record(hash, strings[i]); + if (!match) { + return test_fail( + hash, buffer, strings, "Failed to find `%s'\n", strings[i]); + } + if (match != strings[i]) { + return test_fail( + hash, buffer, strings, "Bad match for `%s': `%s'\n", strings[i], match); + } + } + + static const char* const not_indexed_string = "__not__indexed__"; + + // Do a quick smoke test to ensure that false matches don't succeed + char* const not_indexed = (char*)calloc(1, strlen(not_indexed_string) + 1); + if (not_indexed) { + memcpy(not_indexed, not_indexed_string, strlen(not_indexed_string) + 1); + const char* match = (const char*)zix_hash_find_record(hash, not_indexed); + if (match) { + return test_fail( + hash, buffer, strings, "Unexpectedly found `%s'\n", not_indexed); + } + free(not_indexed); + } + + // Remove strings + for (size_t i = 0; i < n_elems; ++i) { + const size_t initial_size = zix_hash_size(hash); + + // Remove string + const char* removed = NULL; + ZixStatus st = zix_hash_remove(hash, strings[i], &removed); + if (st) { + return test_fail( + hash, buffer, strings, "Failed to remove `%s'\n", strings[i]); + } + + // Ensure the removed value is what we expected + if (removed != strings[i]) { + return test_fail(hash, + buffer, + strings, + "Removed `%s` instead of `%s`\n", + removed, + strings[i]); + } + + // Ensure size is updated + if (zix_hash_size(hash) != initial_size - 1) { + return test_fail( + hash, buffer, strings, "Removing node did not decrease hash size\n"); + } + + // Ensure second removal fails + st = zix_hash_remove(hash, strings[i], &removed); + if (st != ZIX_STATUS_NOT_FOUND) { + return test_fail( + hash, buffer, strings, "Unexpectedly removed `%s' twice\n", strings[i]); + } + + // Ensure value can no longer be found + assert(zix_hash_find(hash, strings[i]) == zix_hash_end(hash)); + + // Check to ensure remaining strings are still present + for (size_t j = i + 1; j < n_elems; ++j) { + const char* match = (const char*)zix_hash_find_record(hash, strings[j]); + if (!match) { + return test_fail(hash, + buffer, + strings, + "Failed to find `%s' after remove\n", + strings[j]); + } + if (match != strings[j]) { + return test_fail(hash, + buffer, + strings, + "Bad match for `%s' after remove\n", + strings[j]); + } + } + } + + // Insert each string again (to check non-empty destruction) + for (size_t i = 0; i < n_elems; ++i) { + ZixHashInsertPlan plan = zix_hash_plan_insert(hash, strings[i]); + + assert(!zix_hash_record_at(hash, plan)); + ZixStatus st = zix_hash_insert_at(hash, plan, strings[i]); + if (st) { + return test_fail( + hash, buffer, strings, "Failed to insert `%s'\n", strings[i]); + } + } + + // Check key == value (and test zix_hash_foreach) + size_t n_checked = 0U; + for (ZixHashIter i = zix_hash_begin(hash); i != zix_hash_end(hash); + i = zix_hash_next(hash, i)) { + const char* const string = (const char*)zix_hash_get(hash, i); + assert(string); + if (strlen(string) < 3) { + return test_fail(hash, buffer, strings, "Corrupt value `%s'\n", string); + } + + ++n_checked; + } + if (n_checked != n_elems) { + return test_fail(hash, buffer, strings, "Check failed\n"); + } + + free(strings); + free(buffer); + zix_hash_free(hash); + + return 0; +} + +static int +stress(ZixAllocator* const allocator, const size_t n_elems) +{ + if (stress_with(allocator, decent_string_hash, n_elems) || + stress_with(allocator, terrible_string_hash, n_elems / 4) || + stress_with(allocator, string_hash_aligned, n_elems / 4) || + stress_with(allocator, string_hash32, n_elems / 4) || + stress_with(allocator, string_hash64, n_elems / 4) || + stress_with(allocator, string_hash32_aligned, n_elems / 4)) { + return 1; + } + +#if UINTPTR_MAX >= UINT64_MAX + if (stress_with(allocator, string_hash64_aligned, n_elems / 4)) { + return 1; + } +#endif + + return 0; +} + +/// Identity hash function for numeric strings for explicitly hitting cases +ZIX_PURE_FUNC static size_t +identity_index_hash(const char* const str) +{ + return strtoul(str, NULL, 10); +} + +static void +test_all_tombstones(void) +{ + /* This tests an edge case where a minimum-sized table can be entirely full + of tombstones. If the search loop is not written carefully, then this can + result in a hang. This has been seen to occur in real code, though it's + very hard to hit with a decent hash function. So, we use the above + degenerate index hashing function to explicitly place elements exactly + where we want to hit this case. */ + +#define N_STRINGS 4 + + static const char* original_strings[N_STRINGS] = { + "0 a", + "1 a", + "2 a", + "3 a", + }; + + static const char* collision_strings[N_STRINGS] = { + "0 b", + "1 b", + "2 b", + "3 b", + }; + + ZixStatus st = ZIX_STATUS_SUCCESS; + ZixHash* hash = + zix_hash_new(NULL, identity, identity_index_hash, string_equal); + + // Insert each element then immediately remove it + for (unsigned i = 0U; i < N_STRINGS; ++i) { + const char* removed = NULL; + + assert(!zix_hash_insert(hash, original_strings[i])); + assert(!zix_hash_remove(hash, original_strings[i], &removed)); + } + + // Now the table should be "empty" but contain tombstones + assert(zix_hash_size(hash) == 0); + + // Insert clashing elements which should hit the "all tombstones" case + for (unsigned i = 0U; i < N_STRINGS; ++i) { + assert(!zix_hash_insert(hash, collision_strings[i])); + assert(!st); + } + + zix_hash_free(hash); + +#undef N_STRINGS +} + +static void +test_failed_alloc(void) +{ + ZixFailingAllocator allocator = zix_failing_allocator(); + + // Successfully stress test the tree to count the number of allocations + assert(!stress(&allocator.base, 16)); + + // Test that each allocation failing is handled gracefully + const size_t n_new_allocs = allocator.n_allocations; + for (size_t i = 0U; i < n_new_allocs; ++i) { + allocator.n_remaining = i; + assert(stress(&allocator.base, 16)); + } +} + +int +main(void) +{ + zix_hash_free(NULL); + + test_all_tombstones(); + test_failed_alloc(); + + static const size_t n_elems = 1024U; + + if (stress(NULL, n_elems)) { + return 1; + } + + return 0; +} diff --git a/test/test_ring.c b/test/test_ring.c new file mode 100644 index 0000000..79aa0f1 --- /dev/null +++ b/test/test_ring.c @@ -0,0 +1,195 @@ +// Copyright 2011-2021 David Robillard +// SPDX-License-Identifier: ISC + +#undef NDEBUG + +#include "failing_allocator.h" + +#include "zix/attributes.h" +#include "zix/ring.h" +#include "zix/thread.h" + +#include +#include +#include +#include +#include +#include + +#define MSG_SIZE 20U + +static ZixRing* ring = 0; +static unsigned n_writes = 0; +static bool read_error = false; + +static int +gen_msg(int* const msg, int start) +{ + for (unsigned i = 0U; i < MSG_SIZE; ++i) { + msg[i] = start; + start = (start + 1) % INT_MAX; + } + return start; +} + +ZIX_PURE_FUNC +static int +cmp_msg(const int* const msg1, const int* const msg2) +{ + for (unsigned i = 0U; i < MSG_SIZE; ++i) { + assert(msg1[i] == msg2[i]); + } + + return 1; +} + +static void* +reader(void* ZIX_UNUSED(arg)) +{ + printf("Reader starting\n"); + + int ref_msg[MSG_SIZE]; // Reference generated for comparison + int read_msg[MSG_SIZE]; // Read from ring + unsigned count = 0; + int start = gen_msg(ref_msg, 0); + for (unsigned i = 0; i < n_writes; ++i) { + if (zix_ring_read_space(ring) >= MSG_SIZE * sizeof(int)) { + if (zix_ring_read(ring, read_msg, MSG_SIZE * sizeof(int))) { + assert(cmp_msg(ref_msg, read_msg)); + start = gen_msg(ref_msg, start); + ++count; + } + } + } + + printf("Reader finished\n"); + return NULL; +} + +static void* +writer(void* ZIX_UNUSED(arg)) +{ + printf("Writer starting\n"); + + int write_msg[MSG_SIZE]; // Written to ring + int start = gen_msg(write_msg, 0); + for (unsigned i = 0; i < n_writes; ++i) { + if (zix_ring_write_space(ring) >= MSG_SIZE * sizeof(int)) { + if (zix_ring_write(ring, write_msg, MSG_SIZE * sizeof(int))) { + start = gen_msg(write_msg, start); + } + } + } + + printf("Writer finished\n"); + return NULL; +} + +static int +test_ring(const unsigned size) +{ + zix_ring_free(NULL); + + printf("Testing %u writes of %u ints to a %u int ring...\n", + n_writes, + MSG_SIZE, + size); + + ring = zix_ring_new(NULL, size); + assert(ring); + assert(zix_ring_read_space(ring) == 0); + assert(zix_ring_write_space(ring) == zix_ring_capacity(ring)); + + zix_ring_mlock(ring); + + ZixThread reader_thread; // NOLINT + assert(!zix_thread_create(&reader_thread, MSG_SIZE * 4UL, reader, NULL)); + + ZixThread writer_thread; // NOLINT + assert(!zix_thread_create(&writer_thread, MSG_SIZE * 4UL, writer, NULL)); + + zix_thread_join(reader_thread, NULL); + zix_thread_join(writer_thread, NULL); + + assert(!read_error); + assert(ring); + zix_ring_reset(ring); + assert(zix_ring_read_space(ring) == 0); + assert(zix_ring_write_space(ring) == zix_ring_capacity(ring)); + + zix_ring_write(ring, "a", 1); + zix_ring_write(ring, "b", 1); + + char buf = 0; + uint32_t n = zix_ring_peek(ring, &buf, 1); + assert(n == 1); + assert(buf == 'a'); + + n = zix_ring_skip(ring, 1); + assert(n == 1); + + assert(zix_ring_read_space(ring) == 1); + + n = zix_ring_read(ring, &buf, 1); + assert(n == 1); + assert(buf == 'b'); + + assert(zix_ring_read_space(ring) == 0); + + n = zix_ring_peek(ring, &buf, 1); + assert(n == 0); + + n = zix_ring_read(ring, &buf, 1); + assert(n == 0); + + n = zix_ring_skip(ring, 1); + assert(n == 0); + + char* big_buf = (char*)calloc(size, 1); + n = zix_ring_write(ring, big_buf, size - 1); + assert(n == (uint32_t)size - 1); + + n = zix_ring_write(ring, big_buf, size); + assert(n == 0); + + free(big_buf); + zix_ring_free(ring); + return 0; +} + +static void +test_failed_alloc(void) +{ + ZixFailingAllocator allocator = zix_failing_allocator(); + + // Successfully allocate a ring to count the number of allocations + ring = zix_ring_new(&allocator.base, 512); + assert(ring); + + // Test that each allocation failing is handled gracefully + const size_t n_new_allocs = allocator.n_allocations; + for (size_t i = 0U; i < n_new_allocs; ++i) { + allocator.n_remaining = i; + assert(!zix_ring_new(&allocator.base, 512)); + } + + zix_ring_free(ring); +} + +int +main(int argc, char** argv) +{ + if (argc > 1 && argv[1][0] == '-') { + printf("Usage: %s SIZE N_WRITES\n", argv[0]); + return 1; + } + + const unsigned size = + (argc > 1) ? (unsigned)strtoul(argv[1], NULL, 10) : 1024; + + n_writes = (argc > 2) ? (unsigned)strtoul(argv[2], NULL, 10) : size * 1024; + + test_failed_alloc(); + test_ring(size); + return 0; +} diff --git a/test/test_sem.c b/test/test_sem.c new file mode 100644 index 0000000..33859f1 --- /dev/null +++ b/test/test_sem.c @@ -0,0 +1,70 @@ +// Copyright 2012-2021 David Robillard +// SPDX-License-Identifier: ISC + +#undef NDEBUG + +#include "zix/attributes.h" +#include "zix/sem.h" +#include "zix/thread.h" + +#include +#include +#include + +static ZixSem sem; +static unsigned n_signals = 1024; + +static void* +reader(void* ZIX_UNUSED(arg)) +{ + printf("Reader starting\n"); + + for (unsigned i = 0; i < n_signals; ++i) { + zix_sem_wait(&sem); + } + + printf("Reader finished\n"); + return NULL; +} + +static void* +writer(void* ZIX_UNUSED(arg)) +{ + printf("Writer starting\n"); + + for (unsigned i = 0; i < n_signals; ++i) { + zix_sem_post(&sem); + } + + printf("Writer finished\n"); + return NULL; +} + +int +main(int argc, char** argv) +{ + if (argc > 2) { + printf("Usage: %s N_SIGNALS\n", argv[0]); + return 1; + } + + if (argc > 1) { + n_signals = (unsigned)strtol(argv[1], NULL, 10); + } + + printf("Testing %u signals...\n", n_signals); + + assert(!zix_sem_init(&sem, 0)); + + ZixThread reader_thread; // NOLINT + assert(!zix_thread_create(&reader_thread, 128, reader, NULL)); + + ZixThread writer_thread; // NOLINT + assert(!zix_thread_create(&writer_thread, 128, writer, NULL)); + + zix_thread_join(reader_thread, NULL); + zix_thread_join(writer_thread, NULL); + + zix_sem_destroy(&sem); + return 0; +} diff --git a/test/test_strerror.c b/test/test_strerror.c new file mode 100644 index 0000000..2f4c090 --- /dev/null +++ b/test/test_strerror.c @@ -0,0 +1,31 @@ +// Copyright 2021 David Robillard +// SPDX-License-Identifier: ISC + +#undef NDEBUG + +#include "zix/common.h" + +#include +#include +#include + +int +main(void) +{ + const char* msg = zix_strerror(ZIX_STATUS_SUCCESS); + assert(!strcmp(msg, "Success")); + + for (int i = ZIX_STATUS_ERROR; i <= ZIX_STATUS_REACHED_END; ++i) { + msg = zix_strerror((ZixStatus)i); + assert(strcmp(msg, "Success")); + } + + msg = zix_strerror((ZixStatus)-1); + assert(!strcmp(msg, "Unknown error")); + + msg = zix_strerror((ZixStatus)1000000); + assert(!strcmp(msg, "Unknown error")); + + printf("Success\n"); + return 0; +} diff --git a/test/test_tree.c b/test/test_tree.c new file mode 100644 index 0000000..7c7fcf4 --- /dev/null +++ b/test/test_tree.c @@ -0,0 +1,224 @@ +// Copyright 2011-2020 David Robillard +// SPDX-License-Identifier: ISC + +#include "test_data.h" + +#include "zix/attributes.h" +#include "zix/common.h" +#include "zix/tree.h" + +#include +#include +#include +#include +#include + +static unsigned seed = 1; + +static int +int_cmp(const void* a, const void* b, const void* ZIX_UNUSED(user_data)) +{ + const uintptr_t ia = (uintptr_t)a; + const uintptr_t ib = (uintptr_t)b; + + return ia < ib ? -1 : ia > ib ? 1 : 0; +} + +static uintptr_t +ith_elem(unsigned test_num, size_t n_elems, size_t i) +{ + switch (test_num % 3) { + case 0: + return i; // Increasing (worst case) + case 1: + return n_elems - i; // Decreasing (worse case) + case 2: + default: + return lcg(seed + i) % 100U; // Random + } +} + +static int +test_fail(void) +{ + return EXIT_FAILURE; +} + +static int +stress(unsigned test_num, size_t n_elems) +{ + uintptr_t r = 0U; + ZixTreeIter* ti = NULL; + ZixTree* t = zix_tree_new(NULL, true, int_cmp, NULL, NULL, NULL); + + // Insert n_elems elements + for (size_t i = 0; i < n_elems; ++i) { + r = ith_elem(test_num, n_elems, i); + + ZixStatus status = zix_tree_insert(t, (void*)r, &ti); + if (status) { + fprintf(stderr, "Insert failed\n"); + return test_fail(); + } + + if ((uintptr_t)zix_tree_get(ti) != r) { + fprintf(stderr, + "Data corrupt (%" PRIuPTR " != %" PRIuPTR ")\n", + (uintptr_t)zix_tree_get(ti), + r); + return test_fail(); + } + } + + // Ensure tree size is correct + if (zix_tree_size(t) != n_elems) { + fprintf(stderr, + "Tree size %" PRIuPTR " != %" PRIuPTR "\n", + zix_tree_size(t), + n_elems); + return test_fail(); + } + + // Search for all elements + for (size_t i = 0; i < n_elems; ++i) { + r = ith_elem(test_num, n_elems, i); + if (zix_tree_find(t, (void*)r, &ti)) { + fprintf(stderr, "Find failed\n"); + return test_fail(); + } + if ((uintptr_t)zix_tree_get(ti) != r) { + fprintf(stderr, + "Data corrupt (%" PRIuPTR " != %" PRIuPTR ")\n", + (uintptr_t)zix_tree_get(ti), + r); + return test_fail(); + } + } + + // Iterate over all elements + size_t i = 0; + uintptr_t last = 0; + for (ZixTreeIter* iter = zix_tree_begin(t); !zix_tree_iter_is_end(iter); + iter = zix_tree_iter_next(iter), ++i) { + const uintptr_t iter_data = (uintptr_t)zix_tree_get(iter); + if (iter_data < last) { + fprintf(stderr, + "Iter corrupt (%" PRIuPTR " < %" PRIuPTR ")\n", + iter_data, + last); + return test_fail(); + } + last = iter_data; + } + if (i != n_elems) { + fprintf(stderr, + "Iteration stopped at %" PRIuPTR "/%" PRIuPTR " elements\n", + i, + n_elems); + return test_fail(); + } + + // Iterate over all elements backwards + i = 0; + last = INTPTR_MAX; + for (ZixTreeIter* iter = zix_tree_rbegin(t); !zix_tree_iter_is_rend(iter); + iter = zix_tree_iter_prev(iter), ++i) { + const uintptr_t iter_data = (uintptr_t)zix_tree_get(iter); + if (iter_data > last) { + fprintf(stderr, + "Iter corrupt (%" PRIuPTR " < %" PRIuPTR ")\n", + iter_data, + last); + return test_fail(); + } + last = iter_data; + } + + // Delete all elements + for (size_t e = 0; e < n_elems; e++) { + r = ith_elem(test_num, n_elems, e); + + ZixTreeIter* item = NULL; + if (zix_tree_find(t, (void*)r, &item) != ZIX_STATUS_SUCCESS) { + fprintf(stderr, "Failed to find item to remove\n"); + return test_fail(); + } + if (zix_tree_remove(t, item)) { + fprintf(stderr, "Error removing item\n"); + } + } + + // Ensure the tree is empty + if (zix_tree_size(t) != 0) { + fprintf(stderr, "Tree size %" PRIuPTR " != 0\n", zix_tree_size(t)); + return test_fail(); + } + + // 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); + + ZixStatus status = zix_tree_insert(t, (void*)r, &ti); + if (status) { + fprintf(stderr, "Insert failed\n"); + return test_fail(); + } + + if ((uintptr_t)zix_tree_get(ti) != r) { + fprintf(stderr, + "Data corrupt (%" PRIuPTR " != %" PRIuPTR ")\n", + (uintptr_t)zix_tree_get(ti), + r); + return test_fail(); + } + } + + // Ensure tree size is correct + if (zix_tree_size(t) != n_elems) { + fprintf(stderr, + "Tree size %" PRIuPTR " != %" PRIuPTR "\n", + zix_tree_size(t), + n_elems); + return test_fail(); + } + + zix_tree_free(t); + + return EXIT_SUCCESS; +} + +int +main(int argc, char** argv) +{ + const unsigned n_tests = 3; + unsigned n_elems = 0; + + if (argc == 1) { + n_elems = 100000; + } else { + n_elems = (unsigned)strtoul(argv[1], NULL, 10); + if (argc > 2) { + seed = (unsigned)strtoul(argv[2], NULL, 10); + } else { + seed = (unsigned)time(NULL); + } + } + + if (n_elems == 0) { + fprintf(stderr, "USAGE: %s [N_ELEMS]\n", argv[0]); + return 1; + } + + printf("Running %u tests with %u elements (seed %u)", n_tests, n_elems, seed); + + for (unsigned i = 0; i < n_tests; ++i) { + printf("."); + fflush(stdout); + if (stress(i, n_elems)) { + fprintf(stderr, "FAIL: Random seed %u\n", seed); + return test_fail(); + } + } + printf("\n"); + return EXIT_SUCCESS; +} diff --git a/test/tree_test.c b/test/tree_test.c deleted file mode 100644 index 7c7fcf4..0000000 --- a/test/tree_test.c +++ /dev/null @@ -1,224 +0,0 @@ -// Copyright 2011-2020 David Robillard -// SPDX-License-Identifier: ISC - -#include "test_data.h" - -#include "zix/attributes.h" -#include "zix/common.h" -#include "zix/tree.h" - -#include -#include -#include -#include -#include - -static unsigned seed = 1; - -static int -int_cmp(const void* a, const void* b, const void* ZIX_UNUSED(user_data)) -{ - const uintptr_t ia = (uintptr_t)a; - const uintptr_t ib = (uintptr_t)b; - - return ia < ib ? -1 : ia > ib ? 1 : 0; -} - -static uintptr_t -ith_elem(unsigned test_num, size_t n_elems, size_t i) -{ - switch (test_num % 3) { - case 0: - return i; // Increasing (worst case) - case 1: - return n_elems - i; // Decreasing (worse case) - case 2: - default: - return lcg(seed + i) % 100U; // Random - } -} - -static int -test_fail(void) -{ - return EXIT_FAILURE; -} - -static int -stress(unsigned test_num, size_t n_elems) -{ - uintptr_t r = 0U; - ZixTreeIter* ti = NULL; - ZixTree* t = zix_tree_new(NULL, true, int_cmp, NULL, NULL, NULL); - - // Insert n_elems elements - for (size_t i = 0; i < n_elems; ++i) { - r = ith_elem(test_num, n_elems, i); - - ZixStatus status = zix_tree_insert(t, (void*)r, &ti); - if (status) { - fprintf(stderr, "Insert failed\n"); - return test_fail(); - } - - if ((uintptr_t)zix_tree_get(ti) != r) { - fprintf(stderr, - "Data corrupt (%" PRIuPTR " != %" PRIuPTR ")\n", - (uintptr_t)zix_tree_get(ti), - r); - return test_fail(); - } - } - - // Ensure tree size is correct - if (zix_tree_size(t) != n_elems) { - fprintf(stderr, - "Tree size %" PRIuPTR " != %" PRIuPTR "\n", - zix_tree_size(t), - n_elems); - return test_fail(); - } - - // Search for all elements - for (size_t i = 0; i < n_elems; ++i) { - r = ith_elem(test_num, n_elems, i); - if (zix_tree_find(t, (void*)r, &ti)) { - fprintf(stderr, "Find failed\n"); - return test_fail(); - } - if ((uintptr_t)zix_tree_get(ti) != r) { - fprintf(stderr, - "Data corrupt (%" PRIuPTR " != %" PRIuPTR ")\n", - (uintptr_t)zix_tree_get(ti), - r); - return test_fail(); - } - } - - // Iterate over all elements - size_t i = 0; - uintptr_t last = 0; - for (ZixTreeIter* iter = zix_tree_begin(t); !zix_tree_iter_is_end(iter); - iter = zix_tree_iter_next(iter), ++i) { - const uintptr_t iter_data = (uintptr_t)zix_tree_get(iter); - if (iter_data < last) { - fprintf(stderr, - "Iter corrupt (%" PRIuPTR " < %" PRIuPTR ")\n", - iter_data, - last); - return test_fail(); - } - last = iter_data; - } - if (i != n_elems) { - fprintf(stderr, - "Iteration stopped at %" PRIuPTR "/%" PRIuPTR " elements\n", - i, - n_elems); - return test_fail(); - } - - // Iterate over all elements backwards - i = 0; - last = INTPTR_MAX; - for (ZixTreeIter* iter = zix_tree_rbegin(t); !zix_tree_iter_is_rend(iter); - iter = zix_tree_iter_prev(iter), ++i) { - const uintptr_t iter_data = (uintptr_t)zix_tree_get(iter); - if (iter_data > last) { - fprintf(stderr, - "Iter corrupt (%" PRIuPTR " < %" PRIuPTR ")\n", - iter_data, - last); - return test_fail(); - } - last = iter_data; - } - - // Delete all elements - for (size_t e = 0; e < n_elems; e++) { - r = ith_elem(test_num, n_elems, e); - - ZixTreeIter* item = NULL; - if (zix_tree_find(t, (void*)r, &item) != ZIX_STATUS_SUCCESS) { - fprintf(stderr, "Failed to find item to remove\n"); - return test_fail(); - } - if (zix_tree_remove(t, item)) { - fprintf(stderr, "Error removing item\n"); - } - } - - // Ensure the tree is empty - if (zix_tree_size(t) != 0) { - fprintf(stderr, "Tree size %" PRIuPTR " != 0\n", zix_tree_size(t)); - return test_fail(); - } - - // 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); - - ZixStatus status = zix_tree_insert(t, (void*)r, &ti); - if (status) { - fprintf(stderr, "Insert failed\n"); - return test_fail(); - } - - if ((uintptr_t)zix_tree_get(ti) != r) { - fprintf(stderr, - "Data corrupt (%" PRIuPTR " != %" PRIuPTR ")\n", - (uintptr_t)zix_tree_get(ti), - r); - return test_fail(); - } - } - - // Ensure tree size is correct - if (zix_tree_size(t) != n_elems) { - fprintf(stderr, - "Tree size %" PRIuPTR " != %" PRIuPTR "\n", - zix_tree_size(t), - n_elems); - return test_fail(); - } - - zix_tree_free(t); - - return EXIT_SUCCESS; -} - -int -main(int argc, char** argv) -{ - const unsigned n_tests = 3; - unsigned n_elems = 0; - - if (argc == 1) { - n_elems = 100000; - } else { - n_elems = (unsigned)strtoul(argv[1], NULL, 10); - if (argc > 2) { - seed = (unsigned)strtoul(argv[2], NULL, 10); - } else { - seed = (unsigned)time(NULL); - } - } - - if (n_elems == 0) { - fprintf(stderr, "USAGE: %s [N_ELEMS]\n", argv[0]); - return 1; - } - - printf("Running %u tests with %u elements (seed %u)", n_tests, n_elems, seed); - - for (unsigned i = 0; i < n_tests; ++i) { - printf("."); - fflush(stdout); - if (stress(i, n_elems)) { - fprintf(stderr, "FAIL: Random seed %u\n", seed); - return test_fail(); - } - } - printf("\n"); - return EXIT_SUCCESS; -} -- cgit v1.2.1