1.1 --- a/tests/test_tree.c Wed Feb 14 22:32:13 2024 +0100
1.2 +++ b/tests/test_tree.c Thu Feb 15 21:54:43 2024 +0100
1.3 @@ -42,6 +42,8 @@
1.4 offsetof(tree_node, parent), offsetof(tree_node, children), \
1.5 offsetof(tree_node, prev), offsetof(tree_node, next)
1.6
1.7 +#define tree_child_list offsetof(tree_node, children),offsetof(tree_node, next)
1.8 +
1.9 CX_TEST(test_tree_link_new_child) {
1.10 tree_node parent = {0};
1.11 tree_node child = {0};
1.12 @@ -160,6 +162,94 @@
1.13 }
1.14 }
1.15
1.16 +static int test_tree_search_function(void const *n, void const *d) {
1.17 + tree_node const *node = n;
1.18 + int data = *((int const*)d);
1.19 +
1.20 + if (data < node->data) return -1;
1.21 + else if (data == node->data) return 0;
1.22 + else return data - node->data;
1.23 +}
1.24 +
1.25 +CX_TEST(test_tree_search) {
1.26 + tree_node root = {0};
1.27 + tree_node a = {0};
1.28 + tree_node b = {0};
1.29 + tree_node c = {0};
1.30 + tree_node aa = {0};
1.31 + tree_node ab = {0};
1.32 + tree_node ba = {0};
1.33 + tree_node ca = {0};
1.34 + tree_node cb = {0};
1.35 + tree_node cc = {0};
1.36 + tree_node cba = {0};
1.37 +
1.38 + int testdata[] = {0, 10, 14, 18, 20, 25, 30, 32, 34, 36, 40};
1.39 + tree_node* testnodes[] = {&root, &a, &aa, &ab, &b, &ba, &c, &ca, &cb, &cba, &cc};
1.40 +
1.41 + for (unsigned i = 0 ; i <= 10 ; i++) {
1.42 + testnodes[i]->data = testdata[i];
1.43 + }
1.44 +
1.45 + cx_tree_link(&root, &a, tree_node_layout);
1.46 + cx_tree_link(&root, &b, tree_node_layout);
1.47 + cx_tree_link(&root, &c, tree_node_layout);
1.48 +
1.49 + cx_tree_link(&a, &aa, tree_node_layout);
1.50 + cx_tree_link(&a, &ab, tree_node_layout);
1.51 +
1.52 + cx_tree_link(&b, &ba, tree_node_layout);
1.53 +
1.54 + cx_tree_link(&c, &ca, tree_node_layout);
1.55 + cx_tree_link(&c, &cb, tree_node_layout);
1.56 + cx_tree_link(&c, &cc, tree_node_layout);
1.57 +
1.58 + cx_tree_link(&cb, &cba, tree_node_layout);
1.59 +
1.60 + int s;
1.61 + int r;
1.62 + tree_node *n;
1.63 + CX_TEST_DO {
1.64 + for (unsigned i = 0 ; i <= 10 ; i++) {
1.65 + s = testdata[i];
1.66 + r = cx_tree_search(&root, &s, test_tree_search_function,
1.67 + (void **) &n, tree_child_list);
1.68 + CX_TEST_ASSERT(r == 0);
1.69 + CX_TEST_ASSERT(n == testnodes[i]);
1.70 + }
1.71 +
1.72 + s = -5;
1.73 + r = cx_tree_search(&root, &s, test_tree_search_function,
1.74 + (void **) &n, tree_child_list);
1.75 + CX_TEST_ASSERT(r < 0);
1.76 + CX_TEST_ASSERT(n == NULL);
1.77 +
1.78 + s = 26;
1.79 + r = cx_tree_search(&root, &s, test_tree_search_function,
1.80 + (void **) &n, tree_child_list);
1.81 + CX_TEST_ASSERT(r > 0);
1.82 + CX_TEST_ASSERT(n == &ba);
1.83 +
1.84 + s = 35;
1.85 + r = cx_tree_search(&root, &s, test_tree_search_function,
1.86 + (void **) &n, tree_child_list);
1.87 + CX_TEST_ASSERT(r > 0);
1.88 + CX_TEST_ASSERT(n == &cb);
1.89 +
1.90 + s = 38;
1.91 + r = cx_tree_search(&root, &s, test_tree_search_function,
1.92 + (void **) &n, tree_child_list);
1.93 + CX_TEST_ASSERT(r > 0);
1.94 + CX_TEST_ASSERT(n == &cba);
1.95 +
1.96 + s = 42;
1.97 + r = cx_tree_search(&root, &s, test_tree_search_function,
1.98 + (void **) &n, tree_child_list);
1.99 + CX_TEST_ASSERT(r > 0);
1.100 + CX_TEST_ASSERT(n == &cc);
1.101 + }
1.102 +}
1.103 +
1.104 CxTestSuite *cx_test_suite_tree_low_level(void) {
1.105 CxTestSuite *suite = cx_test_suite_new("tree (low level)");
1.106
1.107 @@ -167,6 +257,7 @@
1.108 cx_test_register(suite, test_tree_link_add_child);
1.109 cx_test_register(suite, test_tree_link_move_to_other_parent);
1.110 cx_test_register(suite, test_tree_unlink);
1.111 + cx_test_register(suite, test_tree_search);
1.112
1.113 return suite;
1.114 }
