Mon, 22 Jan 2024 19:34:38 +0100
add first basic low level tree functions
relates to #165 tested by issue #167
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@816 | 45 | CX_TEST(test_tree_link_new_child) { |
universe@816 | 46 | tree_node parent = {0}; |
universe@816 | 47 | tree_node child = {0}; |
universe@816 | 48 | |
universe@816 | 49 | CX_TEST_DO { |
universe@816 | 50 | cx_tree_link(&parent, &child, tree_node_layout); |
universe@816 | 51 | CX_TEST_ASSERT(parent.next == NULL); |
universe@816 | 52 | CX_TEST_ASSERT(parent.prev == NULL); |
universe@816 | 53 | CX_TEST_ASSERT(parent.parent == NULL); |
universe@816 | 54 | CX_TEST_ASSERT(parent.children == &child); |
universe@816 | 55 | CX_TEST_ASSERT(child.parent == &parent); |
universe@816 | 56 | CX_TEST_ASSERT(child.next == NULL); |
universe@816 | 57 | CX_TEST_ASSERT(child.prev == NULL); |
universe@816 | 58 | CX_TEST_ASSERT(child.children == NULL); |
universe@816 | 59 | } |
universe@816 | 60 | } |
universe@816 | 61 | |
universe@816 | 62 | CX_TEST(test_tree_link_add_child) { |
universe@816 | 63 | tree_node parent = {0}; |
universe@816 | 64 | tree_node child1 = {0}; |
universe@816 | 65 | tree_node child2 = {0}; |
universe@816 | 66 | tree_node child3 = {0}; |
universe@816 | 67 | |
universe@816 | 68 | CX_TEST_DO { |
universe@816 | 69 | cx_tree_link(&parent, &child1, tree_node_layout); |
universe@816 | 70 | cx_tree_link(&parent, &child2, tree_node_layout); |
universe@816 | 71 | cx_tree_link(&parent, &child3, tree_node_layout); |
universe@816 | 72 | CX_TEST_ASSERT(parent.next == NULL); |
universe@816 | 73 | CX_TEST_ASSERT(parent.prev == NULL); |
universe@816 | 74 | CX_TEST_ASSERT(parent.parent == NULL); |
universe@816 | 75 | CX_TEST_ASSERT(parent.children == &child3); |
universe@816 | 76 | |
universe@816 | 77 | CX_TEST_ASSERT(child1.parent == &parent); |
universe@816 | 78 | CX_TEST_ASSERT(child2.parent == &parent); |
universe@816 | 79 | CX_TEST_ASSERT(child3.parent == &parent); |
universe@816 | 80 | CX_TEST_ASSERT(child1.children == NULL); |
universe@816 | 81 | CX_TEST_ASSERT(child2.children == NULL); |
universe@816 | 82 | CX_TEST_ASSERT(child3.children == NULL); |
universe@816 | 83 | |
universe@816 | 84 | CX_TEST_ASSERT(child3.prev == NULL); |
universe@816 | 85 | CX_TEST_ASSERT(child3.next == &child2); |
universe@816 | 86 | CX_TEST_ASSERT(child2.prev == &child3); |
universe@816 | 87 | CX_TEST_ASSERT(child2.next == &child1); |
universe@816 | 88 | CX_TEST_ASSERT(child1.prev == &child2); |
universe@816 | 89 | CX_TEST_ASSERT(child1.next == NULL); |
universe@816 | 90 | } |
universe@816 | 91 | } |
universe@816 | 92 | |
universe@816 | 93 | CX_TEST(test_tree_link_move_to_other_parent) { |
universe@816 | 94 | tree_node parent = {0}; |
universe@816 | 95 | tree_node child1 = {0}; |
universe@816 | 96 | tree_node child2 = {0}; |
universe@816 | 97 | tree_node child3 = {0}; |
universe@816 | 98 | cx_tree_link(&parent, &child1, tree_node_layout); |
universe@816 | 99 | cx_tree_link(&parent, &child2, tree_node_layout); |
universe@816 | 100 | cx_tree_link(&parent, &child3, tree_node_layout); |
universe@816 | 101 | |
universe@816 | 102 | CX_TEST_DO { |
universe@816 | 103 | cx_tree_link(&child3, &child2, tree_node_layout); |
universe@816 | 104 | |
universe@816 | 105 | CX_TEST_ASSERT(parent.next == NULL); |
universe@816 | 106 | CX_TEST_ASSERT(parent.prev == NULL); |
universe@816 | 107 | CX_TEST_ASSERT(parent.parent == NULL); |
universe@816 | 108 | CX_TEST_ASSERT(parent.children == &child3); |
universe@816 | 109 | |
universe@816 | 110 | CX_TEST_ASSERT(child1.parent == &parent); |
universe@816 | 111 | CX_TEST_ASSERT(child2.parent == &child3); |
universe@816 | 112 | CX_TEST_ASSERT(child3.parent == &parent); |
universe@816 | 113 | CX_TEST_ASSERT(child1.children == NULL); |
universe@816 | 114 | CX_TEST_ASSERT(child2.children == NULL); |
universe@816 | 115 | CX_TEST_ASSERT(child3.children == &child2); |
universe@816 | 116 | |
universe@816 | 117 | CX_TEST_ASSERT(child3.prev == NULL); |
universe@816 | 118 | CX_TEST_ASSERT(child3.next == &child1); |
universe@816 | 119 | CX_TEST_ASSERT(child1.prev == &child3); |
universe@816 | 120 | CX_TEST_ASSERT(child1.next == NULL); |
universe@816 | 121 | |
universe@816 | 122 | CX_TEST_ASSERT(child2.prev == NULL); |
universe@816 | 123 | CX_TEST_ASSERT(child2.next == NULL); |
universe@816 | 124 | } |
universe@816 | 125 | } |
universe@816 | 126 | |
universe@816 | 127 | CX_TEST(test_tree_unlink) { |
universe@816 | 128 | tree_node parent = {0}; |
universe@816 | 129 | tree_node child1 = {0}; |
universe@816 | 130 | tree_node child2 = {0}; |
universe@816 | 131 | tree_node child3 = {0}; |
universe@816 | 132 | cx_tree_link(&parent, &child1, tree_node_layout); |
universe@816 | 133 | cx_tree_link(&parent, &child3, tree_node_layout); |
universe@816 | 134 | cx_tree_link(&child3, &child2, tree_node_layout); |
universe@816 | 135 | |
universe@816 | 136 | CX_TEST_DO { |
universe@816 | 137 | cx_tree_unlink(&child3, tree_node_layout); |
universe@816 | 138 | |
universe@816 | 139 | CX_TEST_ASSERT(parent.next == NULL); |
universe@816 | 140 | CX_TEST_ASSERT(parent.prev == NULL); |
universe@816 | 141 | CX_TEST_ASSERT(parent.parent == NULL); |
universe@816 | 142 | CX_TEST_ASSERT(parent.children == &child1); |
universe@816 | 143 | |
universe@816 | 144 | CX_TEST_ASSERT(child1.parent == &parent); |
universe@816 | 145 | CX_TEST_ASSERT(child1.children == NULL); |
universe@816 | 146 | CX_TEST_ASSERT(child1.prev == NULL); |
universe@816 | 147 | CX_TEST_ASSERT(child1.next == NULL); |
universe@816 | 148 | |
universe@816 | 149 | // child 3 is unlinked |
universe@816 | 150 | CX_TEST_ASSERT(child3.parent == NULL); |
universe@816 | 151 | CX_TEST_ASSERT(child3.prev == NULL); |
universe@816 | 152 | CX_TEST_ASSERT(child3.next == NULL); |
universe@816 | 153 | |
universe@816 | 154 | // child 2 is still child of the unlinked child 3 |
universe@816 | 155 | CX_TEST_ASSERT(child3.children == &child2); |
universe@816 | 156 | CX_TEST_ASSERT(child2.parent == &child3); |
universe@816 | 157 | CX_TEST_ASSERT(child2.children == NULL); |
universe@816 | 158 | CX_TEST_ASSERT(child2.prev == NULL); |
universe@816 | 159 | CX_TEST_ASSERT(child2.next == NULL); |
universe@816 | 160 | } |
universe@816 | 161 | } |
universe@816 | 162 | |
universe@816 | 163 | CxTestSuite *cx_test_suite_tree_low_level(void) { |
universe@816 | 164 | CxTestSuite *suite = cx_test_suite_new("tree (low level)"); |
universe@816 | 165 | |
universe@816 | 166 | cx_test_register(suite, test_tree_link_new_child); |
universe@816 | 167 | cx_test_register(suite, test_tree_link_add_child); |
universe@816 | 168 | cx_test_register(suite, test_tree_link_move_to_other_parent); |
universe@816 | 169 | cx_test_register(suite, test_tree_unlink); |
universe@816 | 170 | |
universe@816 | 171 | return suite; |
universe@816 | 172 | } |