Mercurial > hg > ucx / changeset

--- a/src/cx/tree.h	Thu Mar 14 22:07:19 2024 +0100
+++ b/src/cx/tree.h	Wed Mar 20 23:31:41 2024 +0100
@@ -45,7 +45,7 @@
 #endif
 
 /**
- * Tree iterator.
+ * A depth-first tree iterator.
  *
  * This iterator is not position-aware in a strict sense, as it does not assume a particular order of elements in the
  * tree. However, the iterator keeps track of the number of nodes it has passed in a counter variable.
@@ -74,11 +74,11 @@
     /**
      * Offset in the node struct for the children linked list.
      */
-    off_t loc_children;
+    ptrdiff_t loc_children;
     /**
      * Offset in the node struct for the next pointer.
      */
-    off_t loc_next;
+    ptrdiff_t loc_next;
     /**
      * The total number of distinct nodes that have been passed so far.
      */
@@ -119,19 +119,105 @@
 } CxTreeIterator;
 
 /**
+ * An element in a visitor queue.
+ */
+struct cx_tree_visitor_queue_s {
+    /**
+     * The tree node to visit.
+     */
+    void *node;
+    /**
+     * The depth of the node.
+     */
+    size_t depth;
+    /**
+     * The next element in the queue or \c NULL.
+     */
+    struct cx_tree_visitor_queue_s *next;
+};
+
+/**
+ * A breadth-first tree iterator.
+ *
+ * This iterator needs to maintain a visitor queue that will be automatically freed once the iterator becomes invalid.
+ * If you want to discard the iterator before, you MUST manually call cxTreeVisitorDispose().
+ *
+ * This iterator is not position-aware in a strict sense, as it does not assume a particular order of elements in the
+ * tree. However, the iterator keeps track of the number of nodes it has passed in a counter variable.
+ * Each node, regardless of the number of passes, is counted only once.
+ *
+ * @note Objects that are pointed to by an iterator are mutable through that iterator. However, if the
+ * underlying data structure is mutated by other means than this iterator (e.g. elements added or removed),
+ * the iterator becomes invalid (regardless of what cxIteratorValid() returns).
+ *
+ * @see CxIterator
+ */
+typedef struct cx_tree_visitor_s {
+    /**
+     * The base properties of this iterator.
+     */
+    struct cx_iterator_base_s base;
+    /**
+     * Offset in the node struct for the children linked list.
+     */
+    ptrdiff_t loc_children;
+    /**
+     * Offset in the node struct for the next pointer.
+     */
+    ptrdiff_t loc_next;
+    /**
+     * The total number of distinct nodes that have been passed so far.
+     */
+    size_t counter;
+    /**
+     * The currently observed node.
+     *
+     * This is the same what cxIteratorCurrent() would return.
+     */
+    void *node;
+    /**
+     * The current depth in the tree.
+     */
+    size_t depth;
+    /**
+     * The next element in the visitor queue.
+     */
+    struct cx_tree_visitor_queue_s *queue_next;
+    /**
+     * The last element in the visitor queue.
+     */
+    struct cx_tree_visitor_queue_s *queue_last;
+} CxTreeVisitor;
+
+/**
  * Releases internal memory of the given tree iterator.
  * @param iter the iterator
  */
