6 #include <ccan/ptrint/ptrint.h>
7 #include <ccan/tal/tal.h>
8 #include <ccan/tal/str/str.h>
9 #include <ccan/take/take.h>
10 #include <ccan/tal/grab_file/grab_file.h>
11 #include <ccan/container_of/container_of.h>
13 #include <ccan/aga/aga.h>
15 #include <ccan/tap/tap.h>
18 #define LETTERS "abcdefghijklmnopqrstuvwxyz"
19 #define NLETTERS (sizeof(LETTERS) - 1)
22 char **wordarrayb; /* Word array sorted by length */
29 struct trie_node *next[NLETTERS];
33 /* Sorts by length first, then alphabetically */
34 static int lensort(const void *xv, const void *yv)
36 char *x = *((char **)xv);
37 char *y = *((char **)yv);
46 /* We need this because qsort is not stable */
50 static void setup_words(void)
54 /* read in the words */
55 wordfile = grab_file(NULL, "test/api-lazytrie-words.txt");
57 wordarray = tal_strsplit(NULL, take(wordfile), "\n", STR_NO_EMPTY);
59 nwords = tal_count(wordarray) - 1;
60 diag("lazytrie: %d words loaded", nwords);
61 ok1(nwords == NWORDS);
63 wordarrayb = tal_arr(NULL, char *, nwords);
64 memcpy(wordarrayb, wordarray, tal_count(wordarrayb) * sizeof(char *));
66 qsort(wordarrayb, nwords, sizeof(char *), lensort);
70 struct trie_node root;
74 static void init_trie_node(struct trie_node *n, int start, int end,
82 n->isword = (strcmp(n->prefix, wordarray[n->start]) == 0);
84 for (i = 0; i < NLETTERS; i++)
87 aga_node_init(&n->agan);
90 static ptrint_t *lazytrie_first_edge(const struct aga_graph *g,
91 const struct aga_node *n)
96 static ptrint_t *lazytrie_next_edge(const struct aga_graph *g,
97 const struct aga_node *n,
100 int index = ptr2int(e);
102 assert((index >= 1) && (index <= NLETTERS));
103 if (index == NLETTERS)
106 return int2ptr(index + 1);
109 static int lazytrie_edge_info(const struct aga_graph *g,
110 const struct aga_node *n,
112 struct aga_edge_info *ei)
114 struct trie_node *tn = container_of(n, struct trie_node, agan);
115 struct trie_node *next;
116 int index = ptr2int(e);
118 assert((index >= 1) && (index <= NLETTERS));
120 next = tn->next[index - 1];
123 int depth = strlen(tn->prefix);
127 while (start < tn->end) {
128 if (wordarray[start][depth] >= LETTERS[index - 1])
134 while (end < tn->end) {
135 if (wordarray[end][depth] > LETTERS[index - 1])
141 char plus[2] = { LETTERS[index - 1], '\0' };
142 next = tal(tn, struct trie_node);
143 init_trie_node(next, start, end,
144 tal_strcat(next, tn->prefix, plus));
149 ei->to = &next->agan;
153 static struct lazytrie *setup_trie(void)
157 lt = tal(NULL, struct lazytrie);
158 init_trie_node(<->root, 0, nwords, "");
159 aga_init_graph(<->g, lazytrie_first_edge, lazytrie_next_edge,
170 plan_tests(3 + NWORDS*2);
175 aga_dfs_start(<->g);
178 aga_dfs(an, <->g, <->root.agan) {
179 struct trie_node *n = container_of(an, struct trie_node, agan);
181 diag("Visited \"%s\"\n", n->prefix);
184 ok1(strcmp(n->prefix, wordarray[xn]) == 0);
195 aga_bfs_start(<->g);
198 aga_bfs(an, <->g, <->root.agan) {
199 struct trie_node *n = container_of(an, struct trie_node, agan);
201 diag("Visited \"%s\"\n", n->prefix);
204 ok1(strcmp(n->prefix, wordarrayb[xn]) == 0);
209 /* This exits depending on whether all tests passed */
210 return exit_status();