Mercurial > hg > ucx / changeset

     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  }