Mercurial > hg > ucx / changeset

--- a/src/cx/tree.h	Wed Mar 20 23:35:32 2024 +0100
+++ b/src/cx/tree.h	Wed Apr 03 21:22:23 2024 +0200
@@ -63,6 +63,10 @@
      */
     struct cx_iterator_base_s base;
     /**
+     * Indicates whether the subtree below the current node shall be skipped.
+     */
+    bool skip;
+    /**
      * Set to true, when the iterator shall visit a node again
      * when all it's children have been processed.
      */
@@ -158,6 +162,10 @@
      */
     struct cx_iterator_base_s base;
     /**
+     * Indicates whether the subtree below the current node shall be skipped.
+     */
+    bool skip;
+    /**
      * Offset in the node struct for the children linked list.
      */
     ptrdiff_t loc_children;
@@ -214,6 +222,22 @@
 }
 
 /**
+ * Advises the iterator to skip the subtree below the current node and
+ * also continues the current loop.
+ *
+ * @param iterator the iterator
+ */
+#define cxTreeIteratorContinue(iterator) (iterator).skip = true; continue
+
+/**
+ * Advises the visitor to skip the subtree below the current node and
+ * also continues the current loop.
+ *
+ * @param visitor the visitor
+ */
+#define cxTreeVisitorContinue(visitor) cxTreeIteratorContinue(visitor)
+
+/**
  * Links a node to a (new) parent.
  *
  * If the node has already a parent, it is unlinked, first.

--- a/src/tree.c	Wed Mar 20 23:35:32 2024 +0100
+++ b/src/tree.c	Wed Apr 03 21:22:23 2024 +0200
@@ -186,8 +186,17 @@
     // check if we are currently exiting or entering nodes
     if (iter->exiting) {
         children = NULL;
+        // skipping on exit is pointless, just clear the flag
+        iter->skip = false;
     } else {
-        children = tree_children(iter->node);
+        if (iter->skip) {
+            // skip flag is set, pretend that there are no children
+            iter->skip = false;
+            children = NULL;
+        } else {
+            // try to enter the children (if any)
+            children = tree_children(iter->node);
+        }
     }
 
     if (children == NULL) {
@@ -263,10 +272,12 @@
 
     // visit the root node
     iter.node = root;
+    iter.next = NULL;
     iter.counter = 1;
     iter.depth = 1;
     iter.stack[0] = root;
     iter.exiting = false;
+    iter.skip = false;
 
     // assign base iterator functions
     iter.base.mutating = false;
@@ -310,6 +321,30 @@
     ptrdiff_t const loc_next = iter->loc_next;
     ptrdiff_t const loc_children = iter->loc_children;
 
+    // add the children of the current node to the queue
+    // unless the skip flag is set
+    void *children;
+    if (iter->skip) {
+        iter->skip = false;
+        children = NULL;
+    } else {
+        children = tree_children(iter->node);
+    }
+    if (children != NULL) {
+        struct cx_tree_visitor_queue_s *q;
+        q = malloc(sizeof(struct cx_tree_visitor_queue_s));
+        q->depth = iter->depth + 1;
+        q->node = children;
+        if (iter->queue_last == NULL) {
+            assert(iter->queue_next == NULL);
+            iter->queue_next = q;
+        } else {
+            iter->queue_last->next = q;
+        }
+        iter->queue_last = q;
+        cx_tree_visitor_enqueue_siblings(iter, children, loc_next);
+    }
+
     // check if there is a next node
     if (iter->queue_next == NULL) {
         iter->node = NULL;
@@ -331,23 +366,6 @@
 
     // increment the node counter
     iter->counter++;
-
-    // add the children of the new node to the queue
-    void *children = tree_children(iter->node);
-    if (children != NULL) {
-        struct cx_tree_visitor_queue_s *q;
-        q = malloc(sizeof(struct cx_tree_visitor_queue_s));
-        q->depth = iter->depth + 1;
-        q->node = children;
-        if (iter->queue_last == NULL) {
-            assert(iter->queue_next == NULL);
-            iter->queue_next = q;
-        } else {
-            iter->queue_last->next = q;
-        }
-        iter->queue_last = q;
-        cx_tree_visitor_enqueue_siblings(iter, children, loc_next);
-    }
 }
 
 CxTreeVisitor cx_tree_visitor(
@@ -366,19 +384,9 @@
     iter.node = root;
     iter.counter = 1;
     iter.depth = 1;
-
-    // put all children of root into the queue
-    void *children = tree_children(root);
-    if (children == NULL) {
-        iter.queue_next = NULL;
-        iter.queue_last = NULL;
-    } else {
-        iter.queue_next = malloc(sizeof(struct cx_tree_visitor_queue_s));
-        iter.queue_next->depth = 2;
-        iter.queue_next->node = children;
-        iter.queue_last = iter.queue_next;
-        cx_tree_visitor_enqueue_siblings(&iter, children, loc_next);
-    }
+    iter.skip = false;
+    iter.queue_next = NULL;
+    iter.queue_last = NULL;
 
     // assign base iterator functions
     iter.base.mutating = false;

--- a/tests/test_tree.c	Wed Mar 20 23:35:32 2024 +0100
+++ b/tests/test_tree.c	Wed Apr 03 21:22:23 2024 +0200
@@ -644,6 +644,196 @@
     }
 }
 
+CX_TEST(test_tree_visitor_continue) {
+    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};
+
+    tree_node* expected_order[] = {
+            &root,
+            &c, &b, &a,
+            &ba, &ab, &aa
+    };
+    tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong
+
+    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 {
+        CxTreeVisitor iter = cx_tree_visitor(&root, tree_child_list);
+        unsigned chk = 0;
+        cx_foreach(tree_node*, node, iter) {
+            CX_TEST_ASSERT(node->data == 0);
+            node->data++;
+            actual_order[chk] = node;
+            chk++;
+            CX_TEST_ASSERT(node == iter.node);
+            if (node == &root) {
+                CX_TEST_ASSERT(iter.depth == 1);
+            } else if (node == &a || node == &b || node == &c) {
+                CX_TEST_ASSERT(iter.depth == 2);
+            } else {
+                CX_TEST_ASSERT(iter.depth == 3);
+            }
+            if (node == &c) {
+                cxTreeVisitorContinue(iter);
+            }
+        }
+        CX_TEST_ASSERT(iter.counter == 7);
+        CX_TEST_ASSERT(chk == 7);
+        for (unsigned i = 0 ; i < chk ; i++) {
+            CX_TEST_ASSERT(actual_order[i] == expected_order[i]);
+            CX_TEST_ASSERT(actual_order[i]->data == 1);
+        }
+        CX_TEST_ASSERT(ca.data == 0);
+        CX_TEST_ASSERT(cb.data == 0);
+        CX_TEST_ASSERT(cc.data == 0);
+        CX_TEST_ASSERT(cba.data == 0);
+        CX_TEST_ASSERT(iter.queue_next == NULL);
+        CX_TEST_ASSERT(iter.queue_last == NULL);
+    }
+}
+
+CX_TEST(test_tree_iterator_continue) {
+    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};
+
+    tree_node* expected_order[] = {
+            &root,
+            &c,
+            &b, &ba,
+            &a, &ab, &aa,
+    };
+    tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong
+
+    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++;
+            actual_order[chk] = node;
+            chk++;
+            CX_TEST_ASSERT(node == iter.node);
+            CX_TEST_ASSERT(!iter.exiting);
+            if (node == &root) {
+                CX_TEST_ASSERT(iter.depth == 1);
+            } else if (node == &a || node == &b || node == &c) {
+                CX_TEST_ASSERT(iter.depth == 2);
+            } else {
+                CX_TEST_ASSERT(iter.depth == 3);
+            }
+            if (node == &c) {
+                cxTreeIteratorContinue(iter);
+            }
+        }
+        CX_TEST_ASSERT(iter.counter == 7);
+        CX_TEST_ASSERT(chk == 7);
+        for (unsigned i = 0 ; i < chk ; i++) {
+            CX_TEST_ASSERT(actual_order[i] == expected_order[i]);
+            CX_TEST_ASSERT(actual_order[i]->data == 1);
+        }
+        CX_TEST_ASSERT(ca.data == 0);
+        CX_TEST_ASSERT(cb.data == 0);
+        CX_TEST_ASSERT(cc.data == 0);
+        CX_TEST_ASSERT(cba.data == 0);
+        CX_TEST_ASSERT(iter.stack == NULL);
+    }
+}
+
+CX_TEST(test_tree_iterator_continue_with_exit) {
+    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, true, tree_child_list);
+        unsigned chk = 0;
+        cx_foreach(tree_node*, node, iter) {
+            CX_TEST_ASSERT(iter.exiting || node->data == 0);
+            node->data++;
+            chk++;
+            CX_TEST_ASSERT(node == iter.node);
+            if (node == &root) {
+                CX_TEST_ASSERT(iter.depth == 1);
+            } else if (node == &a || node == &b || node == &c) {
+                CX_TEST_ASSERT(iter.depth == 2);
+            } else {
+                CX_TEST_ASSERT(iter.depth == 3);
+            }
+            if (node == &c) {
+                cxTreeIteratorContinue(iter);
+            }
+        }
+        CX_TEST_ASSERT(iter.counter == 7);
+        CX_TEST_ASSERT(chk == 14);
+        CX_TEST_ASSERT(iter.stack == NULL);
+        CX_TEST_ASSERT(root.data == 2);
+        CX_TEST_ASSERT(a.data == 2);
+        CX_TEST_ASSERT(b.data == 2);
+        CX_TEST_ASSERT(c.data == 2);
+        CX_TEST_ASSERT(aa.data == 2);
+        CX_TEST_ASSERT(ab.data == 2);
+        CX_TEST_ASSERT(ba.data == 2);
+        CX_TEST_ASSERT(ca.data == 0);
+        CX_TEST_ASSERT(cb.data == 0);
+        CX_TEST_ASSERT(cc.data == 0);
+        CX_TEST_ASSERT(cba.data == 0);
+    }
+}
+
 CxTestSuite *cx_test_suite_tree_low_level(void) {
     CxTestSuite *suite = cx_test_suite_new("tree (low level)");
 
@@ -660,6 +850,9 @@
     cx_test_register(suite, test_tree_visitor);
     cx_test_register(suite, test_tree_visitor_no_children);
     cx_test_register(suite, test_tree_visitor_no_branching);
+    cx_test_register(suite, test_tree_visitor_continue);
+    cx_test_register(suite, test_tree_iterator_continue);
+    cx_test_register(suite, test_tree_iterator_continue_with_exit);
 
     return suite;
 }