From 17ea1744b6b98a2f94d2311b4f25896dcfe01f3f Mon Sep 17 00:00:00 2001 From: David Robillard Date: Thu, 18 Dec 2014 21:52:28 +0000 Subject: Add missing files. git-svn-id: http://svn.drobilla.net/zix/trunk@99 df6676b4-ccc9-40e5-b5d6-7c4628a128e3 --- test/btree_test.c | 408 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 408 insertions(+) create mode 100644 test/btree_test.c (limited to 'test/btree_test.c') diff --git a/test/btree_test.c b/test/btree_test.c new file mode 100644 index 0000000..1936f93 --- /dev/null +++ b/test/btree_test.c @@ -0,0 +1,408 @@ +/* + Copyright 2011-2014 David Robillard + + Permission to use, copy, modify, and/or distribute this software for any + purpose with or without fee is hereby granted, provided that the above + copyright notice and this permission notice appear in all copies. + + THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. +*/ + +#include +#include +#include +#include +#include +#include + +#ifdef _MSC_VER +# define PRIdPTR "Id" +#else +# include +#endif + +#include "test_malloc.h" +#include "zix/zix.h" + +static bool expect_failure = false; + +// Return a pseudo-pseudo-pseudo-random-ish integer with no duplicates +static uint32_t +unique_rand(uint32_t i) +{ + i ^= 0x00005CA1E; // 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 + } else { + const uint32_t residue = ((uint64_t)i * i) % prime; + return (i <= prime / 2) ? residue : prime - residue; + } +} + +static int +int_cmp(const void* a, const void* b, void* user_data) +{ + const uintptr_t ia = (uintptr_t)a; + const uintptr_t ib = (uintptr_t)b; + // note the (ia - ib) trick here would overflow + if (ia == ib) { + return 0; + } else if (ia < ib) { + return -1; + } else { + return 1; + } +} + +static uint32_t +ith_elem(int test_num, size_t n_elems, int 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 + } +} + +typedef struct { + int test_num; + size_t n_elems; +} TestContext; + +static uint32_t +wildcard_cut(int 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, void* user_data) +{ + const TestContext* ctx = (TestContext*)user_data; + const size_t n_elems = ctx->n_elems; + const int 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 + } else { + return 1; // Wildcard a > b + } + } else if (ib == 0) { + if (ia >= wildcard_cut(test_num, n_elems)) { + return 0; // Wildcard match + } else { + return -1; // Wildcard b > a + } + } else { + return int_cmp(a, b, user_data); + } +} + +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; +} + +static int +stress(int test_num, size_t n_elems) +{ + uintptr_t r = 0; + ZixBTreeIter* ti = NULL; + 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 + ti = zix_btree_begin(t); + if (!ti) { + return test_fail(t, "Failed to allocate iterator\n"); + } else if (!zix_btree_iter_is_end(ti)) { + return test_fail(t, "Begin iterator on empty tree is not end\n"); + } + zix_btree_iter_free(ti); + + // 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, "%lu already in tree\n", (uintptr_t)r); + } else if ((st = zix_btree_insert(t, (void*)r))) { + return test_fail(t, "Insert %lu 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); + } + + // 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 %lu @ %zu failed\n", (uintptr_t)r, i); + } else if ((uintptr_t)zix_btree_get(ti) != r) { + return test_fail(t, "Search data corrupt (%" PRIdPTR " != %" PRIdPTR ")\n", + (uintptr_t)zix_btree_get(ti), r); + } + zix_btree_iter_free(ti); + } + + // 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 %lu @ %zu failed\n", (uintptr_t)r, i); + } else if (zix_btree_iter_is_end(ti)) { + return test_fail(t, "Lower bound %lu @ %zu hit end\n", (uintptr_t)r, i); + } else if ((uintptr_t)zix_btree_get(ti) != r) { + return test_fail(t, "Lower bound corrupt (%" PRIdPTR " != %" PRIdPTR "\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 %lu\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 (%" PRIdPTR " < %" PRIdPTR ")\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 %lu 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 @ %u %" PRIdPTR "\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 %lu\n", (uintptr_t)r); + } else if (removed != r) { + return test_fail(t, "Removed wrong item %lu != %lu\n", + removed, (uintptr_t)r); + } else 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 %lu != %lu\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 %lu 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 %lu failed\n", (uintptr_t)r); + } else if (removed != r) { + return test_fail(t, "Removed wrong item %lu != %lu\n", + removed, (uintptr_t)r); + } else 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 %lu != %lu\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); + } + + zix_btree_free(t); + + // Test lower_bound with wildcard comparator + + TestContext ctx = { test_num, n_elems }; + if (!(t = zix_btree_new(wildcard_cmp, &ctx, NULL))) { + 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 %lu 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"); + } else 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 %" PRIdPTR " != %" PRIdPTR "\n", + iter_data, cut); + } else if (wildcard_cmp((void*)wildcard, (void*)iter_data, &ctx)) { + return test_fail(t, "Wildcard lower bound %" PRIdPTR " != %" PRIdPTR "\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"); + } else 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) ? atol(argv[1]) : 100000; + + 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"); + + 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); + + return EXIT_SUCCESS; +} -- cgit v1.2.1