5  * See the COPYING.LIB file in the top-level directory.
10 #include "qemu/interval-tree.h"
19     if (last - start > INT32_MAX) {  in rand_interval()
22         l_max = last - start;  in rand_interval()
24     s_ofs = g_test_rand_int_range(0, l_max);  in rand_interval()
27     n->start = start + s_ofs;  in rand_interval()
28     n->last = start + l_ofs;  in rand_interval()
35     g_assert(interval_tree_iter_first(&root, 0, UINT64_MAX) == NULL);  in test_empty()
41     nodes[0].start = 1;  in test_find_one_point()
42     nodes[0].last = 1;  in test_find_one_point()
44     interval_tree_insert(&nodes[0], &root);  in test_find_one_point()
46     g_assert(interval_tree_iter_first(&root, 0, 9) == &nodes[0]);  in test_find_one_point()
47     g_assert(interval_tree_iter_next(&nodes[0], 0, 9) == NULL);  in test_find_one_point()
48     g_assert(interval_tree_iter_first(&root, 0, 0) == NULL);  in test_find_one_point()
49     g_assert(interval_tree_iter_next(&nodes[0], 0, 0) == NULL);  in test_find_one_point()
50     g_assert(interval_tree_iter_first(&root, 0, 1) == &nodes[0]);  in test_find_one_point()
51     g_assert(interval_tree_iter_first(&root, 1, 1) == &nodes[0]);  in test_find_one_point()
52     g_assert(interval_tree_iter_first(&root, 1, 2) == &nodes[0]);  in test_find_one_point()
55     interval_tree_remove(&nodes[0], &root);  in test_find_one_point()
65     nodes[0].start = 1;  in test_find_two_point()
66     nodes[0].last = 1;  in test_find_two_point()
67     nodes[1] = nodes[0];  in test_find_two_point()
69     interval_tree_insert(&nodes[0], &root);  in test_find_two_point()
72     find0 = interval_tree_iter_first(&root, 0, 9);  in test_find_two_point()
73     g_assert(find0 == &nodes[0] || find0 == &nodes[1]);  in test_find_two_point()
75     find1 = interval_tree_iter_next(find0, 0, 9);  in test_find_two_point()
76     g_assert(find1 == &nodes[0] || find1 == &nodes[1]);  in test_find_two_point()
81     g_assert(interval_tree_iter_first(&root, 0, 9) == &nodes[0]);  in test_find_two_point()
82     g_assert(interval_tree_iter_next(&nodes[0], 0, 9) == NULL);  in test_find_two_point()
84     interval_tree_remove(&nodes[0], &root);  in test_find_two_point()
90     nodes[0].start = 1;  in test_find_one_range()
91     nodes[0].last = 8;  in test_find_one_range()
93     interval_tree_insert(&nodes[0], &root);  in test_find_one_range()
95     g_assert(interval_tree_iter_first(&root, 0, 9) == &nodes[0]);  in test_find_one_range()
96     g_assert(interval_tree_iter_next(&nodes[0], 0, 9) == NULL);  in test_find_one_range()
97     g_assert(interval_tree_iter_first(&root, 0, 0) == NULL);  in test_find_one_range()
98     g_assert(interval_tree_iter_first(&root, 0, 1) == &nodes[0]);  in test_find_one_range()
99     g_assert(interval_tree_iter_first(&root, 1, 1) == &nodes[0]);  in test_find_one_range()
100     g_assert(interval_tree_iter_first(&root, 4, 6) == &nodes[0]);  in test_find_one_range()
101     g_assert(interval_tree_iter_first(&root, 8, 8) == &nodes[0]);  in test_find_one_range()
102     g_assert(interval_tree_iter_first(&root, 9, 9) == NULL);  in test_find_one_range()
104     interval_tree_remove(&nodes[0], &root);  in test_find_one_range()
112      * Create a tree of many nodes in [0,99] and [200,299],  in test_find_one_range_many()
115     nodes[0].start = 110;  in test_find_one_range_many()
116     nodes[0].last = 190;  in test_find_one_range_many()
119         rand_interval(&nodes[i], 0, 99);  in test_find_one_range_many()
125     for (i = 0; i < ARRAY_SIZE(nodes); ++i) {  in test_find_one_range_many()
130     g_assert(interval_tree_iter_first(&root, 100, 199) == &nodes[0]);  in test_find_one_range_many()
131     g_assert(interval_tree_iter_next(&nodes[0], 100, 199) == NULL);  in test_find_one_range_many()
133     g_assert(interval_tree_iter_first(&root, 100, 110) == &nodes[0]);  in test_find_one_range_many()
134     g_assert(interval_tree_iter_first(&root, 111, 120) == &nodes[0]);  in test_find_one_range_many()
135     g_assert(interval_tree_iter_first(&root, 111, 199) == &nodes[0]);  in test_find_one_range_many()
136     g_assert(interval_tree_iter_first(&root, 190, 199) == &nodes[0]);  in test_find_one_range_many()
143     g_assert(interval_tree_iter_first(&root, 100, 300) == &nodes[0]);  in test_find_one_range_many()
146     interval_tree_remove(&nodes[0], &root);  in test_find_one_range_many()
165     for (i = 0; i < n; ++i) {  in test_find_many_range()
175     for (i = 0; i < ARRAY_SIZE(nodes); ++i) {  in test_find_many_range()
181     for (i = 0; find != NULL; i++) {  in test_find_many_range()
186     g_assert(interval_tree_iter_first(&root,    0,  999) == NULL);  in test_find_many_range()
191     for (i = 0; i < ARRAY_SIZE(nodes); ++i) {  in test_find_many_range()
200     g_test_add_func("/interval-tree/empty", test_empty);  in main()
201     g_test_add_func("/interval-tree/find-one-point", test_find_one_point);  in main()
202     g_test_add_func("/interval-tree/find-two-point", test_find_two_point);  in main()
203     g_test_add_func("/interval-tree/find-one-range", test_find_one_range);  in main()
204     g_test_add_func("/interval-tree/find-one-range-many",  in main()
206     g_test_add_func("/interval-tree/find-many-range", test_find_many_range);  in main()