1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/tests/test_tree.c Mon Jan 22 19:34:38 2024 +0100 1.3 @@ -0,0 +1,172 @@ 1.4 +/* 1.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 1.6 + * 1.7 + * Copyright 2023 Mike Becker, Olaf Wintermann All rights reserved. 1.8 + * 1.9 + * Redistribution and use in source and binary forms, with or without 1.10 + * modification, are permitted provided that the following conditions are met: 1.11 + * 1.12 + * 1. Redistributions of source code must retain the above copyright 1.13 + * notice, this list of conditions and the following disclaimer. 1.14 + * 1.15 + * 2. Redistributions in binary form must reproduce the above copyright 1.16 + * notice, this list of conditions and the following disclaimer in the 1.17 + * documentation and/or other materials provided with the distribution. 1.18 + * 1.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 1.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 1.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 1.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 1.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 1.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 1.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 1.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 1.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 1.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 1.29 + * POSSIBILITY OF SUCH DAMAGE. 1.30 + */ 1.31 + 1.32 +#include "cx/tree.h" 1.33 + 1.34 +#include "cx/test.h" 1.35 + 1.36 +typedef struct tree_node { 1.37 + struct tree_node *parent; 1.38 + struct tree_node *next; 1.39 + struct tree_node *prev; 1.40 + struct tree_node *children; 1.41 + int data; 1.42 +} tree_node; 1.43 + 1.44 +#define tree_node_layout \ 1.45 + offsetof(tree_node, parent), offsetof(tree_node, children), \ 1.46 + offsetof(tree_node, prev), offsetof(tree_node, next) 1.47 + 1.48 +CX_TEST(test_tree_link_new_child) { 1.49 + tree_node parent = {0}; 1.50 + tree_node child = {0}; 1.51 + 1.52 + CX_TEST_DO { 1.53 + cx_tree_link(&parent, &child, tree_node_layout); 1.54 + CX_TEST_ASSERT(parent.next == NULL); 1.55 + CX_TEST_ASSERT(parent.prev == NULL); 1.56 + CX_TEST_ASSERT(parent.parent == NULL); 1.57 + CX_TEST_ASSERT(parent.children == &child); 1.58 + CX_TEST_ASSERT(child.parent == &parent); 1.59 + CX_TEST_ASSERT(child.next == NULL); 1.60 + CX_TEST_ASSERT(child.prev == NULL); 1.61 + CX_TEST_ASSERT(child.children == NULL); 1.62 + } 1.63 +} 1.64 + 1.65 +CX_TEST(test_tree_link_add_child) { 1.66 + tree_node parent = {0}; 1.67 + tree_node child1 = {0}; 1.68 + tree_node child2 = {0}; 1.69 + tree_node child3 = {0}; 1.70 + 1.71 + CX_TEST_DO { 1.72 + cx_tree_link(&parent, &child1, tree_node_layout); 1.73 + cx_tree_link(&parent, &child2, tree_node_layout); 1.74 + cx_tree_link(&parent, &child3, tree_node_layout); 1.75 + CX_TEST_ASSERT(parent.next == NULL); 1.76 + CX_TEST_ASSERT(parent.prev == NULL); 1.77 + CX_TEST_ASSERT(parent.parent == NULL); 1.78 + CX_TEST_ASSERT(parent.children == &child3); 1.79 + 1.80 + CX_TEST_ASSERT(child1.parent == &parent); 1.81 + CX_TEST_ASSERT(child2.parent == &parent); 1.82 + CX_TEST_ASSERT(child3.parent == &parent); 1.83 + CX_TEST_ASSERT(child1.children == NULL); 1.84 + CX_TEST_ASSERT(child2.children == NULL); 1.85 + CX_TEST_ASSERT(child3.children == NULL); 1.86 + 1.87 + CX_TEST_ASSERT(child3.prev == NULL); 1.88 + CX_TEST_ASSERT(child3.next == &child2); 1.89 + CX_TEST_ASSERT(child2.prev == &child3); 1.90 + CX_TEST_ASSERT(child2.next == &child1); 1.91 + CX_TEST_ASSERT(child1.prev == &child2); 1.92 + CX_TEST_ASSERT(child1.next == NULL); 1.93 + } 1.94 +} 1.95 + 1.96 +CX_TEST(test_tree_link_move_to_other_parent) { 1.97 + tree_node parent = {0}; 1.98 + tree_node child1 = {0}; 1.99 + tree_node child2 = {0}; 1.100 + tree_node child3 = {0}; 1.101 + cx_tree_link(&parent, &child1, tree_node_layout); 1.102 + cx_tree_link(&parent, &child2, tree_node_layout); 1.103 + cx_tree_link(&parent, &child3, tree_node_layout); 1.104 + 1.105 + CX_TEST_DO { 1.106 + cx_tree_link(&child3, &child2, tree_node_layout); 1.107 + 1.108 + CX_TEST_ASSERT(parent.next == NULL); 1.109 + CX_TEST_ASSERT(parent.prev == NULL); 1.110 + CX_TEST_ASSERT(parent.parent == NULL); 1.111 + CX_TEST_ASSERT(parent.children == &child3); 1.112 + 1.113 + CX_TEST_ASSERT(child1.parent == &parent); 1.114 + CX_TEST_ASSERT(child2.parent == &child3); 1.115 + CX_TEST_ASSERT(child3.parent == &parent); 1.116 + CX_TEST_ASSERT(child1.children == NULL); 1.117 + CX_TEST_ASSERT(child2.children == NULL); 1.118 + CX_TEST_ASSERT(child3.children == &child2); 1.119 + 1.120 + CX_TEST_ASSERT(child3.prev == NULL); 1.121 + CX_TEST_ASSERT(child3.next == &child1); 1.122 + CX_TEST_ASSERT(child1.prev == &child3); 1.123 + CX_TEST_ASSERT(child1.next == NULL); 1.124 + 1.125 + CX_TEST_ASSERT(child2.prev == NULL); 1.126 + CX_TEST_ASSERT(child2.next == NULL); 1.127 + } 1.128 +} 1.129 + 1.130 +CX_TEST(test_tree_unlink) { 1.131 + tree_node parent = {0}; 1.132 + tree_node child1 = {0}; 1.133 + tree_node child2 = {0}; 1.134 + tree_node child3 = {0}; 1.135 + cx_tree_link(&parent, &child1, tree_node_layout); 1.136 + cx_tree_link(&parent, &child3, tree_node_layout); 1.137 + cx_tree_link(&child3, &child2, tree_node_layout); 1.138 + 1.139 + CX_TEST_DO { 1.140 + cx_tree_unlink(&child3, tree_node_layout); 1.141 + 1.142 + CX_TEST_ASSERT(parent.next == NULL); 1.143 + CX_TEST_ASSERT(parent.prev == NULL); 1.144 + CX_TEST_ASSERT(parent.parent == NULL); 1.145 + CX_TEST_ASSERT(parent.children == &child1); 1.146 + 1.147 + CX_TEST_ASSERT(child1.parent == &parent); 1.148 + CX_TEST_ASSERT(child1.children == NULL); 1.149 + CX_TEST_ASSERT(child1.prev == NULL); 1.150 + CX_TEST_ASSERT(child1.next == NULL); 1.151 + 1.152 + // child 3 is unlinked 1.153 + CX_TEST_ASSERT(child3.parent == NULL); 1.154 + CX_TEST_ASSERT(child3.prev == NULL); 1.155 + CX_TEST_ASSERT(child3.next == NULL); 1.156 + 1.157 + // child 2 is still child of the unlinked child 3 1.158 + CX_TEST_ASSERT(child3.children == &child2); 1.159 + CX_TEST_ASSERT(child2.parent == &child3); 1.160 + CX_TEST_ASSERT(child2.children == NULL); 1.161 + CX_TEST_ASSERT(child2.prev == NULL); 1.162 + CX_TEST_ASSERT(child2.next == NULL); 1.163 + } 1.164 +} 1.165 + 1.166 +CxTestSuite *cx_test_suite_tree_low_level(void) { 1.167 + CxTestSuite *suite = cx_test_suite_new("tree (low level)"); 1.168 + 1.169 + cx_test_register(suite, test_tree_link_new_child); 1.170 + cx_test_register(suite, test_tree_link_add_child); 1.171 + cx_test_register(suite, test_tree_link_move_to_other_parent); 1.172 + cx_test_register(suite, test_tree_unlink); 1.173 + 1.174 + return suite; 1.175 +}