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 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 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 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 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 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 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 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 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