4f463c90fd33a4329d6491991c495edef7eeb054
[oonf.git] / src / tests / common / test_common_avl.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon version 2 (olsrd2)
4  * Copyright (c) 2004-2015, the olsr.org team - see HISTORY file
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  *
11  * * Redistributions of source code must retain the above copyright
12  *   notice, this list of conditions and the following disclaimer.
13  * * Redistributions in binary form must reproduce the above copyright
14  *   notice, this list of conditions and the following disclaimer in
15  *   the documentation and/or other materials provided with the
16  *   distribution.
17  * * Neither the name of olsr.org, olsrd nor the names of its
18  *   contributors may be used to endorse or promote products derived
19  *   from this software without specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32  * POSSIBILITY OF SUCH DAMAGE.
33  *
34  * Visit http://www.olsr.org for more information.
35  *
36  * If you find this software useful feel free to make a donation
37  * to the project. For more information see the website or contact
38  * the copyright holders.
39  *
40  */
41
42 /**
43  * @file
44  */
45
46 #include <stdlib.h>
47 #include <string.h>
48 #include <stdio.h>
49
50 #include <oonf/libcommon/avl.h>
51 #include <oonf/libcommon/avl_comp.h>
52 #include <oonf/cunit/cunit.h>
53
54 struct tree_element {
55   uint32_t value;
56   struct avl_node node;
57 };
58
59 #define COUNT 6
60
61 static struct avl_tree head;
62 static struct tree_element nodes[COUNT], additional_node1, additional_node2;
63
64 static void clear_elements(void) {
65   uint32_t i;
66
67   memset(&head, 0, sizeof(head));
68   memset(nodes, 0, sizeof(nodes));
69   memset(&additional_node1, 0, sizeof(additional_node1));
70   memset(&additional_node2, 0, sizeof(additional_node2));
71
72   for (i=0; i<COUNT; i++) {
73     nodes[i].value = i+1;
74   }
75 }
76
77 static void add_elements(struct tree_element *elements, bool do_random) {
78   uint32_t i;
79   bool added[COUNT];
80
81   if (do_random) {
82     for (i=0; i<COUNT; i++) {
83       added[i] = false;
84     }
85
86     for (i=0; i<COUNT; i++) {
87       uint32_t num = rand() % COUNT;
88
89       while (added[num]) {
90         num = (num + 1) % COUNT;
91       }
92
93       elements[num].node.key = &elements[num].value;
94       avl_insert(&head, &elements[num].node);
95       added[num] = true;
96     }
97   }
98   else {
99     for (i=0; i<COUNT; i++) {
100       elements[i].node.key = &elements[i].value;
101       avl_insert(&head, &elements[i].node);
102     }
103   }
104 }
105
106 #if 0
107 static void print_tree_int(struct tree_element *e, uint32_t step) {
108   uint32_t i;
109
110   for (i=0; i<step; i++) {
111     printf("\t");
112   }
113   printf("%d: balance %d, leader %d\n", e->value, e->node.balance, e->node.leader);
114
115   if (e->node.left) {
116     for (i=0; i<step; i++) {
117       printf("\t");
118     }
119     printf("=> left\n");
120     print_tree_int(container_of(e->node.left, struct tree_element, node), step+1);
121   }
122   if (e->node.right) {
123     for (i=0; i<step; i++) {
124       printf("\t");
125     }
126     printf("=> right\n");
127     print_tree_int(container_of(e->node.right, struct tree_element, node), step+1);
128   }
129 }
130
131 static void print_tree(void) {
132   printf("Tree count: %d\n", head.count);
133   print_tree_int(container_of(head.root, struct tree_element, node), 0);
134 }
135 #endif
136
137 static uint32_t check_tree_int(const char *name, uint32_t line, struct tree_element *e) {
138   struct tree_element *t;
139   int left = 0, right = 0;
140
141   if (e->node.parent) {
142     CHECK_NAMED_TRUE(e->node.parent->left == &e->node || e->node.parent->right == &e->node,
143         name, line, "parent backlink missing for element %d", e->value);
144
145     if (e->node.parent->left == &e->node) {
146       t = container_of(e->node.parent, struct tree_element, node);
147
148       CHECK_NAMED_TRUE(e->value < t->value, name, line,
149           "Value of parent (%d) <= value of left child (%d)", t->value, e->value);
150     }
151     if (e->node.parent->right == &e->node) {
152       t = container_of(e->node.parent, struct tree_element, node);
153
154       CHECK_NAMED_TRUE(e->value > t->value, name, line,
155           "Value of parent (%d) <= value of right child (%d)", t->value, e->value);
156     }
157   }
158
159   if (e->node.left) {
160     t = container_of(e->node.left, struct tree_element, node);
161     left = check_tree_int(name, line, t);
162   }
163   if (e->node.right) {
164     t = container_of(e->node.right, struct tree_element, node);
165     right = check_tree_int(name, line, t);
166   }
167
168   CHECK_NAMED_TRUE(left - right >= -1 && left - right <= 1, name, line,
169       "Subtree (%d) unbalanced: left %d, right %d", e->value, left, right);
170
171   if (e->node.balance == 0) {
172     CHECK_NAMED_TRUE(left == right, name, line, "Subtree (%d) balance cache wrong (%d): left %d, right %d",
173         e->value, e->node.balance, left, right);
174   }
175   else if (e->node.balance == -1) {
176     CHECK_NAMED_TRUE(left - 1== right, name, line, "Subtree (%d) balance cache wrong (%d): left %d, right %d",
177         e->value, e->node.balance, left, right);
178   }
179   else if (e->node.balance == 1) {
180     CHECK_NAMED_TRUE(left == right - 1, name, line, "Subtree (%d) balance cache wrong (%d): left %d, right %d",
181         e->value, e->node.balance, left, right);
182   }
183   else {
184     CHECK_NAMED_TRUE(false, name, line, "Subtree (%d) with bad balance cache (%d)", e->value, e->node.balance);
185   }
186
187   if (left > right) {
188     return left + 1;
189   }
190   else {
191     return right + 1;
192   }
193 }
194
195 static void check_tree(const char *name, uint32_t line) {
196   uint32_t value;
197   struct list_entity *ptr;
198   struct tree_element *t;
199
200   /* check tree head */
201   CHECK_NAMED_TRUE((head.root != NULL) == (head.count > 0), name, line, "No root pointer, but tree not empty");
202   CHECK_NAMED_TRUE(head.list_head.next != NULL, name, line, "bad next-iterator");
203   CHECK_NAMED_TRUE(head.list_head.prev != NULL, name, line, "bad prev-iterator");
204   CHECK_NAMED_TRUE((head.root == NULL) == list_is_empty(&head.list_head), name, line, "iterator list empty, but tree not empty");
205   if (head.count == 0 || head.root == NULL
206       || head.list_head.next == NULL || head.list_head.prev == NULL || list_is_empty(&head.list_head)) {
207     return;
208   }
209
210   /* check next-iterator */
211   t = container_of(head.list_head.next, struct tree_element, node.list);
212   value = t->value;
213   for (ptr = head.list_head.next; ptr != NULL && ptr != &head.list_head; ptr = ptr->next) {
214     t = container_of(ptr, struct tree_element, node.list);
215     CHECK_NAMED_TRUE(t->value >= value, name, line, "next-iterator (%d < %d)", t->value, value);
216     value = t->value;
217   }
218   CHECK_NAMED_TRUE(ptr == &head.list_head, name, line, "next-iterator contained NULL ptr");
219
220   /* check next-iterator */
221   t = container_of(head.list_head.prev, struct tree_element, node.list);
222   value = t->value;
223   for (ptr = head.list_head.prev; ptr != NULL && ptr != &head.list_head; ptr = ptr->prev) {
224     t = container_of(ptr, struct tree_element, node.list);
225     CHECK_NAMED_TRUE(t->value <= value, name, line, "prev-iterator (%d > %d)", t->value, value);
226     value = t->value;
227   }
228   CHECK_NAMED_TRUE(ptr == &head.list_head, name, line, "prev-iterator contained NULL ptr");
229
230   /* check tree structure */
231   check_tree_int(name, line, container_of(head.root, struct tree_element, node));
232 }
233
234 static void test_insert_nondup(bool do_random) {
235   START_TEST();
236   avl_init(&head, avl_comp_uint32, false);
237   add_elements(nodes, do_random);
238
239   CHECK_TRUE(head.count == COUNT, "tree not completely filled");
240   check_tree(__func__, __LINE__);
241   // print_tree();
242
243   /* try to add duplicate */
244   additional_node1.value = nodes[3].value;
245   additional_node1.node.key = &additional_node1.value;
246   CHECK_TRUE(avl_insert(&head, &additional_node1.node) != 0, "insert duplicate (in non-dup tree) was successful");
247
248   CHECK_TRUE(head.count == COUNT, "tree not completely filled after insert");
249   check_tree(__func__, __LINE__);
250
251   END_TEST();
252 }
253
254 static void test_insert_dup(bool do_random) {
255   START_TEST();
256   avl_init(&head, avl_comp_uint32, true);
257   add_elements(nodes, do_random);
258
259   CHECK_TRUE(head.count == COUNT, "tree not completely filled");
260   check_tree(__func__, __LINE__);
261   // print_tree();
262
263   /* add duplicate */
264   additional_node1.value = nodes[3].value;
265   additional_node1.node.key = &additional_node1.value;
266   CHECK_TRUE(avl_insert(&head, &additional_node1.node) == 0, "insert duplicate (in dup tree) was not successful");
267
268   /* prepare array for check */
269   CHECK_TRUE(head.count == COUNT+1, "tree not completely filled after insert");
270   check_tree(__func__, __LINE__);
271   // print_tree();
272
273   END_TEST();
274 }
275
276 static void test_find(bool do_random) {
277   uint32_t i;
278
279   START_TEST();
280   avl_init(&head, avl_comp_uint32, true);
281   add_elements(nodes, do_random);
282
283   /* search for all existing values */
284   for (i=0; i<COUNT; i++) {
285     CHECK_TRUE(avl_find(&head, &nodes[i].value) == &nodes[i].node, "node of element %d not found", i);
286     CHECK_TRUE(avl_find_element(&head, &nodes[i], &nodes[i], node) == &nodes[i], "element %d not found", i);
287   }
288   i = 255;
289   CHECK_TRUE(avl_find(&head, &i) == NULL, "non-existing element found: %d", i);
290
291   /* add duplicate */
292   additional_node1.value = nodes[3].value;
293   additional_node1.node.key = &additional_node1.value;
294   CHECK_TRUE(avl_insert(&head, &additional_node1.node) == 0, "insert duplicate (in dup tree) was not successful");
295
296   /* search for all existing values in tree with duplicate */
297   for (i=0; i<COUNT; i++) {
298     CHECK_TRUE(avl_find(&head, &nodes[i].value) != NULL, "element %d not found", i);
299   }
300   i = 255;
301   CHECK_TRUE(avl_find(&head, &i) == NULL, "non-existing element found: %d", i);
302
303   END_TEST();
304 }
305
306 static void test_delete_nondup(bool do_random) {
307   START_TEST();
308
309   avl_init(&head, avl_comp_uint32, false);
310   add_elements(nodes, do_random);
311
312   avl_remove(&head, &nodes[2].node);
313   CHECK_TRUE(head.count == COUNT-1, "tree has wrong count after delete");
314   check_tree(__func__, __LINE__);
315
316   END_TEST();
317 }
318
319 static void test_delete_dup(bool do_random) {
320   START_TEST();
321
322   avl_init(&head, avl_comp_uint32, true);
323   add_elements(nodes, do_random);
324
325   /* add duplicate */
326   additional_node1.value = nodes[3].value;
327   additional_node1.node.key = &additional_node1.value;
328   CHECK_TRUE(avl_insert(&head, &additional_node1.node) == 0, "insert duplicate (in dup tree) was not successful");
329
330   avl_remove(&head, &nodes[3].node);
331   CHECK_TRUE(head.count == COUNT, "tree has wrong count after delete of one duplicate");
332   check_tree(__func__, __LINE__);
333
334   END_TEST();
335 }
336
337 static void test_greaterequal(bool do_random) {
338   uint32_t i;
339   START_TEST();
340
341   /* create tree with 1,2,4,5,6 */
342   avl_init(&head, avl_comp_uint32, true);
343   add_elements(nodes, do_random);
344   avl_remove(&head, &nodes[2].node);
345
346   /* find >= 2 */
347   i = 2;
348   CHECK_TRUE(avl_find_greaterequal(&head, &i) == &nodes[1].node, "node of element >= 2 not found");
349   CHECK_TRUE(avl_find_ge_element(&head, &i, &nodes[1], node) == &nodes[1], "element >= 2 not found");
350
351   /* find >= 3 */
352   i = 3;
353   CHECK_TRUE(avl_find_greaterequal(&head, &i) == &nodes[3].node, "node of element >= 3 not found");
354   CHECK_TRUE(avl_find_ge_element(&head, &i, &nodes[3], node) == &nodes[3], "element >= 3 not found");
355
356   /* find >= 4 */
357   i = 4;
358   CHECK_TRUE(avl_find_greaterequal(&head, &i) == &nodes[3].node, "node of element >= 4 not found");
359   CHECK_TRUE(avl_find_ge_element(&head, &i, &nodes[3], node) == &nodes[3], "element >= 4 not found");
360
361   /* find >= 255 */
362   i = 255;
363   CHECK_TRUE(avl_find_greaterequal(&head, &i) == NULL, "node of element >= 255 found");
364   CHECK_TRUE(avl_find_ge_element(&head, &i, &nodes[3], node) == NULL, "element >= 255 found");
365
366   /* add duplicate with value 4 */
367   additional_node1.value = 4;
368   additional_node1.node.key = &additional_node1.value;
369   avl_insert(&head, &additional_node1.node);
370
371   /* find >= 2 */
372   i = 2;
373   CHECK_TRUE(avl_find_greaterequal(&head, &i) == &nodes[1].node, "node of element >= 2 not found (d)");
374   CHECK_TRUE(avl_find_ge_element(&head, &i, &nodes[1], node) == &nodes[1], "element >= 2 not found (d)");
375
376   /* find >= 3 */
377   i = 3;
378   CHECK_TRUE(avl_find_greaterequal(&head, &i) == &nodes[3].node, "node of element >= 3 not found (d)");
379   CHECK_TRUE(avl_find_ge_element(&head, &i, &nodes[3], node) == &nodes[3], "element >= 3 not found (d)");
380
381   /* find >= 4 */
382   i = 4;
383   CHECK_TRUE(avl_find_greaterequal(&head, &i) == &nodes[3].node, "node of element >= 4 not found (d)");
384   CHECK_TRUE(avl_find_ge_element(&head, &i, &nodes[3], node) == &nodes[3], "element >= 4 not found (d)");
385
386   /* find >= 255 */
387   i = 255;
388   CHECK_TRUE(avl_find_greaterequal(&head, &i) == NULL, "node of element >= 255 found (d)");
389   CHECK_TRUE(avl_find_ge_element(&head, &i, &nodes[3], node) == NULL, "element >= 255 found (d)");
390
391   END_TEST();
392 }
393
394 static void test_lessequal(bool do_random) {
395   uint32_t i;
396   START_TEST();
397
398   /* create tree with 1,2,4,5,6 */
399   avl_init(&head, avl_comp_uint32, true);
400   add_elements(nodes, do_random);
401   avl_remove(&head, &nodes[2].node);
402
403   /* find <= 0 */
404   i = 0;
405   CHECK_TRUE(avl_find_lessequal(&head, &i) == NULL, "node of element <= 0 found");
406   CHECK_TRUE(avl_find_le_element(&head, &i, &nodes[3], node) == NULL, "element <= 0 found");
407
408   /* find <= 2 */
409   i = 2;
410   CHECK_TRUE(avl_find_lessequal(&head, &i) == &nodes[1].node, "node of element <= 2 not found");
411   CHECK_TRUE(avl_find_le_element(&head, &i, &nodes[1], node) == &nodes[1], "element <= 2 not found");
412
413   /* find <= 3 */
414   i = 3;
415   CHECK_TRUE(avl_find_lessequal(&head, &i) == &nodes[1].node, "node of element <= 3 not found");
416   CHECK_TRUE(avl_find_le_element(&head, &i, &nodes[1], node) == &nodes[1], "element <= 3 not found");
417
418   /* find <= 4 */
419   i = 4;
420   CHECK_TRUE(avl_find_lessequal(&head, &i) == &nodes[3].node, "node of element <= 4 not found");
421   CHECK_TRUE(avl_find_le_element(&head, &i, &nodes[3], node) == &nodes[3], "element <= 4 not found");
422
423   /* add duplicate with value 4 */
424   additional_node1.value = 4;
425   additional_node1.node.key = &additional_node1.value;
426   avl_insert(&head, &additional_node1.node);
427
428   /* find <= 0 */
429   i = 0;
430   CHECK_TRUE(avl_find_lessequal(&head, &i) == NULL, "node of element <= 0 found (d)");
431   CHECK_TRUE(avl_find_le_element(&head, &i, &nodes[3], node) == NULL, "element <= 0 found (d)");
432
433   /* find <= 2 */
434   i = 2;
435   CHECK_TRUE(avl_find_lessequal(&head, &i) == &nodes[1].node, "node of element <= 2 not found (d)");
436   CHECK_TRUE(avl_find_le_element(&head, &i, &nodes[1], node) == &nodes[1], "element <= 2 not found (d)");
437
438   /* find <= 3 */
439   i = 3;
440   CHECK_TRUE(avl_find_lessequal(&head, &i) == &nodes[1].node, "node of element <= 3 not found (d)");
441   CHECK_TRUE(avl_find_le_element(&head, &i, &nodes[1], node) == &nodes[1], "element <= 3 not found (d)");
442
443   /* find <= 4 */
444   i = 4;
445   CHECK_TRUE(avl_find_lessequal(&head, &i) == &additional_node1.node, "node of element <= 4 not found correctly (d)");
446   CHECK_TRUE(avl_find_le_element(&head, &i, &additional_node1, node) == &additional_node1, "element <= 4 not found correctly (d)");
447
448   END_TEST();
449 }
450
451 static void test_conditions(bool do_random) {
452   START_TEST();
453
454   avl_init(&head, avl_comp_uint32, true);
455   CHECK_TRUE(avl_is_empty(&head), "tree should be empty");
456
457   add_elements(nodes, do_random);
458   CHECK_TRUE(!avl_is_empty(&head), "tree should not be empty");
459
460   CHECK_TRUE(avl_is_first(&head, &nodes[0].node), "element 1 should be first");
461   CHECK_TRUE(!avl_is_first(&head, &nodes[1].node), "element 2 should not be first");
462
463   CHECK_TRUE(avl_is_last(&head, &nodes[COUNT-1].node), "element %d should be first", COUNT);
464   CHECK_TRUE(!avl_is_last(&head, &nodes[0].node), "element 1 should not be first");
465
466   END_TEST();
467 }
468
469 static void test_element_functions(bool do_random) {
470   struct tree_element *e;
471   START_TEST();
472
473   avl_init(&head, avl_comp_uint32, true);
474   add_elements(nodes, do_random);
475
476   CHECK_TRUE(avl_first_element(&head, e, node) == &nodes[0], "Element 1 should be first");
477   CHECK_TRUE(avl_last_element(&head, e, node) == &nodes[COUNT-1], "Element %d should be first", COUNT);
478
479   CHECK_TRUE(avl_next_element(&nodes[0], node) == &nodes[1], "Element 2 is not next of element 1");
480   CHECK_TRUE(avl_prev_element(&nodes[2], node) == &nodes[1], "Element 2 is not prev of element 3");
481   END_TEST();
482 }
483
484 static void test_for_each_macros(bool do_random) {
485   struct tree_element *e;
486   uint32_t i;
487
488   START_TEST();
489   avl_init(&head, avl_comp_uint32, true);
490   add_elements(nodes, do_random);
491
492   i = 0;
493   avl_for_each_element(&head, e, node) {
494     CHECK_TRUE(e == &nodes[i], "for_each iteration %d failed", i);
495     i++;
496   }
497   CHECK_TRUE(i == COUNT, "for_each only had %d of %d iterations", i, COUNT);
498
499   i = 1;
500   avl_for_element_range(&nodes[1], &nodes[4], e, node) {
501     CHECK_TRUE(e == &nodes[i], "for_element_range iteration %d failed", i);
502     i++;
503   }
504   CHECK_TRUE(i == 5, "for_element_range only had %d of %d iterations", i-1, 4);
505
506   i = 1;
507   avl_for_element_to_last(&head, &nodes[1], e, node) {
508     CHECK_TRUE(e == &nodes[i], "element_to_last iteration %d failed", i);
509     i++;
510   }
511   CHECK_TRUE(i == COUNT, "element_to_last only had %d of %d iterations", i-1, 5);
512
513   i = 0;
514   avl_for_first_to_element(&head, &nodes[4], e, node) {
515     CHECK_TRUE(e == &nodes[i], "first_to_element iteration %d failed", i);
516     i++;
517   }
518   CHECK_TRUE(i == 5, "first_to_element only had %d of %d iterations", i-1, 5);
519   END_TEST();
520 }
521
522 static void test_for_each_reverse_macros(bool do_random) {
523   struct tree_element *e;
524   uint32_t i,j;
525
526   START_TEST();
527   avl_init(&head, avl_comp_uint32, true);
528   add_elements(nodes, do_random);
529
530   i = 0;
531   j = COUNT - 1;
532   avl_for_each_element_reverse(&head, e, node) {
533     CHECK_TRUE(e == &nodes[j], "for_each iteration %d failed", i);
534     i++;
535     j--;
536   }
537   CHECK_TRUE(i == COUNT, "for_each only had %d of %d iterations", i, COUNT);
538
539   i = 1;
540   j = 4;
541   avl_for_element_range_reverse(&nodes[1], &nodes[4], e, node) {
542     CHECK_TRUE(e == &nodes[j], "for_element_range iteration %d failed", i);
543     i++;
544     j--;
545   }
546   CHECK_TRUE(i == 5, "for_element_range only had %d of %d iterations", i-1, 4);
547
548   i = 1;
549   j = COUNT - 1;
550   avl_for_element_to_last_reverse(&head, &nodes[1], e, node) {
551     CHECK_TRUE(e == &nodes[j], "element_to_last iteration %d failed", i);
552     i++;
553     j--;
554   }
555   CHECK_TRUE(i == COUNT, "element_to_last only had %d of %d iterations", i-1, 5);
556
557   i = 0;
558   j = 4;
559   avl_for_first_to_element_reverse(&head, &nodes[4], e, node) {
560     CHECK_TRUE(e == &nodes[j], "first_to_element iteration %d failed", i);
561     i++;
562     j--;
563   }
564   CHECK_TRUE(i == 5, "first_to_element only had %d of %d iterations", i-1, 5);
565
566   END_TEST();
567 }
568
569 static void test_for_each_save_macro(bool do_random) {
570   struct tree_element *e, *ptr;
571   uint32_t i;
572
573   START_TEST();
574   avl_init(&head, avl_comp_uint32, true);
575   add_elements(nodes, do_random);
576
577   i = 0;
578   avl_for_each_element_safe(&head, e, node, ptr) {
579     CHECK_TRUE(e == &nodes[i], "for_each_save iteration %d failed", i);
580     avl_remove(&head, &e->node);
581     i++;
582   }
583   CHECK_TRUE(i == COUNT, "for_each_save only had %d of %d iterations", i, COUNT);
584   CHECK_TRUE(avl_is_empty(&head), "for_each_save tree not empty after loop with delete");
585   END_TEST();
586 }
587
588 static void test_for_each_reverse_save_macro(bool do_random) {
589   struct tree_element *e, *ptr;
590   uint32_t i,j;
591
592   START_TEST();
593   avl_init(&head, avl_comp_uint32, true);
594   add_elements(nodes, do_random);
595
596   i = 0;
597   j = COUNT - 1;
598   avl_for_each_element_reverse_safe(&head, e, node, ptr) {
599     CHECK_TRUE(e == &nodes[j], "for_each_save iteration %d failed", i);
600     avl_remove(&head, &e->node);
601     i++;
602     j--;
603   }
604   CHECK_TRUE(i == COUNT, "for_each_save only had %d of %d iterations", i, COUNT);
605   CHECK_TRUE(avl_is_empty(&head), "for_each_save tree not empty after loop with delete");
606   END_TEST();
607 }
608
609 static void test_remove_all_macro(bool do_random) {
610   struct tree_element *e, *ptr;
611   uint32_t i;
612
613   START_TEST();
614   avl_init(&head, avl_comp_uint32, true);
615   add_elements(nodes, do_random);
616
617   i = 0;
618   avl_remove_all_elements(&head, e, node, ptr) {
619     CHECK_TRUE(e == &nodes[i], "for_each_save iteration %u failed", i);
620     i++;
621   }
622   CHECK_TRUE(i == COUNT, "remove_all only had %u of %u iterations", i, COUNT);
623   CHECK_TRUE(avl_is_empty(&head), "remove_all tree not empty after loop with delete");
624
625   check_tree(__func__, __LINE__);
626
627   END_TEST();
628 }
629
630 static void test_for_each_key_macros(void) {
631   struct tree_element *e, *p;
632   uint32_t key;
633   uint32_t i;
634   uint32_t result[4];
635
636   START_TEST();
637   avl_init(&head, avl_comp_uint32, true);
638
639   key = 3;
640   i = 0;
641   avl_for_each_elements_with_key(&head, e, node, p, &key) {
642     CHECK_TRUE(false, "elements returned by loop over empty tree");
643   }
644
645   /* add node with value 4 (4,4,4) */
646   nodes[3].node.key = &nodes[3].value;
647   avl_insert(&head, &nodes[3].node);
648
649   /* add first duplicate with value 4 */
650   additional_node1.value = 4;
651   additional_node1.node.key = &additional_node1.value;
652   avl_insert(&head, &additional_node1.node);
653
654   /* add second duplicate with value 4 */
655   additional_node2.value = 4;
656   additional_node2.node.key = &additional_node2.value;
657   avl_insert(&head, &additional_node2.node);
658
659   key = 4;
660   result[0] = 0;
661   result[1] = 0;
662   result[2] = 0;
663   result[3] = 0;
664
665   avl_for_each_elements_with_key(&head, e, node, p, &key) {
666     if (e == &nodes[3]) {
667       result[0]++;
668     }
669     else if (e == &additional_node1) {
670       result[1]++;
671     }
672     else if (e == &additional_node2) {
673       result[2]++;
674     }
675     else {
676       result[3]++;
677     }
678   }
679
680   CHECK_TRUE(result[0] >= 1, "First node with key=4 not returned");
681   CHECK_TRUE(result[0] <= 1, "First node with key=4 returned multiple times");
682   CHECK_TRUE(result[1] >= 1, "First node with key=4 not returned");
683   CHECK_TRUE(result[1] <= 1, "First node with key=4 returned multiple times");
684   CHECK_TRUE(result[2] >= 1, "First node with key=4 not returned");
685   CHECK_TRUE(result[2] <= 1, "First node with key=4 returned multiple times");
686
687   CHECK_TRUE(result[3] == 0, "Unknown node returned");
688
689   /* add node with value 3 (3,4,4,4) */
690   nodes[2].node.key = &nodes[2].value;
691   avl_insert(&head, &nodes[2].node);
692
693   key = 4;
694   i = 0;
695   result[0] = 0;
696   result[1] = 0;
697   result[2] = 0;
698   result[3] = 0;
699
700   avl_for_each_elements_with_key(&head, e, node, p, &key) {
701     if (e == &nodes[3]) {
702       result[0]++;
703     }
704     else if (e == &additional_node1) {
705       result[1]++;
706     }
707     else if (e == &additional_node2) {
708       result[2]++;
709     }
710     else {
711       result[3]++;
712     }
713   }
714
715   CHECK_TRUE(result[0] >= 1, "First node with key=4 not returned");
716   CHECK_TRUE(result[0] <= 1, "First node with key=4 returned multiple times");
717   CHECK_TRUE(result[1] >= 1, "First node with key=4 not returned");
718   CHECK_TRUE(result[1] <= 1, "First node with key=4 returned multiple times");
719   CHECK_TRUE(result[2] >= 1, "First node with key=4 not returned");
720   CHECK_TRUE(result[2] <= 1, "First node with key=4 returned multiple times");
721
722   CHECK_TRUE(result[3] == 0, "Unknown node returned");
723
724   /* add node with value 5 (3,4,4,4,5) */
725   nodes[4].node.key = &nodes[4].value;
726   avl_insert(&head, &nodes[4].node);
727
728   key = 4;
729   i = 0;
730   result[0] = 0;
731   result[1] = 0;
732   result[2] = 0;
733   result[3] = 0;
734
735   avl_for_each_elements_with_key(&head, e, node, p, &key) {
736     if (e == &nodes[3]) {
737       result[0]++;
738     }
739     else if (e == &additional_node1) {
740       result[1]++;
741     }
742     else if (e == &additional_node2) {
743       result[2]++;
744     }
745     else {
746       result[3]++;
747     }
748   }
749
750   CHECK_TRUE(result[0] >= 1, "First node with key=4 not returned");
751   CHECK_TRUE(result[0] <= 1, "First node with key=4 returned multiple times");
752   CHECK_TRUE(result[1] >= 1, "First node with key=4 not returned");
753   CHECK_TRUE(result[1] <= 1, "First node with key=4 returned multiple times");
754   CHECK_TRUE(result[2] >= 1, "First node with key=4 not returned");
755   CHECK_TRUE(result[2] <= 1, "First node with key=4 returned multiple times");
756
757   CHECK_TRUE(result[3] == 0, "Unknown node returned");
758
759   key = 3;
760   i = 0;
761   avl_for_each_elements_with_key(&head, e, node, p, &key) {
762     i++;
763
764     switch (i) {
765       case 1:
766         CHECK_TRUE(e == &nodes[2], "First node with key=3 not returned first");
767         break;
768       default:
769         CHECK_TRUE(false, "More than one element with key=3 returned");
770         break;
771     }
772   }
773
774   CHECK_TRUE(i>0, "Less than one nodes returned");
775
776   key = 6;
777   avl_for_each_elements_with_key(&head, e, node, p, &key) {
778     CHECK_TRUE(false, "Element returned by loop over non-existing key");
779   }
780
781   END_TEST();
782 }
783
784 static int
785 compare_ints (const void *a, const void *b)
786 {
787   const int *da = (const int *) a;
788   const int *db = (const int *) b;
789
790   return (*da > *db) - (*da < *db);
791 }
792
793 static void random_insert(uint32_t *array, uint32_t count) {
794   uint32_t i,j;
795   struct tree_element *e;
796
797   for (i=0; i<count; i++) {
798     uint32_t value = (uint32_t)rand();
799
800     array[head.count] = value;
801     qsort(array, head.count+1, sizeof(int), compare_ints);
802
803     e = malloc(sizeof(*e));
804     e->value = value;
805     e->node.key = &e->value;
806     avl_insert(&head, &e->node);
807
808     check_tree(__func__, __LINE__);
809
810     j = 0;
811     avl_for_each_element(&head, e, node) {
812       CHECK_TRUE(array[j++] == e->value, "check random delete order");
813     }
814   }
815 }
816
817 static void random_delete(uint32_t *array, uint32_t count) {
818   uint32_t i, j;
819   struct tree_element *e;
820
821   for (i=0; i<count; i++) {
822     j = (uint32_t)rand() % head.count;
823
824     e = avl_find_element(&head, &array[j], e, node);
825     CHECK_TRUE(e != NULL, "cannot find element during large test");
826     if (e) {
827       if (j != head.count - 1) {
828         memmove(&array[j], &array[j+1], sizeof(int) * (head.count - j - 1));
829       }
830
831       avl_remove(&head, &e->node);
832       free(e);
833
834       check_tree(__func__, __LINE__);
835
836       j = 0;
837       avl_for_each_element(&head, e, node) {
838         CHECK_TRUE(array[j++] == e->value, "check random delete order");
839       }
840     }
841   }
842 }
843
844 /* insert/remove 1000's random numbers into tree and check if everything is okay */
845 static void test_random_insert(void) {
846   uint32_t array[1000];
847   struct tree_element *e, *ptr;
848
849   srand(0);
850   START_TEST();
851   avl_init(&head, avl_comp_uint32, true);
852
853   random_insert(array, 1000);
854   random_delete(array, 500);
855   random_insert(array, 400);
856   random_delete(array, 600);
857
858   avl_remove_all_elements(&head, e, node, ptr) {
859     free(e);
860   }
861   END_TEST();
862 }
863
864 static void do_tests(bool do_random) {
865   printf("Do %srandom tests.\n", do_random ? "" : "non ");
866
867   test_insert_nondup(do_random);
868   test_insert_dup(do_random);
869   test_find(do_random);
870   test_delete_nondup(do_random);
871   test_delete_dup(do_random);
872   test_greaterequal(do_random);
873   test_lessequal(do_random);
874   test_conditions(do_random);
875   test_element_functions(do_random);
876   test_for_each_macros(do_random);
877   test_for_each_reverse_macros(do_random);
878   test_for_each_save_macro(do_random);
879   test_for_each_reverse_save_macro(do_random);
880   test_remove_all_macro(do_random);
881 }
882
883 int main(int argc __attribute__ ((unused)), char **argv __attribute__ ((unused))) {
884   BEGIN_TESTING(clear_elements);
885
886   do_tests(false);
887   do_tests(true);
888   test_random_insert();
889   test_for_each_key_macros();
890
891   return FINISH_TESTING();
892 }