www.tinc-vpn.org Git - tinc/blob - test/unit/test_splay_tree.c

   1 #include "unittest.h"
   2 #include "../../src/splay_tree.h"
   3
   4 typedef struct node_t {
   5         int id;
   6 } node_t;
   7
   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));
  14         node->id = id;
  15         return node;
  16 }
  17
  18 static void free_node(node_t *node) {
  19         free(node);
  20 }
  21
  22 static int node_compare(const node_t *lhs, const node_t *rhs) {
  23         return lhs->id - rhs->id;
  24 }
  25
  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);
  28
  29         if(!tree) {
  30                 return -1;
  31         }
  32
  33         *state = tree;
  34         return 0;
  35 }
  36
  37 static int test_teardown(void **state) {
  38         splay_delete_tree(*state);
  39         return 0;
  40 }
  41
  42 static void test_tree_allocation_deletion(void **state) {
  43         (void)state;
  44
  45         splay_tree_t *tree = splay_alloc_tree((splay_compare_t) node_compare,
  46                                               (splay_action_t) free_node);
  47         assert_non_null(tree);
  48
  49         node_t *one = create_node(1);
  50         assert_non_null(splay_insert(tree, one));
  51
  52         node_t *two = create_node(2);
  53         assert_non_null(splay_insert(tree, two));
  54
  55         // AddressSanitizer will notify us if there's a leak
  56         splay_delete_tree(tree);
  57 }
  58
  59 static int multiply_tree_node_calls = 0;
  60
  61 static void increment_id_tree_node(node_t *node) {
  62         ++node->id;
  63         ++multiply_tree_node_calls;
  64 }
  65
  66 static int multiply_splay_node_calls = 0;
  67
  68 static void multiply_id_splay_node(splay_node_t *node) {
  69         node_t *t = node->data;
  70         t->id *= 2;
  71         ++multiply_splay_node_calls;
  72 }
  73
  74 static void test_splay_foreach(void **state) {
  75         splay_tree_t *tree = *state;
  76
  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);
  80
  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);
  84
  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);
  88
  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);
  92
  93         assert_int_equal(2, multiply_tree_node_calls);
  94         assert_int_equal(2, multiply_splay_node_calls);
  95 }
  96
  97 static void test_splay_each(void **state) {
  98         splay_tree_t *tree = *state;
  99
 100         node_t *one = create_node(1);
 101         node_t *two = create_node(2);
 102
 103         splay_insert(tree, one);
 104         splay_insert(tree, two);
 105
 106         // splay_each should iterate over all nodes
 107         for splay_each(node_t, n, tree) {
 108                 n->id = -n->id;
 109         }
 110
 111         assert_int_equal(-1, one->id);
 112         assert_int_equal(-2, two->id);
 113
 114         // splay_each should allow removal of the current node
 115         for splay_each(node_t, n, tree) {
 116                 splay_delete(tree, n);
 117         }
 118 }
 119
 120 static void test_splay_basic_ops(void **state) {
 121         splay_tree_t *tree = *state;
 122         node_t *node = create_node(1);
 123
 124         // Should not find anything if the tree is empty
 125         node_t *found_one = splay_search(tree, node);
 126         assert_null(found_one);
 127
 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);
 131
 132         // Should find after insertion
 133         found_one = splay_search(tree, node);
 134         assert_ptr_equal(node, found_one);
 135 }
 136
 137 static void test_splay_insert_before_after(void **state) {
 138         splay_tree_t *tree = *state;
 139
 140         node_t *one = create_node(1);
 141         splay_node_t *node_one = splay_insert(tree, one);
 142         assert_non_null(node_one);
 143
 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);
 148
 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);
 154
 155         splay_node_t *node_thr = splay_alloc_node();
 156         assert_non_null(node_thr);
 157         node_thr->data = create_node(3);
 158
 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);
 166 }
 167
 168 static void test_search_node(void **state) {
 169         splay_tree_t *tree = *state;
 170
 171         node_t *one = create_node(1);
 172         node_t *two = create_node(2);
 173
 174         splay_node_t *one_node = splay_search_node(tree, one);
 175         assert_null(one_node);
 176
 177         one_node = splay_insert(tree, one);
 178         assert_ptr_equal(one_node, splay_search_node(tree, one));
 179
 180         splay_node_t *two_node = splay_search_node(tree, two);
 181         assert_null(two_node);
 182
 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));
 186
 187         node_t *copy_one = create_node(1);
 188         node_t *copy_two = create_node(2);
 189
 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));
 193
 194         splay_delete(tree, two);
 195         assert_null(splay_search_node(tree, copy_one));
 196         assert_null(splay_search_node(tree, copy_two));
 197
 198         free_node(copy_one);
 199         free_node(copy_two);
 200 }
 201
 202 static void test_unlink(void **state) {
 203         splay_tree_t *tree = *state;
 204         node_t *one = create_node(1);
 205
 206         splay_node_t *node_one = splay_insert(tree, one);
 207
 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);
 211
 212         // Unlinking the same node should return NULL
 213         assert_null(splay_unlink(tree, one));
 214
 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);
 218 }
 219
 220 static void test_unlink_node(void **state) {
 221         splay_tree_t *tree = *state;
 222         node_t *one = create_node(1);
 223
 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));
 228
 229         splay_unlink_node(tree, node_one);
 230         assert_null(splay_search(tree, one));
 231         assert_null(splay_search_node(tree, one));
 232
 233         splay_free_node(tree, node_one);
 234 }
 235
 236 static void test_delete_node(void **state) {
 237         splay_tree_t *tree = *state;
 238         node_t *one = create_node(1);
 239
 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));
 244
 245         node_t *copy = create_node(1);
 246         assert_ptr_equal(one, splay_search(tree, copy));
 247
 248         splay_delete_node(tree, node_one);
 249         assert_null(splay_search(tree, copy));
 250
 251         free_node(copy);
 252 }
 253
 254 #define test_with_state(test_func) \
 255         cmocka_unit_test_setup_teardown((test_func), test_setup, test_teardown)
 256
 257 int main(void) {
 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),
 268         };
 269         return cmocka_run_group_tests(tests, NULL, NULL);
 270 }