summaryrefslogtreecommitdiffstats
path: root/test
diff options
context:
space:
mode:
authorDavid Robillard <d@drobilla.net>2011-09-28 17:41:06 +0000
committerDavid Robillard <d@drobilla.net>2011-09-28 17:41:06 +0000
commit0e3ef580b5d265ee59d50d35053e989b8c4277c2 (patch)
treec3989bba215b866ae8c56a276cd4d577b43f26be /test
parent95fd16cd2d7d2394418210199f1275caab8965d0 (diff)
downloadzix-0e3ef580b5d265ee59d50d35053e989b8c4277c2.tar.gz
zix-0e3ef580b5d265ee59d50d35053e989b8c4277c2.tar.bz2
zix-0e3ef580b5d265ee59d50d35053e989b8c4277c2.zip
Add ZixHash
git-svn-id: http://svn.drobilla.net/zix/trunk@39 df6676b4-ccc9-40e5-b5d6-7c4628a128e3
Diffstat (limited to 'test')
-rw-r--r--test/hash_test.c157
-rw-r--r--test/patree_bench.c41
2 files changed, 194 insertions, 4 deletions
diff --git a/test/hash_test.c b/test/hash_test.c
new file mode 100644
index 0000000..ec8ea6f
--- /dev/null
+++ b/test/hash_test.c
@@ -0,0 +1,157 @@
+/*
+ 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 <stdarg.h>
+#include <stdio.h>
+#include <string.h>
+
+#include "zix/hash.h"
+
+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",
+};
+
+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;
+}
+
+static unsigned n_checked = 0;
+
+static void
+check(const void* key, void* value, void* user_data)
+{
+ if (key == value) {
+ ++n_checked;
+ } else {
+ fprintf(stderr, "ERROR: %s != %s\n",
+ (const char*)key, (const char*)value);
+ }
+}
+
+int
+main(int argc, char** argv)
+{
+ ZixHash* hash = zix_hash_new(zix_string_hash, zix_string_equal);
+
+ const size_t n_strings = sizeof(strings) / sizeof(char*);
+
+ // Insert each string
+ for (size_t i = 0; i < n_strings; ++i) {
+ ZixStatus st = zix_hash_insert(hash, strings[i], (char*)strings[i]);
+ if (st) {
+ return test_fail("Failed to insert `%s'\n", strings[i]);
+ }
+ }
+
+ //zix_hash_print_dot(hash, stdout);
+
+ // Attempt to insert each string again
+ for (size_t i = 0; i < n_strings; ++i) {
+ ZixStatus st = zix_hash_insert(hash, strings[i], (char*)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) {
+ const char* match = (const char*)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'\n", strings[i]);
+ }
+ }
+
+ // 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* match = (const char*)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* match = (const char*)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 desruction)
+ for (size_t i = 0; i < n_strings; ++i) {
+ ZixStatus st = zix_hash_insert(hash, strings[i], (char*)strings[i]);
+ 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;
+}
diff --git a/test/patree_bench.c b/test/patree_bench.c
index 02998d6..64e8042 100644
--- a/test/patree_bench.c
+++ b/test/patree_bench.c
@@ -23,8 +23,9 @@
#include <glib.h>
-#include "zix/patree.h"
#include "zix/fat_patree.h"
+#include "zix/hash.h"
+#include "zix/patree.h"
const unsigned seed = 1;
@@ -52,7 +53,7 @@ main(int argc, char** argv)
return test_fail("Failed to open file %s\n", file);
}
- size_t max_n_strings = 100000;
+ size_t max_n_strings = 10000000;
/* Read input strings */
char** strings = NULL;
@@ -87,12 +88,13 @@ main(int argc, char** argv)
FILE* insert_dat = fopen("insert.dat", "w");
FILE* search_dat = fopen("search.dat", "w");
- fprintf(insert_dat, "# n\tGHashTable\tZixPatree\tZixFatPatree\n");
- fprintf(search_dat, "# n\tGHashTable\tZixPatree\tZixFatPatree\n");
+ fprintf(insert_dat, "# n\tGHashTable\tZixHash\tZixPatree\tZixFatPatree\n");
+ fprintf(search_dat, "# n\tGHashTable\tZixHash\tZixPatree\tZixFatPatree\n");
for (size_t n = 1; n <= n_strings; n *= 2) {
printf("Benchmarking n = %zu\n", n);
ZixPatree* patree = zix_patree_new();
+ ZixHash* zhash = zix_hash_new(zix_string_hash, zix_string_equal);
ZixFatPatree* fat_patree = zix_fat_patree_new();
GHashTable* hash = g_hash_table_new(g_str_hash, g_str_equal);
fprintf(insert_dat, "%zu", n);
@@ -107,6 +109,16 @@ main(int argc, char** argv)
}
fprintf(insert_dat, "\t%lf", bench_end(&insert_start));
+ // ZixHash
+ insert_start = bench_start();
+ for (size_t i = 0; i < n; ++i) {
+ ZixStatus st = zix_hash_insert(zhash, strings[i], strings[i]);
+ if (st && st != ZIX_STATUS_EXISTS) {
+ return test_fail("Failed to insert `%s'\n", strings[i]);
+ }
+ }
+ fprintf(insert_dat, "\t%lf", bench_end(&insert_start));
+
// ZixPatree
insert_start = bench_start();
for (size_t i = 0; i < n; ++i) {
@@ -119,12 +131,14 @@ main(int argc, char** argv)
// ZixFatPatree
insert_start = bench_start();
+ /*
for (size_t i = 0; i < n; ++i) {
ZixStatus st = zix_fat_patree_insert(fat_patree, strings[i]);
if (st && st != ZIX_STATUS_EXISTS) {
return test_fail("Failed to insert `%s'\n", strings[i]);
}
}
+ */
fprintf(insert_dat, "\t%lf\n", bench_end(&insert_start));
// Benchmark search
@@ -141,6 +155,21 @@ main(int argc, char** argv)
}
fprintf(search_dat, "\t%lf", bench_end(&search_start));
+ // ZixHash
+ srand(seed);
+ search_start = bench_start();
+ for (size_t i = 0; i < n; ++i) {
+ const size_t index = rand() % n;
+ const char* match = NULL;
+ if (!(match = zix_hash_find(zhash, strings[index]))) {
+ return test_fail("Hash: Failed to find `%s'\n", strings[index]);
+ }
+ if (strcmp(match, strings[index])) {
+ return test_fail("Hash: Bad match for `%s'\n", strings[index]);
+ }
+ }
+ fprintf(search_dat, "\t%lf", bench_end(&search_start));
+
// ZixPatree
srand(seed);
search_start = bench_start();
@@ -151,6 +180,7 @@ main(int argc, char** argv)
return test_fail("Patree: Failed to find `%s'\n", strings[index]);
}
if (strcmp(match, strings[index])) {
+
return test_fail("Patree: Bad match for `%s'\n", strings[index]);
}
}
@@ -159,6 +189,7 @@ main(int argc, char** argv)
// ZixFatPatree
srand(seed);
search_start = bench_start();
+ /*
for (size_t i = 0; i < n; ++i) {
const size_t index = rand() % n;
char* match = NULL;
@@ -169,10 +200,12 @@ main(int argc, char** argv)
return test_fail("FatPatree: Bad match for `%s'\n", strings[index]);
}
}
+ */
fprintf(search_dat, "\t%lf\n", bench_end(&search_start));
zix_patree_free(patree);
zix_fat_patree_free(fat_patree);
+ zix_hash_free(zhash);
g_hash_table_unref(hash);
}