Wed, 20 Mar 2024 23:35:32 +0100
add missing cxTreeVisitorDispose() test
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@840 | 33 | #include "util_allocator.h" |
universe@840 | 34 | |
universe@816 | 35 | typedef struct tree_node { |
universe@816 | 36 | struct tree_node *parent; |
universe@816 | 37 | struct tree_node *next; |
universe@816 | 38 | struct tree_node *prev; |
universe@816 | 39 | struct tree_node *children; |
universe@816 | 40 | int data; |
universe@816 | 41 | } tree_node; |
universe@816 | 42 | |
universe@816 | 43 | #define tree_node_layout \ |
universe@816 | 44 | offsetof(tree_node, parent), offsetof(tree_node, children), \ |
universe@816 | 45 | offsetof(tree_node, prev), offsetof(tree_node, next) |
universe@816 | 46 | |
universe@826 | 47 | #define tree_child_list offsetof(tree_node, children),offsetof(tree_node, next) |
universe@826 | 48 | |
universe@816 | 49 | CX_TEST(test_tree_link_new_child) { |
universe@816 | 50 | tree_node parent = {0}; |
universe@816 | 51 | tree_node child = {0}; |
universe@816 | 52 | |
universe@816 | 53 | CX_TEST_DO { |
universe@816 | 54 | cx_tree_link(&parent, &child, tree_node_layout); |
universe@816 | 55 | CX_TEST_ASSERT(parent.next == NULL); |
universe@816 | 56 | CX_TEST_ASSERT(parent.prev == NULL); |
universe@816 | 57 | CX_TEST_ASSERT(parent.parent == NULL); |
universe@816 | 58 | CX_TEST_ASSERT(parent.children == &child); |
universe@816 | 59 | CX_TEST_ASSERT(child.parent == &parent); |
universe@816 | 60 | CX_TEST_ASSERT(child.next == NULL); |
universe@816 | 61 | CX_TEST_ASSERT(child.prev == NULL); |
universe@816 | 62 | CX_TEST_ASSERT(child.children == NULL); |
universe@816 | 63 | } |
universe@816 | 64 | } |
universe@816 | 65 | |
universe@816 | 66 | CX_TEST(test_tree_link_add_child) { |
universe@816 | 67 | tree_node parent = {0}; |
universe@816 | 68 | tree_node child1 = {0}; |
universe@816 | 69 | tree_node child2 = {0}; |
universe@816 | 70 | tree_node child3 = {0}; |
universe@816 | 71 | |
universe@816 | 72 | CX_TEST_DO { |
universe@816 | 73 | cx_tree_link(&parent, &child1, tree_node_layout); |
universe@816 | 74 | cx_tree_link(&parent, &child2, tree_node_layout); |
universe@816 | 75 | cx_tree_link(&parent, &child3, tree_node_layout); |
universe@816 | 76 | CX_TEST_ASSERT(parent.next == NULL); |
universe@816 | 77 | CX_TEST_ASSERT(parent.prev == NULL); |
universe@816 | 78 | CX_TEST_ASSERT(parent.parent == NULL); |
universe@816 | 79 | CX_TEST_ASSERT(parent.children == &child3); |
universe@816 | 80 | |
universe@816 | 81 | CX_TEST_ASSERT(child1.parent == &parent); |
universe@816 | 82 | CX_TEST_ASSERT(child2.parent == &parent); |
universe@816 | 83 | CX_TEST_ASSERT(child3.parent == &parent); |
universe@816 | 84 | CX_TEST_ASSERT(child1.children == NULL); |
universe@816 | 85 | CX_TEST_ASSERT(child2.children == NULL); |
universe@816 | 86 | CX_TEST_ASSERT(child3.children == NULL); |
universe@816 | 87 | |
universe@816 | 88 | CX_TEST_ASSERT(child3.prev == NULL); |
universe@816 | 89 | CX_TEST_ASSERT(child3.next == &child2); |
universe@816 | 90 | CX_TEST_ASSERT(child2.prev == &child3); |
universe@816 | 91 | CX_TEST_ASSERT(child2.next == &child1); |
universe@816 | 92 | CX_TEST_ASSERT(child1.prev == &child2); |
universe@816 | 93 | CX_TEST_ASSERT(child1.next == NULL); |
universe@816 | 94 | } |
universe@816 | 95 | } |
universe@816 | 96 | |
universe@816 | 97 | CX_TEST(test_tree_link_move_to_other_parent) { |
universe@816 | 98 | tree_node parent = {0}; |
universe@816 | 99 | tree_node child1 = {0}; |
universe@816 | 100 | tree_node child2 = {0}; |
universe@816 | 101 | tree_node child3 = {0}; |
universe@816 | 102 | cx_tree_link(&parent, &child1, tree_node_layout); |
universe@816 | 103 | cx_tree_link(&parent, &child2, tree_node_layout); |
universe@816 | 104 | cx_tree_link(&parent, &child3, tree_node_layout); |
universe@816 | 105 | |
universe@816 | 106 | CX_TEST_DO { |
universe@816 | 107 | cx_tree_link(&child3, &child2, tree_node_layout); |
universe@816 | 108 | |
universe@816 | 109 | CX_TEST_ASSERT(parent.next == NULL); |
universe@816 | 110 | CX_TEST_ASSERT(parent.prev == NULL); |
universe@816 | 111 | CX_TEST_ASSERT(parent.parent == NULL); |
universe@816 | 112 | CX_TEST_ASSERT(parent.children == &child3); |
universe@816 | 113 | |
universe@816 | 114 | CX_TEST_ASSERT(child1.parent == &parent); |
universe@816 | 115 | CX_TEST_ASSERT(child2.parent == &child3); |
universe@816 | 116 | CX_TEST_ASSERT(child3.parent == &parent); |
universe@816 | 117 | CX_TEST_ASSERT(child1.children == NULL); |
universe@816 | 118 | CX_TEST_ASSERT(child2.children == NULL); |
universe@816 | 119 | CX_TEST_ASSERT(child3.children == &child2); |
universe@816 | 120 | |
universe@816 | 121 | CX_TEST_ASSERT(child3.prev == NULL); |
universe@816 | 122 | CX_TEST_ASSERT(child3.next == &child1); |
universe@816 | 123 | CX_TEST_ASSERT(child1.prev == &child3); |
universe@816 | 124 | CX_TEST_ASSERT(child1.next == NULL); |
universe@816 | 125 | |
universe@816 | 126 | CX_TEST_ASSERT(child2.prev == NULL); |
universe@816 | 127 | CX_TEST_ASSERT(child2.next == NULL); |
universe@816 | 128 | } |
universe@816 | 129 | } |
universe@816 | 130 | |
universe@816 | 131 | CX_TEST(test_tree_unlink) { |
universe@816 | 132 | tree_node parent = {0}; |
universe@816 | 133 | tree_node child1 = {0}; |
universe@816 | 134 | tree_node child2 = {0}; |
universe@816 | 135 | tree_node child3 = {0}; |
universe@816 | 136 | cx_tree_link(&parent, &child1, tree_node_layout); |
universe@816 | 137 | cx_tree_link(&parent, &child3, tree_node_layout); |
universe@816 | 138 | cx_tree_link(&child3, &child2, tree_node_layout); |
universe@816 | 139 | |
universe@816 | 140 | CX_TEST_DO { |
universe@816 | 141 | cx_tree_unlink(&child3, tree_node_layout); |
universe@816 | 142 | |
universe@816 | 143 | CX_TEST_ASSERT(parent.next == NULL); |
universe@816 | 144 | CX_TEST_ASSERT(parent.prev == NULL); |
universe@816 | 145 | CX_TEST_ASSERT(parent.parent == NULL); |
universe@816 | 146 | CX_TEST_ASSERT(parent.children == &child1); |
universe@816 | 147 | |
universe@816 | 148 | CX_TEST_ASSERT(child1.parent == &parent); |
universe@816 | 149 | CX_TEST_ASSERT(child1.children == NULL); |
universe@816 | 150 | CX_TEST_ASSERT(child1.prev == NULL); |
universe@816 | 151 | CX_TEST_ASSERT(child1.next == NULL); |
universe@816 | 152 | |
universe@816 | 153 | // child 3 is unlinked |
universe@816 | 154 | CX_TEST_ASSERT(child3.parent == NULL); |
universe@816 | 155 | CX_TEST_ASSERT(child3.prev == NULL); |
universe@816 | 156 | CX_TEST_ASSERT(child3.next == NULL); |
universe@816 | 157 | |
universe@816 | 158 | // child 2 is still child of the unlinked child 3 |
universe@816 | 159 | CX_TEST_ASSERT(child3.children == &child2); |
universe@816 | 160 | CX_TEST_ASSERT(child2.parent == &child3); |
universe@816 | 161 | CX_TEST_ASSERT(child2.children == NULL); |
universe@816 | 162 | CX_TEST_ASSERT(child2.prev == NULL); |
universe@816 | 163 | CX_TEST_ASSERT(child2.next == NULL); |
universe@816 | 164 | } |
universe@816 | 165 | } |
universe@816 | 166 | |
universe@826 | 167 | static int test_tree_search_function(void const *n, void const *d) { |
universe@826 | 168 | tree_node const *node = n; |
universe@826 | 169 | int data = *((int const*)d); |
universe@826 | 170 | |
universe@826 | 171 | if (data < node->data) return -1; |
universe@826 | 172 | else if (data == node->data) return 0; |
universe@826 | 173 | else return data - node->data; |
universe@826 | 174 | } |
universe@826 | 175 | |
universe@826 | 176 | CX_TEST(test_tree_search) { |
universe@826 | 177 | tree_node root = {0}; |
universe@826 | 178 | tree_node a = {0}; |
universe@826 | 179 | tree_node b = {0}; |
universe@826 | 180 | tree_node c = {0}; |
universe@826 | 181 | tree_node aa = {0}; |
universe@826 | 182 | tree_node ab = {0}; |
universe@826 | 183 | tree_node ba = {0}; |
universe@826 | 184 | tree_node ca = {0}; |
universe@826 | 185 | tree_node cb = {0}; |
universe@826 | 186 | tree_node cc = {0}; |
universe@826 | 187 | tree_node cba = {0}; |
universe@826 | 188 | |
universe@826 | 189 | int testdata[] = {0, 10, 14, 18, 20, 25, 30, 32, 34, 36, 40}; |
universe@826 | 190 | tree_node* testnodes[] = {&root, &a, &aa, &ab, &b, &ba, &c, &ca, &cb, &cba, &cc}; |
universe@826 | 191 | |
universe@826 | 192 | for (unsigned i = 0 ; i <= 10 ; i++) { |
universe@826 | 193 | testnodes[i]->data = testdata[i]; |
universe@826 | 194 | } |
universe@826 | 195 | |
universe@826 | 196 | cx_tree_link(&root, &a, tree_node_layout); |
universe@826 | 197 | cx_tree_link(&root, &b, tree_node_layout); |
universe@826 | 198 | cx_tree_link(&root, &c, tree_node_layout); |
universe@826 | 199 | |
universe@826 | 200 | cx_tree_link(&a, &aa, tree_node_layout); |
universe@826 | 201 | cx_tree_link(&a, &ab, tree_node_layout); |
universe@826 | 202 | |
universe@826 | 203 | cx_tree_link(&b, &ba, tree_node_layout); |
universe@826 | 204 | |
universe@826 | 205 | cx_tree_link(&c, &ca, tree_node_layout); |
universe@826 | 206 | cx_tree_link(&c, &cb, tree_node_layout); |
universe@826 | 207 | cx_tree_link(&c, &cc, tree_node_layout); |
universe@826 | 208 | |
universe@826 | 209 | cx_tree_link(&cb, &cba, tree_node_layout); |
universe@826 | 210 | |
universe@826 | 211 | int s; |
universe@826 | 212 | int r; |
universe@826 | 213 | tree_node *n; |
universe@826 | 214 | CX_TEST_DO { |
universe@826 | 215 | for (unsigned i = 0 ; i <= 10 ; i++) { |
universe@826 | 216 | s = testdata[i]; |
universe@826 | 217 | r = cx_tree_search(&root, &s, test_tree_search_function, |
universe@826 | 218 | (void **) &n, tree_child_list); |
universe@826 | 219 | CX_TEST_ASSERT(r == 0); |
universe@826 | 220 | CX_TEST_ASSERT(n == testnodes[i]); |
universe@826 | 221 | } |
universe@826 | 222 | |
universe@826 | 223 | s = -5; |
universe@826 | 224 | r = cx_tree_search(&root, &s, test_tree_search_function, |
universe@826 | 225 | (void **) &n, tree_child_list); |
universe@826 | 226 | CX_TEST_ASSERT(r < 0); |
universe@826 | 227 | CX_TEST_ASSERT(n == NULL); |
universe@826 | 228 | |
universe@826 | 229 | s = 26; |
universe@826 | 230 | r = cx_tree_search(&root, &s, test_tree_search_function, |
universe@826 | 231 | (void **) &n, tree_child_list); |
universe@826 | 232 | CX_TEST_ASSERT(r > 0); |
universe@826 | 233 | CX_TEST_ASSERT(n == &ba); |
universe@826 | 234 | |
universe@826 | 235 | s = 35; |
universe@826 | 236 | r = cx_tree_search(&root, &s, test_tree_search_function, |
universe@826 | 237 | (void **) &n, tree_child_list); |
universe@826 | 238 | CX_TEST_ASSERT(r > 0); |
universe@826 | 239 | CX_TEST_ASSERT(n == &cb); |
universe@826 | 240 | |
universe@826 | 241 | s = 38; |
universe@826 | 242 | r = cx_tree_search(&root, &s, test_tree_search_function, |
universe@826 | 243 | (void **) &n, tree_child_list); |
universe@826 | 244 | CX_TEST_ASSERT(r > 0); |
universe@826 | 245 | CX_TEST_ASSERT(n == &cba); |
universe@826 | 246 | |
universe@826 | 247 | s = 42; |
universe@826 | 248 | r = cx_tree_search(&root, &s, test_tree_search_function, |
universe@826 | 249 | (void **) &n, tree_child_list); |
universe@826 | 250 | CX_TEST_ASSERT(r > 0); |
universe@826 | 251 | CX_TEST_ASSERT(n == &cc); |
universe@826 | 252 | } |
universe@826 | 253 | } |
universe@826 | 254 | |
universe@836 | 255 | CX_TEST(test_tree_iterator_create_and_dispose) { |
universe@833 | 256 | tree_node root; |
universe@833 | 257 | CX_TEST_DO { |
universe@833 | 258 | CxTreeIterator iter = cx_tree_iterator(&root, false, tree_child_list); |
universe@833 | 259 | CX_TEST_ASSERT(!iter.visit_on_exit); |
universe@833 | 260 | CX_TEST_ASSERT(!iter.exiting); |
universe@833 | 261 | CX_TEST_ASSERT(iter.counter == 1); |
universe@833 | 262 | CX_TEST_ASSERT(iter.node == &root); |
universe@833 | 263 | CX_TEST_ASSERT(!iter.base.mutating); |
universe@833 | 264 | CX_TEST_ASSERT(!iter.base.remove); |
universe@833 | 265 | CX_TEST_ASSERT(iter.stack != NULL); |
universe@833 | 266 | CX_TEST_ASSERT(iter.stack_capacity > 0); |
universe@833 | 267 | CX_TEST_ASSERT(iter.stack_size == 1); |
universe@833 | 268 | CX_TEST_ASSERT(iter.depth == 1); |
universe@833 | 269 | CX_TEST_ASSERT(iter.loc_next == offsetof(tree_node, next)); |
universe@833 | 270 | CX_TEST_ASSERT(iter.loc_children == offsetof(tree_node, children)); |
universe@836 | 271 | cxTreeIteratorDispose(&iter); |
universe@836 | 272 | CX_TEST_ASSERT(iter.stack == NULL); |
universe@836 | 273 | } |
universe@836 | 274 | } |
universe@836 | 275 | |
universe@838 | 276 | CX_TEST(test_tree_iterator_basic_only_enter) { |
universe@836 | 277 | tree_node root = {0}; |
universe@836 | 278 | tree_node a = {0}; |
universe@836 | 279 | tree_node b = {0}; |
universe@836 | 280 | tree_node c = {0}; |
universe@836 | 281 | tree_node aa = {0}; |
universe@836 | 282 | tree_node ab = {0}; |
universe@836 | 283 | tree_node ba = {0}; |
universe@836 | 284 | tree_node ca = {0}; |
universe@836 | 285 | tree_node cb = {0}; |
universe@836 | 286 | tree_node cc = {0}; |
universe@836 | 287 | tree_node cba = {0}; |
universe@836 | 288 | |
universe@845 | 289 | tree_node* expected_order[] = { |
universe@845 | 290 | &root, |
universe@845 | 291 | &c, &cc,&cb, &cba,&ca, |
universe@845 | 292 | &b, &ba, |
universe@845 | 293 | &a, &ab, &aa, |
universe@845 | 294 | }; |
universe@845 | 295 | tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong |
universe@845 | 296 | |
universe@836 | 297 | cx_tree_link(&root, &a, tree_node_layout); |
universe@836 | 298 | cx_tree_link(&root, &b, tree_node_layout); |
universe@836 | 299 | cx_tree_link(&root, &c, tree_node_layout); |
universe@836 | 300 | cx_tree_link(&a, &aa, tree_node_layout); |
universe@836 | 301 | cx_tree_link(&a, &ab, tree_node_layout); |
universe@836 | 302 | cx_tree_link(&b, &ba, tree_node_layout); |
universe@836 | 303 | cx_tree_link(&c, &ca, tree_node_layout); |
universe@836 | 304 | cx_tree_link(&c, &cb, tree_node_layout); |
universe@836 | 305 | cx_tree_link(&c, &cc, tree_node_layout); |
universe@836 | 306 | cx_tree_link(&cb, &cba, tree_node_layout); |
universe@836 | 307 | CX_TEST_DO { |
universe@836 | 308 | CxTreeIterator iter = cx_tree_iterator(&root, false, tree_child_list); |
universe@836 | 309 | unsigned chk = 0; |
universe@836 | 310 | cx_foreach(tree_node*, node, iter) { |
universe@836 | 311 | CX_TEST_ASSERT(node->data == 0); |
universe@836 | 312 | node->data++; |
universe@845 | 313 | actual_order[chk] = node; |
universe@836 | 314 | chk++; |
universe@836 | 315 | CX_TEST_ASSERT(node == iter.node); |
universe@836 | 316 | CX_TEST_ASSERT(!iter.exiting); |
universe@837 | 317 | if (node == &root) { |
universe@837 | 318 | CX_TEST_ASSERT(iter.depth == 1); |
universe@837 | 319 | } else if (node == &a || node == &b || node == &c) { |
universe@837 | 320 | CX_TEST_ASSERT(iter.depth == 2); |
universe@837 | 321 | } else if (node == &cba) { |
universe@837 | 322 | CX_TEST_ASSERT(iter.depth == 4); |
universe@837 | 323 | } else { |
universe@837 | 324 | CX_TEST_ASSERT(iter.depth == 3); |
universe@837 | 325 | } |
universe@836 | 326 | } |
universe@836 | 327 | CX_TEST_ASSERT(iter.counter == 11); |
universe@836 | 328 | CX_TEST_ASSERT(chk == 11); |
universe@845 | 329 | for (unsigned i = 0 ; i < chk ; i++) { |
universe@845 | 330 | CX_TEST_ASSERT(actual_order[i] == expected_order[i]); |
universe@845 | 331 | CX_TEST_ASSERT(actual_order[i]->data == 1); |
universe@845 | 332 | } |
universe@836 | 333 | CX_TEST_ASSERT(iter.stack == NULL); |
universe@833 | 334 | } |
universe@833 | 335 | } |
universe@833 | 336 | |
universe@838 | 337 | CX_TEST(test_tree_iterator_basic_enter_and_exit) { |
universe@838 | 338 | tree_node root = {0}; |
universe@838 | 339 | tree_node a = {0}; |
universe@838 | 340 | tree_node b = {0}; |
universe@838 | 341 | tree_node c = {0}; |
universe@838 | 342 | tree_node aa = {0}; |
universe@838 | 343 | tree_node ab = {0}; |
universe@838 | 344 | tree_node ba = {0}; |
universe@838 | 345 | tree_node ca = {0}; |
universe@838 | 346 | tree_node cb = {0}; |
universe@838 | 347 | tree_node cc = {0}; |
universe@838 | 348 | tree_node cba = {0}; |
universe@838 | 349 | |
universe@838 | 350 | cx_tree_link(&root, &a, tree_node_layout); |
universe@838 | 351 | cx_tree_link(&root, &b, tree_node_layout); |
universe@838 | 352 | cx_tree_link(&root, &c, tree_node_layout); |
universe@838 | 353 | cx_tree_link(&a, &aa, tree_node_layout); |
universe@838 | 354 | cx_tree_link(&a, &ab, tree_node_layout); |
universe@838 | 355 | cx_tree_link(&b, &ba, tree_node_layout); |
universe@838 | 356 | cx_tree_link(&c, &ca, tree_node_layout); |
universe@838 | 357 | cx_tree_link(&c, &cb, tree_node_layout); |
universe@838 | 358 | cx_tree_link(&c, &cc, tree_node_layout); |
universe@838 | 359 | cx_tree_link(&cb, &cba, tree_node_layout); |
universe@838 | 360 | CX_TEST_DO { |
universe@838 | 361 | CxTreeIterator iter = cx_tree_iterator(&root, true, tree_child_list); |
universe@838 | 362 | unsigned chk = 0; |
universe@838 | 363 | cx_foreach(tree_node*, node, iter) { |
universe@838 | 364 | CX_TEST_ASSERT(iter.exiting || node->data == 0); |
universe@838 | 365 | node->data++; |
universe@838 | 366 | chk++; |
universe@838 | 367 | CX_TEST_ASSERT(node == iter.node); |
universe@838 | 368 | if (node == &root) { |
universe@838 | 369 | CX_TEST_ASSERT(iter.depth == 1); |
universe@838 | 370 | } else if (node == &a || node == &b || node == &c) { |
universe@838 | 371 | CX_TEST_ASSERT(iter.depth == 2); |
universe@838 | 372 | } else if (node == &cba) { |
universe@838 | 373 | CX_TEST_ASSERT(iter.depth == 4); |
universe@838 | 374 | } else { |
universe@838 | 375 | CX_TEST_ASSERT(iter.depth == 3); |
universe@838 | 376 | } |
universe@838 | 377 | } |
universe@838 | 378 | CX_TEST_ASSERT(iter.counter == 11); |
universe@838 | 379 | CX_TEST_ASSERT(chk == 22); |
universe@838 | 380 | CX_TEST_ASSERT(iter.stack == NULL); |
universe@838 | 381 | CX_TEST_ASSERT(root.data == 2); |
universe@838 | 382 | CX_TEST_ASSERT(a.data == 2); |
universe@838 | 383 | CX_TEST_ASSERT(b.data == 2); |
universe@838 | 384 | CX_TEST_ASSERT(c.data == 2); |
universe@838 | 385 | CX_TEST_ASSERT(aa.data == 2); |
universe@838 | 386 | CX_TEST_ASSERT(ab.data == 2); |
universe@838 | 387 | CX_TEST_ASSERT(ba.data == 2); |
universe@838 | 388 | CX_TEST_ASSERT(ca.data == 2); |
universe@838 | 389 | CX_TEST_ASSERT(cb.data == 2); |
universe@838 | 390 | CX_TEST_ASSERT(cc.data == 2); |
universe@838 | 391 | CX_TEST_ASSERT(cba.data == 2); |
universe@838 | 392 | } |
universe@838 | 393 | } |
universe@838 | 394 | |
universe@839 | 395 | typedef struct test_xml_node { |
universe@839 | 396 | struct test_xml_node *parent; |
universe@839 | 397 | struct test_xml_node *next; |
universe@839 | 398 | struct test_xml_node *prev; |
universe@839 | 399 | struct test_xml_node *children; |
universe@839 | 400 | char const* name; |
universe@839 | 401 | } test_xml_node; |
universe@839 | 402 | |
universe@839 | 403 | CX_TEST(test_tree_iterator_xml) { |
universe@839 | 404 | test_xml_node project = {0}; |
universe@839 | 405 | test_xml_node config = {0}; |
universe@839 | 406 | test_xml_node var1 = {0}; |
universe@839 | 407 | test_xml_node var2 = {0}; |
universe@839 | 408 | test_xml_node var3 = {0}; |
universe@839 | 409 | test_xml_node dependency1 = {0}; |
universe@839 | 410 | test_xml_node dependency1make = {0}; |
universe@839 | 411 | test_xml_node dependency2 = {0}; |
universe@839 | 412 | test_xml_node dependency2lang = {0}; |
universe@839 | 413 | test_xml_node dependency2make = {0}; |
universe@839 | 414 | test_xml_node target = {0}; |
universe@839 | 415 | test_xml_node target_feature = {0}; |
universe@839 | 416 | test_xml_node target_feature_dependencies = {0}; |
universe@839 | 417 | test_xml_node target_dependencies = {0}; |
universe@839 | 418 | |
universe@839 | 419 | project.name = "project"; |
universe@839 | 420 | config.name = "config"; |
universe@839 | 421 | var1.name = "var"; |
universe@839 | 422 | var2.name = "var"; |
universe@839 | 423 | var3.name = "var"; |
universe@839 | 424 | dependency1.name = "dependency"; |
universe@839 | 425 | dependency1make.name = "make"; |
universe@839 | 426 | dependency2.name = "dependency"; |
universe@839 | 427 | dependency2lang.name = "lang"; |
universe@839 | 428 | dependency2make.name = "make"; |
universe@839 | 429 | target.name = "target"; |
universe@839 | 430 | target_feature.name = "feature"; |
universe@839 | 431 | target_dependencies.name = "dependencies"; |
universe@839 | 432 | target_feature_dependencies.name = "dependencies"; |
universe@839 | 433 | |
universe@839 | 434 | cx_tree_link(&project, &target, tree_node_layout); |
universe@839 | 435 | cx_tree_link(&project, &dependency2, tree_node_layout); |
universe@839 | 436 | cx_tree_link(&project, &dependency1, tree_node_layout); |
universe@839 | 437 | cx_tree_link(&project, &config, tree_node_layout); |
universe@839 | 438 | cx_tree_link(&config, &var3, tree_node_layout); |
universe@839 | 439 | cx_tree_link(&config, &var2, tree_node_layout); |
universe@839 | 440 | cx_tree_link(&config, &var1, tree_node_layout); |
universe@839 | 441 | cx_tree_link(&dependency1, &dependency1make, tree_node_layout); |
universe@839 | 442 | cx_tree_link(&dependency2, &dependency2make, tree_node_layout); |
universe@839 | 443 | cx_tree_link(&dependency2, &dependency2lang, tree_node_layout); |
universe@839 | 444 | cx_tree_link(&target, &target_dependencies, tree_node_layout); |
universe@839 | 445 | cx_tree_link(&target, &target_feature, tree_node_layout); |
universe@839 | 446 | cx_tree_link(&target_feature, &target_feature_dependencies, tree_node_layout); |
universe@839 | 447 | |
universe@839 | 448 | char const *expected = |
universe@839 | 449 | "<project><config><var></var><var></var><var></var></config>" |
universe@839 | 450 | "<dependency><make></make></dependency><dependency><lang></lang><make></make></dependency>" |
universe@839 | 451 | "<target><feature><dependencies></dependencies></feature><dependencies></dependencies></target></project>"; |
universe@839 | 452 | char *actual = malloc(512); |
universe@839 | 453 | CX_TEST_DO { |
universe@839 | 454 | CxTreeIterator iter = cx_tree_iterator(&project, true, tree_child_list); |
universe@839 | 455 | size_t i = 0; |
universe@839 | 456 | cx_foreach(test_xml_node*, node, iter) { |
universe@839 | 457 | size_t len = strlen(node->name); |
universe@839 | 458 | actual[i++] = '<'; |
universe@839 | 459 | if (iter.exiting) { |
universe@839 | 460 | actual[i++] = '/'; |
universe@839 | 461 | } |
universe@839 | 462 | memcpy(actual+i, node->name, len); |
universe@839 | 463 | i += len; |
universe@839 | 464 | actual[i++] = '>'; |
universe@839 | 465 | } |
universe@839 | 466 | actual[i] = '\0'; |
universe@839 | 467 | CX_TEST_ASSERT(0 == strcmp(expected, actual)); |
universe@839 | 468 | } |
universe@839 | 469 | free(actual); |
universe@839 | 470 | } |
universe@839 | 471 | |
universe@840 | 472 | CX_TEST(test_tree_iterator_free_nodes) { |
universe@840 | 473 | CxTestingAllocator talloc; |
universe@840 | 474 | cx_testing_allocator_init(&talloc); |
universe@840 | 475 | CxAllocator *alloc = &talloc.base; |
universe@840 | 476 | CX_TEST_DO { |
universe@840 | 477 | tree_node *root = cxCalloc(alloc, 1, sizeof(tree_node)); |
universe@840 | 478 | tree_node *a = cxCalloc(alloc, 1, sizeof(tree_node)); |
universe@840 | 479 | tree_node *b = cxCalloc(alloc, 1, sizeof(tree_node)); |
universe@840 | 480 | tree_node *c = cxCalloc(alloc, 1, sizeof(tree_node)); |
universe@840 | 481 | tree_node *aa = cxCalloc(alloc, 1, sizeof(tree_node)); |
universe@840 | 482 | tree_node *ab = cxCalloc(alloc, 1, sizeof(tree_node)); |
universe@840 | 483 | tree_node *ba = cxCalloc(alloc, 1, sizeof(tree_node)); |
universe@840 | 484 | tree_node *ca = cxCalloc(alloc, 1, sizeof(tree_node)); |
universe@840 | 485 | tree_node *cb = cxCalloc(alloc, 1, sizeof(tree_node)); |
universe@840 | 486 | tree_node *cc = cxCalloc(alloc, 1, sizeof(tree_node)); |
universe@840 | 487 | tree_node *cba = cxCalloc(alloc, 1, sizeof(tree_node)); |
universe@840 | 488 | |
universe@840 | 489 | cx_tree_link(root, a, tree_node_layout); |
universe@840 | 490 | cx_tree_link(root, b, tree_node_layout); |
universe@840 | 491 | cx_tree_link(root, c, tree_node_layout); |
universe@840 | 492 | cx_tree_link(a, aa, tree_node_layout); |
universe@840 | 493 | cx_tree_link(a, ab, tree_node_layout); |
universe@840 | 494 | cx_tree_link(b, ba, tree_node_layout); |
universe@840 | 495 | cx_tree_link(c, ca, tree_node_layout); |
universe@840 | 496 | cx_tree_link(c, cb, tree_node_layout); |
universe@840 | 497 | cx_tree_link(c, cc, tree_node_layout); |
universe@840 | 498 | cx_tree_link(cb, cba, tree_node_layout); |
universe@840 | 499 | |
universe@840 | 500 | CxTreeIterator iter = cx_tree_iterator(root, true, tree_child_list); |
universe@840 | 501 | cx_foreach(tree_node *, node, iter) { |
universe@840 | 502 | if (iter.exiting) { |
universe@840 | 503 | cxFree(alloc,node); |
universe@840 | 504 | } |
universe@840 | 505 | } |
universe@840 | 506 | |
universe@840 | 507 | CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); |
universe@840 | 508 | } |
universe@840 | 509 | cx_testing_allocator_destroy(&talloc); |
universe@840 | 510 | } |
universe@840 | 511 | |
universe@847 | 512 | CX_TEST(test_tree_visitor_create_and_dispose) { |
universe@847 | 513 | tree_node root; |
universe@847 | 514 | tree_node child; |
universe@847 | 515 | cx_tree_link(&root, &child, tree_node_layout); |
universe@847 | 516 | CX_TEST_DO { |
universe@847 | 517 | CxTreeVisitor iter = cx_tree_visitor(&root, tree_child_list); |
universe@847 | 518 | CX_TEST_ASSERT(iter.counter == 1); |
universe@847 | 519 | CX_TEST_ASSERT(iter.node == &root); |
universe@847 | 520 | CX_TEST_ASSERT(!iter.base.mutating); |
universe@847 | 521 | CX_TEST_ASSERT(!iter.base.remove); |
universe@847 | 522 | CX_TEST_ASSERT(iter.queue_next != NULL); |
universe@847 | 523 | CX_TEST_ASSERT(iter.queue_last != NULL); |
universe@847 | 524 | CX_TEST_ASSERT(iter.depth == 1); |
universe@847 | 525 | CX_TEST_ASSERT(iter.loc_next == offsetof(tree_node, next)); |
universe@847 | 526 | CX_TEST_ASSERT(iter.loc_children == offsetof(tree_node, children)); |
universe@847 | 527 | cxTreeVisitorDispose(&iter); |
universe@847 | 528 | CX_TEST_ASSERT(iter.queue_next == NULL); |
universe@847 | 529 | CX_TEST_ASSERT(iter.queue_last == NULL); |
universe@847 | 530 | } |
universe@847 | 531 | } |
universe@847 | 532 | |
universe@845 | 533 | CX_TEST(test_tree_visitor) { |
universe@845 | 534 | tree_node root = {0}; |
universe@845 | 535 | tree_node a = {0}; |
universe@845 | 536 | tree_node b = {0}; |
universe@845 | 537 | tree_node c = {0}; |
universe@845 | 538 | tree_node aa = {0}; |
universe@845 | 539 | tree_node ab = {0}; |
universe@845 | 540 | tree_node ba = {0}; |
universe@845 | 541 | tree_node ca = {0}; |
universe@845 | 542 | tree_node cb = {0}; |
universe@845 | 543 | tree_node cc = {0}; |
universe@845 | 544 | tree_node cba = {0}; |
universe@845 | 545 | |
universe@845 | 546 | tree_node* expected_order[] = { |
universe@845 | 547 | &root, |
universe@845 | 548 | &c, &b, &a, |
universe@845 | 549 | &cc, &cb, &ca, &ba, &ab, &aa, |
universe@845 | 550 | &cba |
universe@845 | 551 | }; |
universe@845 | 552 | tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong |
universe@845 | 553 | |
universe@845 | 554 | cx_tree_link(&root, &a, tree_node_layout); |
universe@845 | 555 | cx_tree_link(&root, &b, tree_node_layout); |
universe@845 | 556 | cx_tree_link(&root, &c, tree_node_layout); |
universe@845 | 557 | cx_tree_link(&a, &aa, tree_node_layout); |
universe@845 | 558 | cx_tree_link(&a, &ab, tree_node_layout); |
universe@845 | 559 | cx_tree_link(&b, &ba, tree_node_layout); |
universe@845 | 560 | cx_tree_link(&c, &ca, tree_node_layout); |
universe@845 | 561 | cx_tree_link(&c, &cb, tree_node_layout); |
universe@845 | 562 | cx_tree_link(&c, &cc, tree_node_layout); |
universe@845 | 563 | cx_tree_link(&cb, &cba, tree_node_layout); |
universe@845 | 564 | CX_TEST_DO { |
universe@845 | 565 | CxTreeVisitor iter = cx_tree_visitor(&root, tree_child_list); |
universe@845 | 566 | unsigned chk = 0; |
universe@845 | 567 | cx_foreach(tree_node*, node, iter) { |
universe@845 | 568 | CX_TEST_ASSERT(node->data == 0); |
universe@845 | 569 | node->data++; |
universe@845 | 570 | actual_order[chk] = node; |
universe@845 | 571 | chk++; |
universe@845 | 572 | CX_TEST_ASSERT(node == iter.node); |
universe@845 | 573 | if (node == &root) { |
universe@845 | 574 | CX_TEST_ASSERT(iter.depth == 1); |
universe@845 | 575 | } else if (node == &a || node == &b || node == &c) { |
universe@845 | 576 | CX_TEST_ASSERT(iter.depth == 2); |
universe@845 | 577 | } else if (node == &cba) { |
universe@845 | 578 | CX_TEST_ASSERT(iter.depth == 4); |
universe@845 | 579 | } else { |
universe@845 | 580 | CX_TEST_ASSERT(iter.depth == 3); |
universe@845 | 581 | } |
universe@845 | 582 | } |
universe@845 | 583 | CX_TEST_ASSERT(iter.counter == 11); |
universe@845 | 584 | CX_TEST_ASSERT(chk == 11); |
universe@845 | 585 | for (unsigned i = 0 ; i < chk ; i++) { |
universe@845 | 586 | CX_TEST_ASSERT(actual_order[i] == expected_order[i]); |
universe@845 | 587 | CX_TEST_ASSERT(actual_order[i]->data == 1); |
universe@845 | 588 | } |
universe@845 | 589 | CX_TEST_ASSERT(iter.queue_next == NULL); |
universe@845 | 590 | CX_TEST_ASSERT(iter.queue_last == NULL); |
universe@845 | 591 | } |
universe@845 | 592 | } |
universe@845 | 593 | |
universe@845 | 594 | CX_TEST(test_tree_visitor_no_children) { |
universe@845 | 595 | tree_node root = {0}; |
universe@845 | 596 | |
universe@845 | 597 | CX_TEST_DO { |
universe@845 | 598 | CxTreeVisitor iter = cx_tree_visitor(&root, tree_child_list); |
universe@845 | 599 | unsigned chk = 0; |
universe@845 | 600 | cx_foreach(tree_node*, node, iter) { |
universe@845 | 601 | CX_TEST_ASSERT(node == iter.node); |
universe@845 | 602 | chk++; |
universe@845 | 603 | } |
universe@845 | 604 | CX_TEST_ASSERT(iter.counter == 1); |
universe@845 | 605 | CX_TEST_ASSERT(chk == 1); |
universe@845 | 606 | CX_TEST_ASSERT(iter.queue_next == NULL); |
universe@845 | 607 | CX_TEST_ASSERT(iter.queue_last == NULL); |
universe@845 | 608 | } |
universe@845 | 609 | } |
universe@845 | 610 | |
universe@845 | 611 | CX_TEST(test_tree_visitor_no_branching) { |
universe@845 | 612 | tree_node root = {0}; |
universe@845 | 613 | tree_node a = {0}; |
universe@845 | 614 | tree_node b = {0}; |
universe@845 | 615 | tree_node c = {0}; |
universe@845 | 616 | |
universe@845 | 617 | tree_node* expected_order[] = { |
universe@845 | 618 | &root, &a, &b, &c |
universe@845 | 619 | }; |
universe@845 | 620 | tree_node* actual_order[4]; |
universe@845 | 621 | |
universe@845 | 622 | cx_tree_link(&root, &a, tree_node_layout); |
universe@845 | 623 | cx_tree_link(&a, &b, tree_node_layout); |
universe@845 | 624 | cx_tree_link(&b, &c, tree_node_layout); |
universe@845 | 625 | |
universe@845 | 626 | CX_TEST_DO { |
universe@845 | 627 | CxTreeVisitor iter = cx_tree_visitor(&root, tree_child_list); |
universe@845 | 628 | unsigned chk = 0; |
universe@845 | 629 | cx_foreach(tree_node*, node, iter) { |
universe@845 | 630 | CX_TEST_ASSERT(node == iter.node); |
universe@845 | 631 | CX_TEST_ASSERT(node->data == 0); |
universe@845 | 632 | node->data++; |
universe@845 | 633 | actual_order[chk] = node; |
universe@845 | 634 | chk++; |
universe@845 | 635 | } |
universe@845 | 636 | CX_TEST_ASSERT(iter.counter == 4); |
universe@845 | 637 | CX_TEST_ASSERT(chk == 4); |
universe@845 | 638 | CX_TEST_ASSERT(iter.queue_next == NULL); |
universe@845 | 639 | CX_TEST_ASSERT(iter.queue_last == NULL); |
universe@845 | 640 | for (unsigned i = 0 ; i < chk ; i++) { |
universe@845 | 641 | CX_TEST_ASSERT(actual_order[i] == expected_order[i]); |
universe@845 | 642 | CX_TEST_ASSERT(actual_order[i]->data == 1); |
universe@845 | 643 | } |
universe@845 | 644 | } |
universe@845 | 645 | } |
universe@845 | 646 | |
universe@816 | 647 | CxTestSuite *cx_test_suite_tree_low_level(void) { |
universe@816 | 648 | CxTestSuite *suite = cx_test_suite_new("tree (low level)"); |
universe@816 | 649 | |
universe@816 | 650 | cx_test_register(suite, test_tree_link_new_child); |
universe@816 | 651 | cx_test_register(suite, test_tree_link_add_child); |
universe@816 | 652 | cx_test_register(suite, test_tree_link_move_to_other_parent); |
universe@816 | 653 | cx_test_register(suite, test_tree_unlink); |
universe@826 | 654 | cx_test_register(suite, test_tree_search); |
universe@836 | 655 | cx_test_register(suite, test_tree_iterator_create_and_dispose); |
universe@838 | 656 | cx_test_register(suite, test_tree_iterator_basic_only_enter); |
universe@838 | 657 | cx_test_register(suite, test_tree_iterator_basic_enter_and_exit); |
universe@839 | 658 | cx_test_register(suite, test_tree_iterator_xml); |
universe@840 | 659 | cx_test_register(suite, test_tree_iterator_free_nodes); |
universe@845 | 660 | cx_test_register(suite, test_tree_visitor); |
universe@845 | 661 | cx_test_register(suite, test_tree_visitor_no_children); |
universe@845 | 662 | cx_test_register(suite, test_tree_visitor_no_branching); |
universe@816 | 663 | |
universe@816 | 664 | return suite; |
universe@816 | 665 | } |