1 /*
2  * Test interval trees
3  *
4  * This work is licensed under the terms of the GNU LGPL, version 2 or later.
5  * See the COPYING.LIB file in the top-level directory.
6  *
7  */
8 
9 #include "qemu/osdep.h"
10 #include "qemu/interval-tree.h"
11 
12 static IntervalTreeNode nodes[20];
13 static IntervalTreeRoot root;
14 
rand_interval(IntervalTreeNode * n,uint64_t start,uint64_t last)15 static void rand_interval(IntervalTreeNode *n, uint64_t start, uint64_t last)
16 {
17     gint32 s_ofs, l_ofs, l_max;
18 
19     if (last - start > INT32_MAX) {
20         l_max = INT32_MAX;
21     } else {
22         l_max = last - start;
23     }
24     s_ofs = g_test_rand_int_range(0, l_max);
25     l_ofs = g_test_rand_int_range(s_ofs, l_max);
26 
27     n->start = start + s_ofs;
28     n->last = start + l_ofs;
29 }
30 
test_empty(void)31 static void test_empty(void)
32 {
33     g_assert(root.rb_root.rb_node == NULL);
34     g_assert(root.rb_leftmost == NULL);
35     g_assert(interval_tree_iter_first(&root, 0, UINT64_MAX) == NULL);
36 }
37 
test_find_one_point(void)38 static void test_find_one_point(void)
39 {
40     /* Create a tree of a single node, which is the point [1,1]. */
41     nodes[0].start = 1;
42     nodes[0].last = 1;
43 
44     interval_tree_insert(&nodes[0], &root);
45 
46     g_assert(interval_tree_iter_first(&root, 0, 9) == &nodes[0]);
47     g_assert(interval_tree_iter_next(&nodes[0], 0, 9) == NULL);
48     g_assert(interval_tree_iter_first(&root, 0, 0) == NULL);
49     g_assert(interval_tree_iter_next(&nodes[0], 0, 0) == NULL);
50     g_assert(interval_tree_iter_first(&root, 0, 1) == &nodes[0]);
51     g_assert(interval_tree_iter_first(&root, 1, 1) == &nodes[0]);
52     g_assert(interval_tree_iter_first(&root, 1, 2) == &nodes[0]);
53     g_assert(interval_tree_iter_first(&root, 2, 2) == NULL);
54 
55     interval_tree_remove(&nodes[0], &root);
56     g_assert(root.rb_root.rb_node == NULL);
57     g_assert(root.rb_leftmost == NULL);
58 }
59 
test_find_two_point(void)60 static void test_find_two_point(void)
61 {
62     IntervalTreeNode *find0, *find1;
63 
64     /* Create a tree of a two nodes, which are both the point [1,1]. */
65     nodes[0].start = 1;
66     nodes[0].last = 1;
67     nodes[1] = nodes[0];
68 
69     interval_tree_insert(&nodes[0], &root);
70     interval_tree_insert(&nodes[1], &root);
71 
72     find0 = interval_tree_iter_first(&root, 0, 9);
73     g_assert(find0 == &nodes[0] || find0 == &nodes[1]);
74 
75     find1 = interval_tree_iter_next(find0, 0, 9);
76     g_assert(find1 == &nodes[0] || find1 == &nodes[1]);
77     g_assert(find0 != find1);
78 
79     interval_tree_remove(&nodes[1], &root);
80 
81     g_assert(interval_tree_iter_first(&root, 0, 9) == &nodes[0]);
82     g_assert(interval_tree_iter_next(&nodes[0], 0, 9) == NULL);
83 
84     interval_tree_remove(&nodes[0], &root);
85 }
86 
test_find_one_range(void)87 static void test_find_one_range(void)
88 {
89     /* Create a tree of a single node, which is the range [1,8]. */
90     nodes[0].start = 1;
91     nodes[0].last = 8;
92 
93     interval_tree_insert(&nodes[0], &root);
94 
95     g_assert(interval_tree_iter_first(&root, 0, 9) == &nodes[0]);
96     g_assert(interval_tree_iter_next(&nodes[0], 0, 9) == NULL);
97     g_assert(interval_tree_iter_first(&root, 0, 0) == NULL);
98     g_assert(interval_tree_iter_first(&root, 0, 1) == &nodes[0]);
99     g_assert(interval_tree_iter_first(&root, 1, 1) == &nodes[0]);
100     g_assert(interval_tree_iter_first(&root, 4, 6) == &nodes[0]);
101     g_assert(interval_tree_iter_first(&root, 8, 8) == &nodes[0]);
102     g_assert(interval_tree_iter_first(&root, 9, 9) == NULL);
103 
104     interval_tree_remove(&nodes[0], &root);
105 }
106 
test_find_one_range_many(void)107 static void test_find_one_range_many(void)
108 {
109     int i;
110 
111     /*
112      * Create a tree of many nodes in [0,99] and [200,299],
113      * but only one node with exactly [110,190].
114      */
115     nodes[0].start = 110;
116     nodes[0].last = 190;
117 
118     for (i = 1; i < ARRAY_SIZE(nodes) / 2; ++i) {
119         rand_interval(&nodes[i], 0, 99);
120     }
121     for (; i < ARRAY_SIZE(nodes); ++i) {
122         rand_interval(&nodes[i], 200, 299);
123     }
124 
125     for (i = 0; i < ARRAY_SIZE(nodes); ++i) {
126         interval_tree_insert(&nodes[i], &root);
127     }
128 
129     /* Test that we find exactly the one node. */
130     g_assert(interval_tree_iter_first(&root, 100, 199) == &nodes[0]);
131     g_assert(interval_tree_iter_next(&nodes[0], 100, 199) == NULL);
132     g_assert(interval_tree_iter_first(&root, 100, 109) == NULL);
133     g_assert(interval_tree_iter_first(&root, 100, 110) == &nodes[0]);
134     g_assert(interval_tree_iter_first(&root, 111, 120) == &nodes[0]);
135     g_assert(interval_tree_iter_first(&root, 111, 199) == &nodes[0]);
136     g_assert(interval_tree_iter_first(&root, 190, 199) == &nodes[0]);
137     g_assert(interval_tree_iter_first(&root, 192, 199) == NULL);
138 
139     /*
140      * Test that if there are multiple matches, we return the one
141      * with the minimal start.
142      */
143     g_assert(interval_tree_iter_first(&root, 100, 300) == &nodes[0]);
144 
145     /* Test that we don't find it after it is removed. */
146     interval_tree_remove(&nodes[0], &root);
147     g_assert(interval_tree_iter_first(&root, 100, 199) == NULL);
148 
149     for (i = 1; i < ARRAY_SIZE(nodes); ++i) {
150         interval_tree_remove(&nodes[i], &root);
151     }
152 }
153 
test_find_many_range(void)154 static void test_find_many_range(void)
155 {
156     IntervalTreeNode *find;
157     int i, n;
158 
159     n = g_test_rand_int_range(ARRAY_SIZE(nodes) / 3, ARRAY_SIZE(nodes) / 2);
160 
161     /*
162      * Create a fair few nodes in [2000,2999], with the others
163      * distributed around.
164      */
165     for (i = 0; i < n; ++i) {
166         rand_interval(&nodes[i], 2000, 2999);
167     }
168     for (; i < ARRAY_SIZE(nodes) * 2 / 3; ++i) {
169         rand_interval(&nodes[i], 1000, 1899);
170     }
171     for (; i < ARRAY_SIZE(nodes); ++i) {
172         rand_interval(&nodes[i], 3100, 3999);
173     }
174 
175     for (i = 0; i < ARRAY_SIZE(nodes); ++i) {
176         interval_tree_insert(&nodes[i], &root);
177     }
178 
179     /* Test that we find all of the nodes. */
180     find = interval_tree_iter_first(&root, 2000, 2999);
181     for (i = 0; find != NULL; i++) {
182         find = interval_tree_iter_next(find, 2000, 2999);
183     }
184     g_assert_cmpint(i, ==, n);
185 
186     g_assert(interval_tree_iter_first(&root,    0,  999) == NULL);
187     g_assert(interval_tree_iter_first(&root, 1900, 1999) == NULL);
188     g_assert(interval_tree_iter_first(&root, 3000, 3099) == NULL);
189     g_assert(interval_tree_iter_first(&root, 4000, UINT64_MAX) == NULL);
190 
191     for (i = 0; i < ARRAY_SIZE(nodes); ++i) {
192         interval_tree_remove(&nodes[i], &root);
193     }
194 }
195 
main(int argc,char ** argv)196 int main(int argc, char **argv)
197 {
198     g_test_init(&argc, &argv, NULL);
199 
200     g_test_add_func("/interval-tree/empty", test_empty);
201     g_test_add_func("/interval-tree/find-one-point", test_find_one_point);
202     g_test_add_func("/interval-tree/find-two-point", test_find_two_point);
203     g_test_add_func("/interval-tree/find-one-range", test_find_one_range);
204     g_test_add_func("/interval-tree/find-one-range-many",
205                     test_find_one_range_many);
206     g_test_add_func("/interval-tree/find-many-range", test_find_many_range);
207 
208     return g_test_run();
209 }
210