tests/unit/test-interval-tree.c

   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 }