2 #include "../../src/splay_tree.h"
4 typedef struct node_t {
8 // We cannot use test_malloc / test_free here, because the library seems to be
9 // checking for leaks right after running each test, before doing teardown,
10 // which results in a bunch of spurious test failures. We rely on teardown to
11 // clean up after us. Valgrind and ASAN show no leaks.
12 static node_t *create_node(int id) {
13 node_t *node = malloc(sizeof(node_t));
18 static void free_node(node_t *node) {
22 static int node_compare(const node_t *lhs, const node_t *rhs) {
23 return lhs->id - rhs->id;
26 static int test_setup(void **state) {
27 splay_tree_t *tree = splay_alloc_tree((splay_compare_t) node_compare, (splay_action_t) free_node);
37 static int test_teardown(void **state) {
38 splay_delete_tree(*state);
42 static void test_tree_allocation_deletion(void **state) {
45 splay_tree_t *tree = splay_alloc_tree((splay_compare_t) node_compare,
46 (splay_action_t) free_node);
47 assert_non_null(tree);
49 node_t *one = create_node(1);
50 assert_non_null(splay_insert(tree, one));
52 node_t *two = create_node(2);
53 assert_non_null(splay_insert(tree, two));
55 // AddressSanitizer will notify us if there's a leak
56 splay_delete_tree(tree);
59 static int multiply_tree_node_calls = 0;
61 static void increment_id_tree_node(node_t *node) {
63 ++multiply_tree_node_calls;
66 static int multiply_splay_node_calls = 0;
68 static void multiply_id_splay_node(splay_node_t *node) {
69 node_t *t = node->data;
71 ++multiply_splay_node_calls;
74 static void test_splay_foreach(void **state) {
75 splay_tree_t *tree = *state;
77 node_t *one = create_node(1);
78 splay_node_t *node_one = splay_insert(tree, one);
79 assert_ptr_equal(one, node_one->data);
81 node_t *two = create_node(5);
82 splay_node_t *node_two = splay_insert(tree, two);
83 assert_ptr_equal(two, node_two->data);
85 splay_foreach(tree, (splay_action_t) increment_id_tree_node);
86 assert_int_equal(2, one->id);
87 assert_int_equal(6, two->id);
89 splay_foreach_node(tree, (splay_action_t) multiply_id_splay_node);
90 assert_int_equal(4, one->id);
91 assert_int_equal(12, two->id);
93 assert_int_equal(2, multiply_tree_node_calls);
94 assert_int_equal(2, multiply_splay_node_calls);
97 static void test_splay_each(void **state) {
98 splay_tree_t *tree = *state;
100 node_t *one = create_node(1);
101 node_t *two = create_node(2);
103 splay_insert(tree, one);
104 splay_insert(tree, two);
106 // splay_each should iterate over all nodes
107 for splay_each(node_t, n, tree) {
111 assert_int_equal(-1, one->id);
112 assert_int_equal(-2, two->id);
114 // splay_each should allow removal of the current node
115 for splay_each(node_t, n, tree) {
116 splay_delete(tree, n);
120 static void test_splay_basic_ops(void **state) {
121 splay_tree_t *tree = *state;
122 node_t *node = create_node(1);
124 // Should not find anything if the tree is empty
125 node_t *found_one = splay_search(tree, node);
126 assert_null(found_one);
128 // Insertion should return a non-NULL node with `data` pointing to our `tree_node`
129 splay_node_t *node_one = splay_insert(tree, node);
130 assert_ptr_equal(node, node_one->data);
132 // Should find after insertion
133 found_one = splay_search(tree, node);
134 assert_ptr_equal(node, found_one);
137 static void test_splay_insert_before_after(void **state) {
138 splay_tree_t *tree = *state;
140 node_t *one = create_node(1);
141 splay_node_t *node_one = splay_insert(tree, one);
142 assert_non_null(node_one);
144 // splay_insert_before should set up `prev` and `next` pointers
145 splay_node_t *node_two = splay_alloc_node();
146 assert_non_null(node_two);
147 node_two->data = create_node(2);
149 splay_insert_after(tree, node_one, node_two);
150 assert_null(node_one->prev);
151 assert_ptr_equal(node_one->next, node_two);
152 assert_ptr_equal(node_two->prev, node_one);
153 assert_null(node_two->next);
155 splay_node_t *node_thr = splay_alloc_node();
156 assert_non_null(node_thr);
157 node_thr->data = create_node(3);
159 splay_insert_after(tree, node_two, node_thr);
160 assert_null(node_one->prev);
161 assert_ptr_equal(node_one->next, node_two);
162 assert_ptr_equal(node_two->prev, node_one);
163 assert_ptr_equal(node_two->next, node_thr);
164 assert_ptr_equal(node_thr->prev, node_two);
165 assert_null(node_thr->next);
168 static void test_search_node(void **state) {
169 splay_tree_t *tree = *state;
171 node_t *one = create_node(1);
172 node_t *two = create_node(2);
174 splay_node_t *one_node = splay_search_node(tree, one);
175 assert_null(one_node);
177 one_node = splay_insert(tree, one);
178 assert_ptr_equal(one_node, splay_search_node(tree, one));
180 splay_node_t *two_node = splay_search_node(tree, two);
181 assert_null(two_node);
183 two_node = splay_insert(tree, two);
184 assert_ptr_equal(one_node, splay_search_node(tree, one));
185 assert_ptr_equal(two_node, splay_search_node(tree, two));
187 node_t *copy_one = create_node(1);
188 node_t *copy_two = create_node(2);
190 splay_delete(tree, one);
191 assert_null(splay_search_node(tree, copy_one));
192 assert_ptr_equal(two_node, splay_search_node(tree, two));
194 splay_delete(tree, two);
195 assert_null(splay_search_node(tree, copy_one));
196 assert_null(splay_search_node(tree, copy_two));
202 static void test_unlink(void **state) {
203 splay_tree_t *tree = *state;
204 node_t *one = create_node(1);
206 splay_node_t *node_one = splay_insert(tree, one);
208 // Unlink should return the unlinked node
209 splay_node_t *unlinked_one = splay_unlink(tree, one);
210 assert_ptr_equal(one, unlinked_one->data);
212 // Unlinking the same node should return NULL
213 assert_null(splay_unlink(tree, one));
215 // Inserting it back should return the same node
216 unlinked_one = splay_insert_node(tree, unlinked_one);
217 assert_ptr_equal(node_one, unlinked_one);
220 static void test_unlink_node(void **state) {
221 splay_tree_t *tree = *state;
222 node_t *one = create_node(1);
224 splay_node_t *node_one = splay_insert(tree, one);
225 assert_ptr_equal(one, node_one->data);
226 assert_ptr_equal(one, splay_search(tree, one));
227 assert_ptr_equal(node_one, splay_search_node(tree, one));
229 splay_unlink_node(tree, node_one);
230 assert_null(splay_search(tree, one));
231 assert_null(splay_search_node(tree, one));
233 splay_free_node(tree, node_one);
236 static void test_delete_node(void **state) {
237 splay_tree_t *tree = *state;
238 node_t *one = create_node(1);
240 splay_node_t *node_one = splay_insert(tree, one);
241 assert_ptr_equal(one, node_one->data);
242 assert_ptr_equal(one, splay_search(tree, one));
243 assert_ptr_equal(node_one, splay_search_node(tree, one));
245 node_t *copy = create_node(1);
246 assert_ptr_equal(one, splay_search(tree, copy));
248 splay_delete_node(tree, node_one);
249 assert_null(splay_search(tree, copy));
254 #define test_with_state(test_func) \
255 cmocka_unit_test_setup_teardown((test_func), test_setup, test_teardown)
258 const struct CMUnitTest tests[] = {
259 cmocka_unit_test(test_tree_allocation_deletion),
260 test_with_state(test_splay_basic_ops),
261 test_with_state(test_splay_insert_before_after),
262 test_with_state(test_splay_foreach),
263 test_with_state(test_splay_each),
264 test_with_state(test_search_node),
265 test_with_state(test_unlink),
266 test_with_state(test_unlink_node),
267 test_with_state(test_delete_node),
269 return cmocka_run_group_tests(tests, NULL, NULL);