From 2b6c9941272b53c978d418c63669e52e39d9fe4a Mon Sep 17 00:00:00 2001 From: David Robillard Date: Mon, 19 Sep 2011 03:20:05 +0000 Subject: Add ZixPatree. git-svn-id: http://svn.drobilla.net/zix/trunk@21 df6676b4-ccc9-40e5-b5d6-7c4628a128e3 --- test/patree_bench.c | 141 ++++++++++++++++++++++++++++++++++++++++++++++++++++ test/patree_test.c | 100 +++++++++++++++++++++++++++++++++++++ 2 files changed, 241 insertions(+) create mode 100644 test/patree_bench.c create mode 100644 test/patree_test.c (limited to 'test') diff --git a/test/patree_bench.c b/test/patree_bench.c new file mode 100644 index 0000000..559110a --- /dev/null +++ b/test/patree_bench.c @@ -0,0 +1,141 @@ +/* + Copyright 2011 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 "bench.h" + +#include +#include +#include +#include + +#include + +#include "zix/patree.h" + +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; +} + +int +main(int argc, char** argv) +{ + if (argc != 2) { + return test_fail("Usage: %s INPUT_FILE\n", argv[0]); + } + + const char* file = argv[1]; + FILE* fd = fopen(file, "r"); + if (!fd) { + return test_fail("Failed to open file %s\n", file); + } + + /* Read input strings */ + char** strings = NULL; + size_t n_strings = 0; + char* buf = calloc(1, 1); + size_t buf_len = 1; + size_t this_str_len = 0; + for (char c; (c = fgetc(fd)) != EOF;) { + if (c == '\n') { + if (this_str_len == 0) { + continue; + } + strings = realloc(strings, (n_strings + 1) * sizeof(char*)); + strings[n_strings] = malloc(buf_len); + memcpy(strings[n_strings], buf, buf_len); + this_str_len = 0; + ++n_strings; + } else { + ++this_str_len; + if (buf_len < this_str_len + 1) { + buf_len = this_str_len + 1; + buf = realloc(buf, buf_len); + } + buf[this_str_len - 1] = c; + buf[this_str_len] = '\0'; + } + } + + FILE* insert_dat = fopen("insert.dat", "w"); + FILE* search_dat = fopen("search.dat", "w"); + fprintf(insert_dat, "# n\tGHashTable\tZixPatree\n"); + fprintf(search_dat, "# n\tGHashTable\tZixPatree\n"); + + for (size_t n = 1; n <= n_strings; n *= 2) { + ZixPatree* patree = zix_patree_new(); + GHashTable* hash = g_hash_table_new(g_str_hash, g_str_equal); + fprintf(insert_dat, "%zu", n); + fprintf(search_dat, "%zu", n); + + // Benchmark insertion + + // GHashTable + struct timespec insert_start = bench_start(); + for (size_t i = 0; i < n; ++i) { + g_hash_table_insert(hash, strings[i], strings[i]); + } + fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); + + // ZixPatree + insert_start = bench_start(); + for (size_t i = 0; i < n; ++i) { + if (zix_patree_insert(patree, strings[i])) { + return test_fail("Failed to insert `%s'\n", strings[i]); + } + } + fprintf(insert_dat, "\t%lf\n", bench_end(&insert_start)); + + // Benchmark search + + // GHashTable + struct timespec search_start = bench_start(); + for (size_t i = 0; i < n; ++i) { + char* match = g_hash_table_lookup(hash, strings[i]); + if (match != strings[i]) { + return test_fail("Bad match for `%s'\n", strings[i]); + } + } + fprintf(search_dat, "\t%lf", bench_end(&search_start)); + + // ZixPatree + search_start = bench_start(); + for (size_t i = 0; i < n; ++i) { + char* match = NULL; + if (zix_patree_find(patree, strings[i], &match)) { + return test_fail("Failed to find `%s'\n", strings[i]); + } + if (match != strings[i]) { + return test_fail("Bad match for `%s'\n", strings[i]); + } + } + fprintf(search_dat, "\t%lf\n", bench_end(&search_start)); + + zix_patree_free(patree); + g_hash_table_unref(hash); + } + + fclose(insert_dat); + fclose(search_dat); + + return 0; +} diff --git a/test/patree_test.c b/test/patree_test.c new file mode 100644 index 0000000..b1f94fe --- /dev/null +++ b/test/patree_test.c @@ -0,0 +1,100 @@ +/* + Copyright 2011 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 "zix/patree.h" + +static const char* strings[] = { + "http://example.org/foo", + "http://example.org/bar", + "http://example.org/baz", + "http://example.net/foo", + "http://example.net/bar", + "http://example.net/baz", + "http://drobilla.net/", + "http://drobilla.net/software/zix", +}; + +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; +} + +int +main(int argc, char** argv) +{ + ZixPatree* patree = zix_patree_new(); + + const size_t n_strings = sizeof(strings) / sizeof(char*); + + // Insert each string + for (size_t i = 0; i < n_strings; ++i) { + ZixStatus st = zix_patree_insert(patree, strings[i]); + if (st) { + return test_fail("Failed to insert `%s'\n", strings[i]); + } + } + + //zix_patree_print_dot(patree, stdout); + + // Attempt to insert each string again + for (size_t i = 0; i < n_strings; ++i) { + ZixStatus st = zix_patree_insert(patree, strings[i]); + 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) { + char* match = NULL; + ZixStatus st = zix_patree_find(patree, strings[i], &match); + if (st) { + return test_fail("Failed to find `%s'\n", strings[i]); + } + if (match != strings[i]) { + return test_fail("Bad match for `%s'\n", strings[i]); + } + } + + // Try some false matches + const char* not_indexed[] = { + "ftp://example.org/not-there-at-all", + "http://example.org/foobar", + "http://" + }; + const size_t n_not_indexed = sizeof(not_indexed) / sizeof(char*); + for (size_t i = 0; i < n_not_indexed; ++i) { + char* match = NULL; + ZixStatus st = zix_patree_find(patree, not_indexed[i], &match); + if (st != ZIX_STATUS_NOT_FOUND) { + return test_fail("Unexpectedly found `%s'\n", not_indexed[i]); + } + } + + zix_patree_free(patree); + + return 0; +} -- cgit v1.2.1