1#include "structures/tests/test_internal.h"
2
3TEST_GROUP_DECLARE(splay);
4
5struct test_splay_node {
6 int key;
7 struct splay_node node;
8};
9
10static int test_splay_cmp(const struct splay_node *a,
11 const struct splay_node *b) {
12 int ka = splay_entry(a, struct test_splay_node, node)->key;
13 int kb = splay_entry(b, struct test_splay_node, node)->key;
14 return (ka > kb) - (ka < kb);
15}
16
17static int test_splay_cmp_key(const struct splay_node *a, const void *key) {
18 int ka = splay_entry(a, struct test_splay_node, node)->key;
19 int kk = *(const int *) key;
20 return (ka > kk) - (ka < kk);
21}
22
23static const struct splay_node_ops test_splay_ops = {
24 .cmp = test_splay_cmp,
25 .cmp_key = test_splay_cmp_key,
26};
27
28static bool verify_splay_bst_invariants(struct splay_node *n, int *min,
29 int *max) {
30 if (!n) {
31 return true;
32 }
33
34 int k = splay_entry(n, struct test_splay_node, node)->key;
35
36 if (min && k <= *min) {
37 return false;
38 }
39 if (max && k >= *max) {
40 return false;
41 }
42
43 if (n->left) {
44 if (n->left->parent != n) {
45 return false;
46 }
47 if (!verify_splay_bst_invariants(n: n->left, min, max: &k)) {
48 return false;
49 }
50 }
51 if (n->right) {
52 if (n->right->parent != n) {
53 return false;
54 }
55 if (!verify_splay_bst_invariants(n: n->right, min: &k, max)) {
56 return false;
57 }
58 }
59
60 return true;
61}
62
63TEST_DECLARE_UNIT(splay, basic_operations) {
64 struct splay_tree tree;
65 splay_tree_init(tree: &tree, ops: &test_splay_ops);
66
67 struct test_splay_node nodes[8];
68 int keys[8] = {50, 20, 70, 10, 30, 60, 80, 25};
69
70 for (int i = 0; i < 8; i++) {
71 nodes[i].key = keys[i];
72 splay_insert(tree: &tree, node: &nodes[i].node);
73 TEST_ASSERT(verify_splay_bst_invariants(tree.root, NULL, NULL));
74 /* The newly inserted node should be at the root */
75 TEST_ASSERT_EQ(tree.root, &nodes[i].node);
76 }
77
78 /* Verify search & splay-to-root property */
79 for (int i = 0; i < 8; i++) {
80 struct splay_node *found = splay_find(tree: &tree, key: &keys[i]);
81 TEST_ASSERT_NONNULL(found);
82 TEST_ASSERT_EQ(found, &nodes[i].node);
83 TEST_ASSERT_EQ(tree.root, found);
84 TEST_ASSERT(verify_splay_bst_invariants(tree.root, NULL, NULL));
85 }
86
87 int missing = 999;
88 TEST_ASSERT_NULL(splay_find(&tree, &missing));
89
90 /* In-order traversal must be ascending */
91 struct splay_node *cur = splay_first(tree: &tree);
92 int prev = -1;
93 int count = 0;
94 while (cur) {
95 int k = splay_entry(cur, struct test_splay_node, node)->key;
96 TEST_ASSERT_GT_S(k, prev);
97 prev = k;
98 count++;
99 cur = splay_next(node: cur);
100 }
101 TEST_ASSERT_EQ(count, 8);
102
103 /* Test removal */
104 for (int i = 0; i < 8; i++) {
105 splay_remove(tree: &tree, node: &nodes[i].node);
106 TEST_ASSERT(verify_splay_bst_invariants(tree.root, NULL, NULL));
107 TEST_ASSERT_NULL(splay_find(&tree, &keys[i]));
108 }
109
110 TEST_ASSERT(splay_tree_empty(&tree));
111
112 return TEST_SUCCESS;
113}
114