40 |
40 |
41 #define tree_node_layout \ |
41 #define tree_node_layout \ |
42 offsetof(tree_node, parent), offsetof(tree_node, children), \ |
42 offsetof(tree_node, parent), offsetof(tree_node, children), \ |
43 offsetof(tree_node, prev), offsetof(tree_node, next) |
43 offsetof(tree_node, prev), offsetof(tree_node, next) |
44 |
44 |
|
45 #define tree_child_list offsetof(tree_node, children),offsetof(tree_node, next) |
|
46 |
45 CX_TEST(test_tree_link_new_child) { |
47 CX_TEST(test_tree_link_new_child) { |
46 tree_node parent = {0}; |
48 tree_node parent = {0}; |
47 tree_node child = {0}; |
49 tree_node child = {0}; |
48 |
50 |
49 CX_TEST_DO { |
51 CX_TEST_DO { |
158 CX_TEST_ASSERT(child2.prev == NULL); |
160 CX_TEST_ASSERT(child2.prev == NULL); |
159 CX_TEST_ASSERT(child2.next == NULL); |
161 CX_TEST_ASSERT(child2.next == NULL); |
160 } |
162 } |
161 } |
163 } |
162 |
164 |
|
165 static int test_tree_search_function(void const *n, void const *d) { |
|
166 tree_node const *node = n; |
|
167 int data = *((int const*)d); |
|
168 |
|
169 if (data < node->data) return -1; |
|
170 else if (data == node->data) return 0; |
|
171 else return data - node->data; |
|
172 } |
|
173 |
|
174 CX_TEST(test_tree_search) { |
|
175 tree_node root = {0}; |
|
176 tree_node a = {0}; |
|
177 tree_node b = {0}; |
|
178 tree_node c = {0}; |
|
179 tree_node aa = {0}; |
|
180 tree_node ab = {0}; |
|
181 tree_node ba = {0}; |
|
182 tree_node ca = {0}; |
|
183 tree_node cb = {0}; |
|
184 tree_node cc = {0}; |
|
185 tree_node cba = {0}; |
|
186 |
|
187 int testdata[] = {0, 10, 14, 18, 20, 25, 30, 32, 34, 36, 40}; |
|
188 tree_node* testnodes[] = {&root, &a, &aa, &ab, &b, &ba, &c, &ca, &cb, &cba, &cc}; |
|
189 |
|
190 for (unsigned i = 0 ; i <= 10 ; i++) { |
|
191 testnodes[i]->data = testdata[i]; |
|
192 } |
|
193 |
|
194 cx_tree_link(&root, &a, tree_node_layout); |
|
195 cx_tree_link(&root, &b, tree_node_layout); |
|
196 cx_tree_link(&root, &c, tree_node_layout); |
|
197 |
|
198 cx_tree_link(&a, &aa, tree_node_layout); |
|
199 cx_tree_link(&a, &ab, tree_node_layout); |
|
200 |
|
201 cx_tree_link(&b, &ba, tree_node_layout); |
|
202 |
|
203 cx_tree_link(&c, &ca, tree_node_layout); |
|
204 cx_tree_link(&c, &cb, tree_node_layout); |
|
205 cx_tree_link(&c, &cc, tree_node_layout); |
|
206 |
|
207 cx_tree_link(&cb, &cba, tree_node_layout); |
|
208 |
|
209 int s; |
|
210 int r; |
|
211 tree_node *n; |
|
212 CX_TEST_DO { |
|
213 for (unsigned i = 0 ; i <= 10 ; i++) { |
|
214 s = testdata[i]; |
|
215 r = cx_tree_search(&root, &s, test_tree_search_function, |
|
216 (void **) &n, tree_child_list); |
|
217 CX_TEST_ASSERT(r == 0); |
|
218 CX_TEST_ASSERT(n == testnodes[i]); |
|
219 } |
|
220 |
|
221 s = -5; |
|
222 r = cx_tree_search(&root, &s, test_tree_search_function, |
|
223 (void **) &n, tree_child_list); |
|
224 CX_TEST_ASSERT(r < 0); |
|
225 CX_TEST_ASSERT(n == NULL); |
|
226 |
|
227 s = 26; |
|
228 r = cx_tree_search(&root, &s, test_tree_search_function, |
|
229 (void **) &n, tree_child_list); |
|
230 CX_TEST_ASSERT(r > 0); |
|
231 CX_TEST_ASSERT(n == &ba); |
|
232 |
|
233 s = 35; |
|
234 r = cx_tree_search(&root, &s, test_tree_search_function, |
|
235 (void **) &n, tree_child_list); |
|
236 CX_TEST_ASSERT(r > 0); |
|
237 CX_TEST_ASSERT(n == &cb); |
|
238 |
|
239 s = 38; |
|
240 r = cx_tree_search(&root, &s, test_tree_search_function, |
|
241 (void **) &n, tree_child_list); |
|
242 CX_TEST_ASSERT(r > 0); |
|
243 CX_TEST_ASSERT(n == &cba); |
|
244 |
|
245 s = 42; |
|
246 r = cx_tree_search(&root, &s, test_tree_search_function, |
|
247 (void **) &n, tree_child_list); |
|
248 CX_TEST_ASSERT(r > 0); |
|
249 CX_TEST_ASSERT(n == &cc); |
|
250 } |
|
251 } |
|
252 |
163 CxTestSuite *cx_test_suite_tree_low_level(void) { |
253 CxTestSuite *cx_test_suite_tree_low_level(void) { |
164 CxTestSuite *suite = cx_test_suite_new("tree (low level)"); |
254 CxTestSuite *suite = cx_test_suite_new("tree (low level)"); |
165 |
255 |
166 cx_test_register(suite, test_tree_link_new_child); |
256 cx_test_register(suite, test_tree_link_new_child); |
167 cx_test_register(suite, test_tree_link_add_child); |
257 cx_test_register(suite, test_tree_link_add_child); |
168 cx_test_register(suite, test_tree_link_move_to_other_parent); |
258 cx_test_register(suite, test_tree_link_move_to_other_parent); |
169 cx_test_register(suite, test_tree_unlink); |
259 cx_test_register(suite, test_tree_unlink); |
|
260 cx_test_register(suite, test_tree_search); |
170 |
261 |
171 return suite; |
262 return suite; |
172 } |
263 } |