1 /*
2 * Copyright © 2017 Faith Ekstrand
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
13 *
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
20 * DEALINGS IN THE SOFTWARE.
21 */
22
23 #undef NDEBUG
24
25 #include "rb_tree.h"
26
27 #include <assert.h>
28 #include <gtest/gtest.h>
29 #include <limits.h>
30
31 #include "macros.h"
32
33 /* A list of 100 random numbers from 1 to 100. The number 30 is explicitly
34 * missing from this list.
35 */
36 int test_numbers[] = {
37 26, 12, 35, 15, 48, 11, 39, 23, 40, 18,
38 39, 15, 40, 11, 42, 2, 5, 2, 28, 8,
39 10, 22, 23, 38, 47, 12, 31, 22, 26, 39,
40 9, 42, 32, 18, 36, 8, 32, 29, 9, 3,
41 32, 49, 23, 11, 43, 41, 22, 42, 6, 35,
42 38, 48, 5, 35, 39, 44, 22, 16, 16, 32,
43 31, 50, 48, 5, 50, 8, 2, 32, 27, 34,
44 42, 48, 22, 47, 10, 48, 39, 36, 28, 40,
45 32, 33, 21, 17, 14, 38, 27, 6, 25, 18,
46 32, 38, 19, 22, 20, 47, 50, 41, 29, 50,
47 };
48
49 #define NON_EXISTANT_NUMBER 30
50
51 struct rb_test_node {
52 int key;
53 struct rb_node node;
54 };
55
56 static int
rb_test_node_cmp_void(const struct rb_node * n,const void * v)57 rb_test_node_cmp_void(const struct rb_node *n, const void *v)
58 {
59 struct rb_test_node *tn = rb_node_data(struct rb_test_node, n, node);
60 return *(int *)v - tn->key;
61 }
62
63 static int
rb_test_node_cmp(const struct rb_node * a,const struct rb_node * b)64 rb_test_node_cmp(const struct rb_node *a, const struct rb_node *b)
65 {
66 struct rb_test_node *ta = rb_node_data(struct rb_test_node, a, node);
67 struct rb_test_node *tb = rb_node_data(struct rb_test_node, b, node);
68
69 return tb->key - ta->key;
70 }
71
72 static void
validate_tree_order(struct rb_tree * tree,unsigned expected_count)73 validate_tree_order(struct rb_tree *tree, unsigned expected_count)
74 {
75 struct rb_test_node *prev = NULL;
76 int max_val = -1;
77 unsigned count = 0;
78 rb_tree_foreach(struct rb_test_node, n, tree, node) {
79 /* Everything should be in increasing order */
80 assert(n->key >= max_val);
81 if (n->key > max_val) {
82 max_val = n->key;
83 } else {
84 /* Things should be stable, i.e., given equal keys, they should
85 * show up in the list in order of insertion. We insert them
86 * in the order they are in in the array.
87 */
88 assert(prev == NULL || prev < n);
89 }
90
91 prev = n;
92 count++;
93 }
94 assert(count == expected_count);
95
96 prev = NULL;
97 max_val = -1;
98 count = 0;
99 rb_tree_foreach_safe(struct rb_test_node, n, tree, node) {
100 /* Everything should be in increasing order */
101 assert(n->key >= max_val);
102 if (n->key > max_val) {
103 max_val = n->key;
104 } else {
105 /* Things should be stable, i.e., given equal keys, they should
106 * show up in the list in order of insertion. We insert them
107 * in the order they are in in the array.
108 */
109 assert(prev == NULL || prev < n);
110 }
111
112 prev = n;
113 count++;
114 }
115 assert(count == expected_count);
116
117 prev = NULL;
118 int min_val = INT_MAX;
119 count = 0;
120 rb_tree_foreach_rev(struct rb_test_node, n, tree, node) {
121 /* Everything should be in increasing order */
122 assert(n->key <= min_val);
123 if (n->key < min_val) {
124 min_val = n->key;
125 } else {
126 /* Things should be stable, i.e., given equal keys, they should
127 * show up in the list in order of insertion. We insert them
128 * in the order they are in in the array.
129 */
130 assert(prev == NULL || prev > n);
131 }
132
133 prev = n;
134 count++;
135 }
136 assert(count == expected_count);
137
138 prev = NULL;
139 min_val = INT_MAX;
140 count = 0;
141 rb_tree_foreach_rev_safe(struct rb_test_node, n, tree, node) {
142 /* Everything should be in increasing order */
143 assert(n->key <= min_val);
144 if (n->key < min_val) {
145 min_val = n->key;
146 } else {
147 /* Things should be stable, i.e., given equal keys, they should
148 * show up in the list in order of insertion. We insert them
149 * in the order they are in in the array.
150 */
151 assert(prev == NULL || prev > n);
152 }
153
154 prev = n;
155 count++;
156 }
157 assert(count == expected_count);
158 }
159
160 static void
validate_search(struct rb_tree * tree,int first_number,int last_number)161 validate_search(struct rb_tree *tree, int first_number,
162 int last_number)
163 {
164 struct rb_node *n;
165 struct rb_test_node *tn;
166
167 /* Search for all of the values */
168 for (int i = first_number; i <= last_number; i++) {
169 n = rb_tree_search(tree, &test_numbers[i], rb_test_node_cmp_void);
170 tn = rb_node_data(struct rb_test_node, n, node);
171 assert(tn->key == test_numbers[i]);
172
173 n = rb_tree_search_sloppy(tree, &test_numbers[i],
174 rb_test_node_cmp_void);
175 tn = rb_node_data(struct rb_test_node, n, node);
176 assert(tn->key == test_numbers[i]);
177 }
178
179 int missing_key = NON_EXISTANT_NUMBER;
180 n = rb_tree_search(tree, &missing_key, rb_test_node_cmp_void);
181 assert(n == NULL);
182
183 n = rb_tree_search_sloppy(tree, &missing_key, rb_test_node_cmp_void);
184 if (rb_tree_is_empty(tree)) {
185 assert(n == NULL);
186 } else {
187 assert(n != NULL);
188 tn = rb_node_data(struct rb_test_node, n, node);
189 assert(tn->key != missing_key);
190 if (tn->key < missing_key) {
191 struct rb_node *next = rb_node_next(n);
192 if (next != NULL) {
193 struct rb_test_node *tnext =
194 rb_node_data(struct rb_test_node, next, node);
195 assert(missing_key < tnext->key);
196 }
197 } else {
198 struct rb_node *prev = rb_node_prev(n);
199 if (prev != NULL) {
200 struct rb_test_node *tprev =
201 rb_node_data(struct rb_test_node, prev, node);
202 assert(missing_key > tprev->key);
203 }
204 }
205 }
206 }
207
TEST(RBTreeTest,InsertAndSearch)208 TEST(RBTreeTest, InsertAndSearch)
209 {
210 struct rb_test_node nodes[ARRAY_SIZE(test_numbers)];
211 struct rb_tree tree;
212
213 rb_tree_init(&tree);
214
215 for (unsigned i = 0; i < ARRAY_SIZE(test_numbers); i++) {
216 nodes[i].key = test_numbers[i];
217 rb_tree_insert(&tree, &nodes[i].node, rb_test_node_cmp);
218 rb_tree_validate(&tree);
219 validate_tree_order(&tree, i + 1);
220 validate_search(&tree, 0, i);
221 }
222
223 for (unsigned i = 0; i < ARRAY_SIZE(test_numbers); i++) {
224 rb_tree_remove(&tree, &nodes[i].node);
225 rb_tree_validate(&tree);
226 validate_tree_order(&tree, ARRAY_SIZE(test_numbers) - i - 1);
227 validate_search(&tree, i + 1, ARRAY_SIZE(test_numbers) - 1);
228 }
229 }
230
TEST(RBTreeTest,FindFirst)231 TEST(RBTreeTest, FindFirst)
232 {
233 struct rb_test_node nodes[100];
234 struct rb_tree tree;
235
236 rb_tree_init(&tree);
237
238 const int x = 13;
239
240 for (unsigned i = 0; i < ARRAY_SIZE(nodes); i++) {
241 nodes[i].key = x;
242 rb_tree_insert(&tree, &nodes[i].node, rb_test_node_cmp);
243 }
244
245 struct rb_node *n = rb_tree_search(&tree, &x, rb_test_node_cmp_void);
246
247 ASSERT_NE(nullptr, n);
248 EXPECT_EQ(nullptr, rb_node_prev(n));
249 EXPECT_EQ(n, rb_tree_first(&tree));
250 }
251
TEST(RBTreeTest,FindFirstOfMiddle)252 TEST(RBTreeTest, FindFirstOfMiddle)
253 {
254 struct rb_test_node nodes[3 * 33];
255 struct rb_tree tree;
256
257 rb_tree_init(&tree);
258
259 unsigned i;
260 for (i = 0; i < ARRAY_SIZE(nodes) / 3; i++) {
261 nodes[i].key = i * 13;
262 rb_tree_insert(&tree, &nodes[i].node, rb_test_node_cmp);
263 }
264
265 const int x = i * 13;
266 for (/* empty */; i < 2 * ARRAY_SIZE(nodes) / 3; i++) {
267 nodes[i].key = x;
268 rb_tree_insert(&tree, &nodes[i].node, rb_test_node_cmp);
269 }
270
271 for (/* empty */; i < ARRAY_SIZE(nodes); i++) {
272 nodes[i].key = i * 13;
273 rb_tree_insert(&tree, &nodes[i].node, rb_test_node_cmp);
274 }
275
276 struct rb_node *n = rb_tree_search(&tree, &x, rb_test_node_cmp_void);
277
278 ASSERT_NE(nullptr, n);
279
280 struct rb_node *prev = rb_node_prev(n);
281
282 ASSERT_NE(nullptr, prev);
283
284 EXPECT_NE(rb_test_node_cmp(prev, n), 0);
285 }
286
287 struct uinterval_test_node {
288 struct uinterval_node node;
289 };
290
291 static void
validate_interval_search(struct rb_tree * tree,struct uinterval_test_node * nodes,int first_node,int last_node,unsigned start,unsigned end)292 validate_interval_search(struct rb_tree *tree,
293 struct uinterval_test_node *nodes,
294 int first_node, int last_node,
295 unsigned start,
296 unsigned end)
297 {
298 /* Count the number of intervals intersecting */
299 unsigned actual_count = 0;
300 for (int i = first_node; i <= last_node; i++) {
301 if (nodes[i].node.interval.start <= end &&
302 nodes[i].node.interval.end >= start)
303 actual_count++;
304 }
305
306 /* iterate over matching intervals */
307 struct uinterval interval = { start, end };
308 unsigned max_val = 0;
309 struct uinterval_test_node *prev = NULL;
310 unsigned count = 0;
311 uinterval_tree_foreach (struct uinterval_test_node, n, interval, tree, node) {
312 assert(n->node.interval.start <= end &&
313 n->node.interval.end >= start);
314
315 /* Everything should be in increasing order */
316 assert(n->node.interval.start >= max_val);
317 if (n->node.interval.start > max_val) {
318 max_val = n->node.interval.start;
319 } else {
320 /* Things should be stable, i.e., given equal keys, they should
321 * show up in the list in order of insertion. We insert them
322 * in the order they are in in the array.
323 */
324 assert(prev == NULL || prev < n);
325 }
326
327 prev = n;
328 count++;
329 }
330
331 assert(count == actual_count);
332 }
333
TEST(IntervalTreeTest,InsertAndSearch)334 TEST(IntervalTreeTest, InsertAndSearch)
335 {
336 struct uinterval_test_node nodes[ARRAY_SIZE(test_numbers) / 2];
337 struct rb_tree tree;
338
339 rb_tree_init(&tree);
340
341 for (unsigned i = 0; 2 * i < ARRAY_SIZE(test_numbers); i++) {
342 nodes[i].node.interval.start = MIN2(test_numbers[2 * i], test_numbers[2 * i + 1]);
343 nodes[i].node.interval.end = MAX2(test_numbers[2 * i], test_numbers[2 * i + 1]);
344 uinterval_tree_insert(&tree, &nodes[i].node);
345 rb_tree_validate(&tree);
346 validate_interval_search(&tree, nodes, 0, i, 0, 100);
347 validate_interval_search(&tree, nodes, 0, i, 0, 50);
348 validate_interval_search(&tree, nodes, 0, i, 50, 100);
349 validate_interval_search(&tree, nodes, 0, i, 0, 2);
350 }
351
352 for (unsigned i = 0; 2 * i < ARRAY_SIZE(test_numbers); i++) {
353 uinterval_tree_remove(&tree, &nodes[i].node);
354 rb_tree_validate(&tree);
355 validate_interval_search(&tree, nodes, i + 1,
356 ARRAY_SIZE(test_numbers) / 2 - 1,
357 0, 100);
358 validate_interval_search(&tree, nodes, i + 1,
359 ARRAY_SIZE(test_numbers) / 2 - 1,
360 0, 50);
361 validate_interval_search(&tree, nodes, i + 1,
362 ARRAY_SIZE(test_numbers) / 2 - 1,
363 50, 100);
364 validate_interval_search(&tree, nodes, i + 1,
365 ARRAY_SIZE(test_numbers) / 2 - 1,
366 0, 2);
367 }
368 }
369