|
1 /* |
|
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. |
|
3 * |
|
4 * Copyright 2023 Mike Becker, Olaf Wintermann All rights reserved. |
|
5 * |
|
6 * Redistribution and use in source and binary forms, with or without |
|
7 * modification, are permitted provided that the following conditions are met: |
|
8 * |
|
9 * 1. Redistributions of source code must retain the above copyright |
|
10 * notice, this list of conditions and the following disclaimer. |
|
11 * |
|
12 * 2. Redistributions in binary form must reproduce the above copyright |
|
13 * notice, this list of conditions and the following disclaimer in the |
|
14 * documentation and/or other materials provided with the distribution. |
|
15 * |
|
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
|
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
|
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
|
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE |
|
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
|
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
|
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
|
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
|
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
|
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
|
26 * POSSIBILITY OF SUCH DAMAGE. |
|
27 */ |
|
28 |
|
29 #include "cx/tree.h" |
|
30 |
|
31 #include "cx/test.h" |
|
32 |
|
33 typedef struct tree_node { |
|
34 struct tree_node *parent; |
|
35 struct tree_node *next; |
|
36 struct tree_node *prev; |
|
37 struct tree_node *children; |
|
38 int data; |
|
39 } tree_node; |
|
40 |
|
41 #define tree_node_layout \ |
|
42 offsetof(tree_node, parent), offsetof(tree_node, children), \ |
|
43 offsetof(tree_node, prev), offsetof(tree_node, next) |
|
44 |
|
45 CX_TEST(test_tree_link_new_child) { |
|
46 tree_node parent = {0}; |
|
47 tree_node child = {0}; |
|
48 |
|
49 CX_TEST_DO { |
|
50 cx_tree_link(&parent, &child, tree_node_layout); |
|
51 CX_TEST_ASSERT(parent.next == NULL); |
|
52 CX_TEST_ASSERT(parent.prev == NULL); |
|
53 CX_TEST_ASSERT(parent.parent == NULL); |
|
54 CX_TEST_ASSERT(parent.children == &child); |
|
55 CX_TEST_ASSERT(child.parent == &parent); |
|
56 CX_TEST_ASSERT(child.next == NULL); |
|
57 CX_TEST_ASSERT(child.prev == NULL); |
|
58 CX_TEST_ASSERT(child.children == NULL); |
|
59 } |
|
60 } |
|
61 |
|
62 CX_TEST(test_tree_link_add_child) { |
|
63 tree_node parent = {0}; |
|
64 tree_node child1 = {0}; |
|
65 tree_node child2 = {0}; |
|
66 tree_node child3 = {0}; |
|
67 |
|
68 CX_TEST_DO { |
|
69 cx_tree_link(&parent, &child1, tree_node_layout); |
|
70 cx_tree_link(&parent, &child2, tree_node_layout); |
|
71 cx_tree_link(&parent, &child3, tree_node_layout); |
|
72 CX_TEST_ASSERT(parent.next == NULL); |
|
73 CX_TEST_ASSERT(parent.prev == NULL); |
|
74 CX_TEST_ASSERT(parent.parent == NULL); |
|
75 CX_TEST_ASSERT(parent.children == &child3); |
|
76 |
|
77 CX_TEST_ASSERT(child1.parent == &parent); |
|
78 CX_TEST_ASSERT(child2.parent == &parent); |
|
79 CX_TEST_ASSERT(child3.parent == &parent); |
|
80 CX_TEST_ASSERT(child1.children == NULL); |
|
81 CX_TEST_ASSERT(child2.children == NULL); |
|
82 CX_TEST_ASSERT(child3.children == NULL); |
|
83 |
|
84 CX_TEST_ASSERT(child3.prev == NULL); |
|
85 CX_TEST_ASSERT(child3.next == &child2); |
|
86 CX_TEST_ASSERT(child2.prev == &child3); |
|
87 CX_TEST_ASSERT(child2.next == &child1); |
|
88 CX_TEST_ASSERT(child1.prev == &child2); |
|
89 CX_TEST_ASSERT(child1.next == NULL); |
|
90 } |
|
91 } |
|
92 |
|
93 CX_TEST(test_tree_link_move_to_other_parent) { |
|
94 tree_node parent = {0}; |
|
95 tree_node child1 = {0}; |
|
96 tree_node child2 = {0}; |
|
97 tree_node child3 = {0}; |
|
98 cx_tree_link(&parent, &child1, tree_node_layout); |
|
99 cx_tree_link(&parent, &child2, tree_node_layout); |
|
100 cx_tree_link(&parent, &child3, tree_node_layout); |
|
101 |
|
102 CX_TEST_DO { |
|
103 cx_tree_link(&child3, &child2, tree_node_layout); |
|
104 |
|
105 CX_TEST_ASSERT(parent.next == NULL); |
|
106 CX_TEST_ASSERT(parent.prev == NULL); |
|
107 CX_TEST_ASSERT(parent.parent == NULL); |
|
108 CX_TEST_ASSERT(parent.children == &child3); |
|
109 |
|
110 CX_TEST_ASSERT(child1.parent == &parent); |
|
111 CX_TEST_ASSERT(child2.parent == &child3); |
|
112 CX_TEST_ASSERT(child3.parent == &parent); |
|
113 CX_TEST_ASSERT(child1.children == NULL); |
|
114 CX_TEST_ASSERT(child2.children == NULL); |
|
115 CX_TEST_ASSERT(child3.children == &child2); |
|
116 |
|
117 CX_TEST_ASSERT(child3.prev == NULL); |
|
118 CX_TEST_ASSERT(child3.next == &child1); |
|
119 CX_TEST_ASSERT(child1.prev == &child3); |
|
120 CX_TEST_ASSERT(child1.next == NULL); |
|
121 |
|
122 CX_TEST_ASSERT(child2.prev == NULL); |
|
123 CX_TEST_ASSERT(child2.next == NULL); |
|
124 } |
|
125 } |
|
126 |
|
127 CX_TEST(test_tree_unlink) { |
|
128 tree_node parent = {0}; |
|
129 tree_node child1 = {0}; |
|
130 tree_node child2 = {0}; |
|
131 tree_node child3 = {0}; |
|
132 cx_tree_link(&parent, &child1, tree_node_layout); |
|
133 cx_tree_link(&parent, &child3, tree_node_layout); |
|
134 cx_tree_link(&child3, &child2, tree_node_layout); |
|
135 |
|
136 CX_TEST_DO { |
|
137 cx_tree_unlink(&child3, tree_node_layout); |
|
138 |
|
139 CX_TEST_ASSERT(parent.next == NULL); |
|
140 CX_TEST_ASSERT(parent.prev == NULL); |
|
141 CX_TEST_ASSERT(parent.parent == NULL); |
|
142 CX_TEST_ASSERT(parent.children == &child1); |
|
143 |
|
144 CX_TEST_ASSERT(child1.parent == &parent); |
|
145 CX_TEST_ASSERT(child1.children == NULL); |
|
146 CX_TEST_ASSERT(child1.prev == NULL); |
|
147 CX_TEST_ASSERT(child1.next == NULL); |
|
148 |
|
149 // child 3 is unlinked |
|
150 CX_TEST_ASSERT(child3.parent == NULL); |
|
151 CX_TEST_ASSERT(child3.prev == NULL); |
|
152 CX_TEST_ASSERT(child3.next == NULL); |
|
153 |
|
154 // child 2 is still child of the unlinked child 3 |
|
155 CX_TEST_ASSERT(child3.children == &child2); |
|
156 CX_TEST_ASSERT(child2.parent == &child3); |
|
157 CX_TEST_ASSERT(child2.children == NULL); |
|
158 CX_TEST_ASSERT(child2.prev == NULL); |
|
159 CX_TEST_ASSERT(child2.next == NULL); |
|
160 } |
|
161 } |
|
162 |
|
163 CxTestSuite *cx_test_suite_tree_low_level(void) { |
|
164 CxTestSuite *suite = cx_test_suite_new("tree (low level)"); |
|
165 |
|
166 cx_test_register(suite, test_tree_link_new_child); |
|
167 cx_test_register(suite, test_tree_link_add_child); |
|
168 cx_test_register(suite, test_tree_link_move_to_other_parent); |
|
169 cx_test_register(suite, test_tree_unlink); |
|
170 |
|
171 return suite; |
|
172 } |