diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | Makefile | 14 | ||||
| -rw-r--r-- | tests/trie.c | 118 |
3 files changed, 129 insertions, 4 deletions
@@ -2,4 +2,5 @@ *.d /bfs /tests/mksock +/tests/trie /tests/xtimegm @@ -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; +} |