Wed, 03 Apr 2024 21:22:23 +0200
implement tree continue - fixes #376
src/cx/tree.h | file | annotate | diff | comparison | revisions | |
src/tree.c | file | annotate | diff | comparison | revisions | |
tests/test_tree.c | file | annotate | diff | comparison | revisions |
1.1 --- a/src/cx/tree.h Wed Mar 20 23:35:32 2024 +0100 1.2 +++ b/src/cx/tree.h Wed Apr 03 21:22:23 2024 +0200 1.3 @@ -63,6 +63,10 @@ 1.4 */ 1.5 struct cx_iterator_base_s base; 1.6 /** 1.7 + * Indicates whether the subtree below the current node shall be skipped. 1.8 + */ 1.9 + bool skip; 1.10 + /** 1.11 * Set to true, when the iterator shall visit a node again 1.12 * when all it's children have been processed. 1.13 */ 1.14 @@ -158,6 +162,10 @@ 1.15 */ 1.16 struct cx_iterator_base_s base; 1.17 /** 1.18 + * Indicates whether the subtree below the current node shall be skipped. 1.19 + */ 1.20 + bool skip; 1.21 + /** 1.22 * Offset in the node struct for the children linked list. 1.23 */ 1.24 ptrdiff_t loc_children; 1.25 @@ -214,6 +222,22 @@ 1.26 } 1.27 1.28 /** 1.29 + * Advises the iterator to skip the subtree below the current node and 1.30 + * also continues the current loop. 1.31 + * 1.32 + * @param iterator the iterator 1.33 + */ 1.34 +#define cxTreeIteratorContinue(iterator) (iterator).skip = true; continue 1.35 + 1.36 +/** 1.37 + * Advises the visitor to skip the subtree below the current node and 1.38 + * also continues the current loop. 1.39 + * 1.40 + * @param visitor the visitor 1.41 + */ 1.42 +#define cxTreeVisitorContinue(visitor) cxTreeIteratorContinue(visitor) 1.43 + 1.44 +/** 1.45 * Links a node to a (new) parent. 1.46 * 1.47 * If the node has already a parent, it is unlinked, first.
2.1 --- a/src/tree.c Wed Mar 20 23:35:32 2024 +0100 2.2 +++ b/src/tree.c Wed Apr 03 21:22:23 2024 +0200 2.3 @@ -186,8 +186,17 @@ 2.4 // check if we are currently exiting or entering nodes 2.5 if (iter->exiting) { 2.6 children = NULL; 2.7 + // skipping on exit is pointless, just clear the flag 2.8 + iter->skip = false; 2.9 } else { 2.10 - children = tree_children(iter->node); 2.11 + if (iter->skip) { 2.12 + // skip flag is set, pretend that there are no children 2.13 + iter->skip = false; 2.14 + children = NULL; 2.15 + } else { 2.16 + // try to enter the children (if any) 2.17 + children = tree_children(iter->node); 2.18 + } 2.19 } 2.20 2.21 if (children == NULL) { 2.22 @@ -263,10 +272,12 @@ 2.23 2.24 // visit the root node 2.25 iter.node = root; 2.26 + iter.next = NULL; 2.27 iter.counter = 1; 2.28 iter.depth = 1; 2.29 iter.stack[0] = root; 2.30 iter.exiting = false; 2.31 + iter.skip = false; 2.32 2.33 // assign base iterator functions 2.34 iter.base.mutating = false; 2.35 @@ -310,6 +321,30 @@ 2.36 ptrdiff_t const loc_next = iter->loc_next; 2.37 ptrdiff_t const loc_children = iter->loc_children; 2.38 2.39 + // add the children of the current node to the queue 2.40 + // unless the skip flag is set 2.41 + void *children; 2.42 + if (iter->skip) { 2.43 + iter->skip = false; 2.44 + children = NULL; 2.45 + } else { 2.46 + children = tree_children(iter->node); 2.47 + } 2.48 + if (children != NULL) { 2.49 + struct cx_tree_visitor_queue_s *q; 2.50 + q = malloc(sizeof(struct cx_tree_visitor_queue_s)); 2.51 + q->depth = iter->depth + 1; 2.52 + q->node = children; 2.53 + if (iter->queue_last == NULL) { 2.54 + assert(iter->queue_next == NULL); 2.55 + iter->queue_next = q; 2.56 + } else { 2.57 + iter->queue_last->next = q; 2.58 + } 2.59 + iter->queue_last = q; 2.60 + cx_tree_visitor_enqueue_siblings(iter, children, loc_next); 2.61 + } 2.62 + 2.63 // check if there is a next node 2.64 if (iter->queue_next == NULL) { 2.65 iter->node = NULL; 2.66 @@ -331,23 +366,6 @@ 2.67 2.68 // increment the node counter 2.69 iter->counter++; 2.70 - 2.71 - // add the children of the new node to the queue 2.72 - void *children = tree_children(iter->node); 2.73 - if (children != NULL) { 2.74 - struct cx_tree_visitor_queue_s *q; 2.75 - q = malloc(sizeof(struct cx_tree_visitor_queue_s)); 2.76 - q->depth = iter->depth + 1; 2.77 - q->node = children; 2.78 - if (iter->queue_last == NULL) { 2.79 - assert(iter->queue_next == NULL); 2.80 - iter->queue_next = q; 2.81 - } else { 2.82 - iter->queue_last->next = q; 2.83 - } 2.84 - iter->queue_last = q; 2.85 - cx_tree_visitor_enqueue_siblings(iter, children, loc_next); 2.86 - } 2.87 } 2.88 2.89 CxTreeVisitor cx_tree_visitor( 2.90 @@ -366,19 +384,9 @@ 2.91 iter.node = root; 2.92 iter.counter = 1; 2.93 iter.depth = 1; 2.94 - 2.95 - // put all children of root into the queue 2.96 - void *children = tree_children(root); 2.97 - if (children == NULL) { 2.98 - iter.queue_next = NULL; 2.99 - iter.queue_last = NULL; 2.100 - } else { 2.101 - iter.queue_next = malloc(sizeof(struct cx_tree_visitor_queue_s)); 2.102 - iter.queue_next->depth = 2; 2.103 - iter.queue_next->node = children; 2.104 - iter.queue_last = iter.queue_next; 2.105 - cx_tree_visitor_enqueue_siblings(&iter, children, loc_next); 2.106 - } 2.107 + iter.skip = false; 2.108 + iter.queue_next = NULL; 2.109 + iter.queue_last = NULL; 2.110 2.111 // assign base iterator functions 2.112 iter.base.mutating = false;
3.1 --- a/tests/test_tree.c Wed Mar 20 23:35:32 2024 +0100 3.2 +++ b/tests/test_tree.c Wed Apr 03 21:22:23 2024 +0200 3.3 @@ -644,6 +644,196 @@ 3.4 } 3.5 } 3.6 3.7 +CX_TEST(test_tree_visitor_continue) { 3.8 + tree_node root = {0}; 3.9 + tree_node a = {0}; 3.10 + tree_node b = {0}; 3.11 + tree_node c = {0}; 3.12 + tree_node aa = {0}; 3.13 + tree_node ab = {0}; 3.14 + tree_node ba = {0}; 3.15 + tree_node ca = {0}; 3.16 + tree_node cb = {0}; 3.17 + tree_node cc = {0}; 3.18 + tree_node cba = {0}; 3.19 + 3.20 + tree_node* expected_order[] = { 3.21 + &root, 3.22 + &c, &b, &a, 3.23 + &ba, &ab, &aa 3.24 + }; 3.25 + tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong 3.26 + 3.27 + cx_tree_link(&root, &a, tree_node_layout); 3.28 + cx_tree_link(&root, &b, tree_node_layout); 3.29 + cx_tree_link(&root, &c, tree_node_layout); 3.30 + cx_tree_link(&a, &aa, tree_node_layout); 3.31 + cx_tree_link(&a, &ab, tree_node_layout); 3.32 + cx_tree_link(&b, &ba, tree_node_layout); 3.33 + cx_tree_link(&c, &ca, tree_node_layout); 3.34 + cx_tree_link(&c, &cb, tree_node_layout); 3.35 + cx_tree_link(&c, &cc, tree_node_layout); 3.36 + cx_tree_link(&cb, &cba, tree_node_layout); 3.37 + CX_TEST_DO { 3.38 + CxTreeVisitor iter = cx_tree_visitor(&root, tree_child_list); 3.39 + unsigned chk = 0; 3.40 + cx_foreach(tree_node*, node, iter) { 3.41 + CX_TEST_ASSERT(node->data == 0); 3.42 + node->data++; 3.43 + actual_order[chk] = node; 3.44 + chk++; 3.45 + CX_TEST_ASSERT(node == iter.node); 3.46 + if (node == &root) { 3.47 + CX_TEST_ASSERT(iter.depth == 1); 3.48 + } else if (node == &a || node == &b || node == &c) { 3.49 + CX_TEST_ASSERT(iter.depth == 2); 3.50 + } else { 3.51 + CX_TEST_ASSERT(iter.depth == 3); 3.52 + } 3.53 + if (node == &c) { 3.54 + cxTreeVisitorContinue(iter); 3.55 + } 3.56 + } 3.57 + CX_TEST_ASSERT(iter.counter == 7); 3.58 + CX_TEST_ASSERT(chk == 7); 3.59 + for (unsigned i = 0 ; i < chk ; i++) { 3.60 + CX_TEST_ASSERT(actual_order[i] == expected_order[i]); 3.61 + CX_TEST_ASSERT(actual_order[i]->data == 1); 3.62 + } 3.63 + CX_TEST_ASSERT(ca.data == 0); 3.64 + CX_TEST_ASSERT(cb.data == 0); 3.65 + CX_TEST_ASSERT(cc.data == 0); 3.66 + CX_TEST_ASSERT(cba.data == 0); 3.67 + CX_TEST_ASSERT(iter.queue_next == NULL); 3.68 + CX_TEST_ASSERT(iter.queue_last == NULL); 3.69 + } 3.70 +} 3.71 + 3.72 +CX_TEST(test_tree_iterator_continue) { 3.73 + tree_node root = {0}; 3.74 + tree_node a = {0}; 3.75 + tree_node b = {0}; 3.76 + tree_node c = {0}; 3.77 + tree_node aa = {0}; 3.78 + tree_node ab = {0}; 3.79 + tree_node ba = {0}; 3.80 + tree_node ca = {0}; 3.81 + tree_node cb = {0}; 3.82 + tree_node cc = {0}; 3.83 + tree_node cba = {0}; 3.84 + 3.85 + tree_node* expected_order[] = { 3.86 + &root, 3.87 + &c, 3.88 + &b, &ba, 3.89 + &a, &ab, &aa, 3.90 + }; 3.91 + tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong 3.92 + 3.93 + cx_tree_link(&root, &a, tree_node_layout); 3.94 + cx_tree_link(&root, &b, tree_node_layout); 3.95 + cx_tree_link(&root, &c, tree_node_layout); 3.96 + cx_tree_link(&a, &aa, tree_node_layout); 3.97 + cx_tree_link(&a, &ab, tree_node_layout); 3.98 + cx_tree_link(&b, &ba, tree_node_layout); 3.99 + cx_tree_link(&c, &ca, tree_node_layout); 3.100 + cx_tree_link(&c, &cb, tree_node_layout); 3.101 + cx_tree_link(&c, &cc, tree_node_layout); 3.102 + cx_tree_link(&cb, &cba, tree_node_layout); 3.103 + CX_TEST_DO { 3.104 + CxTreeIterator iter = cx_tree_iterator(&root, false, tree_child_list); 3.105 + unsigned chk = 0; 3.106 + cx_foreach(tree_node*, node, iter) { 3.107 + CX_TEST_ASSERT(node->data == 0); 3.108 + node->data++; 3.109 + actual_order[chk] = node; 3.110 + chk++; 3.111 + CX_TEST_ASSERT(node == iter.node); 3.112 + CX_TEST_ASSERT(!iter.exiting); 3.113 + if (node == &root) { 3.114 + CX_TEST_ASSERT(iter.depth == 1); 3.115 + } else if (node == &a || node == &b || node == &c) { 3.116 + CX_TEST_ASSERT(iter.depth == 2); 3.117 + } else { 3.118 + CX_TEST_ASSERT(iter.depth == 3); 3.119 + } 3.120 + if (node == &c) { 3.121 + cxTreeIteratorContinue(iter); 3.122 + } 3.123 + } 3.124 + CX_TEST_ASSERT(iter.counter == 7); 3.125 + CX_TEST_ASSERT(chk == 7); 3.126 + for (unsigned i = 0 ; i < chk ; i++) { 3.127 + CX_TEST_ASSERT(actual_order[i] == expected_order[i]); 3.128 + CX_TEST_ASSERT(actual_order[i]->data == 1); 3.129 + } 3.130 + CX_TEST_ASSERT(ca.data == 0); 3.131 + CX_TEST_ASSERT(cb.data == 0); 3.132 + CX_TEST_ASSERT(cc.data == 0); 3.133 + CX_TEST_ASSERT(cba.data == 0); 3.134 + CX_TEST_ASSERT(iter.stack == NULL); 3.135 + } 3.136 +} 3.137 + 3.138 +CX_TEST(test_tree_iterator_continue_with_exit) { 3.139 + tree_node root = {0}; 3.140 + tree_node a = {0}; 3.141 + tree_node b = {0}; 3.142 + tree_node c = {0}; 3.143 + tree_node aa = {0}; 3.144 + tree_node ab = {0}; 3.145 + tree_node ba = {0}; 3.146 + tree_node ca = {0}; 3.147 + tree_node cb = {0}; 3.148 + tree_node cc = {0}; 3.149 + tree_node cba = {0}; 3.150 + 3.151 + cx_tree_link(&root, &a, tree_node_layout); 3.152 + cx_tree_link(&root, &b, tree_node_layout); 3.153 + cx_tree_link(&root, &c, tree_node_layout); 3.154 + cx_tree_link(&a, &aa, tree_node_layout); 3.155 + cx_tree_link(&a, &ab, tree_node_layout); 3.156 + cx_tree_link(&b, &ba, tree_node_layout); 3.157 + cx_tree_link(&c, &ca, tree_node_layout); 3.158 + cx_tree_link(&c, &cb, tree_node_layout); 3.159 + cx_tree_link(&c, &cc, tree_node_layout); 3.160 + cx_tree_link(&cb, &cba, tree_node_layout); 3.161 + CX_TEST_DO { 3.162 + CxTreeIterator iter = cx_tree_iterator(&root, true, tree_child_list); 3.163 + unsigned chk = 0; 3.164 + cx_foreach(tree_node*, node, iter) { 3.165 + CX_TEST_ASSERT(iter.exiting || node->data == 0); 3.166 + node->data++; 3.167 + chk++; 3.168 + CX_TEST_ASSERT(node == iter.node); 3.169 + if (node == &root) { 3.170 + CX_TEST_ASSERT(iter.depth == 1); 3.171 + } else if (node == &a || node == &b || node == &c) { 3.172 + CX_TEST_ASSERT(iter.depth == 2); 3.173 + } else { 3.174 + CX_TEST_ASSERT(iter.depth == 3); 3.175 + } 3.176 + if (node == &c) { 3.177 + cxTreeIteratorContinue(iter); 3.178 + } 3.179 + } 3.180 + CX_TEST_ASSERT(iter.counter == 7); 3.181 + CX_TEST_ASSERT(chk == 14); 3.182 + CX_TEST_ASSERT(iter.stack == NULL); 3.183 + CX_TEST_ASSERT(root.data == 2); 3.184 + CX_TEST_ASSERT(a.data == 2); 3.185 + CX_TEST_ASSERT(b.data == 2); 3.186 + CX_TEST_ASSERT(c.data == 2); 3.187 + CX_TEST_ASSERT(aa.data == 2); 3.188 + CX_TEST_ASSERT(ab.data == 2); 3.189 + CX_TEST_ASSERT(ba.data == 2); 3.190 + CX_TEST_ASSERT(ca.data == 0); 3.191 + CX_TEST_ASSERT(cb.data == 0); 3.192 + CX_TEST_ASSERT(cc.data == 0); 3.193 + CX_TEST_ASSERT(cba.data == 0); 3.194 + } 3.195 +} 3.196 + 3.197 CxTestSuite *cx_test_suite_tree_low_level(void) { 3.198 CxTestSuite *suite = cx_test_suite_new("tree (low level)"); 3.199 3.200 @@ -660,6 +850,9 @@ 3.201 cx_test_register(suite, test_tree_visitor); 3.202 cx_test_register(suite, test_tree_visitor_no_children); 3.203 cx_test_register(suite, test_tree_visitor_no_branching); 3.204 + cx_test_register(suite, test_tree_visitor_continue); 3.205 + cx_test_register(suite, test_tree_iterator_continue); 3.206 + cx_test_register(suite, test_tree_iterator_continue_with_exit); 3.207 3.208 return suite; 3.209 }