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