check_type: fix incorrect documentation.
[ccan] / ccan / btree / test / run-trivial.c
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>
6
7 #include <string.h>
8
9 struct test_item {
10         int key;
11         int value;
12 };
13
14 static btree_search_implement(
15         order_by_key,
16         struct test_item *,
17         ,
18         a->key == b->key,
19         a->key < b->key
20 )
21
22 static int insert_test_item(struct btree *btree, int key, int value)
23 {
24         struct test_item key_item = {key, -101};
25         struct test_item *item;
26         btree_iterator iter;
27         
28         if (btree_find_first(btree, &key_item, iter)) {
29                 /* Don't insert new item, but do update its value. */
30                 item = iter->item;
31                 item->value = value;
32                 return 0;
33         }
34         
35         item = malloc(sizeof(*item));
36         item->key = key;
37         item->value = value;
38         
39         btree_insert_at(iter, item);
40         
41         return 1;
42 }
43
44 static int lookup_test_item(const struct btree *btree, int key)
45 {
46         struct test_item key_item = {key, -102};
47         struct test_item *item;
48         btree_iterator iter;
49         
50         if (!btree_find_first(btree, &key_item, iter))
51                 return -100;
52         
53         item = iter->item;
54         return item->value;
55 }
56
57 static int destroy_test_item(void *item, void *ctx) {
58         (void) ctx;
59         free(item);
60         return 1;
61 }
62
63 struct test_insert_entry {
64         int key;
65         int value;
66         int expected_return;
67 };
68
69 struct test_traverse_entry {
70         int key;
71         int value;
72 };
73
74 static void print_indent(unsigned int indent) {
75         while (indent--)
76                 fputs("\t", stdout);
77 }
78
79 static void btree_node_trace(struct btree_node *node, unsigned int indent)
80 {
81         unsigned int i;
82         for (i=0; i<node->count; i++) {
83                 if (node->depth)
84                         btree_node_trace(node->branch[i], indent+1);
85                 print_indent(indent);
86                 puts(node->item[i]);
87         }
88         if (node->depth)
89                 btree_node_trace(node->branch[node->count], indent+1);
90 }
91
92 static void btree_trace(struct btree *btree)
93 {
94         btree_node_trace(btree->root, 0);
95 }
96
97 static void test_insert(struct btree *btree)
98 {
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},
105                 {4, 5, 0}, {9, 2, 0}
106         };
107         size_t i, count = sizeof(ent) / sizeof(*ent);
108         
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);
112         }
113 }
114
115 static void test_find_traverse(struct btree *btree)
116 {
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}
120         };
121         size_t i, count = sizeof(ent) / sizeof(*ent);
122         btree_iterator iter;
123         
124         i = 0;
125         for (btree_begin(btree, iter); btree_next(iter);) {
126                 struct test_item *item = iter->item;
127                 
128                 if (i >= count) {
129                         fail("Too many items in btree according to forward traversal");
130                         break;
131                 }
132                 
133                 ok1(lookup_test_item(btree, item->key) == item->value);
134                 ok1(item->key == ent[i].key && item->value == ent[i].value);
135                 
136                 i++;
137         }
138         
139         if (i != count)
140                 fail("Not enough items in btree according to forward traversal");
141         
142         i = count;
143         for (btree_end(btree, iter); btree_prev(iter);) {
144                 struct test_item *item = iter->item;
145                 
146                 if (!i--) {
147                         fail("Too many items in btree according to backward traversal");
148                         break;
149                 }
150                 
151                 ok1(lookup_test_item(btree, item->key) == item->value);
152                 ok1(item->key == ent[i].key && item->value == ent[i].value);
153         }
154         
155         if (i != 0)
156                 fail("Not enough items in btree according to backward traversal");
157 }
158
159 static btree_search_proto order_by_string;
160
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
167 )
168
169 //used in the test case to sort the test strings
170 static int compare_by_string(const void *ap, const void *bp)
171 {
172         const char * const *a = ap;
173         const char * const *b = bp;
174         return strcmp(*a, *b);
175 }
176
177 static void test_traverse(struct btree *btree, const char *sorted[], size_t count)
178 {
179         btree_iterator iter, iter2;
180         size_t i;
181         
182         i = 0;
183         for (btree_begin(btree, iter); btree_next(iter);) {
184                 if (i >= count) {
185                         fail("Too many items in btree according to forward traversal");
186                         break;
187                 }
188                 
189                 ok1(iter->item == sorted[i]);
190                 
191                 btree_find_first(btree, sorted[i], iter2);
192                 ok1(iter2->item == sorted[i]);
193                 
194                 i++;
195         }
196         
197         if (i != count)
198                 fail("Not enough items in btree according to forward traversal");
199         
200         i = count;
201         for (btree_end(btree, iter); btree_prev(iter);) {
202                 if (!i--) {
203                         fail("Too many items in btree according to backward traversal");
204                         break;
205                 }
206                 
207                 ok1(iter->item == sorted[i]);
208                 
209                 btree_find_first(btree, sorted[i], iter2);
210                 ok1(iter2->item == sorted[i]);
211         }
212         
213         if (i != 0)
214                 fail("Not enough items in btree according to backward traversal");
215 }
216
217 #if 0
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)
223 {
224         size_t i;
225         
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));
230                         (*count)--;
231                         
232                         //puts("----------");
233                         //btree_trace(btree);
234                         
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);
238                 }
239         }
240         
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);
244 }
245 #endif
246
247 static void test_search_implement(void)
248 {
249         struct btree *btree = btree_new(order_by_string);
250         size_t i;
251         
252         const char *unsorted[] = {
253                 "md4",
254                 "isaac",
255                 "noerr",
256                 "talloc_link",
257                 "asearch",
258                 "tap",
259                 "crcsync",
260                 "wwviaudio",
261                 "array_size",
262                 "alignof",
263                 "str",
264                 "read_write_all",
265                 "grab_file",
266                 "out",
267                 "daemonize",
268                 "array",
269                 "crc",
270                 "str_talloc",
271                 "build_assert",
272                 "talloc",
273                 "alloc",
274                 "endian",
275                 "btree",
276                 "typesafe_cb",
277                 "check_type",
278                 "list",
279                 "ciniparser",
280                 "ilog",
281                 "ccan_tokenizer",
282                 "tdb",
283                 "block_pool",
284                 "sparse_bsearch",
285                 "container_of",
286                 "stringmap",
287                 "hash",
288                 "short_types",
289                 "ogg_to_pcm",
290                 "antithread",
291         };
292         size_t count = sizeof(unsorted) / sizeof(*unsorted);
293         const char *sorted[count];
294         
295         memcpy(sorted, unsorted, sizeof(sorted));
296         qsort(sorted, count, sizeof(*sorted), compare_by_string);
297         
298         for (i=0; i<count; i++) {
299                 btree_iterator iter;
300                 
301                 if (btree_find_first(btree, unsorted[i], iter))
302                         fail("btree_insert thinks the test array has duplicates, but it doesn't");
303                 else
304                         btree_insert_at(iter, unsorted[i]);
305         }
306         btree_trace(btree);
307         
308         test_traverse(btree, sorted, count);
309         
310         /*
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"));
322         
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, ""));
329         
330         //test the traversal again to make sure things are okay
331         test_traverse(btree, sorted, count);
332         
333         //remove the rest of the items, then make sure tree is empty
334         while (count)
335                 ok1(test_remove(btree, sorted, &count, sorted[count-1].key));
336         ok1(btree->root == NULL);
337         */
338         
339         btree_delete(btree);
340 }
341
342 int main(void)
343 {
344         struct btree *btree;
345         
346         plan_tests(224);
347         
348         btree = btree_new(order_by_key);
349         btree->destroy = destroy_test_item;
350         test_insert(btree);
351         test_find_traverse(btree);
352         btree_delete(btree);
353         
354         test_search_implement();
355         
356         return exit_status();
357 }