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