+ __attribute__((__nonnull__))
 static inline void cxTreeIteratorDispose(CxTreeIterator *iter) {
     free(iter->stack);
     iter->stack = NULL;
 }
 
 /**
+ * Releases internal memory of the given tree visitor.
+ * @param visitor the visitor
+ */
+__attribute__((__nonnull__))
+static inline void cxTreeVisitorDispose(CxTreeVisitor *visitor) {
+    struct cx_tree_visitor_queue_s *q = visitor->queue_next;
+    while (q != NULL) {
+        struct cx_tree_visitor_queue_s *next = q->next;
+        free(q);
+        q = next;
+    }
+}
+
+/**
  * Links a node to a (new) parent.
  *
  * If the node has already a parent, it is unlinked, first.
- * If the parent has children already, the node is prepended to the list
+ * If the parent has children already, the node is \em prepended to the list
  * of all currently existing children.
  *
  * @param parent the parent node
@@ -234,14 +320,14 @@
 );
 
 /**
- * Creates an iterator for a tree with the specified root node.
+ * Creates a depth-first iterator for a tree with the specified root node.
  *
  * @note A tree iterator needs to maintain a stack of visited nodes, which is allocated using stdlib malloc().
  * When the iterator becomes invalid, this memory is automatically released. However, if you wish to cancel the
  * iteration before the iterator becomes invalid by itself, you MUST call cxTreeIteratorDispose() manually to release
  * the memory.
  *
- * @remark At the moment, the returned iterator does not support cxIteratorFlagRemoval().
+ * @remark The returned iterator does not support cxIteratorFlagRemoval().
  *
  * @param root the root node
  * @param visit_on_exit set to true, when the iterator shall visit a node again after processing all children
@@ -258,6 +344,29 @@
         ptrdiff_t loc_next
 );
 
+/**
+ * Creates a breadth-first iterator for a tree with the specified root node.
+ *
+ * @note A tree visitor needs to maintain a queue of to be visited nodes, which is allocated using stdlib malloc().
+ * When the visitor becomes invalid, this memory is automatically released. However, if you wish to cancel the
+ * iteration before the visitor becomes invalid by itself, you MUST call cxTreeVisitorDispose() manually to release
+ * the memory.
+ *
+ * @remark The returned iterator does not support cxIteratorFlagRemoval().
+ *
+ * @param root the root node
+ * @param loc_children offset in the node struct for the children linked list
+ * @param loc_next offset in the node struct for the next pointer
+ * @return the new tree visitor
+ * @see cxTreeVisitorDispose()
+ */
+__attribute__((__nonnull__))
+CxTreeVisitor cx_tree_visitor(
+        void *root,
+        ptrdiff_t loc_children,
+        ptrdiff_t loc_next
+);
+
 #ifdef __cplusplus
 } // extern "C"
 #endif

--- a/src/tree.c	Thu Mar 14 22:07:19 2024 +0100
+++ b/src/tree.c	Wed Mar 20 23:31:41 2024 +0100
@@ -178,10 +178,8 @@
 
 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
+    ptrdiff_t const loc_next = iter->loc_next;
+    ptrdiff_t const loc_children = iter->loc_children;
 
     void *children;
 
@@ -280,3 +278,116 @@
 
     return iter;
 }
+
+static bool cx_tree_visitor_valid(void const *it) {
+    struct cx_tree_visitor_s const *iter = it;
+    return iter->node != NULL;
+}
+
+static void *cx_tree_visitor_current(void const *it) {
+    struct cx_tree_visitor_s const *iter = it;
+    return iter->node;
+}
+
+__attribute__((__nonnull__))
+static void cx_tree_visitor_enqueue_siblings(
+        struct cx_tree_visitor_s *iter, void *node, ptrdiff_t loc_next) {
+    node = tree_next(node);
+    while (node != NULL) {
+        struct cx_tree_visitor_queue_s *q;
+        q = malloc(sizeof(struct cx_tree_visitor_queue_s));
+        q->depth = iter->queue_last->depth;
+        q->node = node;
+        iter->queue_last->next = q;
+        iter->queue_last = q;
+        node = tree_next(node);
+    }
+    iter->queue_last->next = NULL;
+}
+
+static void cx_tree_visitor_next(void *it) {
+    struct cx_tree_visitor_s *iter = it;
+    ptrdiff_t const loc_next = iter->loc_next;
+    ptrdiff_t const loc_children = iter->loc_children;
+
+    // check if there is a next node
+    if (iter->queue_next == NULL) {
+        iter->node = NULL;
+        return;
+    }
+
+    // dequeue the next node
+    iter->node = iter->queue_next->node;
+    iter->depth = iter->queue_next->depth;
+    {
+        struct cx_tree_visitor_queue_s *q = iter->queue_next;
+        iter->queue_next = q->next;
+        if (iter->queue_next == NULL) {
+            assert(iter->queue_last == q);
+            iter->queue_last = NULL;
+        }
+        free(q);
+    }
+
+    // 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(
+        void *root,
+        ptrdiff_t loc_children,
+        ptrdiff_t loc_next
+) {
+    CxTreeVisitor iter;
+    iter.loc_children = loc_children;
+    iter.loc_next = loc_next;
+
+    // allocate stack
+    iter.depth = 0;
+
+    // visit the root node
+    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);
+    }
+
+    // assign base iterator functions
+    iter.base.mutating = false;
+    iter.base.remove = false;
+    iter.base.current_impl = NULL;
+    iter.base.valid = cx_tree_visitor_valid;
+    iter.base.next = cx_tree_visitor_next;
+    iter.base.current = cx_tree_visitor_current;
+
+    return iter;
+}
+

