Wed, 21 Feb 2024 18:32:38 +0100
add visit_on_exit to iterator implementation
relates to #371
src/tree.c | file | annotate | diff | comparison | revisions | |
tests/test_tree.c | file | annotate | diff | comparison | revisions |
1.1 --- a/src/tree.c Mon Feb 19 22:12:13 2024 +0100 1.2 +++ b/src/tree.c Wed Feb 21 18:32:38 2024 +0100 1.3 @@ -182,40 +182,58 @@ 1.4 off_t const loc_children = iter->loc_children; 1.5 1.6 // TODO: support mutating iterator 1.7 - // TODO: support visit_on_exit 1.8 1.9 - void *children = tree_children(iter->node); 1.10 + void *children; 1.11 + 1.12 + // check if we are currently exiting or entering nodes 1.13 + if (iter->exiting) { 1.14 + children = NULL; 1.15 + } else { 1.16 + children = tree_children(iter->node); 1.17 + } 1.18 + 1.19 if (children == NULL) { 1.20 // search for the next node 1.21 - void *current = iter->node; 1.22 - do { 1.23 - // check if there is a sibling 1.24 - void *next = tree_next(current); 1.25 - if (next == NULL) { 1.26 - // no sibling, check again for parent node 1.27 - --iter->depth; 1.28 - if (iter->depth == 0) { 1.29 + void *next; 1.30 + cx_tree_iter_search_next: 1.31 + // check if there is a sibling 1.32 + next = tree_next(iter->node); 1.33 + if (next == NULL) { 1.34 + // no sibling, we are done with this node and exit 1.35 + if (iter->visit_on_exit && !iter->exiting) { 1.36 + // iter is supposed to visit the node again 1.37 + iter->exiting = true; 1.38 + } else { 1.39 + iter->exiting = false; 1.40 + if (iter->depth == 1) { 1.41 // there is no parent - we have iterated the entire tree 1.42 // invalidate the iterator and free the node stack 1.43 iter->node = NULL; 1.44 - current = NULL; 1.45 - iter->stack_capacity = 0; 1.46 + iter->stack_capacity = iter->depth = 0; 1.47 free(iter->stack); 1.48 iter->stack = NULL; 1.49 } else { 1.50 // the parent node can be obtained from the top of stack 1.51 // this way we can avoid the loc_parent in the iterator 1.52 - current = iter->stack[iter->depth - 1]; 1.53 + iter->depth--; 1.54 + iter->node = iter->stack[iter->depth - 1]; 1.55 + // retry with the parent node to find a sibling 1.56 + goto cx_tree_iter_search_next; 1.57 } 1.58 + } 1.59 + } else { 1.60 + if (iter->visit_on_exit && !iter->exiting) { 1.61 + // iter is supposed to visit the node again 1.62 + iter->exiting = true; 1.63 } else { 1.64 - // move to the sibling and break the loop 1.65 - current = NULL; 1.66 + iter->exiting = false; 1.67 + // move to the sibling 1.68 iter->counter++; 1.69 iter->node = next; 1.70 // new top of stack is the sibling 1.71 iter->stack[iter->depth - 1] = next; 1.72 } 1.73 - } while (current != NULL); 1.74 + } 1.75 } else { 1.76 // node has children, push the first child onto the stack and enter it 1.77 cx_array_simple_add(iter->stack, children);
2.1 --- a/tests/test_tree.c Mon Feb 19 22:12:13 2024 +0100 2.2 +++ b/tests/test_tree.c Wed Feb 21 18:32:38 2024 +0100 2.3 @@ -271,7 +271,7 @@ 2.4 } 2.5 } 2.6 2.7 -CX_TEST(test_tree_iterator_basic_test_only_enter) { 2.8 +CX_TEST(test_tree_iterator_basic_only_enter) { 2.9 tree_node root = {0}; 2.10 tree_node a = {0}; 2.11 tree_node b = {0}; 2.12 @@ -330,6 +330,64 @@ 2.13 } 2.14 } 2.15 2.16 +CX_TEST(test_tree_iterator_basic_enter_and_exit) { 2.17 + tree_node root = {0}; 2.18 + tree_node a = {0}; 2.19 + tree_node b = {0}; 2.20 + tree_node c = {0}; 2.21 + tree_node aa = {0}; 2.22 + tree_node ab = {0}; 2.23 + tree_node ba = {0}; 2.24 + tree_node ca = {0}; 2.25 + tree_node cb = {0}; 2.26 + tree_node cc = {0}; 2.27 + tree_node cba = {0}; 2.28 + 2.29 + cx_tree_link(&root, &a, tree_node_layout); 2.30 + cx_tree_link(&root, &b, tree_node_layout); 2.31 + cx_tree_link(&root, &c, tree_node_layout); 2.32 + cx_tree_link(&a, &aa, tree_node_layout); 2.33 + cx_tree_link(&a, &ab, tree_node_layout); 2.34 + cx_tree_link(&b, &ba, tree_node_layout); 2.35 + cx_tree_link(&c, &ca, tree_node_layout); 2.36 + cx_tree_link(&c, &cb, tree_node_layout); 2.37 + cx_tree_link(&c, &cc, tree_node_layout); 2.38 + cx_tree_link(&cb, &cba, tree_node_layout); 2.39 + CX_TEST_DO { 2.40 + CxTreeIterator iter = cx_tree_iterator(&root, true, tree_child_list); 2.41 + unsigned chk = 0; 2.42 + cx_foreach(tree_node*, node, iter) { 2.43 + CX_TEST_ASSERT(iter.exiting || node->data == 0); 2.44 + node->data++; 2.45 + chk++; 2.46 + CX_TEST_ASSERT(node == iter.node); 2.47 + if (node == &root) { 2.48 + CX_TEST_ASSERT(iter.depth == 1); 2.49 + } else if (node == &a || node == &b || node == &c) { 2.50 + CX_TEST_ASSERT(iter.depth == 2); 2.51 + } else if (node == &cba) { 2.52 + CX_TEST_ASSERT(iter.depth == 4); 2.53 + } else { 2.54 + CX_TEST_ASSERT(iter.depth == 3); 2.55 + } 2.56 + } 2.57 + CX_TEST_ASSERT(iter.counter == 11); 2.58 + CX_TEST_ASSERT(chk == 22); 2.59 + CX_TEST_ASSERT(iter.stack == NULL); 2.60 + CX_TEST_ASSERT(root.data == 2); 2.61 + CX_TEST_ASSERT(a.data == 2); 2.62 + CX_TEST_ASSERT(b.data == 2); 2.63 + CX_TEST_ASSERT(c.data == 2); 2.64 + CX_TEST_ASSERT(aa.data == 2); 2.65 + CX_TEST_ASSERT(ab.data == 2); 2.66 + CX_TEST_ASSERT(ba.data == 2); 2.67 + CX_TEST_ASSERT(ca.data == 2); 2.68 + CX_TEST_ASSERT(cb.data == 2); 2.69 + CX_TEST_ASSERT(cc.data == 2); 2.70 + CX_TEST_ASSERT(cba.data == 2); 2.71 + } 2.72 +} 2.73 + 2.74 CxTestSuite *cx_test_suite_tree_low_level(void) { 2.75 CxTestSuite *suite = cx_test_suite_new("tree (low level)"); 2.76 2.77 @@ -339,7 +397,8 @@ 2.78 cx_test_register(suite, test_tree_unlink); 2.79 cx_test_register(suite, test_tree_search); 2.80 cx_test_register(suite, test_tree_iterator_create_and_dispose); 2.81 - cx_test_register(suite, test_tree_iterator_basic_test_only_enter); 2.82 + cx_test_register(suite, test_tree_iterator_basic_only_enter); 2.83 + cx_test_register(suite, test_tree_iterator_basic_enter_and_exit); 2.84 2.85 return suite; 2.86 }