Mercurial > hg > ucx / changeset

--- a/src/cx/tree.h	Sat Feb 17 20:51:27 2024 +0100
+++ b/src/cx/tree.h	Sun Feb 18 12:24:04 2024 +0100
@@ -46,14 +46,23 @@
 
 /**
  * When entering a node.
+ *
+ * When this is the first sibling, source is the parent, otherwise it is the previous child.
  */
 #define CX_TREE_ITERATOR_ENTER      0x1
 /**
  * When advancing to the next child.
+ *
+ * The visited node is the next child and the source is the previous child.
+ * This pass is triggered after exiting the previous child and before entering the next child.
  */
 #define CX_TREE_ITERATOR_NEXT_CHILD 0x2
 /**
  * When exiting the node.
+ *
+ * The visited node is the node being exited and source is the previously entered node
+ * (usually the last child of the exited node, unless it has no children, in which case it is the node itself).
+ * When advancing to the next child in a list of siblings, the previous child is exited, first.
  */
 #define CX_TREE_ITERATOR_EXIT       0x4
 
@@ -278,8 +287,8 @@
  * @see cxTreeIteratorDispose()
  */
 __attribute__((__nonnull__))
-CxTreeIterator cx_tree_iterate(
-        void const *root,
+CxTreeIterator cx_tree_iterator(
+        void *root,
         int passes,
         ptrdiff_t loc_children,
         ptrdiff_t loc_next

--- a/src/tree.c	Sat Feb 17 20:51:27 2024 +0100
+++ b/src/tree.c	Sun Feb 18 12:24:04 2024 +0100
@@ -169,3 +169,111 @@
     free(work);
     return ret;
 }
+
+static bool cx_tree_iter_valid(void const *it) {
+    struct cx_tree_iterator_s const *iter = it;
+    return iter->node != NULL;
+}
+
+static void *cx_tree_iter_current(void const *it) {
+    struct cx_tree_iterator_s const *iter = it;
+    return iter->node;
+}
+
+static void cx_tree_iter_stack_add(
+        struct cx_tree_iterator_s *iter,
+        void *node
+) {
+    cx_array_add(&iter->stack, &iter->depth, &iter->stack_capacity,
+        sizeof(void*), &node, cx_array_default_reallocator);
+}
+
+static void cx_tree_iter_next(void *it) {
+    struct cx_tree_iterator_s *iter = it;
+    // TODO: support mutating iterator
+
+    // TODO: implement
+}
+
+
+CxTreeIterator cx_tree_iterator(
+        void *root,
+        int passes,
+        ptrdiff_t loc_children,
+        ptrdiff_t loc_next
+) {
+    CxTreeIterator iter;
+    iter.loc_children = loc_children;
+    iter.loc_next = loc_next;
+    iter.requested_passes = passes;
+
+    // invalidate iterator immediately when passes is invalid
+    if ((passes & (CX_TREE_ITERATOR_ENTER |
+                   CX_TREE_ITERATOR_NEXT_CHILD |
+                   CX_TREE_ITERATOR_EXIT)) == 0) {
+        iter.stack = NULL;
+        iter.node = NULL;
+        return iter;
+    }
+
+    // allocate stack
+    iter.stack_capacity = 16;
+    iter.stack = malloc(sizeof(void *) * 16);
+    iter.depth = 0;
+
+    // determine start
+    if ((passes & CX_TREE_ITERATOR_ENTER) == 0) {
+        // we have to skip the first "entering" passes
+        void *s = NULL;
+        void *n = root;
+        iter.counter = 0;
+        do {
+            iter.counter++;
+            iter.source = s;
+            iter.node = n;
+            cx_tree_iter_stack_add(&iter, n);
+            s = n;
+            n = tree_children(n);
+        } while (n != NULL);
+        // found a leaf node s (might be root itself if it has no children)
+
+        // check if there is a sibling
+        n = tree_next(s);
+
+        if (n == NULL) {
+            // no sibling found, exit back to parent node
+            // TODO: implement
+        } else {
+            // there is a sibling
+            if ((passes & CX_TREE_ITERATOR_EXIT) == 0) {
+                // no exit requested, conclude that only next_child is requested
+                iter.source = s;
+                iter.node = n;
+                iter.counter++;
+                iter.current_pass = CX_TREE_ITERATOR_NEXT_CHILD;
+            } else {
+                // exit requested, so we have found our first pass
+                // iter.node and iter.source are still correct
+                iter.current_pass = CX_TREE_ITERATOR_EXIT;
+            }
+        }
+    } else {
+        // enter passes are requested, we can start by entering the root node
+        iter.source = NULL;
+        iter.node = root;
+        iter.current_pass = CX_TREE_ITERATOR_ENTER;
+        iter.counter = 1;
+        iter.depth = 1;
+        iter.stack[0] = root;
+    }
+
+    // assign base iterator functions
+    iter.base.mutating = false;
+    iter.base.remove = false;
+    iter.base.current_impl = NULL;
+    iter.base.valid = cx_tree_iter_valid;
+    iter.base.next = cx_tree_iter_next;
+    iter.base.current = cx_tree_iter_current;
+
+    return iter;
+}