Sun, 18 Feb 2024 13:38:42 +0100
vastly simplify tree iterators and add test for creating them
relates to #371
universe@816 | 1 | /* |
universe@816 | 2 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. |
universe@816 | 3 | * |
universe@816 | 4 | * Copyright 2023 Mike Becker, Olaf Wintermann All rights reserved. |
universe@816 | 5 | * |
universe@816 | 6 | * Redistribution and use in source and binary forms, with or without |
universe@816 | 7 | * modification, are permitted provided that the following conditions are met: |
universe@816 | 8 | * |
universe@816 | 9 | * 1. Redistributions of source code must retain the above copyright |
universe@816 | 10 | * notice, this list of conditions and the following disclaimer. |
universe@816 | 11 | * |
universe@816 | 12 | * 2. Redistributions in binary form must reproduce the above copyright |
universe@816 | 13 | * notice, this list of conditions and the following disclaimer in the |
universe@816 | 14 | * documentation and/or other materials provided with the distribution. |
universe@816 | 15 | * |
universe@816 | 16 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
universe@816 | 17 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
universe@816 | 18 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
universe@816 | 19 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE |
universe@816 | 20 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
universe@816 | 21 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
universe@816 | 22 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
universe@816 | 23 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
universe@816 | 24 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
universe@816 | 25 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
universe@816 | 26 | * POSSIBILITY OF SUCH DAMAGE. |
universe@816 | 27 | */ |
universe@816 | 28 | |
universe@816 | 29 | #include "cx/tree.h" |
universe@816 | 30 | |
universe@816 | 31 | #include "cx/test.h" |
universe@816 | 32 | |
universe@816 | 33 | typedef struct tree_node { |
universe@816 | 34 | struct tree_node *parent; |
universe@816 | 35 | struct tree_node *next; |
universe@816 | 36 | struct tree_node *prev; |
universe@816 | 37 | struct tree_node *children; |
universe@816 | 38 | int data; |
universe@816 | 39 | } tree_node; |
universe@816 | 40 | |
universe@816 | 41 | #define tree_node_layout \ |
universe@816 | 42 | offsetof(tree_node, parent), offsetof(tree_node, children), \ |
universe@816 | 43 | offsetof(tree_node, prev), offsetof(tree_node, next) |
universe@816 | 44 | |
universe@826 | 45 | #define tree_child_list offsetof(tree_node, children),offsetof(tree_node, next) |
universe@826 | 46 | |
universe@816 | 47 | CX_TEST(test_tree_link_new_child) { |
universe@816 | 48 | tree_node parent = {0}; |
universe@816 | 49 | tree_node child = {0}; |
universe@816 | 50 | |
universe@816 | 51 | CX_TEST_DO { |
universe@816 | 52 | cx_tree_link(&parent, &child, tree_node_layout); |
universe@816 | 53 | CX_TEST_ASSERT(parent.next == NULL); |
universe@816 | 54 | CX_TEST_ASSERT(parent.prev == NULL); |
universe@816 | 55 | CX_TEST_ASSERT(parent.parent == NULL); |
universe@816 | 56 | CX_TEST_ASSERT(parent.children == &child); |
universe@816 | 57 | CX_TEST_ASSERT(child.parent == &parent); |
universe@816 | 58 | CX_TEST_ASSERT(child.next == NULL); |
universe@816 | 59 | CX_TEST_ASSERT(child.prev == NULL); |
universe@816 | 60 | CX_TEST_ASSERT(child.children == NULL); |
universe@816 | 61 | } |
universe@816 | 62 | } |
universe@816 | 63 | |
universe@816 | 64 | CX_TEST(test_tree_link_add_child) { |
universe@816 | 65 | tree_node parent = {0}; |
universe@816 | 66 | tree_node child1 = {0}; |
universe@816 | 67 | tree_node child2 = {0}; |
universe@816 | 68 | tree_node child3 = {0}; |
universe@816 | 69 | |
universe@816 | 70 | CX_TEST_DO { |
universe@816 | 71 | cx_tree_link(&parent, &child1, tree_node_layout); |
universe@816 | 72 | cx_tree_link(&parent, &child2, tree_node_layout); |
universe@816 | 73 | cx_tree_link(&parent, &child3, tree_node_layout); |
universe@816 | 74 | CX_TEST_ASSERT(parent.next == NULL); |
universe@816 | 75 | CX_TEST_ASSERT(parent.prev == NULL); |
universe@816 | 76 | CX_TEST_ASSERT(parent.parent == NULL); |
universe@816 | 77 | CX_TEST_ASSERT(parent.children == &child3); |
universe@816 | 78 | |
universe@816 | 79 | CX_TEST_ASSERT(child1.parent == &parent); |
universe@816 | 80 | CX_TEST_ASSERT(child2.parent == &parent); |
universe@816 | 81 | CX_TEST_ASSERT(child3.parent == &parent); |
universe@816 | 82 | CX_TEST_ASSERT(child1.children == NULL); |
universe@816 | 83 | CX_TEST_ASSERT(child2.children == NULL); |
universe@816 | 84 | CX_TEST_ASSERT(child3.children == NULL); |
universe@816 | 85 | |
universe@816 | 86 | CX_TEST_ASSERT(child3.prev == NULL); |
universe@816 | 87 | CX_TEST_ASSERT(child3.next == &child2); |
universe@816 | 88 | CX_TEST_ASSERT(child2.prev == &child3); |
universe@816 | 89 | CX_TEST_ASSERT(child2.next == &child1); |
universe@816 | 90 | CX_TEST_ASSERT(child1.prev == &child2); |
universe@816 | 91 | CX_TEST_ASSERT(child1.next == NULL); |
universe@816 | 92 | } |
universe@816 | 93 | } |
universe@816 | 94 | |
universe@816 | 95 | CX_TEST(test_tree_link_move_to_other_parent) { |
universe@816 | 96 | tree_node parent = {0}; |
universe@816 | 97 | tree_node child1 = {0}; |
universe@816 | 98 | tree_node child2 = {0}; |
universe@816 | 99 | tree_node child3 = {0}; |
universe@816 | 100 | cx_tree_link(&parent, &child1, tree_node_layout); |
universe@816 | 101 | cx_tree_link(&parent, &child2, tree_node_layout); |
universe@816 | 102 | cx_tree_link(&parent, &child3, tree_node_layout); |
universe@816 | 103 | |
universe@816 | 104 | CX_TEST_DO { |
universe@816 | 105 | cx_tree_link(&child3, &child2, tree_node_layout); |
universe@816 | 106 | |
universe@816 | 107 | CX_TEST_ASSERT(parent.next == NULL); |
universe@816 | 108 | CX_TEST_ASSERT(parent.prev == NULL); |
universe@816 | 109 | CX_TEST_ASSERT(parent.parent == NULL); |
universe@816 | 110 | CX_TEST_ASSERT(parent.children == &child3); |
universe@816 | 111 | |
universe@816 | 112 | CX_TEST_ASSERT(child1.parent == &parent); |
universe@816 | 113 | CX_TEST_ASSERT(child2.parent == &child3); |
universe@816 | 114 | CX_TEST_ASSERT(child3.parent == &parent); |
universe@816 | 115 | CX_TEST_ASSERT(child1.children == NULL); |
universe@816 | 116 | CX_TEST_ASSERT(child2.children == NULL); |
universe@816 | 117 | CX_TEST_ASSERT(child3.children == &child2); |
universe@816 | 118 | |
universe@816 | 119 | CX_TEST_ASSERT(child3.prev == NULL); |
universe@816 | 120 | CX_TEST_ASSERT(child3.next == &child1); |
universe@816 | 121 | CX_TEST_ASSERT(child1.prev == &child3); |
universe@816 | 122 | CX_TEST_ASSERT(child1.next == NULL); |
universe@816 | 123 | |
universe@816 | 124 | CX_TEST_ASSERT(child2.prev == NULL); |
universe@816 | 125 | CX_TEST_ASSERT(child2.next == NULL); |
universe@816 | 126 | } |
universe@816 | 127 | } |
universe@816 | 128 | |
universe@816 | 129 | CX_TEST(test_tree_unlink) { |
universe@816 | 130 | tree_node parent = {0}; |
universe@816 | 131 | tree_node child1 = {0}; |
universe@816 | 132 | tree_node child2 = {0}; |
universe@816 | 133 | tree_node child3 = {0}; |
universe@816 | 134 | cx_tree_link(&parent, &child1, tree_node_layout); |
universe@816 | 135 | cx_tree_link(&parent, &child3, tree_node_layout); |
universe@816 | 136 | cx_tree_link(&child3, &child2, tree_node_layout); |
universe@816 | 137 | |
universe@816 | 138 | CX_TEST_DO { |
universe@816 | 139 | cx_tree_unlink(&child3, tree_node_layout); |
universe@816 | 140 | |
universe@816 | 141 | CX_TEST_ASSERT(parent.next == NULL); |
universe@816 | 142 | CX_TEST_ASSERT(parent.prev == NULL); |
universe@816 | 143 | CX_TEST_ASSERT(parent.parent == NULL); |
universe@816 | 144 | CX_TEST_ASSERT(parent.children == &child1); |
universe@816 | 145 | |
universe@816 | 146 | CX_TEST_ASSERT(child1.parent == &parent); |
universe@816 | 147 | CX_TEST_ASSERT(child1.children == NULL); |
universe@816 | 148 | CX_TEST_ASSERT(child1.prev == NULL); |
universe@816 | 149 | CX_TEST_ASSERT(child1.next == NULL); |
universe@816 | 150 | |
universe@816 | 151 | // child 3 is unlinked |
universe@816 | 152 | CX_TEST_ASSERT(child3.parent == NULL); |
universe@816 | 153 | CX_TEST_ASSERT(child3.prev == NULL); |
universe@816 | 154 | CX_TEST_ASSERT(child3.next == NULL); |
universe@816 | 155 | |
universe@816 | 156 | // child 2 is still child of the unlinked child 3 |
universe@816 | 157 | CX_TEST_ASSERT(child3.children == &child2); |
universe@816 | 158 | CX_TEST_ASSERT(child2.parent == &child3); |
universe@816 | 159 | CX_TEST_ASSERT(child2.children == NULL); |
universe@816 | 160 | CX_TEST_ASSERT(child2.prev == NULL); |
universe@816 | 161 | CX_TEST_ASSERT(child2.next == NULL); |
universe@816 | 162 | } |
universe@816 | 163 | } |
universe@816 | 164 | |
universe@826 | 165 | static int test_tree_search_function(void const *n, void const *d) { |
universe@826 | 166 | tree_node const *node = n; |
universe@826 | 167 | int data = *((int const*)d); |
universe@826 | 168 | |
universe@826 | 169 | if (data < node->data) return -1; |
universe@826 | 170 | else if (data == node->data) return 0; |
universe@826 | 171 | else return data - node->data; |
universe@826 | 172 | } |
universe@826 | 173 | |
universe@826 | 174 | CX_TEST(test_tree_search) { |
universe@826 | 175 | tree_node root = {0}; |
universe@826 | 176 | tree_node a = {0}; |
universe@826 | 177 | tree_node b = {0}; |
universe@826 | 178 | tree_node c = {0}; |
universe@826 | 179 | tree_node aa = {0}; |
universe@826 | 180 | tree_node ab = {0}; |
universe@826 | 181 | tree_node ba = {0}; |
universe@826 | 182 | tree_node ca = {0}; |
universe@826 | 183 | tree_node cb = {0}; |
universe@826 | 184 | tree_node cc = {0}; |
universe@826 | 185 | tree_node cba = {0}; |
universe@826 | 186 | |
universe@826 | 187 | int testdata[] = {0, 10, 14, 18, 20, 25, 30, 32, 34, 36, 40}; |
universe@826 | 188 | tree_node* testnodes[] = {&root, &a, &aa, &ab, &b, &ba, &c, &ca, &cb, &cba, &cc}; |
universe@826 | 189 | |
universe@826 | 190 | for (unsigned i = 0 ; i <= 10 ; i++) { |
universe@826 | 191 | testnodes[i]->data = testdata[i]; |
universe@826 | 192 | } |
universe@826 | 193 | |
universe@826 | 194 | cx_tree_link(&root, &a, tree_node_layout); |
universe@826 | 195 | cx_tree_link(&root, &b, tree_node_layout); |
universe@826 | 196 | cx_tree_link(&root, &c, tree_node_layout); |
universe@826 | 197 | |
universe@826 | 198 | cx_tree_link(&a, &aa, tree_node_layout); |
universe@826 | 199 | cx_tree_link(&a, &ab, tree_node_layout); |
universe@826 | 200 | |
universe@826 | 201 | cx_tree_link(&b, &ba, tree_node_layout); |
universe@826 | 202 | |
universe@826 | 203 | cx_tree_link(&c, &ca, tree_node_layout); |
universe@826 | 204 | cx_tree_link(&c, &cb, tree_node_layout); |
universe@826 | 205 | cx_tree_link(&c, &cc, tree_node_layout); |
universe@826 | 206 | |
universe@826 | 207 | cx_tree_link(&cb, &cba, tree_node_layout); |
universe@826 | 208 | |
universe@826 | 209 | int s; |
universe@826 | 210 | int r; |
universe@826 | 211 | tree_node *n; |
universe@826 | 212 | CX_TEST_DO { |
universe@826 | 213 | for (unsigned i = 0 ; i <= 10 ; i++) { |
universe@826 | 214 | s = testdata[i]; |
universe@826 | 215 | r = cx_tree_search(&root, &s, test_tree_search_function, |
universe@826 | 216 | (void **) &n, tree_child_list); |
universe@826 | 217 | CX_TEST_ASSERT(r == 0); |
universe@826 | 218 | CX_TEST_ASSERT(n == testnodes[i]); |
universe@826 | 219 | } |
universe@826 | 220 | |
universe@826 | 221 | s = -5; |
universe@826 | 222 | r = cx_tree_search(&root, &s, test_tree_search_function, |
universe@826 | 223 | (void **) &n, tree_child_list); |
universe@826 | 224 | CX_TEST_ASSERT(r < 0); |
universe@826 | 225 | CX_TEST_ASSERT(n == NULL); |
universe@826 | 226 | |
universe@826 | 227 | s = 26; |
universe@826 | 228 | r = cx_tree_search(&root, &s, test_tree_search_function, |
universe@826 | 229 | (void **) &n, tree_child_list); |
universe@826 | 230 | CX_TEST_ASSERT(r > 0); |
universe@826 | 231 | CX_TEST_ASSERT(n == &ba); |
universe@826 | 232 | |
universe@826 | 233 | s = 35; |
universe@826 | 234 | r = cx_tree_search(&root, &s, test_tree_search_function, |
universe@826 | 235 | (void **) &n, tree_child_list); |
universe@826 | 236 | CX_TEST_ASSERT(r > 0); |
universe@826 | 237 | CX_TEST_ASSERT(n == &cb); |
universe@826 | 238 | |
universe@826 | 239 | s = 38; |
universe@826 | 240 | r = cx_tree_search(&root, &s, test_tree_search_function, |
universe@826 | 241 | (void **) &n, tree_child_list); |
universe@826 | 242 | CX_TEST_ASSERT(r > 0); |
universe@826 | 243 | CX_TEST_ASSERT(n == &cba); |
universe@826 | 244 | |
universe@826 | 245 | s = 42; |
universe@826 | 246 | r = cx_tree_search(&root, &s, test_tree_search_function, |
universe@826 | 247 | (void **) &n, tree_child_list); |
universe@826 | 248 | CX_TEST_ASSERT(r > 0); |
universe@826 | 249 | CX_TEST_ASSERT(n == &cc); |
universe@826 | 250 | } |
universe@826 | 251 | } |
universe@826 | 252 | |
universe@833 | 253 | CX_TEST(test_tree_iterator_create) { |
universe@833 | 254 | tree_node root; |
universe@833 | 255 | CX_TEST_DO { |
universe@833 | 256 | CxTreeIterator iter = cx_tree_iterator(&root, false, tree_child_list); |
universe@833 | 257 | CX_TEST_ASSERT(!iter.visit_on_exit); |
universe@833 | 258 | CX_TEST_ASSERT(!iter.exiting); |
universe@833 | 259 | CX_TEST_ASSERT(iter.counter == 1); |
universe@833 | 260 | CX_TEST_ASSERT(iter.node == &root); |
universe@833 | 261 | CX_TEST_ASSERT(!iter.base.mutating); |
universe@833 | 262 | CX_TEST_ASSERT(!iter.base.remove); |
universe@833 | 263 | CX_TEST_ASSERT(iter.stack != NULL); |
universe@833 | 264 | CX_TEST_ASSERT(iter.stack_capacity > 0); |
universe@833 | 265 | CX_TEST_ASSERT(iter.stack_size == 1); |
universe@833 | 266 | CX_TEST_ASSERT(iter.depth == 1); |
universe@833 | 267 | CX_TEST_ASSERT(iter.loc_next == offsetof(tree_node, next)); |
universe@833 | 268 | CX_TEST_ASSERT(iter.loc_children == offsetof(tree_node, children)); |
universe@833 | 269 | } |
universe@833 | 270 | } |
universe@833 | 271 | |
universe@816 | 272 | CxTestSuite *cx_test_suite_tree_low_level(void) { |
universe@816 | 273 | CxTestSuite *suite = cx_test_suite_new("tree (low level)"); |
universe@816 | 274 | |
universe@816 | 275 | cx_test_register(suite, test_tree_link_new_child); |
universe@816 | 276 | cx_test_register(suite, test_tree_link_add_child); |
universe@816 | 277 | cx_test_register(suite, test_tree_link_move_to_other_parent); |
universe@816 | 278 | cx_test_register(suite, test_tree_unlink); |
universe@826 | 279 | cx_test_register(suite, test_tree_search); |
universe@833 | 280 | cx_test_register(suite, test_tree_iterator_create); |
universe@816 | 281 | |
universe@816 | 282 | return suite; |
universe@816 | 283 | } |