summaryrefslogtreecommitdiffstats
path: root/tests/trie.c
blob: 7182a03e2f50adecaf153d4d5ca570d9b6230581 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
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;
}