tests/trie: New acceptance test for tries

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;
+}