--- a/tests/test_tree.c	Thu Mar 14 22:07:19 2024 +0100
+++ b/tests/test_tree.c	Wed Mar 20 23:31:41 2024 +0100
@@ -286,6 +286,14 @@
     tree_node cc = {0};
     tree_node cba = {0};
 
+    tree_node* expected_order[] = {
+            &root,
+            &c, &cc,&cb, &cba,&ca,
+            &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);
@@ -302,6 +310,7 @@
         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);
@@ -317,18 +326,11 @@
         }
         CX_TEST_ASSERT(iter.counter == 11);
         CX_TEST_ASSERT(chk == 11);
+        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(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);
     }
 }
 
@@ -507,6 +509,120 @@
     cx_testing_allocator_destroy(&talloc);
 }
 
+CX_TEST(test_tree_visitor) {
+    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,
+            &cc, &cb, &ca, &ba, &ab, &aa,
+            &cba
+    };
+    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 if (node == &cba) {
+                CX_TEST_ASSERT(iter.depth == 4);
+            } else {
+                CX_TEST_ASSERT(iter.depth == 3);
+            }
+        }
+        CX_TEST_ASSERT(iter.counter == 11);
+        CX_TEST_ASSERT(chk == 11);
+        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(iter.queue_next == NULL);
+        CX_TEST_ASSERT(iter.queue_last == NULL);
+    }
+}
+
+CX_TEST(test_tree_visitor_no_children) {
+    tree_node root = {0};
+
+    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 == iter.node);
+            chk++;
+        }
+        CX_TEST_ASSERT(iter.counter == 1);
+        CX_TEST_ASSERT(chk == 1);
+        CX_TEST_ASSERT(iter.queue_next == NULL);
+        CX_TEST_ASSERT(iter.queue_last == NULL);
+    }
+}
+
+CX_TEST(test_tree_visitor_no_branching) {
+    tree_node root = {0};
+    tree_node a = {0};
+    tree_node b = {0};
+    tree_node c = {0};
+
+    tree_node* expected_order[] = {
+            &root, &a, &b, &c
+    };
+    tree_node* actual_order[4];
+
+    cx_tree_link(&root, &a, tree_node_layout);
+    cx_tree_link(&a, &b, tree_node_layout);
+    cx_tree_link(&b, &c, 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 == iter.node);
+            CX_TEST_ASSERT(node->data == 0);
+            node->data++;
+            actual_order[chk] = node;
+            chk++;
+        }
+        CX_TEST_ASSERT(iter.counter == 4);
+        CX_TEST_ASSERT(chk == 4);
+        CX_TEST_ASSERT(iter.queue_next == NULL);
+        CX_TEST_ASSERT(iter.queue_last == NULL);
+        for (unsigned i = 0 ; i < chk ; i++) {
+            CX_TEST_ASSERT(actual_order[i] == expected_order[i]);
+            CX_TEST_ASSERT(actual_order[i]->data == 1);
+        }
+    }
+}
+
 CxTestSuite *cx_test_suite_tree_low_level(void) {
     CxTestSuite *suite = cx_test_suite_new("tree (low level)");
 
@@ -520,6 +636,9 @@
     cx_test_register(suite, test_tree_iterator_basic_enter_and_exit);
     cx_test_register(suite, test_tree_iterator_xml);
     cx_test_register(suite, test_tree_iterator_free_nodes);
+    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);
 
     return suite;
 }