tests/trie: New acceptance test for tries

3 files changed, 129 insertions, 4 deletions

diff --git a/.gitignore b/.gitignore
index c18ddc3..7a60b0c 100644
--- a/.gitignore
+++ b/.gitignore
@@ -2,4 +2,5 @@
 *.d
 /bfs
 /tests/mksock
+/tests/trie
 /tests/xtimegm
diff --git a/Makefile b/Makefile
index 4f4c1e3..3844966 100644
--- a/Makefile
+++ b/Makefile
@@ -89,7 +89,7 @@ ALL_LDLIBS = $(LOCAL_LDLIBS) $(LDLIBS)
 
 default: bfs
 
-all: bfs tests/mksock tests/xtimegm
+all: bfs tests/mksock tests/trie tests/xtimegm
 
 bfs: \
     bftw.o \
@@ -126,13 +126,19 @@ release: bfs
 tests/mksock: tests/mksock.o
 	$(CC) $(ALL_LDFLAGS) $^ -o $@
 
+tests/trie: trie.o tests/trie.o
+	$(CC) $(ALL_LDFLAGS) $^ -o $@
+
 tests/xtimegm: time.o tests/xtimegm.o
 	$(CC) $(ALL_LDFLAGS) $^ -o $@
 
 %.o: %.c
 	$(CC) $(ALL_CFLAGS) -c $< -o $@
 
-check: check-xtimegm check-bfs check-dfs check-ids
+check: check-trie check-xtimegm check-bfs check-dfs check-ids
+
+check-trie: tests/trie
+	$<
 
 check-xtimegm: tests/xtimegm
 	$<
@@ -150,7 +156,7 @@ endif
 	+$(MAKE) -B check $(DISTCHECK_FLAGS)
 
 clean:
-	$(RM) bfs *.[od] tests/mksock tests/xtimegm tests/*.[od]
+	$(RM) bfs *.[od] tests/mksock tests/trie tests/xtimegm tests/*.[od]
 
 install:
 	$(MKDIR) $(DESTDIR)$(PREFIX)/bin
@@ -162,6 +168,6 @@ uninstall:
 	$(RM) $(DESTDIR)$(PREFIX)/bin/bfs
 	$(RM) $(DESTDIR)$(MANDIR)/man1/bfs.1
 
-.PHONY: all asan ubsan msan release check distcheck clean install uninstall
+.PHONY: all asan ubsan msan release check check-trie check-xtimegm distcheck clean install uninstall
 
 -include $(wildcard *.d)
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;
+}