summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid Robillard <d@drobilla.net>2018-11-14 11:51:01 +0100
committerDavid Robillard <d@drobilla.net>2018-11-14 12:10:06 +0100
commit7f4dced5a5c69e8382aa5a02abb1632fc5aabcec (patch)
treea55dfa4e0c9c41ca1a8addcb271ef82f14e69411
parentf928e67b46bca4922532d909bddd116f3d991179 (diff)
downloadzix-7f4dced5a5c69e8382aa5a02abb1632fc5aabcec.tar.gz
zix-7f4dced5a5c69e8382aa5a02abb1632fc5aabcec.tar.bz2
zix-7f4dced5a5c69e8382aa5a02abb1632fc5aabcec.zip
Remove rotten test code that somehow got lost
-rw-r--r--zix/btree_test.c249
1 files changed, 0 insertions, 249 deletions
diff --git a/zix/btree_test.c b/zix/btree_test.c
deleted file mode 100644
index 93c2b1d..0000000
--- a/zix/btree_test.c
+++ /dev/null
@@ -1,249 +0,0 @@
-/*
- Copyright 2011-2014 David Robillard <http://drobilla.net>
-
- 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 <limits.h>
-#include <stdarg.h>
-#include <stdint.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <time.h>
-
-#ifdef _MSC_VER
-# define PRIdPTR "Id"
-#else
-# include <inttypes.h>
-#endif
-
-#include "zix/zix.h"
-
-unsigned seed = 1;
-
-// Return a pseudo-pseudo-pseudo-random-ish integer with no duplicates
-static uint32_t
-unique_rand(uint32_t i)
-{
- i ^= 0x5CA1AB1E; // 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 intptr_t ia = (intptr_t)a;
- const intptr_t ib = (intptr_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; // Increasing
- case 1: return n_elems - i - 1; // Decreasing
- default: return unique_rand(i); // Pseudo-random
- }
-}
-
-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 EXIT_FAILURE;
-}
-
-static int
-stress(int test_num, size_t n_elems)
-{
- intptr_t r = 0;
- ZixBTreeIter* ti = NULL;
- ZixBTree* t = zix_btree_new(int_cmp, NULL, NULL);
-
- // Ensure begin iterator is end on empty tree
- ti = zix_btree_begin(t);
- if (!zix_btree_iter_is_end(ti)) {
- return test_fail("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_insert(t, (void*)r)) {
- return test_fail("Insert failed\n");
- }
- }
-
- // Ensure tree size is correct
- if (zix_btree_size(t) != n_elems) {
- return test_fail("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("Find %lu @ %zu failed\n", (uintptr_t)r, i);
- }
- if ((intptr_t)zix_btree_get(ti) != r) {
- return test_fail("Corrupt search: %" PRIdPTR " != %" PRIdPTR "\n",
- (intptr_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("Unexpectedly found %lu\n", (uintptr_t)r);
- }
- }
-
- // Iterate over all elements
- size_t i = 0;
- intptr_t last = -1;
- for (ti = zix_btree_begin(t);
- !zix_btree_iter_is_end(ti);
- zix_btree_iter_increment(ti), ++i) {
- const intptr_t iter_data = (intptr_t)zix_btree_get(ti);
- if (iter_data < last) {
- return test_fail("Corrupt iter: %" PRIdPTR " < %" PRIdPTR "\n",
- iter_data, last);
- }
- last = iter_data;
- }
- zix_btree_iter_free(ti);
- if (i != n_elems) {
- return test_fail("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("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("Find %lu failed\n", (uintptr_t)r);
- }
- zix_btree_iter_increment(ti);
- for (i = 0; !zix_btree_iter_is_end(ti); zix_btree_iter_increment(ti), ++i) {
- if ((intptr_t)zix_btree_get(ti) == r) {
- return test_fail("Duplicate element %" PRIdPTR "\n",
- (intptr_t)zix_btree_get(ti), r);
- }
- r = ith_elem(test_num, n_elems, n_elems / 2 + i + 1);
- }
- zix_btree_iter_free(ti);
-
- // Delete all elements
- for (size_t e = 0; e < n_elems; e++) {
- r = ith_elem(test_num, n_elems, e);
- if (zix_btree_remove(t, (void*)r)) {
- return test_fail("Error removing item %lu\n", (uintptr_t)r);
- }
- }
-
- // Ensure the tree is empty
- if (zix_btree_size(t) != 0) {
- return test_fail("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("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);
- if (!zix_btree_remove(t, (void*)r)) {
- return test_fail("Unexpected successful deletion of %lu\n",
- (uintptr_t)r);
- }
- }
-
- // Ensure tree size is still correct
- if (zix_btree_size(t) != n_elems) {
- return test_fail("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);
- if (zix_btree_remove(t, (void*)r)) {
- return test_fail("Deletion of %lu faileded\n", (uintptr_t)r);
- }
- }
-
- // Check tree size
- if (zix_btree_size(t) != n_elems - (n_elems / 4)) {
- return test_fail("Tree size %zu != %zu\n", zix_btree_size(t), n_elems);
- }
-
- 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]) : 10000;
-
- 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");
- return EXIT_SUCCESS;
-}