summaryrefslogtreecommitdiffstats
path: root/test
diff options
context:
space:
mode:
authorDavid Robillard <d@drobilla.net>2011-09-05 04:31:38 +0000
committerDavid Robillard <d@drobilla.net>2011-09-05 04:31:38 +0000
commita54b3fcd7b73411f9decc82ebf7ddb906e13052b (patch)
tree2dd1094bcfd34e1ed57f9010f594e81e550c5cbc /test
downloadzix-a54b3fcd7b73411f9decc82ebf7ddb906e13052b.tar.gz
zix-a54b3fcd7b73411f9decc82ebf7ddb906e13052b.tar.bz2
zix-a54b3fcd7b73411f9decc82ebf7ddb906e13052b.zip
Initial import.
git-svn-id: http://svn.drobilla.net/zix/trunk@1 df6676b4-ccc9-40e5-b5d6-7c4628a128e3
Diffstat (limited to 'test')
-rw-r--r--test/tree_bench.c205
-rw-r--r--test/tree_test.c158
2 files changed, 363 insertions, 0 deletions
diff --git a/test/tree_bench.c b/test/tree_bench.c
new file mode 100644
index 0000000..48d5935
--- /dev/null
+++ b/test/tree_bench.c
@@ -0,0 +1,205 @@
+/*
+ Copyright 2011 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.
+*/
+
+#define _POSIX_C_SOURCE 199309L
+
+#include <time.h>
+#include <sys/time.h>
+
+#include <inttypes.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <limits.h>
+
+#include <glib.h>
+
+#include "zix/zix.h"
+
+const unsigned seed = 1;
+
+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;
+ return ia - ib;
+}
+
+static int
+test_fail()
+{
+ fprintf(stderr, "ERROR\n");
+ return EXIT_FAILURE;
+}
+
+static inline double
+elapsed_s(const struct timespec* start, const struct timespec* end)
+{
+ return ( (end->tv_sec - start->tv_sec)
+ + ((end->tv_nsec - start->tv_nsec) * 0.000000001) );
+}
+
+static inline struct timespec
+bench_start()
+{
+ struct timespec start_t;
+ clock_gettime(CLOCK_REALTIME, &start_t);
+ return start_t;
+}
+
+static inline double
+bench_end(const struct timespec* start_t)
+{
+ struct timespec end_t;
+ clock_gettime(CLOCK_REALTIME, &end_t);
+ return elapsed_s(start_t, &end_t);
+}
+
+static int
+bench_zix(size_t n_elems, FILE* insert_dat, FILE* search_dat)
+{
+ intptr_t r;
+ ZixTreeIter ti;
+
+ ZixTree* t = zix_tree_new(true, int_cmp, NULL);
+
+ srand(seed);
+
+ // Insert n_elems elements
+ struct timespec insert_start = bench_start();
+ for (size_t i = 0; i < n_elems; i++) {
+ r = rand();
+ int status = zix_tree_insert(t, (void*)r, &ti);
+ if (status && status != ZIX_STATUS_EXISTS) {
+ return test_fail();
+ }
+ }
+ fprintf(insert_dat, "\t%lf", bench_end(&insert_start));
+
+ srand(seed);
+
+ // Search for all elements
+ struct timespec search_start = bench_start();
+ for (size_t i = 0; i < n_elems; i++) {
+ r = rand();
+ if (zix_tree_find(t, (void*)r, &ti)) {
+ return test_fail();
+ }
+ if ((intptr_t)zix_tree_get_data(ti) != r) {
+ return test_fail();
+ }
+ }
+ fprintf(search_dat, "\t%lf", bench_end(&search_start));
+
+ srand(seed);
+
+ // Delete all elements
+ for (size_t i = 0; i < n_elems; i++) {
+ r = rand();
+ ZixTreeIter item;
+ if (zix_tree_find(t, (void*)r, &item)) {
+ return test_fail();
+ }
+ if (zix_tree_remove(t, item)) {
+ return test_fail();
+ }
+ }
+
+ zix_tree_free(t);
+
+ return EXIT_SUCCESS;
+}
+
+static int
+bench_glib(size_t n_elems, FILE* insert_dat, FILE* search_dat)
+{
+ intptr_t r;
+ GSequence* t = g_sequence_new(NULL);
+
+ srand(seed);
+
+ // Insert n_elems elements
+ struct timespec insert_start = bench_start();
+ for (size_t i = 0; i < n_elems; i++) {
+ r = rand();
+ g_sequence_insert_sorted(t, (void*)r, int_cmp, NULL);
+ }
+ fprintf(insert_dat, "\t%lf", bench_end(&insert_start));
+
+ srand(seed);
+
+ // Search for all elements
+ struct timespec search_start = bench_start();
+ for (size_t i = 0; i < n_elems; i++) {
+ r = rand();
+ if (!g_sequence_search(t, (void*)r, int_cmp, NULL)) {
+ return test_fail();
+ }
+ }
+ fprintf(search_dat, "\t%lf", bench_end(&search_start));
+
+#if 0
+ srand(seed);
+
+ // Delete all elements
+ for (size_t i = 0; i < n_elems; i++) {
+ r = rand();
+ GSequenceIter item;
+ if (g_sequence_find(t, (void*)r, &item)) {
+ return test_fail();
+ }
+ if (g_sequence_remove(t, item)) {
+ return test_fail();
+ }
+ }
+#endif
+
+ g_sequence_free(t);
+
+ return EXIT_SUCCESS;
+}
+
+int
+main(int argc, char** argv)
+{
+ if (argc != 3) {
+ fprintf(stderr, "USAGE: %s MIN_N MAX_N\n", argv[0]);
+ return 1;
+ }
+
+ const size_t min_n = atol(argv[1]);
+ const size_t max_n = atol(argv[2]);
+
+ fprintf(stderr, "Benchmarking %zu .. %zu elements\n", min_n, max_n);
+
+ FILE* insert_dat = fopen("insert.dat", "w");
+ FILE* search_dat = fopen("search.dat", "w");
+ fprintf(insert_dat, "# n\tZixTree\tGSequence\n");
+ fprintf(search_dat, "# n\tZixTree\tGSequence\n");
+ for (size_t n = min_n; n <= max_n; n *= 2) {
+ fprintf(insert_dat, "%zu", n);
+ fprintf(search_dat, "%zu", n);
+ bench_zix(n, insert_dat, search_dat);
+ bench_glib(n, insert_dat, search_dat);
+ fprintf(insert_dat, "\n");
+ fprintf(search_dat, "\n");
+ }
+ fclose(insert_dat);
+ fclose(search_dat);
+
+ return EXIT_SUCCESS;
+}
diff --git a/test/tree_test.c b/test/tree_test.c
new file mode 100644
index 0000000..d4fb283
--- /dev/null
+++ b/test/tree_test.c
@@ -0,0 +1,158 @@
+/*
+ Copyright 2011 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 <inttypes.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <limits.h>
+
+#include <sys/time.h>
+
+#include "zix/zix.h"
+
+unsigned seed = 1;
+
+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;
+ return ia - ib;
+}
+
+static int
+ith_elem(int test_num, size_t n_elems, int 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
+ }
+}
+
+static int
+test_fail()
+{
+ return EXIT_FAILURE;
+}
+
+static int
+stress(int test_num, size_t n_elems)
+{
+ intptr_t r;
+ ZixTreeIter ti;
+
+ ZixTree* t = zix_tree_new(true, int_cmp, 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 == ZIX_STATUS_EXISTS) {
+ continue;
+ } else if (status != ZIX_STATUS_SUCCESS) {
+ fprintf(stderr, "Insert failed\n");
+ return test_fail();
+ }
+ if ((intptr_t)zix_tree_get_data(ti) != r) {
+ fprintf(stderr, "Data is corrupted! Saw %" PRIdPTR ", expected %zu\n",
+ (intptr_t)zix_tree_get_data(ti), i);
+ 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_data(ti) != r) {
+ fprintf(stderr, "Data corrupted (saw %" PRIdPTR ", expected %zu\n",
+ (intptr_t)zix_tree_get_data(ti), i);
+ return test_fail();
+ }
+ }
+
+ srand(seed);
+
+ // Delete all elements
+ for (size_t i = 0; i < n_elems; i++) {
+ r = ith_elem(test_num, n_elems, i);
+ 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");
+ }
+ }
+
+ zix_tree_free(t);
+
+ return EXIT_SUCCESS;
+}
+
+int
+main(int argc, char** argv)
+{
+ const size_t n_tests = 3;
+ size_t n_elems = 0;
+
+ struct timeval time;
+ gettimeofday(&time, NULL);
+
+ if (argc == 1) {
+ n_elems = 4096;
+ } else {
+ n_elems = atol(argv[1]);
+ if (argc > 2) {
+ seed = atol(argv[2]);
+ } else {
+ seed = time.tv_sec + time.tv_usec;
+ }
+ }
+
+ if (n_elems == 0) {
+ fprintf(stderr, "USAGE: %s [N_ELEMS]\n", argv[0]);
+ return 1;
+ }
+
+ printf("Running %zu tests with %zu elements (seed %d)",
+ n_tests, n_elems, seed);
+
+ for (size_t 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;
+}