summaryrefslogtreecommitdiffstats
path: root/test
diff options
context:
space:
mode:
Diffstat (limited to 'test')
-rw-r--r--test/bitset_test.c112
-rw-r--r--test/btree_test.c871
-rw-r--r--test/digest_test.c86
-rw-r--r--test/hash_test.c308
-rw-r--r--test/inline_test.c6
-rw-r--r--test/ring_test.c342
-rw-r--r--test/sem_test.c90
-rw-r--r--test/sorted_array_test.c254
-rw-r--r--test/strindex_test.c54
-rw-r--r--test/test_malloc.c58
-rw-r--r--test/test_malloc.h12
-rw-r--r--test/tree_test.c355
12 files changed, 1294 insertions, 1254 deletions
diff --git a/test/bitset_test.c b/test/bitset_test.c
index 8fa610f..5482f1b 100644
--- a/test/bitset_test.c
+++ b/test/bitset_test.c
@@ -20,7 +20,7 @@
#include <stdarg.h>
#include <stdio.h>
-#define N_BITS 256
+#define N_BITS 256
#define N_ELEMS (ZIX_BITSET_ELEMS(N_BITS))
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
@@ -29,64 +29,64 @@ ZIX_LOG_FUNC(1, 2)
static int
test_fail(const char* fmt, ...)
{
- va_list args;
- va_start(args, fmt);
- fprintf(stderr, "error: ");
- vfprintf(stderr, fmt, args);
- va_end(args);
- return 1;
+ va_list args;
+ va_start(args, fmt);
+ fprintf(stderr, "error: ");
+ vfprintf(stderr, fmt, args);
+ va_end(args);
+ return 1;
}
int
main(void)
{
- ZixBitset b[N_ELEMS];
- ZixBitsetTally t[N_ELEMS];
-
- zix_bitset_clear(b, t, N_BITS);
- if (zix_bitset_count_up_to(b, t, N_BITS) != 0) {
- return test_fail("Cleared bitset has non-zero count\n");
- }
-
- for (size_t i = 0; i < N_BITS; ++i) {
- zix_bitset_set(b, t, i);
- const size_t count = zix_bitset_count_up_to(b, t, N_BITS);
- if (count != i + 1) {
- return test_fail("Count %zu != %zu\n", count, i + 1);
- }
-
- if (!zix_bitset_get(b, i)) {
- return test_fail("Bit %zu is not set\n", i);
- }
- }
-
- for (size_t i = 0; i <= N_BITS; ++i) {
- const size_t count = zix_bitset_count_up_to(b, t, i);
- if (count != i) {
- return test_fail("Count to %zu is %zu != %zu\n", i, 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);
- if (count != 0) {
- return test_fail("Count to %zu is %zu != %d\n", i, 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);
- if (count != result) {
- return test_fail("Count to %zu is %zu != %zu\n", i, count, result);
- }
- }
-
- return 0;
+ ZixBitset b[N_ELEMS];
+ ZixBitsetTally t[N_ELEMS];
+
+ zix_bitset_clear(b, t, N_BITS);
+ if (zix_bitset_count_up_to(b, t, N_BITS) != 0) {
+ return test_fail("Cleared bitset has non-zero count\n");
+ }
+
+ for (size_t i = 0; i < N_BITS; ++i) {
+ zix_bitset_set(b, t, i);
+ const size_t count = zix_bitset_count_up_to(b, t, N_BITS);
+ if (count != i + 1) {
+ return test_fail("Count %zu != %zu\n", count, i + 1);
+ }
+
+ if (!zix_bitset_get(b, i)) {
+ return test_fail("Bit %zu is not set\n", i);
+ }
+ }
+
+ for (size_t i = 0; i <= N_BITS; ++i) {
+ const size_t count = zix_bitset_count_up_to(b, t, i);
+ if (count != i) {
+ return test_fail("Count to %zu is %zu != %zu\n", i, 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);
+ if (count != 0) {
+ return test_fail("Count to %zu is %zu != %d\n", i, 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);
+ if (count != result) {
+ return test_fail("Count to %zu is %zu != %zu\n", i, count, result);
+ }
+ }
+
+ return 0;
}
diff --git a/test/btree_test.c b/test/btree_test.c
index 3336d91..5c32020 100644
--- a/test/btree_test.c
+++ b/test/btree_test.c
@@ -34,483 +34,506 @@ static bool expect_failure = false;
static uintptr_t
unique_rand(size_t i)
{
- i ^= 0x00005CA1Eu; // Juggle bits to avoid linear clumps
+ i ^= 0x00005CA1Eu; // Juggle bits to avoid linear clumps
- // Largest prime < 2^32 which satisfies (2^32 = 3 mod 4)
- static const uint32_t prime = 4294967291;
- if (i >= prime) {
- return i; // Values >= prime are mapped to themselves
- }
+ // Largest prime < 2^32 which satisfies (2^32 = 3 mod 4)
+ static const uint32_t prime = 4294967291;
+ if (i >= prime) {
+ return i; // Values >= prime are mapped to themselves
+ }
- const uint64_t residue = ((uint64_t)i * i) % prime;
- return (i <= prime / 2) ? residue : prime - residue;
+ const uint64_t residue = ((uint64_t)i * i) % prime;
+ return (i <= prime / 2) ? residue : prime - residue;
}
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;
+ const uintptr_t ia = (uintptr_t)a;
+ const uintptr_t ib = (uintptr_t)b;
- return ia < ib ? -1 : ia > ib ? 1 : 0;
+ 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 unique_rand(i); // Pseudo-random
- }
+ switch (test_num % 3) {
+ case 0:
+ return i + 1; // Increasing
+ case 1:
+ return n_elems - i; // Decreasing
+ default:
+ return unique_rand(i); // Pseudo-random
+ }
}
-static void destroy(void* ZIX_UNUSED(ptr))
+static void
+destroy(void* ZIX_UNUSED(ptr))
{
}
typedef struct {
- unsigned test_num;
- size_t n_elems;
+ 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);
+ 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;
+ 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
- }
+ if (ia == 0) {
+ if (ib >= wildcard_cut(test_num, n_elems)) {
+ return 0; // Wildcard match
+ }
- return 1; // Wildcard a > b
- }
+ return 1; // Wildcard a > b
+ }
- if (ib == 0) {
- if (ia >= wildcard_cut(test_num, n_elems)) {
- return 0; // Wildcard match
- }
+ if (ib == 0) {
+ if (ia >= wildcard_cut(test_num, n_elems)) {
+ return 0; // Wildcard match
+ }
- return -1; // Wildcard b > a
- }
+ return -1; // Wildcard b > a
+ }
- return int_cmp(a, b, user_data);
+ 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);
- 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;
+ zix_btree_free(t);
+ 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 int
stress(const unsigned test_num, const size_t n_elems)
{
- if (n_elems == 0) {
- return 0;
- }
-
- uintptr_t r = 0;
- ZixBTree* t = zix_btree_new(int_cmp, NULL, 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 (!ti) {
- return test_fail(t, "Failed to allocate iterator\n");
- }
-
- 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");
- }
-
- zix_btree_iter_free(end);
- zix_btree_iter_free(ti);
-
- if (zix_btree_iter_copy(NULL)) {
- return test_fail(t, "Copy of null iterator returned non-null\n");
- }
-
- // Insert n_elems elements
- for (size_t i = 0; i < n_elems; ++i) {
- r = ith_elem(test_num, n_elems, i);
- 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 %zu != %zu\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");
- }
- zix_btree_iter_free(end);
-
- // Ensure non-null iterator copying works
- ZixBTreeIter* begin_copy = zix_btree_iter_copy(ti);
- if (!zix_btree_iter_equals(ti, begin_copy)) {
- return test_fail(t, "Iterator copy is not equal to original\n");
- }
- zix_btree_iter_free(begin_copy);
- zix_btree_iter_free(ti);
-
- // Search for all elements
- for (size_t i = 0; i < n_elems; ++i) {
- r = ith_elem(test_num, n_elems, i);
- if (zix_btree_find(t, (void*)r, &ti)) {
- return test_fail(t, "Find %" PRIuPTR " @ %zu 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);
- }
-
- zix_btree_iter_free(ti);
- }
-
- if (zix_btree_lower_bound(NULL, (void*)r, &ti) != ZIX_STATUS_BAD_ARG) {
- return test_fail(t, "Lower bound on NULL tree succeeded\n");
- }
-
- // Find the lower bound of all elements and ensure it's exact
- for (size_t i = 0; i < n_elems; ++i) {
- r = ith_elem(test_num, n_elems, i);
- if (zix_btree_lower_bound(t, (void*)r, &ti)) {
- return test_fail(t, "Lower bound %" PRIuPTR " @ %zu failed\n",
- (uintptr_t)r, i);
- }
-
- if (zix_btree_iter_is_end(ti)) {
- return test_fail(t, "Lower bound %" PRIuPTR " @ %zu 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);
- }
-
- zix_btree_iter_free(ti);
- }
-
- // 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 @ %zu corrupt (%" PRIuPTR " < %" PRIuPTR ")\n",
- i, iter_data, last);
- }
- last = iter_data;
- }
- zix_btree_iter_free(ti);
- if (i != n_elems) {
- return test_fail(t, "Iteration stopped at %zu/%zu 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);
- }
- zix_btree_iter_free(ti);
-
- // Delete all elements
- ZixBTreeIter* next = NULL;
- for (size_t e = 0; e < n_elems; e++) {
- r = ith_elem(test_num, n_elems, e);
- uintptr_t removed;
- 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);
- }
- }
- }
- zix_btree_iter_free(next);
- next = NULL;
-
- // Ensure the tree is empty
- if (zix_btree_size(t) != 0) {
- return test_fail(t, "Tree size %zu != 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;
- if (!zix_btree_remove(t, (void*)r, (void**)&removed, &next)) {
- return test_fail(t, "Non-existant deletion of %" PRIuPTR " succeeded\n",
- (uintptr_t)r);
- }
- }
- zix_btree_iter_free(next);
- next = NULL;
-
- // Ensure tree size is still correct
- if (zix_btree_size(t) != n_elems) {
- return test_fail(t, "Tree size %zu != %zu\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;
- 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);
- }
- }
- }
- zix_btree_iter_free(next);
- next = NULL;
-
- // Check tree size
- if (zix_btree_size(t) != n_elems - (n_elems / 4)) {
- return test_fail(t, "Tree size %zu != %zu\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, rand() % n_elems);
- uintptr_t removed;
- 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);
- }
- }
- zix_btree_iter_free(next);
- next = NULL;
-
- // 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(!next || zix_btree_size(t) == 0);
- zix_btree_iter_free(next);
- next = NULL;
-
- zix_btree_free(t);
-
- // Test lower_bound with wildcard comparator
-
- TestContext ctx = { test_num, n_elems };
- if (!(t = zix_btree_new(wildcard_cmp, &ctx, destroy))) {
- 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 (r != 0) { // Can't insert wildcards
- 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, (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);
- }
-
- zix_btree_iter_free(ti);
-
- // Find lower bound of value past end
- const uintptr_t max = (uintptr_t)-1;
- if (zix_btree_lower_bound(t, (void*)max, &ti)) {
- 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_iter_free(ti);
- zix_btree_free(t);
-
- return EXIT_SUCCESS;
+ if (n_elems == 0) {
+ return 0;
+ }
+
+ uintptr_t r = 0;
+ ZixBTree* t = zix_btree_new(int_cmp, NULL, 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 (!ti) {
+ return test_fail(t, "Failed to allocate iterator\n");
+ }
+
+ 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");
+ }
+
+ zix_btree_iter_free(end);
+ zix_btree_iter_free(ti);
+
+ if (zix_btree_iter_copy(NULL)) {
+ return test_fail(t, "Copy of null iterator returned non-null\n");
+ }
+
+ // Insert n_elems elements
+ for (size_t i = 0; i < n_elems; ++i) {
+ r = ith_elem(test_num, n_elems, i);
+ 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 %zu != %zu\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");
+ }
+ zix_btree_iter_free(end);
+
+ // Ensure non-null iterator copying works
+ ZixBTreeIter* begin_copy = zix_btree_iter_copy(ti);
+ if (!zix_btree_iter_equals(ti, begin_copy)) {
+ return test_fail(t, "Iterator copy is not equal to original\n");
+ }
+ zix_btree_iter_free(begin_copy);
+ zix_btree_iter_free(ti);
+
+ // Search for all elements
+ for (size_t i = 0; i < n_elems; ++i) {
+ r = ith_elem(test_num, n_elems, i);
+ if (zix_btree_find(t, (void*)r, &ti)) {
+ return test_fail(t, "Find %" PRIuPTR " @ %zu 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);
+ }
+
+ zix_btree_iter_free(ti);
+ }
+
+ if (zix_btree_lower_bound(NULL, (void*)r, &ti) != ZIX_STATUS_BAD_ARG) {
+ return test_fail(t, "Lower bound on NULL tree succeeded\n");
+ }
+
+ // Find the lower bound of all elements and ensure it's exact
+ for (size_t i = 0; i < n_elems; ++i) {
+ r = ith_elem(test_num, n_elems, i);
+ if (zix_btree_lower_bound(t, (void*)r, &ti)) {
+ return test_fail(
+ t, "Lower bound %" PRIuPTR " @ %zu failed\n", (uintptr_t)r, i);
+ }
+
+ if (zix_btree_iter_is_end(ti)) {
+ return test_fail(
+ t, "Lower bound %" PRIuPTR " @ %zu 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);
+ }
+
+ zix_btree_iter_free(ti);
+ }
+
+ // 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 @ %zu corrupt (%" PRIuPTR " < %" PRIuPTR ")\n",
+ i,
+ iter_data,
+ last);
+ }
+ last = iter_data;
+ }
+ zix_btree_iter_free(ti);
+ if (i != n_elems) {
+ return test_fail(t, "Iteration stopped at %zu/%zu 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);
+ }
+ zix_btree_iter_free(ti);
+
+ // Delete all elements
+ ZixBTreeIter* next = NULL;
+ for (size_t e = 0; e < n_elems; e++) {
+ r = ith_elem(test_num, n_elems, e);
+ uintptr_t removed;
+ 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);
+ }
+ }
+ }
+ zix_btree_iter_free(next);
+ next = NULL;
+
+ // Ensure the tree is empty
+ if (zix_btree_size(t) != 0) {
+ return test_fail(t, "Tree size %zu != 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;
+ if (!zix_btree_remove(t, (void*)r, (void**)&removed, &next)) {
+ return test_fail(
+ t, "Non-existant deletion of %" PRIuPTR " succeeded\n", (uintptr_t)r);
+ }
+ }
+ zix_btree_iter_free(next);
+ next = NULL;
+
+ // Ensure tree size is still correct
+ if (zix_btree_size(t) != n_elems) {
+ return test_fail(t, "Tree size %zu != %zu\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;
+ 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);
+ }
+ }
+ }
+ zix_btree_iter_free(next);
+ next = NULL;
+
+ // Check tree size
+ if (zix_btree_size(t) != n_elems - (n_elems / 4)) {
+ return test_fail(t, "Tree size %zu != %zu\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, rand() % n_elems);
+ uintptr_t removed;
+ 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);
+ }
+ }
+ zix_btree_iter_free(next);
+ next = NULL;
+
+ // 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(!next || zix_btree_size(t) == 0);
+ zix_btree_iter_free(next);
+ next = NULL;
+
+ zix_btree_free(t);
+
+ // Test lower_bound with wildcard comparator
+
+ TestContext ctx = {test_num, n_elems};
+ if (!(t = zix_btree_new(wildcard_cmp, &ctx, destroy))) {
+ 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 (r != 0) { // Can't insert wildcards
+ 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, (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);
+ }
+
+ zix_btree_iter_free(ti);
+
+ // Find lower bound of value past end
+ const uintptr_t max = (uintptr_t)-1;
+ if (zix_btree_lower_bound(t, (void*)max, &ti)) {
+ 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_iter_free(ti);
+ zix_btree_free(t);
+
+ return EXIT_SUCCESS;
}
int
main(int argc, char** argv)
{
- if (argc > 2) {
- fprintf(stderr, "Usage: %s [N_ELEMS]\n", argv[0]);
- return EXIT_FAILURE;
- }
-
- const unsigned n_tests = 3;
- unsigned n_elems = (argc > 1) ? (unsigned)atol(argv[1]) : 524288u;
-
- printf("Running %u tests with %u elements", n_tests, n_elems);
- for (unsigned i = 0; i < n_tests; ++i) {
- printf(".");
- fflush(stdout);
- if (stress(i, n_elems)) {
- return EXIT_FAILURE;
- }
- }
- printf("\n");
+ if (argc > 2) {
+ fprintf(stderr, "Usage: %s [N_ELEMS]\n", argv[0]);
+ return EXIT_FAILURE;
+ }
+
+ const unsigned n_tests = 3;
+ unsigned n_elems = (argc > 1) ? (unsigned)atol(argv[1]) : 524288u;
+
+ printf("Running %u tests with %u elements", n_tests, n_elems);
+ for (unsigned i = 0; i < n_tests; ++i) {
+ printf(".");
+ fflush(stdout);
+ if (stress(i, n_elems)) {
+ return EXIT_FAILURE;
+ }
+ }
+ printf("\n");
#ifdef ZIX_WITH_TEST_MALLOC
- const size_t total_n_allocs = test_malloc_get_n_allocs();
- const size_t fail_n_elems = 1000;
- printf("Testing 0 ... %zu failed allocations\n", total_n_allocs);
- expect_failure = true;
- for (size_t i = 0; i < total_n_allocs; ++i) {
- test_malloc_reset(i);
- stress(0, fail_n_elems);
- if (i > test_malloc_get_n_allocs()) {
- break;
- }
- }
-
- test_malloc_reset((size_t)-1);
+ const size_t total_n_allocs = test_malloc_get_n_allocs();
+ const size_t fail_n_elems = 1000;
+ printf("Testing 0 ... %zu failed allocations\n", total_n_allocs);
+ expect_failure = true;
+ for (size_t i = 0; i < total_n_allocs; ++i) {
+ test_malloc_reset(i);
+ stress(0, fail_n_elems);
+ if (i > test_malloc_get_n_allocs()) {
+ break;
+ }
+ }
+
+ test_malloc_reset((size_t)-1);
#endif
- return EXIT_SUCCESS;
+ return EXIT_SUCCESS;
}
diff --git a/test/digest_test.c b/test/digest_test.c
index 00a58d9..809f432 100644
--- a/test/digest_test.c
+++ b/test/digest_test.c
@@ -24,68 +24,68 @@
static void
test_bytes(void)
{
- static const uint8_t data[] = {1, 2, 3, 4, 5, 6, 7, 8};
+ static const uint8_t data[] = {1, 2, 3, 4, 5, 6, 7, 8};
- for (size_t offset = 0; offset < 7; ++offset) {
- const size_t len = 8 - offset;
+ for (size_t offset = 0; offset < 7; ++offset) {
+ const size_t len = 8 - offset;
- uint32_t d = zix_digest_start();
- for (size_t i = offset; i < 8; ++i) {
- const uint32_t new_d = zix_digest_add(d, &data[i], 1);
- assert(new_d != d);
- d = new_d;
- }
+ uint32_t d = zix_digest_start();
+ for (size_t i = offset; i < 8; ++i) {
+ const uint32_t new_d = zix_digest_add(d, &data[i], 1);
+ assert(new_d != d);
+ d = new_d;
+ }
- assert(zix_digest_add(zix_digest_start(), &data[offset], len) == d);
- }
+ assert(zix_digest_add(zix_digest_start(), &data[offset], len) == d);
+ }
}
static void
test_64(void)
{
- static const uint64_t data[] = {1, 2, 3, 4, 5, 6, 7, 8};
+ static const uint64_t data[] = {1, 2, 3, 4, 5, 6, 7, 8};
- uint32_t d = zix_digest_start();
- for (size_t i = 0; i < 8; ++i) {
- const uint32_t new_d = zix_digest_add_64(d, &data[i], sizeof(uint64_t));
- assert(new_d != d);
- d = new_d;
- }
+ uint32_t d = zix_digest_start();
+ for (size_t i = 0; i < 8; ++i) {
+ const uint32_t new_d = zix_digest_add_64(d, &data[i], sizeof(uint64_t));
+ assert(new_d != d);
+ d = new_d;
+ }
- assert(zix_digest_add(zix_digest_start(), data, 8 * sizeof(uint64_t)) == d);
+ assert(zix_digest_add(zix_digest_start(), data, 8 * sizeof(uint64_t)) == d);
}
static void
test_ptr(void)
{
- static const uint64_t pointees[] = {1, 2, 3, 4, 5, 6, 7, 8};
-
- static const void* data[] = {&pointees[0],
- &pointees[1],
- &pointees[2],
- &pointees[3],
- &pointees[4],
- &pointees[5],
- &pointees[6],
- &pointees[7],
- &pointees[8]};
-
- uint32_t d = zix_digest_start();
- for (size_t i = 0; i < 8; ++i) {
- const uint32_t new_d = zix_digest_add_ptr(d, data[i]);
- assert(new_d != d);
- d = new_d;
- }
-
- assert(zix_digest_add(zix_digest_start(), data, 8 * sizeof(void*)) == d);
+ static const uint64_t pointees[] = {1, 2, 3, 4, 5, 6, 7, 8};
+
+ static const void* data[] = {&pointees[0],
+ &pointees[1],
+ &pointees[2],
+ &pointees[3],
+ &pointees[4],
+ &pointees[5],
+ &pointees[6],
+ &pointees[7],
+ &pointees[8]};
+
+ uint32_t d = zix_digest_start();
+ for (size_t i = 0; i < 8; ++i) {
+ const uint32_t new_d = zix_digest_add_ptr(d, data[i]);
+ assert(new_d != d);
+ d = new_d;
+ }
+
+ assert(zix_digest_add(zix_digest_start(), data, 8 * sizeof(void*)) == d);
}
ZIX_PURE_FUNC int
main(void)
{
- test_bytes();
- test_64();
- test_ptr();
+ test_bytes();
+ test_64();
+ test_ptr();
- return 0;
+ return 0;
}
diff --git a/test/hash_test.c b/test/hash_test.c
index bfddc49..b55820c 100644
--- a/test/hash_test.c
+++ b/test/hash_test.c
@@ -29,34 +29,34 @@
static bool expect_failure = false;
static const char* strings[] = {
- "one", "two", "three", "four", "five", "six", "seven", "eight",
- "2one", "2two", "2three", "2four", "2five", "2six", "2seven", "2eight",
- "3one", "3two", "3three", "3four", "3five", "3six", "3seven", "3eight",
- "4one", "4two", "4three", "4four", "4five", "4six", "4seven", "4eight",
- "5one", "5two", "5three", "5four", "5five", "5six", "5seven", "5eight",
- "6one", "6two", "6three", "6four", "6five", "6six", "6seven", "6eight",
- "7one", "7two", "7three", "7four", "7five", "7six", "7seven", "7eight",
- "8one", "8two", "8three", "8four", "8five", "8six", "8seven", "8eight",
- "9one", "9two", "9three", "9four", "9five", "9six", "9seven", "9eight",
- "Aone", "Atwo", "Athree", "Afour", "Afive", "Asix", "Aseven", "Aeight",
- "Bone", "Btwo", "Bthree", "Bfour", "Bfive", "Bsix", "Bseven", "Beight",
- "Cone", "Ctwo", "Cthree", "Cfour", "Cfive", "Csix", "Cseven", "Ceight",
- "Done", "Dtwo", "Dthree", "Dfour", "Dfive", "Dsix", "Dseven", "Deight",
+ "one", "two", "three", "four", "five", "six", "seven", "eight",
+ "2one", "2two", "2three", "2four", "2five", "2six", "2seven", "2eight",
+ "3one", "3two", "3three", "3four", "3five", "3six", "3seven", "3eight",
+ "4one", "4two", "4three", "4four", "4five", "4six", "4seven", "4eight",
+ "5one", "5two", "5three", "5four", "5five", "5six", "5seven", "5eight",
+ "6one", "6two", "6three", "6four", "6five", "6six", "6seven", "6eight",
+ "7one", "7two", "7three", "7four", "7five", "7six", "7seven", "7eight",
+ "8one", "8two", "8three", "8four", "8five", "8six", "8seven", "8eight",
+ "9one", "9two", "9three", "9four", "9five", "9six", "9seven", "9eight",
+ "Aone", "Atwo", "Athree", "Afour", "Afive", "Asix", "Aseven", "Aeight",
+ "Bone", "Btwo", "Bthree", "Bfour", "Bfive", "Bsix", "Bseven", "Beight",
+ "Cone", "Ctwo", "Cthree", "Cfour", "Cfive", "Csix", "Cseven", "Ceight",
+ "Done", "Dtwo", "Dthree", "Dfour", "Dfive", "Dsix", "Dseven", "Deight",
};
ZIX_LOG_FUNC(1, 2)
static int
test_fail(const char* fmt, ...)
{
- if (expect_failure) {
- return 0;
- }
- va_list args;
- va_start(args, fmt);
- fprintf(stderr, "error: ");
- vfprintf(stderr, fmt, args);
- va_end(args);
- return 1;
+ if (expect_failure) {
+ return 0;
+ }
+ va_list args;
+ va_start(args, fmt);
+ fprintf(stderr, "error: ");
+ vfprintf(stderr, fmt, args);
+ va_end(args);
+ return 1;
}
static unsigned n_checked = 0;
@@ -64,163 +64,161 @@ static unsigned n_checked = 0;
static void
check(void* value, void* ZIX_UNUSED(user_data))
{
- if (strlen(*(const char*const*)value) >= 3) {
- ++n_checked;
- } else {
- fprintf(stderr, "ERROR: %s\n", (const char*)value);
- }
+ if (strlen(*(const char* const*)value) >= 3) {
+ ++n_checked;
+ } else {
+ fprintf(stderr, "ERROR: %s\n", (const char*)value);
+ }
}
static uint32_t
string_ptr_hash(const void* value)
{
- const char* const str = *(const char* const*)value;
+ const char* const str = *(const char* const*)value;
- return zix_digest_add(zix_digest_start(), str, strlen(str));
+ return zix_digest_add(zix_digest_start(), str, strlen(str));
}
static bool
string_ptr_equal(const void* a, const void* b)
{
- return !strcmp(*(const char*const*)a, *(const char*const*)b);
+ return !strcmp(*(const char* const*)a, *(const char* const*)b);
}
static int
stress(void)
{
- ZixHash* hash = zix_hash_new(
- string_ptr_hash, string_ptr_equal, sizeof(const char*));
- if (!hash) {
- return test_fail("Failed to allocate hash\n");
- }
-
- const size_t n_strings = sizeof(strings) / sizeof(const char*);
-
- // Insert each string
- for (size_t i = 0; i < n_strings; ++i) {
- void* inserted = NULL;
- ZixStatus st = zix_hash_insert(hash, &strings[i], &inserted);
- if (st) {
- return test_fail("Failed to insert `%s'\n", strings[i]);
- }
-
- if (*(const void*const*)inserted != strings[i]) {
- return test_fail("Corrupt insertion %s != %s\n",
- strings[i], *(const char*const*)inserted);
- }
- }
-
- // Ensure hash size is correct
- if (zix_hash_size(hash) != n_strings) {
- return test_fail("Hash size %zu != %zu\n",
- zix_hash_size(hash), n_strings);
- }
-
- //zix_hash_print_dot(hash, stdout);
-
- // Attempt to insert each string again
- for (size_t i = 0; i < n_strings; ++i) {
- void* inserted = NULL;
- ZixStatus st = zix_hash_insert(hash, &strings[i], &inserted);
- if (st != ZIX_STATUS_EXISTS) {
- return test_fail("Double inserted `%s'\n", strings[i]);
- }
- }
-
- // Search for each string
- for (size_t i = 0; i < n_strings; ++i) {
- const char*const* match = (const char*const*)zix_hash_find(
- hash, &strings[i]);
- if (!match) {
- return test_fail("Failed to find `%s'\n", strings[i]);
- }
- if (*match != strings[i]) {
- return test_fail("Bad match for `%s': `%s'\n", strings[i], *match);
- }
- }
-
- // Try some false matches
- const char* not_indexed[] = {
- "ftp://example.org/not-there-at-all",
- "http://example.org/foobar",
- "http://",
- "http://otherdomain.com"
- };
- const size_t n_not_indexed = sizeof(not_indexed) / sizeof(char*);
- for (size_t i = 0; i < n_not_indexed; ++i) {
- const char*const* match = (const char*const*)zix_hash_find(
- hash, &not_indexed[i]);
- if (match) {
- return test_fail("Unexpectedly found `%s'\n", not_indexed[i]);
- }
- }
-
- // Remove strings
- for (size_t i = 0; i < n_strings; ++i) {
- // Remove string
- ZixStatus st = zix_hash_remove(hash, &strings[i]);
- if (st) {
- return test_fail("Failed to remove `%s'\n", strings[i]);
- }
-
- // Ensure second removal fails
- st = zix_hash_remove(hash, &strings[i]);
- if (st != ZIX_STATUS_NOT_FOUND) {
- return test_fail("Unexpectedly removed `%s' twice\n", strings[i]);
- }
-
- // Check to ensure remaining strings are still present
- for (size_t j = i + 1; j < n_strings; ++j) {
- const char*const* match = (const char*const*)zix_hash_find(
- hash, &strings[j]);
- if (!match) {
- return test_fail("Failed to find `%s' after remove\n", strings[j]);
- }
- if (*match != strings[j]) {
- return test_fail("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_strings; ++i) {
- ZixStatus st = zix_hash_insert(hash, &strings[i], NULL);
- if (st) {
- return test_fail("Failed to insert `%s'\n", strings[i]);
- }
- }
-
- // Check key == value (and test zix_hash_foreach)
- zix_hash_foreach(hash, check, NULL);
- if (n_checked != n_strings) {
- return test_fail("Check failed\n");
- }
-
- zix_hash_free(hash);
-
- return 0;
+ ZixHash* hash =
+ zix_hash_new(string_ptr_hash, string_ptr_equal, sizeof(const char*));
+ if (!hash) {
+ return test_fail("Failed to allocate hash\n");
+ }
+
+ const size_t n_strings = sizeof(strings) / sizeof(const char*);
+
+ // Insert each string
+ for (size_t i = 0; i < n_strings; ++i) {
+ void* inserted = NULL;
+ ZixStatus st = zix_hash_insert(hash, &strings[i], &inserted);
+ if (st) {
+ return test_fail("Failed to insert `%s'\n", strings[i]);
+ }
+
+ if (*(const void* const*)inserted != strings[i]) {
+ return test_fail("Corrupt insertion %s != %s\n",
+ strings[i],
+ *(const char* const*)inserted);
+ }
+ }
+
+ // Ensure hash size is correct
+ if (zix_hash_size(hash) != n_strings) {
+ return test_fail("Hash size %zu != %zu\n", zix_hash_size(hash), n_strings);
+ }
+
+ // zix_hash_print_dot(hash, stdout);
+
+ // Attempt to insert each string again
+ for (size_t i = 0; i < n_strings; ++i) {
+ void* inserted = NULL;
+ ZixStatus st = zix_hash_insert(hash, &strings[i], &inserted);
+ if (st != ZIX_STATUS_EXISTS) {
+ return test_fail("Double inserted `%s'\n", strings[i]);
+ }
+ }
+
+ // Search for each string
+ for (size_t i = 0; i < n_strings; ++i) {
+ const char* const* match =
+ (const char* const*)zix_hash_find(hash, &strings[i]);
+ if (!match) {
+ return test_fail("Failed to find `%s'\n", strings[i]);
+ }
+ if (*match != strings[i]) {
+ return test_fail("Bad match for `%s': `%s'\n", strings[i], *match);
+ }
+ }
+
+ // Try some false matches
+ const char* not_indexed[] = {"ftp://example.org/not-there-at-all",
+ "http://example.org/foobar",
+ "http://",
+ "http://otherdomain.com"};
+ const size_t n_not_indexed = sizeof(not_indexed) / sizeof(char*);
+ for (size_t i = 0; i < n_not_indexed; ++i) {
+ const char* const* match =
+ (const char* const*)zix_hash_find(hash, &not_indexed[i]);
+ if (match) {
+ return test_fail("Unexpectedly found `%s'\n", not_indexed[i]);
+ }
+ }
+
+ // Remove strings
+ for (size_t i = 0; i < n_strings; ++i) {
+ // Remove string
+ ZixStatus st = zix_hash_remove(hash, &strings[i]);
+ if (st) {
+ return test_fail("Failed to remove `%s'\n", strings[i]);
+ }
+
+ // Ensure second removal fails
+ st = zix_hash_remove(hash, &strings[i]);
+ if (st != ZIX_STATUS_NOT_FOUND) {
+ return test_fail("Unexpectedly removed `%s' twice\n", strings[i]);
+ }
+
+ // Check to ensure remaining strings are still present
+ for (size_t j = i + 1; j < n_strings; ++j) {
+ const char* const* match =
+ (const char* const*)zix_hash_find(hash, &strings[j]);
+ if (!match) {
+ return test_fail("Failed to find `%s' after remove\n", strings[j]);
+ }
+ if (*match != strings[j]) {
+ return test_fail("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_strings; ++i) {
+ ZixStatus st = zix_hash_insert(hash, &strings[i], NULL);
+ if (st) {
+ return test_fail("Failed to insert `%s'\n", strings[i]);
+ }
+ }
+
+ // Check key == value (and test zix_hash_foreach)
+ zix_hash_foreach(hash, check, NULL);
+ if (n_checked != n_strings) {
+ return test_fail("Check failed\n");
+ }
+
+ zix_hash_free(hash);
+
+ return 0;
}
int
main(void)
{
- zix_hash_free(NULL);
+ zix_hash_free(NULL);
- if (stress()) {
- return 1;
- }
+ if (stress()) {
+ return 1;
+ }
#ifdef ZIX_WITH_TEST_MALLOC
- const size_t total_n_allocs = test_malloc_get_n_allocs();
- printf("Testing 0 ... %zu failed allocations\n", total_n_allocs);
- expect_failure = true;
- for (size_t i = 0; i < total_n_allocs; ++i) {
- test_malloc_reset(i);
- stress();
- }
-
- test_malloc_reset((size_t)-1);
+ const size_t total_n_allocs = test_malloc_get_n_allocs();
+ printf("Testing 0 ... %zu failed allocations\n", total_n_allocs);
+ expect_failure = true;
+ for (size_t i = 0; i < total_n_allocs; ++i) {
+ test_malloc_reset(i);
+ stress();
+ }
+
+ test_malloc_reset((size_t)-1);
#endif
- return 0;
+ return 0;
}
diff --git a/test/inline_test.c b/test/inline_test.c
index 75c43d0..b07f28a 100644
--- a/test/inline_test.c
+++ b/test/inline_test.c
@@ -25,7 +25,7 @@
ZIX_CONST_FUNC int
main(void)
{
- zix_hash_free(NULL);
- zix_tree_free(NULL);
- return 0;
+ zix_hash_free(NULL);
+ zix_tree_free(NULL);
+ return 0;
}
diff --git a/test/ring_test.c b/test/ring_test.c
index 092606b..915d099 100644
--- a/test/ring_test.c
+++ b/test/ring_test.c
@@ -35,200 +35,202 @@ ZIX_LOG_FUNC(1, 2)
static int
failure(const char* fmt, ...)
{
- va_list args;
- va_start(args, fmt);
- fprintf(stderr, "error: ");
- vfprintf(stderr, fmt, args);
- va_end(args);
- return 1;
+ va_list args;
+ va_start(args, fmt);
+ fprintf(stderr, "error: ");
+ vfprintf(stderr, fmt, args);
+ va_end(args);
+ return 1;
}
static int
gen_msg(int* msg, int start)
{
- for (int i = 0; i < MSG_SIZE; ++i) {
- msg[i] = start;
- start = (start + 1) % INT_MAX;
- }
- return start;
+ for (int i = 0; i < MSG_SIZE; ++i) {
+ msg[i] = start;
+ start = (start + 1) % INT_MAX;
+ }
+ return start;
}
static int
cmp_msg(int* msg1, int* msg2)
{
- for (int i = 0; i < MSG_SIZE; ++i) {
- if (msg1[i] != msg2[i]) {
- return !failure("%d != %d @ %d\n", msg1[i], msg2[i], i);
- }
- }
+ for (int i = 0; i < MSG_SIZE; ++i) {
+ if (msg1[i] != msg2[i]) {
+ return !failure("%d != %d @ %d\n", msg1[i], msg2[i], i);
+ }
+ }
- return 1;
+ 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))) {
- if (!cmp_msg(ref_msg, read_msg)) {
- printf("FAIL: Message %u is corrupt\n", count);
- read_error = true;
- return NULL;
- }
- start = gen_msg(ref_msg, start);
- ++count;
- }
- }
- }
-
- printf("Reader finished\n");
- return NULL;
+ 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))) {
+ if (!cmp_msg(ref_msg, read_msg)) {
+ printf("FAIL: Message %u is corrupt\n", count);
+ read_error = true;
+ return NULL;
+ }
+ 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;
+ 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;
}
int
main(int argc, char** argv)
{
- if (argc > 1 && argv[1][0] == '-') {
- printf("Usage: %s SIZE N_WRITES\n", argv[0]);
- return 1;
- }
-
- unsigned size = 1024;
- if (argc > 1) {
- size = (unsigned)atoi(argv[1]);
- }
-
- n_writes = size * 1024;
- if (argc > 2) {
- n_writes = (unsigned)atoi(argv[2]);
- }
-
- printf("Testing %u writes of %d ints to a %u int ring...\n",
- n_writes, MSG_SIZE, size);
-
- ring = zix_ring_new(size);
- if (zix_ring_read_space(ring) != 0) {
- return failure("New ring is not empty\n");
- }
- if (zix_ring_write_space(ring) != zix_ring_capacity(ring)) {
- return failure("New ring write space != capacity\n");
- }
-
- zix_ring_mlock(ring);
-
- ZixThread reader_thread;
- if (zix_thread_create(&reader_thread, MSG_SIZE * 4, reader, NULL)) {
- return failure("Failed to create reader thread\n");
- }
-
- ZixThread writer_thread;
- if (zix_thread_create(&writer_thread, MSG_SIZE * 4, writer, NULL)) {
- return failure("Failed to create writer thread\n");
- }
-
- zix_thread_join(reader_thread, NULL);
- zix_thread_join(writer_thread, NULL);
-
- if (read_error) {
- return failure("Read error\n");
- }
-
- zix_ring_reset(ring);
- if (zix_ring_read_space(ring) > 0) {
- return failure("Reset did not empty ring.\n");
- }
- if (zix_ring_write_space(ring) != zix_ring_capacity(ring)) {
- return failure("Empty write space != capacity\n");
- }
-
- zix_ring_write(ring, "a", 1);
- zix_ring_write(ring, "b", 1);
-
- char buf;
- uint32_t n = zix_ring_peek(ring, &buf, 1);
- if (n != 1) {
- return failure("Peek n (%u) != 1\n", n);
- }
- if (buf != 'a') {
- return failure("Peek error: '%c' != 'a'\n", buf);
- }
-
- n = zix_ring_skip(ring, 1);
- if (n != 1) {
- return failure("Skip n (%u) != 1\n", n);
- }
-
- if (zix_ring_read_space(ring) != 1) {
- return failure("Read space %u != 1\n", zix_ring_read_space(ring));
- }
-
- n = zix_ring_read(ring, &buf, 1);
- if (n != 1) {
- return failure("Peek n (%u) != 1\n", n);
- }
- if (buf != 'b') {
- return failure("Peek error: '%c' != 'b'\n", buf);
- }
-
- if (zix_ring_read_space(ring) != 0) {
- return failure("Read space %u != 0\n", zix_ring_read_space(ring));
- }
-
- n = zix_ring_peek(ring, &buf, 1);
- if (n > 0) {
- return failure("Successful underrun peak\n");
- }
-
- n = zix_ring_read(ring, &buf, 1);
- if (n > 0) {
- return failure("Successful underrun read\n");
- }
-
- n = zix_ring_skip(ring, 1);
- if (n > 0) {
- return failure("Successful underrun read\n");
- }
-
- char* big_buf = (char*)calloc(size, 1);
- n = zix_ring_write(ring, big_buf, size - 1);
- if (n != (uint32_t)size - 1) {
- free(big_buf);
- return failure("Maximum size write failed (wrote %u)\n", n);
- }
-
- n = zix_ring_write(ring, big_buf, size);
- if (n != 0) {
- free(big_buf);
- return failure("Successful overrun write (size %u)\n", n);
- }
-
- free(big_buf);
- zix_ring_free(ring);
- return 0;
+ if (argc > 1 && argv[1][0] == '-') {
+ printf("Usage: %s SIZE N_WRITES\n", argv[0]);
+ return 1;
+ }
+
+ unsigned size = 1024;
+ if (argc > 1) {
+ size = (unsigned)atoi(argv[1]);
+ }
+
+ n_writes = size * 1024;
+ if (argc > 2) {
+ n_writes = (unsigned)atoi(argv[2]);
+ }
+
+ printf("Testing %u writes of %d ints to a %u int ring...\n",
+ n_writes,
+ MSG_SIZE,
+ size);
+
+ ring = zix_ring_new(size);
+ if (zix_ring_read_space(ring) != 0) {
+ return failure("New ring is not empty\n");
+ }
+ if (zix_ring_write_space(ring) != zix_ring_capacity(ring)) {
+ return failure("New ring write space != capacity\n");
+ }
+
+ zix_ring_mlock(ring);
+
+ ZixThread reader_thread;
+ if (zix_thread_create(&reader_thread, MSG_SIZE * 4, reader, NULL)) {
+ return failure("Failed to create reader thread\n");
+ }
+
+ ZixThread writer_thread;
+ if (zix_thread_create(&writer_thread, MSG_SIZE * 4, writer, NULL)) {
+ return failure("Failed to create writer thread\n");
+ }
+
+ zix_thread_join(reader_thread, NULL);
+ zix_thread_join(writer_thread, NULL);
+
+ if (read_error) {
+ return failure("Read error\n");
+ }
+
+ zix_ring_reset(ring);
+ if (zix_ring_read_space(ring) > 0) {
+ return failure("Reset did not empty ring.\n");
+ }
+ if (zix_ring_write_space(ring) != zix_ring_capacity(ring)) {
+ return failure("Empty write space != capacity\n");
+ }
+
+ zix_ring_write(ring, "a", 1);
+ zix_ring_write(ring, "b", 1);
+
+ char buf;
+ uint32_t n = zix_ring_peek(ring, &buf, 1);
+ if (n != 1) {
+ return failure("Peek n (%u) != 1\n", n);
+ }
+ if (buf != 'a') {
+ return failure("Peek error: '%c' != 'a'\n", buf);
+ }
+
+ n = zix_ring_skip(ring, 1);
+ if (n != 1) {
+ return failure("Skip n (%u) != 1\n", n);
+ }
+
+ if (zix_ring_read_space(ring) != 1) {
+ return failure("Read space %u != 1\n", zix_ring_read_space(ring));
+ }
+
+ n = zix_ring_read(ring, &buf, 1);
+ if (n != 1) {
+ return failure("Peek n (%u) != 1\n", n);
+ }
+ if (buf != 'b') {
+ return failure("Peek error: '%c' != 'b'\n", buf);
+ }
+
+ if (zix_ring_read_space(ring) != 0) {
+ return failure("Read space %u != 0\n", zix_ring_read_space(ring));
+ }
+
+ n = zix_ring_peek(ring, &buf, 1);
+ if (n > 0) {
+ return failure("Successful underrun peak\n");
+ }
+
+ n = zix_ring_read(ring, &buf, 1);
+ if (n > 0) {
+ return failure("Successful underrun read\n");
+ }
+
+ n = zix_ring_skip(ring, 1);
+ if (n > 0) {
+ return failure("Successful underrun read\n");
+ }
+
+ char* big_buf = (char*)calloc(size, 1);
+ n = zix_ring_write(ring, big_buf, size - 1);
+ if (n != (uint32_t)size - 1) {
+ free(big_buf);
+ return failure("Maximum size write failed (wrote %u)\n", n);
+ }
+
+ n = zix_ring_write(ring, big_buf, size);
+ if (n != 0) {
+ free(big_buf);
+ return failure("Successful overrun write (size %u)\n", n);
+ }
+
+ free(big_buf);
+ zix_ring_free(ring);
+ return 0;
}
diff --git a/test/sem_test.c b/test/sem_test.c
index 7ff9b08..5db7c08 100644
--- a/test/sem_test.c
+++ b/test/sem_test.c
@@ -26,63 +26,63 @@ static unsigned n_signals = 1024;
static void*
reader(void* ZIX_UNUSED(arg))
{
- printf("Reader starting\n");
+ printf("Reader starting\n");
- for (unsigned i = 0; i < n_signals; ++i) {
- zix_sem_wait(&sem);
- }
+ for (unsigned i = 0; i < n_signals; ++i) {
+ zix_sem_wait(&sem);
+ }
- printf("Reader finished\n");
- return NULL;
+ printf("Reader finished\n");
+ return NULL;
}
static void*
writer(void* ZIX_UNUSED(arg))
{
- printf("Writer starting\n");
+ printf("Writer starting\n");
- for (unsigned i = 0; i < n_signals; ++i) {
- zix_sem_post(&sem);
- }
+ for (unsigned i = 0; i < n_signals; ++i) {
+ zix_sem_post(&sem);
+ }
- printf("Writer finished\n");
- return NULL;
+ 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)atoi(argv[1]);
- }
-
- printf("Testing %u signals...\n", n_signals);
-
- if (zix_sem_init(&sem, 0)) {
- fprintf(stderr, "Failed to create semaphore.\n");
- return 1;
- }
-
- ZixThread reader_thread;
- if (zix_thread_create(&reader_thread, 128, reader, NULL)) {
- fprintf(stderr, "Failed to create reader thread\n");
- return 1;
- }
-
- ZixThread writer_thread;
- if (zix_thread_create(&writer_thread, 128, writer, NULL)) {
- fprintf(stderr, "Failed to create writer thread\n");
- return 1;
- }
-
- zix_thread_join(reader_thread, NULL);
- zix_thread_join(writer_thread, NULL);
-
- zix_sem_destroy(&sem);
- return 0;
+ if (argc > 2) {
+ printf("Usage: %s N_SIGNALS\n", argv[0]);
+ return 1;
+ }
+
+ if (argc > 1) {
+ n_signals = (unsigned)atoi(argv[1]);
+ }
+
+ printf("Testing %u signals...\n", n_signals);
+
+ if (zix_sem_init(&sem, 0)) {
+ fprintf(stderr, "Failed to create semaphore.\n");
+ return 1;
+ }
+
+ ZixThread reader_thread;
+ if (zix_thread_create(&reader_thread, 128, reader, NULL)) {
+ fprintf(stderr, "Failed to create reader thread\n");
+ return 1;
+ }
+
+ ZixThread writer_thread;
+ if (zix_thread_create(&writer_thread, 128, writer, NULL)) {
+ fprintf(stderr, "Failed to create writer thread\n");
+ return 1;
+ }
+
+ zix_thread_join(reader_thread, NULL);
+ zix_thread_join(writer_thread, NULL);
+
+ zix_sem_destroy(&sem);
+ return 0;
}
diff --git a/test/sorted_array_test.c b/test/sorted_array_test.c
index db7c1d0..d991784 100644
--- a/test/sorted_array_test.c
+++ b/test/sorted_array_test.c
@@ -29,149 +29,155 @@ static unsigned seed = 1;
static int
int_cmp(const void* a, const void* b, const void* ZIX_UNUSED(user_data))
{
- const intptr_t ia = *(const intptr_t*)a;
- const intptr_t ib = *(const intptr_t*)b;
+ const intptr_t ia = *(const intptr_t*)a;
+ const intptr_t ib = *(const intptr_t*)b;
- return ia < ib ? -1 : ia > ib ? 1 : 0;
+ return ia < ib ? -1 : ia > ib ? 1 : 0;
}
static intptr_t
ith_elem(unsigned test_num, unsigned n_elems, unsigned 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 rand() % 100; // Random
- }
+ switch (test_num % 3) {
+ case 0:
+ return i; // Increasing (worst case)
+ case 1:
+ return n_elems - i; // Decreasing (worse case)
+ case 2:
+ default:
+ return rand() % 100; // Random
+ }
}
static int
test_fail(void)
{
- return EXIT_FAILURE;
+ return EXIT_FAILURE;
}
static int
stress(unsigned test_num, unsigned n_elems)
{
- intptr_t r;
- ZixSortedArrayIter ti;
-
- ZixSortedArray* t = zix_sorted_array_new(true, int_cmp, NULL, sizeof(intptr_t));
-
- srand(seed);
-
- // Insert n_elems elements
- for (unsigned i = 0; i < n_elems; ++i) {
- r = ith_elem(test_num, n_elems, i);
- int status = zix_sorted_array_insert(t, &r, &ti);
- if (status) {
- fprintf(stderr, "Insert failed\n");
- return test_fail();
- }
- if (*(intptr_t*)zix_sorted_array_get_data(ti) != r) {
- fprintf(stderr, "Data corrupt (%" PRIdPTR " != %" PRIdPTR ")\n",
- *(intptr_t*)zix_sorted_array_get_data(ti), r);
- return test_fail();
- }
- }
-
- srand(seed);
-
- // Search for all elements
- for (unsigned i = 0; i < n_elems; ++i) {
- r = ith_elem(test_num, n_elems, i);
- if (zix_sorted_array_find(t, &r, &ti)) {
- fprintf(stderr, "Find failed\n");
- return test_fail();
- }
- if (*(intptr_t*)zix_sorted_array_get_data(ti) != r) {
- fprintf(stderr, "Data corrupt (%" PRIdPTR " != %" PRIdPTR ")\n",
- *(intptr_t*)zix_sorted_array_get_data(ti), r);
- return test_fail();
- }
- }
-
- srand(seed);
-
- // Iterate over all elements
- unsigned i = 0;
- intptr_t last = -1;
- for (ZixSortedArrayIter iter = zix_sorted_array_begin(t);
- !zix_sorted_array_iter_is_end(t, iter);
- iter = zix_sorted_array_iter_next(t, iter), ++i) {
- r = ith_elem(test_num, n_elems, i);
- const intptr_t iter_data = *(intptr_t*)zix_sorted_array_get_data(iter);
- if (iter_data < last) {
- fprintf(stderr, "Iter corrupt (%" PRIdPTR " < %" PRIdPTR ")\n",
- iter_data, last);
- return test_fail();
- }
- last = iter_data;
- }
-
- srand(seed);
-
- // Delete all elements
- for (unsigned e = 0; e < n_elems; e++) {
- r = ith_elem(test_num, n_elems, e);
- ZixSortedArrayIter item;
- if (zix_sorted_array_find(t, &r, &item) != ZIX_STATUS_SUCCESS) {
- fprintf(stderr, "Failed to find item to remove\n");
- return test_fail();
- }
- if (zix_sorted_array_remove(t, item)) {
- fprintf(stderr, "Error removing item\n");
- }
- }
-
- if (zix_sorted_array_size(t) != 0) {
- fprintf(stderr, "Array is not empty after removing all items\n");
- return test_fail();
- }
-
- zix_sorted_array_free(t);
-
- return EXIT_SUCCESS;
+ intptr_t r;
+ ZixSortedArrayIter ti;
+
+ ZixSortedArray* t =
+ zix_sorted_array_new(true, int_cmp, NULL, sizeof(intptr_t));
+
+ srand(seed);
+
+ // Insert n_elems elements
+ for (unsigned i = 0; i < n_elems; ++i) {
+ r = ith_elem(test_num, n_elems, i);
+ int status = zix_sorted_array_insert(t, &r, &ti);
+ if (status) {
+ fprintf(stderr, "Insert failed\n");
+ return test_fail();
+ }
+ if (*(intptr_t*)zix_sorted_array_get_data(ti) != r) {
+ fprintf(stderr,
+ "Data corrupt (%" PRIdPTR " != %" PRIdPTR ")\n",
+ *(intptr_t*)zix_sorted_array_get_data(ti),
+ r);
+ return test_fail();
+ }
+ }
+
+ srand(seed);
+
+ // Search for all elements
+ for (unsigned i = 0; i < n_elems; ++i) {
+ r = ith_elem(test_num, n_elems, i);
+ if (zix_sorted_array_find(t, &r, &ti)) {
+ fprintf(stderr, "Find failed\n");
+ return test_fail();
+ }
+ if (*(intptr_t*)zix_sorted_array_get_data(ti) != r) {
+ fprintf(stderr,
+ "Data corrupt (%" PRIdPTR " != %" PRIdPTR ")\n",
+ *(intptr_t*)zix_sorted_array_get_data(ti),
+ r);
+ return test_fail();
+ }
+ }
+
+ srand(seed);
+
+ // Iterate over all elements
+ unsigned i = 0;
+ intptr_t last = -1;
+ for (ZixSortedArrayIter iter = zix_sorted_array_begin(t);
+ !zix_sorted_array_iter_is_end(t, iter);
+ iter = zix_sorted_array_iter_next(t, iter), ++i) {
+ r = ith_elem(test_num, n_elems, i);
+ const intptr_t iter_data = *(intptr_t*)zix_sorted_array_get_data(iter);
+ if (iter_data < last) {
+ fprintf(stderr,
+ "Iter corrupt (%" PRIdPTR " < %" PRIdPTR ")\n",
+ iter_data,
+ last);
+ return test_fail();
+ }
+ last = iter_data;
+ }
+
+ srand(seed);
+
+ // Delete all elements
+ for (unsigned e = 0; e < n_elems; e++) {
+ r = ith_elem(test_num, n_elems, e);
+ ZixSortedArrayIter item;
+ if (zix_sorted_array_find(t, &r, &item) != ZIX_STATUS_SUCCESS) {
+ fprintf(stderr, "Failed to find item to remove\n");
+ return test_fail();
+ }
+ if (zix_sorted_array_remove(t, item)) {
+ fprintf(stderr, "Error removing item\n");
+ }
+ }
+
+ if (zix_sorted_array_size(t) != 0) {
+ fprintf(stderr, "Array is not empty after removing all items\n");
+ return test_fail();
+ }
+
+ zix_sorted_array_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 = 4096;
- } else {
- n_elems = (unsigned)atol(argv[1]);
- if (argc > 2) {
- seed = (unsigned)atol(argv[2]);
- } 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;
+ const unsigned n_tests = 3;
+ unsigned n_elems = 0;
+
+ if (argc == 1) {
+ n_elems = 4096;
+ } else {
+ n_elems = (unsigned)atol(argv[1]);
+ if (argc > 2) {
+ seed = (unsigned)atol(argv[2]);
+ } 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/strindex_test.c b/test/strindex_test.c
index 1dcd062..d19d77e 100644
--- a/test/strindex_test.c
+++ b/test/strindex_test.c
@@ -25,37 +25,35 @@ ZIX_LOG_FUNC(1, 2)
static int
test_fail(const char* fmt, ...)
{
- va_list args;
- va_start(args, fmt);
- fprintf(stderr, "error: ");
- vfprintf(stderr, fmt, args);
- va_end(args);
- return 1;
+ va_list args;
+ va_start(args, fmt);
+ fprintf(stderr, "error: ");
+ vfprintf(stderr, fmt, args);
+ va_end(args);
+ return 1;
}
int
main(void)
{
- const char* str = "BANANA";
- const size_t str_len = strlen(str);
- ZixStrindex* strindex = zix_strindex_new(str);
-
- for (size_t l = 1; l <= str_len; ++l) {
- for (size_t i = 0; i < str_len - l; ++i) {
- char* match = NULL;
- ZixStatus ret = zix_strindex_find(strindex, str + i, &match);
- if (ret) {
- return test_fail("No match for substring at %zu length %zu\n",
- i, l);
- }
-
- if (strncmp(str + i, match, l)) {
- return test_fail("Bad match for substring at %zu length %zu\n",
- i, l);
- }
- }
- }
-
- zix_strindex_free(strindex);
- return 0;
+ const char* str = "BANANA";
+ const size_t str_len = strlen(str);
+ ZixStrindex* strindex = zix_strindex_new(str);
+
+ for (size_t l = 1; l <= str_len; ++l) {
+ for (size_t i = 0; i < str_len - l; ++i) {
+ char* match = NULL;
+ ZixStatus ret = zix_strindex_find(strindex, str + i, &match);
+ if (ret) {
+ return test_fail("No match for substring at %zu length %zu\n", i, l);
+ }
+
+ if (strncmp(str + i, match, l)) {
+ return test_fail("Bad match for substring at %zu length %zu\n", i, l);
+ }
+ }
+ }
+
+ zix_strindex_free(strindex);
+ return 0;
}
diff --git a/test/test_malloc.c b/test/test_malloc.c
index 1138502..971d583 100644
--- a/test/test_malloc.c
+++ b/test/test_malloc.c
@@ -15,7 +15,7 @@
*/
#ifndef __APPLE__
-#define _GNU_SOURCE
+# define _GNU_SOURCE
#endif
#include "test_malloc.h"
@@ -34,64 +34,64 @@ static volatile bool in_test_malloc_init = false;
static void*
test_malloc(size_t size)
{
- if (in_test_malloc_init) {
- return NULL; // dlsym is asking for memory, but handles this fine
- }
+ if (in_test_malloc_init) {
+ return NULL; // dlsym is asking for memory, but handles this fine
+ }
- if (!test_malloc_sys_malloc) {
- test_malloc_init();
- }
+ if (!test_malloc_sys_malloc) {
+ test_malloc_init();
+ }
- if (test_malloc_n_allocs < test_malloc_fail_after) {
- ++test_malloc_n_allocs;
- return test_malloc_sys_malloc(size);
- }
+ if (test_malloc_n_allocs < test_malloc_fail_after) {
+ ++test_malloc_n_allocs;
+ return test_malloc_sys_malloc(size);
+ }
- return NULL;
+ return NULL;
}
void*
malloc(size_t size)
{
- return test_malloc(size);
+ return test_malloc(size);
}
void*
calloc(size_t nmemb, size_t size)
{
- void* ptr = test_malloc(nmemb * size);
- if (ptr) {
- memset(ptr, 0, nmemb * size);
- }
- return ptr;
+ void* ptr = test_malloc(nmemb * size);
+ if (ptr) {
+ memset(ptr, 0, nmemb * size);
+ }
+ return ptr;
}
void
test_malloc_reset(size_t fail_after)
{
- test_malloc_fail_after = fail_after;
- test_malloc_n_allocs = 0;
+ test_malloc_fail_after = fail_after;
+ test_malloc_n_allocs = 0;
}
void
test_malloc_init(void)
{
- in_test_malloc_init = true;
+ in_test_malloc_init = true;
- /* Avoid pedantic warnings about casting pointer to function pointer by
- casting dlsym instead. */
+ /* Avoid pedantic warnings about casting pointer to function pointer by
+ casting dlsym instead. */
- typedef void* (*MallocFunc)(size_t);
- typedef MallocFunc (*MallocFuncGetter)(void*, const char*);
+ typedef void* (*MallocFunc)(size_t);
+ typedef MallocFunc (*MallocFuncGetter)(void*, const char*);
- MallocFuncGetter dlfunc = (MallocFuncGetter)dlsym;
- test_malloc_sys_malloc = (MallocFunc)dlfunc(RTLD_NEXT, "malloc");
+ MallocFuncGetter dlfunc = (MallocFuncGetter)dlsym;
+ test_malloc_sys_malloc = (MallocFunc)dlfunc(RTLD_NEXT, "malloc");
- in_test_malloc_init = false;
+ in_test_malloc_init = false;
}
size_t
test_malloc_get_n_allocs(void)
{
- return test_malloc_n_allocs;
+ return test_malloc_n_allocs;
}
diff --git a/test/test_malloc.h b/test/test_malloc.h
index be59008..42b22df 100644
--- a/test/test_malloc.h
+++ b/test/test_malloc.h
@@ -18,6 +18,12 @@
#include <stddef.h>
-void test_malloc_init(void);
-void test_malloc_reset(size_t fail_after);
-ZIX_PURE_API size_t test_malloc_get_n_allocs(void);
+void
+test_malloc_init(void);
+
+void
+test_malloc_reset(size_t fail_after);
+
+ZIX_PURE_API
+size_t
+test_malloc_get_n_allocs(void);
diff --git a/test/tree_test.c b/test/tree_test.c
index 52caede..08913e8 100644
--- a/test/tree_test.c
+++ b/test/tree_test.c
@@ -30,199 +30,206 @@ static unsigned seed = 1;
static int
int_cmp(const void* a, const void* b, const void* ZIX_UNUSED(user_data))
{
- const intptr_t ia = (intptr_t)a;
- const intptr_t ib = (intptr_t)b;
+ const intptr_t ia = (intptr_t)a;
+ const intptr_t ib = (intptr_t)b;
- return ia < ib ? -1 : ia > ib ? 1 : 0;
+ 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 rand() % 100; // Random
- }
+ switch (test_num % 3) {
+ case 0:
+ return i; // Increasing (worst case)
+ case 1:
+ return n_elems - i; // Decreasing (worse case)
+ case 2:
+ default:
+ return rand() % 100; // Random
+ }
}
static int
test_fail(void)
{
- return EXIT_FAILURE;
+ return EXIT_FAILURE;
}
static int
stress(unsigned test_num, size_t n_elems)
{
- intptr_t r;
- ZixTreeIter* ti;
-
- ZixTree* t = zix_tree_new(true, int_cmp, NULL, NULL);
-
- srand(seed);
-
- // Insert n_elems elements
- for (size_t i = 0; i < n_elems; ++i) {
- r = ith_elem(test_num, n_elems, i);
- int status = zix_tree_insert(t, (void*)r, &ti);
- if (status) {
- fprintf(stderr, "Insert failed\n");
- return test_fail();
- }
- if ((intptr_t)zix_tree_get(ti) != r) {
- fprintf(stderr, "Data corrupt (%" PRIdPTR" != %" PRIdPTR ")\n",
- (intptr_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 %zu != %zu\n", zix_tree_size(t), n_elems);
- return test_fail();
- }
-
- srand(seed);
-
- // 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 ((intptr_t)zix_tree_get(ti) != r) {
- fprintf(stderr, "Data corrupt (%" PRIdPTR " != %" PRIdPTR ")\n",
- (intptr_t)zix_tree_get(ti), r);
- return test_fail();
- }
- }
-
- srand(seed);
-
- // Iterate over all elements
- size_t i = 0;
- intptr_t last = -1;
- for (ZixTreeIter* iter = zix_tree_begin(t);
- !zix_tree_iter_is_end(iter);
- iter = zix_tree_iter_next(iter), ++i) {
- const intptr_t iter_data = (intptr_t)zix_tree_get(iter);
- if (iter_data < last) {
- fprintf(stderr, "Iter corrupt (%" PRIdPTR " < %" PRIdPTR ")\n",
- iter_data, last);
- return test_fail();
- }
- last = iter_data;
- }
- if (i != n_elems) {
- fprintf(stderr, "Iteration stopped at %zu/%zu elements\n", i, n_elems);
- return test_fail();
- }
-
- srand(seed);
-
- // 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 intptr_t iter_data = (intptr_t)zix_tree_get(iter);
- if (iter_data > last) {
- fprintf(stderr, "Iter corrupt (%" PRIdPTR " < %" PRIdPTR ")\n",
- iter_data, last);
- return test_fail();
- }
- last = iter_data;
- }
-
- srand(seed);
-
- // Delete all elements
- for (size_t e = 0; e < n_elems; e++) {
- r = ith_elem(test_num, n_elems, e);
- ZixTreeIter* item;
- 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 %zu != 0\n", zix_tree_size(t));
- return test_fail();
- }
-
- srand(seed);
-
- // 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);
- int status = zix_tree_insert(t, (void*)r, &ti);
- if (status) {
- fprintf(stderr, "Insert failed\n");
- return test_fail();
- }
- if ((intptr_t)zix_tree_get(ti) != r) {
- fprintf(stderr, "Data corrupt (%" PRIdPTR " != %" PRIdPTR ")\n",
- (intptr_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 %zu != %zu\n", zix_tree_size(t), n_elems);
- return test_fail();
- }
-
- zix_tree_free(t);
-
- return EXIT_SUCCESS;
+ intptr_t r;
+ ZixTreeIter* ti;
+
+ ZixTree* t = zix_tree_new(true, int_cmp, NULL, NULL);
+
+ srand(seed);
+
+ // Insert n_elems elements
+ for (size_t i = 0; i < n_elems; ++i) {
+ r = ith_elem(test_num, n_elems, i);
+ int status = zix_tree_insert(t, (void*)r, &ti);
+ if (status) {
+ fprintf(stderr, "Insert failed\n");
+ return test_fail();
+ }
+ if ((intptr_t)zix_tree_get(ti) != r) {
+ fprintf(stderr,
+ "Data corrupt (%" PRIdPTR " != %" PRIdPTR ")\n",
+ (intptr_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 %zu != %zu\n", zix_tree_size(t), n_elems);
+ return test_fail();
+ }
+
+ srand(seed);
+
+ // 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 ((intptr_t)zix_tree_get(ti) != r) {
+ fprintf(stderr,
+ "Data corrupt (%" PRIdPTR " != %" PRIdPTR ")\n",
+ (intptr_t)zix_tree_get(ti),
+ r);
+ return test_fail();
+ }
+ }
+
+ srand(seed);
+
+ // Iterate over all elements
+ size_t i = 0;
+ intptr_t last = -1;
+ for (ZixTreeIter* iter = zix_tree_begin(t); !zix_tree_iter_is_end(iter);
+ iter = zix_tree_iter_next(iter), ++i) {
+ const intptr_t iter_data = (intptr_t)zix_tree_get(iter);
+ if (iter_data < last) {
+ fprintf(stderr,
+ "Iter corrupt (%" PRIdPTR " < %" PRIdPTR ")\n",
+ iter_data,
+ last);
+ return test_fail();
+ }
+ last = iter_data;
+ }
+ if (i != n_elems) {
+ fprintf(stderr, "Iteration stopped at %zu/%zu elements\n", i, n_elems);
+ return test_fail();
+ }
+
+ srand(seed);
+
+ // 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 intptr_t iter_data = (intptr_t)zix_tree_get(iter);
+ if (iter_data > last) {
+ fprintf(stderr,
+ "Iter corrupt (%" PRIdPTR " < %" PRIdPTR ")\n",
+ iter_data,
+ last);
+ return test_fail();
+ }
+ last = iter_data;
+ }
+
+ srand(seed);
+
+ // Delete all elements
+ for (size_t e = 0; e < n_elems; e++) {
+ r = ith_elem(test_num, n_elems, e);
+ ZixTreeIter* item;
+ 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 %zu != 0\n", zix_tree_size(t));
+ return test_fail();
+ }
+
+ srand(seed);
+
+ // 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);
+ int status = zix_tree_insert(t, (void*)r, &ti);
+ if (status) {
+ fprintf(stderr, "Insert failed\n");
+ return test_fail();
+ }
+ if ((intptr_t)zix_tree_get(ti) != r) {
+ fprintf(stderr,
+ "Data corrupt (%" PRIdPTR " != %" PRIdPTR ")\n",
+ (intptr_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 %zu != %zu\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)atol(argv[1]);
- if (argc > 2) {
- seed = (unsigned)atol(argv[2]);
- } 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;
+ const unsigned n_tests = 3;
+ unsigned n_elems = 0;
+
+ if (argc == 1) {
+ n_elems = 100000;
+ } else {
+ n_elems = (unsigned)atol(argv[1]);
+ if (argc > 2) {
+ seed = (unsigned)atol(argv[2]);
+ } 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;
}
generated by cgit v1.2.1 (git 2.18.0) at 2025-02-09 11:55:55 +0000