summaryrefslogtreecommitdiffstats
path: root/tests
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@tavianator.com>2020-06-09 12:56:28 -0400
committerTavian Barnes <tavianator@tavianator.com>2020-06-09 13:01:37 -0400
commit174f98fca012215238554c29b199e4b0377e416f (patch)
tree85fdefda37cab90366b17029e6c224c708240b0f /tests
parente541a7a48ef162895bd5840f3bddfcd23bb231ac (diff)
downloadbfs-174f98fca012215238554c29b199e4b0377e416f.tar.xz
tests/trie: New acceptance test for tries
Diffstat (limited to 'tests')
-rw-r--r--tests/trie.c118
1 files changed, 118 insertions, 0 deletions
diff --git a/tests/trie.c b/tests/trie.c
new file mode 100644
index 0000000..7182a03
--- /dev/null
+++ b/tests/trie.c
@@ -0,0 +1,118 @@
+#undef NDEBUG
+
+#include "../trie.h"
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+const char *keys[] = {
+ "foo",
+ "bar",
+ "baz",
+ "qux",
+ "quux",
+ "quuux",
+ "quuuux",
+
+ "pre",
+ "pref",
+ "prefi",
+ "prefix",
+
+ "AAAA",
+ "AADD",
+ "ABCD",
+ "DDAA",
+ "DDDD",
+
+ "<<<",
+ "<<<>>>",
+ "<<<<<<",
+ "<<<<<<>>>>>>",
+ ">>>>>>",
+ ">>><<<",
+ ">>>",
+};
+
+const size_t nkeys = sizeof(keys) / sizeof(keys[0]);
+
+int main(void) {
+ struct trie trie;
+ trie_init(&trie);
+
+ for (size_t i = 0; i < nkeys; ++i) {
+ assert(!trie_find_str(&trie, keys[i]));
+
+ const char *prefix = NULL;
+ for (size_t j = 0; j < i; ++j) {
+ if (strncmp(keys[i], keys[j], strlen(keys[j])) == 0) {
+ if (!prefix || strcmp(keys[j], prefix) > 0) {
+ prefix = keys[j];
+ }
+ }
+ }
+
+ struct trie_leaf *leaf = trie_find_prefix(&trie, keys[i]);
+ if (prefix) {
+ assert(leaf);
+ assert(strcmp(prefix, leaf->key) == 0);
+ } else {
+ assert(!leaf);
+ }
+
+ leaf = trie_insert_str(&trie, keys[i]);
+ assert(leaf);
+ assert(strcmp(keys[i], leaf->key) == 0);
+ assert(leaf->length == strlen(keys[i]) + 1);
+ }
+
+ for (size_t i = 0; i < nkeys; ++i) {
+ struct trie_leaf *leaf = trie_find_str(&trie, keys[i]);
+ assert(leaf);
+ assert(strcmp(keys[i], leaf->key) == 0);
+ assert(leaf->length == strlen(keys[i]) + 1);
+
+ trie_remove(&trie, leaf);
+ leaf = trie_find_str(&trie, keys[i]);
+ assert(!leaf);
+
+ const char *postfix = NULL;
+ for (size_t j = i + 1; j < nkeys; ++j) {
+ if (strncmp(keys[i], keys[j], strlen(keys[i])) == 0) {
+ if (!postfix || strcmp(keys[j], postfix) < 0) {
+ postfix = keys[j];
+ }
+ }
+ }
+
+ leaf = trie_find_postfix(&trie, keys[i]);
+ if (postfix) {
+ assert(leaf);
+ assert(strcmp(postfix, leaf->key) == 0);
+ } else {
+ assert(!leaf);
+ }
+ }
+
+ // This tests the "jump" node handline on 32-bit platforms
+ size_t longsize = 1 << 20;
+ char *longstr = malloc(longsize);
+ assert(longstr);
+
+ memset(longstr, 0xAC, longsize);
+ assert(!trie_find_mem(&trie, longstr, longsize));
+ assert(trie_insert_mem(&trie, longstr, longsize));
+
+ memset(longstr + longsize/2, 0xAB, longsize/2);
+ assert(!trie_find_mem(&trie, longstr, longsize));
+ assert(trie_insert_mem(&trie, longstr, longsize));
+
+ memset(longstr, 0xAA, longsize/2);
+ assert(!trie_find_mem(&trie, longstr, longsize));
+ assert(trie_insert_mem(&trie, longstr, longsize));
+
+ free(longstr);
+ trie_destroy(&trie);
+ return EXIT_SUCCESS;
+}