1 /* Include the main header first, to test it works */
2 #include <ccan/btree/btree.h>
3 /* Include the C files directly. */
4 #include <ccan/btree/btree.c>
5 #include <ccan/tap/tap.h>
14 static btree_search_implement(
22 static int insert_test_item(struct btree *btree, int key, int value)
24 struct test_item key_item = {key, -101};
25 struct test_item *item;
28 if (btree_find_first(btree, &key_item, iter)) {
29 /* Don't insert new item, but do update its value. */
35 item = malloc(sizeof(*item));
39 btree_insert_at(iter, item);
44 static int lookup_test_item(const struct btree *btree, int key)
46 struct test_item key_item = {key, -102};
47 struct test_item *item;
50 if (!btree_find_first(btree, &key_item, iter))
57 static int destroy_test_item(void *item, void *ctx) {
63 struct test_insert_entry {
69 struct test_traverse_entry {
74 static void print_indent(unsigned int indent) {
79 static void btree_node_trace(struct btree_node *node, unsigned int indent)
82 for (i=0; i<node->count; i++) {
84 btree_node_trace(node->branch[i], indent+1);
89 btree_node_trace(node->branch[node->count], indent+1);
92 static void btree_trace(struct btree *btree)
94 btree_node_trace(btree->root, 0);
97 static void test_insert(struct btree *btree)
99 struct test_insert_entry ent[] = {
100 {3, 1, 1}, {4, 1, 1}, {5, 9, 1}, {2, 6, 1}, {5, 3, 0}, {5, 8, 0},
101 {9, 7, 1}, {9, 3, 0}, {2, 3, 0}, {8, 4, 1}, {6, 2, 1}, {6, 4, 0},
102 {3, 3, 0}, {8, 3, 0}, {2, 7, 0}, {9, 5, 0}, {0, 2, 1}, {8, 8, 0},
103 {4, 1, 0}, {9, 7, 0}, {1, 6, 1}, {9, 3, 0}, {9, 9, 0}, {3, 7, 0},
104 {5, 1, 0}, {0, 5, 0}, {8, 2, 0}, {0, 9, 0}, {7, 4, 1}, {9, 4, 0},
107 size_t i, count = sizeof(ent) / sizeof(*ent);
109 for (i = 0; i < count; i++) {
110 int ret = insert_test_item(btree, ent[i].key, ent[i].value);
111 ok1(ret == ent[i].expected_return);
115 static void test_find_traverse(struct btree *btree)
117 struct test_traverse_entry ent[] = {
118 {0, 9}, {1, 6}, {2, 7}, {3, 7}, {4, 5},
119 {5, 1}, {6, 4}, {7, 4}, {8, 2}, {9, 2}
121 size_t i, count = sizeof(ent) / sizeof(*ent);
125 for (btree_begin(btree, iter); btree_next(iter);) {
126 struct test_item *item = iter->item;
129 fail("Too many items in btree according to forward traversal");
133 ok1(lookup_test_item(btree, item->key) == item->value);
134 ok1(item->key == ent[i].key && item->value == ent[i].value);
140 fail("Not enough items in btree according to forward traversal");
143 for (btree_end(btree, iter); btree_prev(iter);) {
144 struct test_item *item = iter->item;
147 fail("Too many items in btree according to backward traversal");
151 ok1(lookup_test_item(btree, item->key) == item->value);
152 ok1(item->key == ent[i].key && item->value == ent[i].value);
156 fail("Not enough items in btree according to backward traversal");
159 static btree_search_proto order_by_string;
161 static btree_search_implement(
162 order_by_string, //function name
163 const char*, //key type
164 int c = strcmp(a, b), //setup
165 c == 0, // a == b predicate
166 c < 0 // a < b predicate
169 //used in the test case to sort the test strings
170 static int compare_by_string(const void *ap, const void *bp)
172 const char * const *a = ap;
173 const char * const *b = bp;
174 return strcmp(*a, *b);
177 static void test_traverse(struct btree *btree, const char *sorted[], size_t count)
179 btree_iterator iter, iter2;
183 for (btree_begin(btree, iter); btree_next(iter);) {
185 fail("Too many items in btree according to forward traversal");
189 ok1(iter->item == sorted[i]);
191 btree_find_first(btree, sorted[i], iter2);
192 ok1(iter2->item == sorted[i]);
198 fail("Not enough items in btree according to forward traversal");
201 for (btree_end(btree, iter); btree_prev(iter);) {
203 fail("Too many items in btree according to backward traversal");
207 ok1(iter->item == sorted[i]);
209 btree_find_first(btree, sorted[i], iter2);
210 ok1(iter2->item == sorted[i]);
214 fail("Not enough items in btree according to backward traversal");
218 //(tries to) remove the key from both the btree and the test array. Returns 1 on success, 0 on failure.
219 //success is when an item is removed from the btree and the array, or when none is removed from either
220 //failure is when an item is removed from the btree but not the array or vice versa
221 //after removing, it tries removing again to make sure that removal returns 0
222 static int test_remove(struct btree *btree, struct btree_item items[], size_t *count, const char *key)
226 for (i = *count; i--;) {
227 if (!strcmp(items[i].key, key)) {
228 //item found in array
229 memmove(&items[i], &items[i+1], (*count-(i+1))*sizeof(*items));
232 //puts("----------");
233 //btree_trace(btree);
235 //removal should succeed, as the key should be there
236 //this is not a contradiction; the test is performed twice
237 return btree_remove(btree, key) && !btree_remove(btree, key);
241 //removal should fail, as the key should not be there
242 //this is not redundant; the test is performed twice
243 return !btree_remove(btree, key) && !btree_remove(btree, key);
247 static void test_search_implement(void)
249 struct btree *btree = btree_new(order_by_string);
252 const char *unsorted[] = {
292 size_t count = sizeof(unsorted) / sizeof(*unsorted);
293 const char *sorted[count];
295 memcpy(sorted, unsorted, sizeof(sorted));
296 qsort(sorted, count, sizeof(*sorted), compare_by_string);
298 for (i=0; i<count; i++) {
301 if (btree_find_first(btree, unsorted[i], iter))
302 fail("btree_insert thinks the test array has duplicates, but it doesn't");
304 btree_insert_at(iter, unsorted[i]);
308 test_traverse(btree, sorted, count);
311 //try removing items that should be in the tree
312 ok1(test_remove(btree, sorted, &count, "btree"));
313 ok1(test_remove(btree, sorted, &count, "ccan_tokenizer"));
314 ok1(test_remove(btree, sorted, &count, "endian"));
315 ok1(test_remove(btree, sorted, &count, "md4"));
316 ok1(test_remove(btree, sorted, &count, "asearch"));
317 ok1(test_remove(btree, sorted, &count, "alloc"));
318 ok1(test_remove(btree, sorted, &count, "build_assert"));
319 ok1(test_remove(btree, sorted, &count, "typesafe_cb"));
320 ok1(test_remove(btree, sorted, &count, "sparse_bsearch"));
321 ok1(test_remove(btree, sorted, &count, "stringmap"));
323 //try removing items that should not be in the tree
324 ok1(test_remove(btree, sorted, &count, "java"));
325 ok1(test_remove(btree, sorted, &count, "openoffice"));
326 ok1(test_remove(btree, sorted, &count, "firefox"));
327 ok1(test_remove(btree, sorted, &count, "linux"));
328 ok1(test_remove(btree, sorted, &count, ""));
330 //test the traversal again to make sure things are okay
331 test_traverse(btree, sorted, count);
333 //remove the rest of the items, then make sure tree is empty
335 ok1(test_remove(btree, sorted, &count, sorted[count-1].key));
336 ok1(btree->root == NULL);
348 btree = btree_new(order_by_key);
349 btree->destroy = destroy_test_item;
351 test_find_traverse(btree);
354 test_search_implement();
356 return exit_status();