Mercurial > hg > ucx / changeset

--- a/src/tree.c	Mon Feb 19 22:08:09 2024 +0100
+++ b/src/tree.c	Mon Feb 19 22:09:16 2024 +0100
@@ -178,9 +178,50 @@
 
 static void cx_tree_iter_next(void *it) {
     struct cx_tree_iterator_s *iter = it;
+    off_t const loc_next = iter->loc_next;
+    off_t const loc_children = iter->loc_children;
+
     // TODO: support mutating iterator
+    // TODO: support visit_on_exit
 
-    // TODO: implement
+    void *children = tree_children(iter->node);
+    if (children == NULL) {
+        // search for the next node
+        void *current = iter->node;
+        do {
+            // check if there is a sibling
+            void *next = tree_next(current);
+            if (next == NULL) {
+                // no sibling, check again for parent node
+                --iter->depth;
+                if (iter->depth == 0) {
+                    // there is no parent - we have iterated the entire tree
+                    // invalidate the iterator and free the node stack
+                    iter->node = NULL;
+                    current = NULL;
+                    iter->stack_capacity = 0;
+                    free(iter->stack);
+                    iter->stack = NULL;
+                } else {
+                    // the parent node can be obtained from the top of stack
+                    // this way we can avoid the loc_parent in the iterator
+                    current = iter->stack[iter->depth - 1];
+                }
+            } else {
+                // move to the sibling and break the loop
+                current = NULL;
+                iter->counter++;
+                iter->node = next;
+                // new top of stack is the sibling
+                iter->stack[iter->depth - 1] = next;
+            }
+        } while (current != NULL);
+    } else {
+        // node has children, push the first child onto the stack and enter it
+        cx_array_simple_add(iter->stack, children);
+        iter->node = children;
+        iter->counter++;
+    }
 }
 
 CxTreeIterator cx_tree_iterator(

--- a/tests/test_tree.c	Mon Feb 19 22:08:09 2024 +0100
+++ b/tests/test_tree.c	Mon Feb 19 22:09:16 2024 +0100
@@ -250,7 +250,7 @@
     }
 }
 
-CX_TEST(test_tree_iterator_create) {
+CX_TEST(test_tree_iterator_create_and_dispose) {
     tree_node root;
     CX_TEST_DO {
         CxTreeIterator iter = cx_tree_iterator(&root, false, tree_child_list);
@@ -266,6 +266,58 @@
         CX_TEST_ASSERT(iter.depth == 1);
         CX_TEST_ASSERT(iter.loc_next == offsetof(tree_node, next));
         CX_TEST_ASSERT(iter.loc_children == offsetof(tree_node, children));
+        cxTreeIteratorDispose(&iter);
+        CX_TEST_ASSERT(iter.stack == NULL);
+    }
+}
+
+CX_TEST(test_tree_iterator_basic_test_only_enter) {
+    tree_node root = {0};
+    tree_node a = {0};
+    tree_node b = {0};
+    tree_node c = {0};
+    tree_node aa = {0};
+    tree_node ab = {0};
+    tree_node ba = {0};
+    tree_node ca = {0};
+    tree_node cb = {0};
+    tree_node cc = {0};
+    tree_node cba = {0};
+
+    cx_tree_link(&root, &a, tree_node_layout);
+    cx_tree_link(&root, &b, tree_node_layout);
+    cx_tree_link(&root, &c, tree_node_layout);
+    cx_tree_link(&a, &aa, tree_node_layout);
+    cx_tree_link(&a, &ab, tree_node_layout);
+    cx_tree_link(&b, &ba, tree_node_layout);
+    cx_tree_link(&c, &ca, tree_node_layout);
+    cx_tree_link(&c, &cb, tree_node_layout);
+    cx_tree_link(&c, &cc, tree_node_layout);
+    cx_tree_link(&cb, &cba, tree_node_layout);
+    CX_TEST_DO {
+        CxTreeIterator iter = cx_tree_iterator(&root, false, tree_child_list);
+        unsigned chk = 0;
+        cx_foreach(tree_node*, node, iter) {
+            CX_TEST_ASSERT(node->data == 0);
+            node->data++;
+            chk++;
+            CX_TEST_ASSERT(node == iter.node);
+            CX_TEST_ASSERT(!iter.exiting);
+        }
+        CX_TEST_ASSERT(iter.counter == 11);
+        CX_TEST_ASSERT(chk == 11);
+        CX_TEST_ASSERT(iter.stack == NULL);
+        CX_TEST_ASSERT(root.data == 1);
+        CX_TEST_ASSERT(a.data == 1);
+        CX_TEST_ASSERT(b.data == 1);
+        CX_TEST_ASSERT(c.data == 1);
+        CX_TEST_ASSERT(aa.data == 1);
+        CX_TEST_ASSERT(ab.data == 1);
+        CX_TEST_ASSERT(ba.data == 1);
+        CX_TEST_ASSERT(ca.data == 1);
+        CX_TEST_ASSERT(cb.data == 1);
+        CX_TEST_ASSERT(cc.data == 1);
+        CX_TEST_ASSERT(cba.data == 1);
     }
 }
 
@@ -277,7 +329,8 @@
     cx_test_register(suite, test_tree_link_move_to_other_parent);
     cx_test_register(suite, test_tree_unlink);
     cx_test_register(suite, test_tree_search);
-    cx_test_register(suite, test_tree_iterator_create);
+    cx_test_register(suite, test_tree_iterator_create_and_dispose);
+    cx_test_register(suite, test_tree_iterator_basic_test_only_enter);
 
     return suite;
 }