1 /*
2 * Copyright (c) 2019 LK Trusty Authors. All Rights Reserved.
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining
5 * a copy of this software and associated documentation files
6 * (the "Software"), to deal in the Software without restriction,
7 * including without limitation the rights to use, copy, modify, merge,
8 * publish, distribute, sublicense, and/or sell copies of the Software,
9 * and to permit persons to whom the Software is furnished to do so,
10 * subject to the following conditions:
11 *
12 * The above copyright notice and this permission notice shall be
13 * included in all copies or substantial portions of the Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
16 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
17 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
18 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
19 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
20 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
21 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
22 */
23
24 #include <lib/binary_search_tree.h>
25 #include <lk/compiler.h>
26 #include <stdlib.h>
27
28 #include "gtest/gtest.h"
29
30 class BstTest : public testing::TestWithParam<bool> {
31 };
32
33 struct bst_test_entry {
34 struct bst_node node;
35 };
36
37 INSTANTIATE_TEST_SUITE_P(BstTestMirror, BstTest, testing::Bool());
38
bst_test_compare(struct bst_node * a,struct bst_node * b)39 static int bst_test_compare(struct bst_node *a, struct bst_node *b) {
40 if (BstTest::GetParam()) {
41 return a > b ? 1 : a < b ? -1 : 0;
42 } else {
43 return a < b ? 1 : a > b ? -1 : 0;
44 }
45 }
46
bst_test_search(struct bst_root * root,struct bst_node * node)47 static struct bst_node *bst_test_search(struct bst_root *root,
48 struct bst_node *node) {
49 return bst_search(root, node, bst_test_compare);
50 }
51
bst_node(struct bst_node nodes[],size_t index[],size_t i,size_t i_size)52 static struct bst_node *bst_node(struct bst_node nodes[], size_t index[],
53 size_t i, size_t i_size) {
54 if (BstTest::GetParam()) {
55 i = i_size - 1 - i;
56 }
57 if (index) {
58 i = index[i];
59 }
60 return &nodes[i];
61 }
62
operator <<(std::ostream & os,const struct bst_node * node)63 std::ostream& operator<<(std::ostream& os, const struct bst_node* node) {
64 return os <<
65 "Node (" << (void*)node << "):\n" <<
66 " Parent:" << (void*)node->parent << "\n" <<
67 " Rank: " << node->rank << "\n" <<
68 " Left child: " << (void*)node->child[0] << "\n" <<
69 " Right child: " << (void*)node->child[1] << "\n";
70 }
71
operator <<(std::ostream & os,const struct bst_root * root)72 std::ostream& operator<<(std::ostream& os, const struct bst_root* root) {
73 return os << "Root (" << (void*)root << ")\n";
74 }
75
76 /**
77 * bst_subtree_depth - Internal helper function
78 * @node: Root of a subtree.
79 *
80 * Return: Depth of subtree at @node, or 0 if @node is %NULL.
81 */
bst_subtree_depth(struct bst_node * node)82 static size_t bst_subtree_depth(struct bst_node *node) {
83 if (!node) {
84 return 0;
85 } else {
86 size_t child_depth[2];
87 for (size_t i = 0; i < 2; i++) {
88 child_depth[i] = bst_subtree_depth(node->child[i]);
89 }
90 return 1 + MAX(child_depth[0], child_depth[1]);
91 }
92 }
93
94 /**
95 * bst_depth - Debug function - return depth of tree
96 * @root: Tree.
97 *
98 * Return: Depth of @root.
99 */
bst_depth(struct bst_root * root)100 static size_t bst_depth(struct bst_root *root) {
101 return bst_subtree_depth(root->root);
102 }
103
bst_is_right_child(struct bst_node * node)104 static bool bst_is_right_child(struct bst_node *node) {
105 DEBUG_ASSERT(node);
106 DEBUG_ASSERT(!node->parent || node->parent->child[0] == node ||
107 node->parent->child[1] == node);
108 return node->parent && node->parent->child[1] == node;
109 }
110
bst_test_check_node(struct bst_root * root,struct bst_node * node)111 static void bst_test_check_node(struct bst_root *root, struct bst_node *node) {
112 if (node->parent) {
113 ASSERT_NE(root->root, node) << node << root;
114 ASSERT_EQ(node->parent->child[bst_is_right_child(node)], node) << node << root;
115 ASSERT_GE(node->parent->rank, node->rank + 1) << node << root;
116 ASSERT_LE(node->parent->rank, node->rank + 2) << node << root;
117 } else {
118 ASSERT_EQ(root->root, node) << node << root;;
119 }
120 if (!node->child[0] && !node->child[1]) {
121 ASSERT_EQ(node->rank, 1U) << node << root;;
122 }
123 }
124
print_rep(char ch,size_t count)125 static void print_rep(char ch, size_t count) {
126 for (size_t i = 0; i < count; i++) {
127 printf("%c", ch);
128 }
129 }
130
bst_test_node_num(struct bst_node * node,struct bst_node nodes[])131 static size_t bst_test_node_num(struct bst_node *node,
132 struct bst_node nodes[]) {
133 return nodes ? node - nodes : 0;
134 }
135
bst_test_print_node_at(struct bst_root * root,struct bst_node nodes[],size_t row,size_t col,size_t depth)136 static void bst_test_print_node_at(struct bst_root *root,
137 struct bst_node nodes[], size_t row,
138 size_t col, size_t depth) {
139 size_t space = (1 << (depth - row)) - 2;
140 struct bst_node *node = root->root;
141 for (size_t mask = 1 << row >> 1; node && mask; mask >>= 1) {
142 node = node->child[!!(col & mask)];
143 }
144 if (col) {
145 printf(" ");
146 }
147 print_rep(' ', space);
148 print_rep(node && node->child[0] ? '_' : ' ', space);
149 if (node) {
150 printf("%02zur%01zu", bst_test_node_num(node, nodes), node->rank);
151 } else {
152 printf(" ");
153 }
154 print_rep(node && node->child[1] ? '_' : ' ', space);
155 print_rep(' ', space);
156 /*
157 * ______________0004______________
158 * ______0003______ ______0003______
159 * __0002__ __0002__ __0002__ __0002__
160 * 0001 0001 0001 0001 0001 0001 0001 0001
161 */
162 }
163
bst_test_print_tree(struct bst_root * root,struct bst_node nodes[])164 static void bst_test_print_tree(struct bst_root *root, struct bst_node nodes[]) {
165 size_t depth = bst_depth(root);
166 printf("Tree depth %zu\n", depth);
167 for (size_t row = 0; row < depth; row++) {
168 for (size_t col = 0; col < 1 << row; col++) {
169 bst_test_print_node_at(root, nodes, row, col, depth);
170 }
171 printf("\n");
172 }
173 }
174
bst_test_check_tree_valid(struct bst_root * root)175 static void bst_test_check_tree_valid(struct bst_root *root) {
176 struct bst_node *node = 0;
177 while (true) {
178 node = bst_next(root, node);
179 if (!node) {
180 break;
181 }
182 bst_test_check_node(root, node);
183 }
184 if(::testing::Test::HasFailure()) {
185 bst_test_print_tree(root, NULL);
186 }
187 }
188
189 static void bst_test_check_sub_tree(struct bst_node *subtree,
190 struct bst_node nodes[],
191 struct bst_node *parent,
192 const char **expected_tree,
193 int is_right_child);
194
bst_test_check_child(struct bst_node * subtree,struct bst_node nodes[],const char ** expected_tree,int child)195 static void bst_test_check_child(struct bst_node *subtree,
196 struct bst_node nodes[],
197 const char **expected_tree,
198 int child) {
199 if (BstTest::GetParam()) {
200 child = !child;
201 }
202 while (isspace(**expected_tree)) {
203 (*expected_tree)++;
204 }
205
206 if (**expected_tree == '(') {
207 (*expected_tree)++;
208 bst_test_check_sub_tree(subtree->child[child], nodes, subtree,
209 expected_tree, child);
210 if (::testing::Test::HasFatalFailure()) {
211 return;
212 }
213 ASSERT_EQ(**expected_tree, ')');
214 (*expected_tree)++;
215 } else {
216 EXPECT_EQ(subtree->child[child], nullptr);
217 }
218
219 while (isspace(**expected_tree)) {
220 (*expected_tree)++;
221 }
222 }
223
bst_test_check_sub_tree(struct bst_node * subtree,struct bst_node nodes[],struct bst_node * parent,const char ** expected_tree,int is_right_child)224 static void bst_test_check_sub_tree(struct bst_node *subtree,
225 struct bst_node nodes[],
226 struct bst_node *parent,
227 const char **expected_tree,
228 int is_right_child) {
229 size_t index;
230 size_t rank;
231
232 if (!parent && **expected_tree == '\0') {
233 return;
234 }
235 ASSERT_NE(subtree, nullptr);
236
237 bst_test_check_child(subtree, nodes, expected_tree, 0);
238 if (::testing::Test::HasFatalFailure()) {
239 return;
240 }
241
242 index = strtoul(*expected_tree, (char **)expected_tree, 0);
243 ASSERT_EQ(**expected_tree, 'r');
244 (*expected_tree)++;
245 rank = strtoul(*expected_tree, (char **)expected_tree, 0);
246
247 EXPECT_EQ(subtree, &nodes[index]);
248 EXPECT_EQ(subtree->rank, rank);
249 EXPECT_EQ(subtree->parent, parent);
250 EXPECT_EQ(bst_is_right_child(subtree), is_right_child);
251
252 bst_test_check_child(subtree, nodes, expected_tree, 1);
253 if (::testing::Test::HasFatalFailure()) {
254 return;
255 }
256 }
257
258 /*
259 * Check if tree has expected structure and ranks. The expected tree is
260 * described by a string, "(left child) <node index>r<rank> (right child)". For
261 * example: "((0r1) 1r2 (2r1)) 3r3 ((4r1) 5r2)".
262 */
_bst_test_check_tree(struct bst_root * root,struct bst_node nodes[],const char * expected_tree)263 static void _bst_test_check_tree(struct bst_root *root, struct bst_node nodes[],
264 const char *expected_tree) {
265 bst_test_check_sub_tree(root->root, nodes, NULL, &expected_tree, 0);
266 EXPECT_EQ(*expected_tree, '\0');
267 if(::testing::Test::HasFailure()) {
268 bst_test_print_tree(root, nodes);
269 }
270 }
271
bst_test_check_array(struct bst_root * root,struct bst_node nodes[],size_t index[],size_t count,struct bst_node * left,struct bst_node * right)272 static void bst_test_check_array(struct bst_root *root,
273 struct bst_node nodes[],
274 size_t index[],
275 size_t count,
276 struct bst_node *left,
277 struct bst_node *right) {
278 for (size_t i = 0; i < count; i++) {
279 struct bst_node *node = bst_node(nodes, index, i, count);
280 EXPECT_EQ(bst_test_search(root, node), node) << "Node: " << (node - nodes) << "\n";
281 }
282
283 if (!count) {
284 EXPECT_EQ(bst_next(root, left), right);
285 EXPECT_EQ(bst_prev(root, right), left);
286 return;
287 }
288
289 EXPECT_EQ(bst_next(root, left), bst_node(nodes, index, 0, count));
290 EXPECT_EQ(bst_prev(root, bst_node(nodes, index, 0, count)), left);
291 for (size_t i = 0; i < count - 1; i++) {
292 struct bst_node *node = bst_node(nodes, index, i, count);
293 struct bst_node *next = bst_node(nodes, index, i + 1, count);
294 EXPECT_EQ(bst_next(root, node), next) << "node: " << (node - nodes) << ", next: " << (next - nodes);
295 EXPECT_EQ(bst_prev(root, next), node) << "next: " << (next - nodes) << ", node: " << (node - nodes);
296 }
297 EXPECT_EQ(bst_next(root, bst_node(nodes, index, count - 1, count)), right);
298 EXPECT_EQ(bst_prev(root, right), bst_node(nodes, index, count - 1, count));}
299
300 #define bst_countof(a) (sizeof(a) / sizeof((a))[0])
301
302 #define bst_test_check(root, nodes, items...) do { \
303 SCOPED_TRACE("bst_test_check"); \
304 size_t index[] = {items}; \
305 bst_test_check_array(root, nodes, index, bst_countof(index), NULL, NULL); \
306 if (HasFatalFailure()) return; \
307 } while(0)
308
309 #define bst_test_check_tree(root, node, treestr) do { \
310 SCOPED_TRACE("bst_test_check_tree"); \
311 _bst_test_check_tree(root, nodes, treestr); \
312 if (HasFatalFailure()) return; \
313 } while(0)
314
bst_test_insert_func(struct bst_root * root,struct bst_node * node)315 static void bst_test_insert_func(struct bst_root *root, struct bst_node *node) {
316 ASSERT_EQ(node->rank, 0U);
317 bst_insert(root, node, bst_test_compare);
318 bst_test_check_tree_valid(root);
319 EXPECT_EQ(bst_test_search(root, node), node);
320 }
321
322 #define bst_test_insert(root, node) do { \
323 SCOPED_TRACE(testing::Message() << "bst_insert" << node); \
324 bst_test_insert_func(root, node); \
325 if (HasFatalFailure()) return; \
326 } while(0)
327
328 #define bst_test_insert_check(root, nodes, insert, items...) do { \
329 bst_test_insert(root, &nodes[insert]); \
330 bst_test_check(root, nodes, items); \
331 } while(0)
332
333 #define bst_test_delete_check(root, nodes, insert, items...) do { \
334 bst_test_delete(root, &nodes[insert]); \
335 bst_test_check(root, nodes, items); \
336 } while(0)
337
338 #define bst_test_insert_check_tree(root, nodes, insert, treestr) do { \
339 bst_test_insert(root, &nodes[insert]); \
340 bst_test_check_tree(root, nodes, treestr); \
341 } while(0)
342
343 #define bst_test_delete_check_tree(root, nodes, insert, treestr) do { \
344 bst_test_delete(root, &nodes[insert]); \
345 bst_test_check_tree(root, nodes, treestr); \
346 } while(0)
347
bst_test_delete_func(struct bst_root * root,struct bst_node * node)348 static void bst_test_delete_func(struct bst_root *root, struct bst_node *node) {
349 bst_delete(root, node);
350 bst_test_check_tree_valid(root);
351 EXPECT_EQ(bst_test_search(root, node), nullptr);
352 }
353
354 #define bst_test_delete(root, node) do { \
355 SCOPED_TRACE(testing::Message() << "bst_delete" << node); \
356 bst_test_delete_func(root, node); \
357 if (HasFatalFailure()) return; \
358 } while(0)
359
360 /*
361 * Test init api
362 */
TEST(BstTest,InitRootValue)363 TEST(BstTest, InitRootValue) {
364 struct bst_root root = BST_ROOT_INITIAL_VALUE;
365 EXPECT_EQ(root.root, nullptr);
366 }
367
TEST(BstTest,InitRootFunction)368 TEST(BstTest, InitRootFunction) {
369 struct bst_root root;
370 memset(&root, 0xff, sizeof(root));
371 bst_root_initialize(&root);
372 EXPECT_EQ(root.root, nullptr);
373 }
374
TEST(BstTest,InitNodeValue)375 TEST(BstTest, InitNodeValue) {
376 struct bst_node node = BST_NODE_INITIAL_VALUE;
377 EXPECT_EQ(node.rank, 0U);
378 }
379
TEST(BstTest,InitNodeFnction)380 TEST(BstTest, InitNodeFnction) {
381 struct bst_node node;
382 memset(&node, 0xff, sizeof(node));
383 bst_node_initialize(&node);
384 EXPECT_EQ(node.rank, 0U);
385 }
386
387 /*
388 * Simple tests to check that api return expected results.
389 */
TEST_P(BstTest,InsertAscending)390 TEST_P(BstTest, InsertAscending) {
391 /* Insert nodes in ascending order (or decending for mirrored test) */
392 struct bst_root root = BST_ROOT_INITIAL_VALUE;
393 struct bst_node nodes[] = {[0 ... 14] = BST_NODE_INITIAL_VALUE};
394
395 bst_test_check(&root, nodes);
396 for (size_t i = 0; i < countof(nodes); i++) {
397 bst_test_insert(&root, &nodes[i]);
398 if (GetParam()) {
399 EXPECT_EQ(bst_prev(&root, &nodes[i]), nullptr);
400 } else {
401 EXPECT_EQ(bst_next(&root, &nodes[i]), nullptr);
402 }
403 }
404 bst_test_check_array(&root, nodes, NULL, countof(nodes), NULL, NULL);
405 EXPECT_GE(bst_depth(&root), 4U); /* Minimum depth for a binary tree */
406 EXPECT_LT(bst_depth(&root), 15U); /* We should have a tree, not a list */
407 EXPECT_LE(bst_depth(&root), 8U); /* RB tree should have depth <= 8 */
408 EXPECT_LE(bst_depth(&root), 6U); /* WAVL tree should have depth <= 6 */
409 }
410
TEST_P(BstTest,InsertBalanced)411 TEST_P(BstTest, InsertBalanced) {
412 /*
413 * ______7_____
414 * / \
415 * __3__ _11_
416 * / \ / \
417 * 1 5 9 13
418 * / \ / \ / \ / \
419 * 0 2 4 6 8 10 12 14
420 */
421 struct bst_root root = BST_ROOT_INITIAL_VALUE;
422 struct bst_node nodes[] = {[0 ... 14] = BST_NODE_INITIAL_VALUE};
423 size_t index[] = { 7, 3, 11, 1, 5, 9, 13, 0, 2, 4, 6, 8, 10, 12, 14 };
424 for (size_t i = 0; i < countof(index); i++) { \
425 bst_test_insert(&root, &nodes[index[i]]);
426 }
427 bst_test_check_array(&root, nodes, NULL, countof(nodes), NULL, NULL);
428 EXPECT_EQ(bst_depth(&root), 4U);
429 }
430
TEST_P(BstTest,DeleteOnlyEntry)431 TEST_P(BstTest, DeleteOnlyEntry) {
432 struct bst_root root = BST_ROOT_INITIAL_VALUE;
433 struct bst_node nodes[] = {[0 ... 0] = BST_NODE_INITIAL_VALUE};
434 bst_test_insert_check(&root, nodes, 0, 0);
435 /*
436 * 0
437 */
438 bst_test_delete_check(&root, nodes, 0);
439 }
440
TEST_P(BstTest,DeleteRootOneChild)441 TEST_P(BstTest, DeleteRootOneChild) {
442 struct bst_root root = BST_ROOT_INITIAL_VALUE;
443 struct bst_node nodes[] = {[0 ... 1] = BST_NODE_INITIAL_VALUE};
444 bst_test_insert_check(&root, nodes, 1, 1);
445 bst_test_insert_check(&root, nodes, 0, 0, 1);
446 /*
447 * 1
448 * /
449 * 0
450 */
451 bst_test_delete_check(&root, nodes, 1, 0);
452 }
453
TEST_P(BstTest,DeleteRootTwoChildren)454 TEST_P(BstTest, DeleteRootTwoChildren) {
455 struct bst_root root = BST_ROOT_INITIAL_VALUE;
456 struct bst_node nodes[] = {[0 ... 2] = BST_NODE_INITIAL_VALUE};
457
458 bst_test_insert_check(&root, nodes, 1, 1);
459 bst_test_insert_check(&root, nodes, 0, 0, 1);
460 bst_test_insert_check(&root, nodes, 2, 0, 1, 2);
461 /*
462 * 1
463 * / \
464 * 0 2
465 */
466 bst_test_delete_check(&root, nodes, 1, 0, 2);
467 }
468
TEST_P(BstTest,DeleteRootManyChildrenOneSide)469 TEST_P(BstTest, DeleteRootManyChildrenOneSide) {
470 struct bst_root root = BST_ROOT_INITIAL_VALUE;
471 struct bst_node nodes[] = {[0 ... 4] = BST_NODE_INITIAL_VALUE};
472
473 bst_test_insert_check(&root, nodes, 3, 3);
474 bst_test_insert_check(&root, nodes, 1, 1, 3);
475 bst_test_insert_check(&root, nodes, 4, 1, 3, 4);
476 bst_test_insert_check(&root, nodes, 0, 0, 1, 3, 4);
477 bst_test_insert_check(&root, nodes, 2, 0, 1, 2, 3, 4);
478 /*
479 * __3__
480 * / \
481 * 1 4
482 * / \
483 * 0 2
484 */
485 bst_test_delete_check(&root, nodes, 3, 0, 1, 2, 4);
486 }
487
TEST_P(BstTest,DeleteRootManyChildrenBothSides)488 TEST_P(BstTest, DeleteRootManyChildrenBothSides) {
489 struct bst_root root = BST_ROOT_INITIAL_VALUE;
490 struct bst_node nodes[] = {[0 ... 6] = BST_NODE_INITIAL_VALUE};
491
492 bst_test_insert_check(&root, nodes, 3, 3);
493 bst_test_insert_check(&root, nodes, 1, 1, 3);
494 bst_test_insert_check(&root, nodes, 5, 1, 3, 5);
495 bst_test_insert_check(&root, nodes, 0, 0, 1, 3, 5);
496 bst_test_insert_check(&root, nodes, 2, 0, 1, 2, 3, 5);
497 bst_test_insert_check(&root, nodes, 4, 0, 1, 2, 3, 4, 5);
498 bst_test_insert_check(&root, nodes, 6, 0, 1, 2, 3, 4, 5, 6);
499 /*
500 * __3__
501 * / \
502 * 1 5
503 * / \ / \
504 * 0 2 4 6
505 */
506 bst_test_delete_check(&root, nodes, 3, 0, 1, 2, 4, 5, 6);
507 }
508
TEST_P(BstTest,DeleteEdge1)509 TEST_P(BstTest, DeleteEdge1) {
510 struct bst_root root = BST_ROOT_INITIAL_VALUE;
511 struct bst_node nodes[] = {[0 ... 4] = BST_NODE_INITIAL_VALUE};
512
513 bst_test_insert_check(&root, nodes, 3, 3);
514 bst_test_insert_check(&root, nodes, 1, 1, 3);
515 bst_test_insert_check(&root, nodes, 4, 1, 3, 4);
516 bst_test_insert_check(&root, nodes, 0, 0, 1, 3, 4);
517 bst_test_insert_check(&root, nodes, 2, 0, 1, 2, 3, 4);
518 /*
519 * __3__
520 * / \
521 * 1 4
522 * / \
523 * 0 2
524 */
525
526 bst_test_delete_check(&root, nodes, 4, 0, 1, 2, 3);
527 }
528
TEST_P(BstTest,DeleteInternal)529 TEST_P(BstTest, DeleteInternal) {
530 struct bst_root root = BST_ROOT_INITIAL_VALUE;
531 struct bst_node nodes[] = {[0 ... 4] = BST_NODE_INITIAL_VALUE};
532
533 bst_test_insert_check(&root, nodes, 3, 3);
534 bst_test_insert_check(&root, nodes, 1, 1, 3);
535 bst_test_insert_check(&root, nodes, 4, 1, 3, 4);
536 bst_test_insert_check(&root, nodes, 0, 0, 1, 3, 4);
537 bst_test_insert_check(&root, nodes, 2, 0, 1, 2, 3, 4);
538 /*
539 * __3__
540 * / \
541 * 1 4
542 * / \
543 * 0 2
544 */
545 bst_test_delete_check(&root, nodes, 1, 0, 2, 3, 4);
546 }
547
TEST_P(BstTest,ForEveryEntry)548 TEST_P(BstTest, ForEveryEntry) {
549 struct bst_root root = BST_ROOT_INITIAL_VALUE;
550 struct bst_node nodes[] = {[0 ... 254] = BST_NODE_INITIAL_VALUE};
551 struct bst_test_entry *entry;
552
553 for (size_t i = 0; i < countof(nodes); i++) {
554 bst_test_insert(&root, &nodes[i]);
555 }
556
557 size_t i = 0;
558 bst_for_every_entry(&root, entry, struct bst_test_entry, node) {
559 EXPECT_EQ(&entry->node, bst_node(nodes, NULL, i, countof(nodes)));
560 i++;
561 }
562 EXPECT_EQ(i, countof(nodes));
563 }
564
TEST_P(BstTest,ForEveryEntryExplicitDelete)565 TEST_P(BstTest, ForEveryEntryExplicitDelete) {
566 struct bst_root root = BST_ROOT_INITIAL_VALUE;
567 struct bst_node nodes[] = {[0 ... 254] = BST_NODE_INITIAL_VALUE};
568 struct bst_test_entry *entry;
569
570 for (size_t i = 0; i < countof(nodes); i++) {
571 bst_test_insert(&root, &nodes[i]);
572 }
573
574 size_t i = 0;
575 bst_for_every_entry(&root, entry, struct bst_test_entry, node) {
576 EXPECT_EQ(&entry->node, bst_node(nodes, NULL, i, countof(nodes)));
577 i++;
578 bst_delete(&root, &entry->node);
579 }
580 EXPECT_EQ(i, countof(nodes));
581
582 EXPECT_EQ(bst_next(&root, NULL), nullptr);
583 }
584
TEST_P(BstTest,ForEveryEntryDelete)585 TEST_P(BstTest, ForEveryEntryDelete) {
586 struct bst_root root = BST_ROOT_INITIAL_VALUE;
587 struct bst_node nodes[] = {[0 ... 254] = BST_NODE_INITIAL_VALUE};
588 struct bst_test_entry *entry;
589
590 for (size_t i = 0; i < countof(nodes); i++) {
591 bst_test_insert(&root, &nodes[i]);
592 }
593
594 size_t i = 0;
595 bst_for_every_entry_delete(&root, entry, struct bst_test_entry, node) {
596 EXPECT_EQ(&entry->node, bst_node(nodes, NULL, i, countof(nodes)));
597 i++;
598 }
599 EXPECT_EQ(i, countof(nodes));
600
601 EXPECT_EQ(bst_next(&root, NULL), nullptr);
602 }
603
604 /*
605 * WAVL specific tests.
606 * Name describe non-mirrored test (/0).
607 * Swap left/right for mirrrored test run (/1).
608 */
TEST_P(BstTest,WAVLPromoteRootInsertLeft)609 TEST_P(BstTest, WAVLPromoteRootInsertLeft) {
610 struct bst_root root = BST_ROOT_INITIAL_VALUE;
611 struct bst_node nodes[] = {[0 ... 1] = BST_NODE_INITIAL_VALUE};
612
613 bst_test_insert_check_tree(&root, nodes, 1, "1r1");
614 bst_test_insert_check_tree(&root, nodes, 0, "(0r1) 1r2");
615 }
616
TEST_P(BstTest,WAVLPromote2InsertLeft)617 TEST_P(BstTest, WAVLPromote2InsertLeft) {
618 struct bst_root root = BST_ROOT_INITIAL_VALUE;
619 struct bst_node nodes[] = {[0 ... 3] = BST_NODE_INITIAL_VALUE};
620
621 bst_test_insert_check_tree(&root, nodes, 2, "2r1");
622 bst_test_insert_check_tree(&root, nodes, 1, "(1r1) 2r2");
623 bst_test_insert_check_tree(&root, nodes, 3, "(1r1) 2r2 (3r1)");
624 bst_test_insert_check_tree(&root, nodes, 0, "((0r1) 1r2) 2r3 (3r1)");
625 }
626
TEST_P(BstTest,WAVLRootRotateRightNoChildNodesInsertLeft)627 TEST_P(BstTest, WAVLRootRotateRightNoChildNodesInsertLeft) {
628 struct bst_root root = BST_ROOT_INITIAL_VALUE;
629 struct bst_node nodes[] = {[0 ... 2] = BST_NODE_INITIAL_VALUE};
630
631 bst_test_insert_check_tree(&root, nodes, 2, "2r1");
632 bst_test_insert_check_tree(&root, nodes, 1, "(1r1) 2r2");
633
634 /*
635 * 2r2* 1r2
636 * / / \
637 * 1r2 => 0r1 2r1
638 * /
639 * 0r1
640 */
641 bst_test_insert_check_tree(&root, nodes, 0, "(0r1) 1r2 (2r1)");
642 }
643
TEST_P(BstTest,WAVLRootRotateRightNoChildNodesInsertRight)644 TEST_P(BstTest, WAVLRootRotateRightNoChildNodesInsertRight) {
645 struct bst_root root = BST_ROOT_INITIAL_VALUE;
646 struct bst_node nodes[] = {[0 ... 2] = BST_NODE_INITIAL_VALUE};
647
648 bst_test_insert_check_tree(&root, nodes, 2, "2r1");
649 bst_test_insert_check_tree(&root, nodes, 0, "(0r1) 2r2");
650
651 /*
652 * ___2r2* 1r2
653 * / / \
654 * 0r2 => 0r1 2r1
655 * \
656 * 1r1
657 */
658 bst_test_insert_check_tree(&root, nodes, 1, "(0r1) 1r2 (2r1)");
659 }
660
661
TEST_P(BstTest,WAVLRootRotateRightWithChildNodesInsertLeft)662 TEST_P(BstTest, WAVLRootRotateRightWithChildNodesInsertLeft) {
663 struct bst_root root = BST_ROOT_INITIAL_VALUE;
664 struct bst_node nodes[] = {[0 ... 5] = BST_NODE_INITIAL_VALUE};
665
666 bst_test_insert_check_tree(&root, nodes, 4, "4r1");
667 bst_test_insert_check_tree(&root, nodes, 2, "(2r1) 4r2");
668 bst_test_insert_check_tree(&root, nodes, 5, "(2r1) 4r2 (5r1)");
669 bst_test_insert_check_tree(&root, nodes, 1, "((1r1) 2r2) 4r3 (5r1)");
670 bst_test_insert_check_tree(&root, nodes, 3, "((1r1) 2r2 (3r1)) 4r3 (5r1)");
671
672 /*
673 * ___4r3* 2r3___
674 * / \ / \
675 * 2r3 5r1 => 1r2 4r2
676 * / \ / / \
677 * 1r2 3r1 0r1 3r1 5r1
678 * /
679 * 0r1
680 */
681 bst_test_insert_check_tree(&root, nodes, 0, "((0r1) 1r2) 2r3 ((3r1) 4r2 (5r1))");
682 }
683
TEST_P(BstTest,WAVLNonRootRotateRightWithChildNodesInsertLeft)684 TEST_P(BstTest, WAVLNonRootRotateRightWithChildNodesInsertLeft) {
685 struct bst_root root = BST_ROOT_INITIAL_VALUE;
686 struct bst_node nodes[] = {[0 ... 8] = BST_NODE_INITIAL_VALUE};
687
688 bst_test_insert_check_tree(&root, nodes, 6, "6r1");
689 bst_test_insert_check_tree(&root, nodes, 4, "(4r1) 6r2");
690 bst_test_insert_check_tree(&root, nodes, 7, "(4r1) 6r2 (7r1)");
691 bst_test_insert_check_tree(&root, nodes, 2, "((2r1) 4r2) 6r3 (7r1)");
692 bst_test_insert_check_tree(&root, nodes, 8, "((2r1) 4r2) 6r3 (7r2 (8r1))");
693 bst_test_insert_check_tree(&root, nodes, 5, "((2r1) 4r2 (5r1)) 6r3 (7r2 (8r1))");
694 bst_test_insert_check_tree(&root, nodes, 1, "(((1r1) 2r2) 4r3 (5r1)) 6r4 (7r2 (8r1))");
695 bst_test_insert_check_tree(&root, nodes, 3, "(((1r1) 2r2 (3r1)) 4r3 (5r1)) 6r4 (7r2 (8r1))");
696
697 /*
698 * ___6r4... _________6r4...
699 * / /
700 * ___4r3* 2r3___
701 * / \ / \
702 * 2r3 5r1 => 1r2 4r1
703 * / \ / / \
704 * 1r2 3r1 0r1 3r1 5r1
705 * /
706 * 0r1
707 */
708 bst_test_insert_check_tree(&root, nodes, 0, "(((0r1) 1r2) 2r3 ((3r1) 4r2 (5r1))) 6r4 (7r2 (8r1))");
709 }
710
TEST_P(BstTest,WAVLRotateLeftRightSimpleInsertRight)711 TEST_P(BstTest, WAVLRotateLeftRightSimpleInsertRight) {
712 struct bst_root root = BST_ROOT_INITIAL_VALUE;
713 struct bst_node nodes[] = {[0 ... 5] = BST_NODE_INITIAL_VALUE};
714
715 bst_test_insert_check_tree(&root, nodes, 4, "4r1");
716 bst_test_insert_check_tree(&root, nodes, 1, "(1r1) 4r2");
717 bst_test_insert_check_tree(&root, nodes, 5, "(1r1) 4r2 (5r1)");
718 bst_test_insert_check_tree(&root, nodes, 0, "((0r1) 1r2) 4r3 (5r1)");
719 bst_test_insert_check_tree(&root, nodes, 2, "((0r1) 1r2 (2r1)) 4r3 (5r1)");
720
721 /*
722 * ______4r3 ___4r3 2r3___
723 * / \ / \ / \
724 * 1r3 5r1 2r3 5r1 1r2 4r2
725 * / \ => / \ => / / \
726 * 0r1 2r2 1r2 3r1 0r1 3r1 5r1
727 * \ /
728 * 3r1 0r1
729 */
730 bst_test_insert_check_tree(&root, nodes, 3, "((0r1) 1r2) 2r3 ((3r1) 4r2 (5r1))");
731 }
732
TEST_P(BstTest,WAVLRotateRightLeftSimpleInsertLeft)733 TEST_P(BstTest, WAVLRotateRightLeftSimpleInsertLeft) {
734 struct bst_root root = BST_ROOT_INITIAL_VALUE;
735 struct bst_node nodes[] = {[0 ... 5] = BST_NODE_INITIAL_VALUE};
736
737 bst_test_insert_check_tree(&root, nodes, 1, "1r1");
738 bst_test_insert_check_tree(&root, nodes, 0, "(0r1) 1r2");
739 bst_test_insert_check_tree(&root, nodes, 4, "(0r1) 1r2 (4r1)");
740 bst_test_insert_check_tree(&root, nodes, 3, "(0r1) 1r3 ((3r1) 4r2)");
741 bst_test_insert_check_tree(&root, nodes, 5, "(0r1) 1r3 ((3r1) 4r2 (5r1))");
742
743 /*
744 * 1r3______ 1r3___ ___3r3
745 * / \ / \ / \
746 * 0r1 4r3 0r1 3r3 1r2 4r2
747 * / \ => / \ => / \ \
748 * 3r2 5r1 2r1 4r2 0r1 2r1 5r1
749 * / \
750 * 2r1 5r1
751 */
752 bst_test_insert_check_tree(&root, nodes, 2, "((0r1) 1r2 (2r1)) 3r3 (4r2 (5r1))");
753 }
754
TEST_P(BstTest,WAVLDemoteLeaf)755 TEST_P(BstTest, WAVLDemoteLeaf) {
756 struct bst_root root = BST_ROOT_INITIAL_VALUE;
757 struct bst_node nodes[] = {[0 ... 1] = BST_NODE_INITIAL_VALUE};
758
759 bst_test_insert_check_tree(&root, nodes, 1, "1r1");
760 bst_test_insert_check_tree(&root, nodes, 0, "(0r1) 1r2");
761 /*
762 * 1r2 1r2* 1r1
763 * / => =>
764 * 0r1
765 */
766 bst_test_delete_check_tree(&root, nodes, 0, "1r1");
767 }
768
TEST_P(BstTest,WAVLDemoteNonLeaf)769 TEST_P(BstTest, WAVLDemoteNonLeaf) {
770 struct bst_root root = BST_ROOT_INITIAL_VALUE;
771 struct bst_node nodes[] = {[0 ... 3] = BST_NODE_INITIAL_VALUE};
772
773 bst_test_insert_check_tree(&root, nodes, 1, "1r1");
774 bst_test_insert_check_tree(&root, nodes, 0, "(0r1) 1r2");
775 bst_test_insert_check_tree(&root, nodes, 2, "(0r1) 1r2 (2r1)");
776 bst_test_insert_check_tree(&root, nodes, 3, "(0r1) 1r3 (2r2 (3r1))");
777 bst_test_delete_check_tree(&root, nodes, 3, "(0r1) 1r3 (2r1)");
778 /*
779 * 1r3 1r3 1r2
780 * / \ => \ => \
781 * 0r1 2r1 2r1 2r1
782 */
783 bst_test_delete_check_tree(&root, nodes, 0, "1r2 (2r1)");
784 }
785
TEST_P(BstTest,WAVLDoubleDemote)786 TEST_P(BstTest, WAVLDoubleDemote) {
787 struct bst_root root = BST_ROOT_INITIAL_VALUE;
788 struct bst_node nodes[] = {[0 ... 6] = BST_NODE_INITIAL_VALUE};
789
790 bst_test_insert_check_tree(&root, nodes, 2, "2r1");
791 bst_test_insert_check_tree(&root, nodes, 1, "(1r1) 2r2");
792 bst_test_insert_check_tree(&root, nodes, 4, "(1r1) 2r2 (4r1)");
793 bst_test_insert_check_tree(&root, nodes, 0, "((0r1) 1r2) 2r3 (4r1)");
794 bst_test_insert_check_tree(&root, nodes, 3, "((0r1) 1r2) 2r3 ((3r1) 4r2)");
795 bst_test_insert_check_tree(&root, nodes, 5, "((0r1) 1r2) 2r3 ((3r1) 4r2 (5r1))");
796 bst_test_insert_check_tree(&root, nodes, 6, "((0r1) 1r2) 2r4 ((3r1) 4r3 (5r2 (6r1)))");
797 bst_test_delete_check_tree(&root, nodes, 6, "((0r1) 1r2) 2r4 ((3r1) 4r3 (5r1))");
798 /*
799 * 2r4___ 2r4___ 2r3___
800 * / \ => / \ => / \
801 * 1r2 4r3 1r1 4r3 1r1 4r2
802 * / / \ / \ / \
803 * 0r1 3r1 5r1 3r1 5r1 3r1 5r1
804 */
805 bst_test_delete_check_tree(&root, nodes, 0, "(1r1) 2r3 ((3r1) 4r2 (5r1))");
806 }
807
TEST_P(BstTest,WAVLRotateNoChildrenAfterDelete)808 TEST_P(BstTest, WAVLRotateNoChildrenAfterDelete) {
809 struct bst_root root = BST_ROOT_INITIAL_VALUE;
810 struct bst_node nodes[] = {[0 ... 3] = BST_NODE_INITIAL_VALUE};
811
812 bst_test_insert_check_tree(&root, nodes, 1, "1r1");
813 bst_test_insert_check_tree(&root, nodes, 0, "(0r1) 1r2");
814 bst_test_insert_check_tree(&root, nodes, 2, "(0r1) 1r2 (2r1)");
815 bst_test_insert_check_tree(&root, nodes, 3, "(0r1) 1r3 (2r2 (3r1))");
816 /*
817 * 1r3 1r3 2r3
818 * / \ \ / \
819 * 0r1 2r2 => 2r2 => 1r1 3r1
820 * \ \
821 * 3r1 3r1
822 *
823 * (2r2 would also be a valid wavl tree after this rotate, but that does
824 * not work in the general case where 2 could have started with a left
825 * child)
826 */
827 bst_test_delete_check_tree(&root, nodes, 0, "(1r1) 2r3 (3r1)");
828 }
829
TEST_P(BstTest,WAVLRotateWithChildren1AfterDelete)830 TEST_P(BstTest, WAVLRotateWithChildren1AfterDelete) {
831 struct bst_root root = BST_ROOT_INITIAL_VALUE;
832 struct bst_node nodes[] = {[0 ... 6] = BST_NODE_INITIAL_VALUE};
833
834 bst_test_insert_check_tree(&root, nodes, 2, "2r1");
835 bst_test_insert_check_tree(&root, nodes, 1, "(1r1) 2r2");
836 bst_test_insert_check_tree(&root, nodes, 4, "(1r1) 2r2 (4r1)");
837 bst_test_insert_check_tree(&root, nodes, 0, "((0r1) 1r2) 2r3 (4r1)");
838 bst_test_insert_check_tree(&root, nodes, 3, "((0r1) 1r2) 2r3 ((3r1) 4r2)");
839 bst_test_insert_check_tree(&root, nodes, 5, "((0r1) 1r2) 2r3 ((3r1) 4r2 (5r1))");
840 bst_test_insert_check_tree(&root, nodes, 6, "((0r1) 1r2) 2r4 ((3r1) 4r3 (5r2 (6r1)))");
841 /*
842 * 2r4___ 2r4___ ___4r4
843 * / \ / \ / \
844 * 1r2 4r3 1r1 4r3 2r2 5r2
845 * / / \ => / \ => / \ \
846 * 0r1 3r1 5r2 3r1 5r2 1r1 3r1 6r1
847 * \ \
848 * 6r1 6r1
849 *
850 * (4r3/2r2 would also be a valid wavl tree after this rotate, but that does
851 * not work in the general case where 3r1 could be 3r2. 2r3 would also be
852 * valid, but since we have to demote it when it is a leaf node, the current
853 * implementation demotes it when possible)
854 */
855 bst_test_delete_check_tree(&root, nodes, 0, "((1r1) 2r2 (3r1)) 4r4 (5r2 (6r1))");
856 }
857
TEST_P(BstTest,WAVLRotateWithChildren2AfterDelete)858 TEST_P(BstTest, WAVLRotateWithChildren2AfterDelete) {
859 struct bst_root root = BST_ROOT_INITIAL_VALUE;
860 struct bst_node nodes[] = {[0 ... 7] = BST_NODE_INITIAL_VALUE};
861
862 bst_test_insert_check_tree(&root, nodes, 2, "2r1");
863 bst_test_insert_check_tree(&root, nodes, 1, "(1r1) 2r2");
864 bst_test_insert_check_tree(&root, nodes, 5, "(1r1) 2r2 (5r1)");
865 bst_test_insert_check_tree(&root, nodes, 0, "((0r1) 1r2) 2r3 (5r1)");
866 bst_test_insert_check_tree(&root, nodes, 4, "((0r1) 1r2) 2r3 ((4r1) 5r2)");
867 bst_test_insert_check_tree(&root, nodes, 6, "((0r1) 1r2) 2r3 ((4r1) 5r2 (6r1))");
868 bst_test_insert_check_tree(&root, nodes, 3, "((0r1) 1r2) 2r4 (((3r1) 4r2) 5r3 (6r1))");
869 bst_test_insert_check_tree(&root, nodes, 7, "((0r1) 1r2) 2r4 (((3r1) 4r2) 5r3 (6r2 (7r1)))");
870 /*
871 * 2r4_____ 2r4______ ______5r4
872 * / \ / \ / \
873 * 1r2 5r3 1r1 5r3 2r3___ 6r2
874 * / / \ => / \ => / \ \
875 * 0r1 4r2 6r2 4r2 6r2 1r1 4r2 7r1
876 * / \ / \ /
877 * 3r1 7r1 3r1 7r1 3r1
878 */
879 bst_test_delete_check_tree(&root, nodes, 0, "((1r1) 2r3 ((3r1) 4r2)) 5r4 (6r2 (7r1))");
880 }
881
TEST_P(BstTest,WAVLDoubleRotateWithChildren2AfterDelete)882 TEST_P(BstTest, WAVLDoubleRotateWithChildren2AfterDelete) {
883 /*
884 * Swap nodes @up2 and @up1 then @up2 and @down
885 * (pictured for up_was_right_child==false):
886 *
887 * down(0) down up2(0)
888 * / \ / \ / \
889 * up1(-1) D(-3) up2 D up1(-2) down(-2)
890 * / \ / \ / \ / \
891 * A(-3) up2(-2) up1 C A(-3) B C D(-3)
892 * / \ / \
893 * B C A(-3) B
894 */
895 struct bst_root root = BST_ROOT_INITIAL_VALUE;
896 struct bst_node nodes[] = {[0 ... 7] = BST_NODE_INITIAL_VALUE};
897
898 bst_test_insert_check_tree(&root, nodes, 2, "2r1");
899 bst_test_insert_check_tree(&root, nodes, 1, "(1r1) 2r2");
900 bst_test_insert_check_tree(&root, nodes, 6, "(1r1) 2r2 (6r1)");
901 bst_test_insert_check_tree(&root, nodes, 0, "((0r1) 1r2) 2r3 (6r1)");
902 bst_test_insert_check_tree(&root, nodes, 4, "((0r1) 1r2) 2r3 ((4r1) 6r2)");
903 bst_test_insert_check_tree(&root, nodes, 7, "((0r1) 1r2) 2r3 ((4r1) 6r2 (7r1))");
904 bst_test_insert_check_tree(&root, nodes, 3, "((0r1) 1r2) 2r4 (((3r1) 4r2) 6r3 (7r1))");
905 bst_test_insert_check_tree(&root, nodes, 5, "((0r1) 1r2) 2r4 (((3r1) 4r2 (5r1)) 6r3 (7r1))");
906 /*
907 * 2r4_________ 2r4___ ___4r4___
908 * / \ / \ / \
909 * 1r1 ___6r3 1r1 4r3___ 2r2 6r2
910 * / \ => / \ => / \ / \
911 * 4r2 7r1 3r1 6r2 1r1 3r1 5r1 7r1
912 * / \ / \
913 * 3r1 5r1 5r1 7r1
914 */
915 bst_test_delete_check_tree(&root, nodes, 0, "((1r1) 2r2 (3r1)) 4r4 ((5r1) 6r2 (7r1))");
916 }
917
TEST_P(BstTest,RandomInsert)918 TEST_P(BstTest, RandomInsert) {
919 struct bst_root root = BST_ROOT_INITIAL_VALUE;
920 struct bst_node nodes[] = {[0 ... 999] = BST_NODE_INITIAL_VALUE};
921 for (size_t i = 0; i < countof(nodes);) {
922 struct bst_node *node = &nodes[lrand48() % countof(nodes)];
923 if (!node->rank) {
924 bst_test_insert(&root, node);
925 ASSERT_GE(node->rank, 1U);
926 EXPECT_EQ(bst_test_search(&root, node), node);
927 i++;
928 }
929 }
930 }
931
TEST_P(BstTest,RandomInsertRandomDelete)932 TEST_P(BstTest, RandomInsertRandomDelete) {
933 struct bst_root root = BST_ROOT_INITIAL_VALUE;
934 struct bst_node nodes[] = {[0 ... 999] = BST_NODE_INITIAL_VALUE};
935 for (size_t i = 0; i < countof(nodes);) {
936 struct bst_node *node = &nodes[lrand48() % countof(nodes)];
937 if (!node->rank) {
938 bst_test_insert(&root, node);
939 ASSERT_GE(node->rank, 1U);
940 EXPECT_EQ(bst_test_search(&root, node), node);
941 i++;
942 }
943 }
944 for (size_t i = 0; i < countof(nodes);) {
945 struct bst_node *node = &nodes[lrand48() % countof(nodes)];
946 if (node->rank) {
947 bst_test_delete(&root, node);
948 EXPECT_EQ(node->rank, 0U);
949 EXPECT_EQ(bst_test_search(&root, node), nullptr) << node;
950 i++;
951 }
952 }
953 }
954
TEST_P(BstTest,RandomInsertDelete)955 TEST_P(BstTest, RandomInsertDelete) {
956 struct bst_root root = BST_ROOT_INITIAL_VALUE;
957 struct bst_node nodes[] = {[0 ... 499] = BST_NODE_INITIAL_VALUE};
958 for (size_t i = 0; i < countof(nodes) * 100; i++) {
959 struct bst_node *node = &nodes[lrand48() % countof(nodes)];
960 if (node->rank) {
961 bst_test_delete(&root, node);
962 ASSERT_EQ(node->rank, 0U);
963 EXPECT_EQ(bst_test_search(&root, node), nullptr);
964 } else {
965 bst_test_insert(&root, node);
966 EXPECT_GE(node->rank, 1U);
967 EXPECT_EQ(bst_test_search(&root, node), node);
968 }
969 }
970 }
971