1#include "structures/tests/test_internal.h"
2
3TEST_GROUP_DEFINE(rbit, .intensity_desc = {
4 .curve = SCALE_PIECEWISE_LOG,
5 .unit = "ops",
6 });
7
8#define RBIT_N 256
9#define RBIT_OPS 4000
10#define RBIT_SEED 0xC0FFEEULL
11
12static size_t subtree_nodes(struct rbit_node *n) {
13 if (!n)
14 return 0;
15 return 1 + subtree_nodes(n: n->left) + subtree_nodes(n: n->right);
16}
17
18static int overlaps(struct interval a, struct interval b) {
19 return a.low <= b.high && b.low <= a.high;
20}
21
22TEST_DEFINE_UNIT(rbit, order_and_search, TEST_INTENSITY(32, 256, 4096)) {
23 prng_seed(RBIT_SEED);
24 struct rbit tree;
25 rbit_init(rbit: &tree);
26
27 size_t count_n = ctx->intensity_val ? ctx->intensity_val : RBIT_N;
28 struct rbit_node *nodes = vnews(nodes, count_n, ALLOC_ZERO);
29 TEST_ASSERT_NONNULL(nodes);
30
31 size_t low = 1;
32 for (size_t i = 0; i < count_n; i++) {
33 low += 1 + (prng_next() % 64);
34 rbit_init_node(n: &nodes[i]);
35 nodes[i].interval.low = low;
36 nodes[i].interval.high = low + (prng_next() % 32);
37 rbit_insert(tree: &tree, new_node: &nodes[i]);
38 }
39
40 size_t prev = 0;
41 size_t count = 0;
42 struct rbit_node *it;
43 rbit_for_each(it, &tree) {
44 TEST_ASSERT_GE(it->interval.low, prev);
45 prev = it->interval.low;
46 count++;
47 }
48 TEST_ASSERT_EQ(count, count_n);
49
50 for (size_t i = 0; i < count_n; i++)
51 TEST_ASSERT_PTR_EQ(rbit_search(tree.root, nodes[i].interval),
52 &nodes[i]);
53
54 for (size_t i = 0; i < count_n; i += 2)
55 rbit_delete(tree: &tree, z: &nodes[i]);
56 for (size_t i = 0; i < count_n; i++) {
57 struct rbit_node *f = rbit_search(root: tree.root, iv: nodes[i].interval);
58 TEST_ASSERT((i % 2 == 0) ? (f == NULL) : (f == &nodes[i]));
59 }
60
61 for (size_t i = 1; i < count_n; i += 2)
62 rbit_delete(tree: &tree, z: &nodes[i]);
63 TEST_ASSERT(rbit_empty(&tree));
64
65 vfree(nodes);
66 return TEST_SUCCESS;
67}
68
69TEST_DEFINE_UNIT(rbit, overlap_search, TEST_INTENSITY(200, 4000, 20000)) {
70 prng_seed(RBIT_SEED + 1);
71 struct rbit tree;
72 rbit_init(rbit: &tree);
73
74 struct rbit_node *nodes = vnews(nodes, RBIT_N, ALLOC_ZERO);
75 TEST_ASSERT_NONNULL(nodes);
76
77 /* Random (possibly overlapping) intervals in a bounded space. */
78 for (size_t i = 0; i < RBIT_N; i++) {
79 size_t lo = prng_next() % 100000;
80 rbit_init_node(n: &nodes[i]);
81 nodes[i].interval.low = lo;
82 nodes[i].interval.high = lo + (prng_next() % 500);
83 rbit_insert(tree: &tree, new_node: &nodes[i]);
84 }
85
86 size_t ops = ctx->intensity_val ? ctx->intensity_val : RBIT_OPS;
87 for (size_t q = 0; q < ops; q++) {
88 size_t lo = prng_next() % 100000;
89 struct interval iv = {.low = lo, .high = lo + (prng_next() % 500)};
90
91 bool brute = false;
92 for (size_t i = 0; i < RBIT_N; i++)
93 if (overlaps(a: nodes[i].interval, b: iv)) {
94 brute = true;
95 break;
96 }
97
98 struct rbit_node *res = rbit_overlap_search(root: tree.root, iv);
99 TEST_ASSERT_EQ((res != NULL), brute);
100 if (res)
101 TEST_ASSERT(overlaps(res->interval, iv));
102 }
103
104 vfree(nodes);
105 return TEST_SUCCESS;
106}
107
108struct count_node {
109 struct rbit_node node;
110 size_t subtree_count; /* maintained by augment */
111};
112
113static size_t cn_count(struct rbit_node *n) {
114 return n ? rbit_entry(n, struct count_node, node)->subtree_count : 0;
115}
116
117static bool count_augment(struct rbit_node *n) {
118 struct count_node *c = rbit_entry(n, struct count_node, node);
119 size_t old_max = n->max, old_cnt = c->subtree_count;
120
121 size_t mx = n->interval.high;
122 if (rbit_node_max(n: n->left) > mx)
123 mx = rbit_node_max(n: n->left);
124 if (rbit_node_max(n: n->right) > mx)
125 mx = rbit_node_max(n: n->right);
126
127 n->max = mx;
128 c->subtree_count = 1 + cn_count(n: n->left) + cn_count(n: n->right);
129 return n->max != old_max || c->subtree_count != old_cnt;
130}
131
132TEST_DEFINE_UNIT(rbit, augment_hook, TEST_INTENSITY(200, 4000, 20000)) {
133 prng_seed(RBIT_SEED + 2);
134 struct rbit tree;
135 rbit_init(rbit: &tree);
136 tree.augment = count_augment;
137
138 struct count_node *nodes = vnews(nodes, RBIT_N, ALLOC_ZERO);
139 TEST_ASSERT_NONNULL(nodes);
140 bool *live = vnews(live, RBIT_N, ALLOC_ZERO);
141 TEST_ASSERT_NONNULL(live);
142
143 for (size_t i = 0; i < RBIT_N; i++) {
144 rbit_init_node(n: &nodes[i].node);
145 nodes[i].node.interval.low = i * 100 + 1;
146 nodes[i].node.interval.high = i * 100 + 50;
147 }
148
149 size_t ops = ctx->intensity_val ? ctx->intensity_val : RBIT_OPS;
150 for (size_t op = 0; op < ops; op++) {
151 size_t i = prng_next() % RBIT_N;
152 if (live[i]) {
153 rbit_delete(tree: &tree, z: &nodes[i].node);
154 live[i] = false;
155 } else {
156 rbit_insert(tree: &tree, new_node: &nodes[i].node);
157 live[i] = true;
158 }
159
160 struct rbit_node *it;
161 rbit_for_each(it, &tree) {
162 struct count_node *c = rbit_entry(it, struct count_node, node);
163 TEST_ASSERT_EQ(c->subtree_count, subtree_nodes(it));
164 }
165 }
166
167 vfree(nodes);
168 vfree(live);
169 return TEST_SUCCESS;
170}
171