Mercurial > hg > ucx / changeset

--- a/src/cx/tree.h	Thu Feb 15 21:54:43 2024 +0100
+++ b/src/cx/tree.h	Fri Feb 16 20:23:48 2024 +0100
@@ -38,10 +38,102 @@
 
 #include "common.h"
 
+#include "iterator.h"
+
 #ifdef __cplusplus
 extern "C" {
 #endif
 
+/**
+ * When entering a node.
+ */
+#define CX_TREE_ITERATOR_ENTER      0x1
+/**
+ * When advancing to the next child.
+ */
+#define CX_TREE_ITERATOR_NEXT_CHILD 0x2
+/**
+ * When exiting the node.
+ */
+#define CX_TREE_ITERATOR_EXIT       0x4
+
+/**
+ * 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.
+ * 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
+ * iterator is based on a collection and the underlying collection is mutated by other means than this iterator
+ * (e.g. elements added or removed), the iterator becomes invalid (regardless of what cxIteratorValid() returns)
+ * and MUST be re-obtained from the collection.
+ *
+ * @see CxIterator
+ */
+typedef struct cx_tree_iterator_s {
+    /**
+     * The base properties of this iterator.
+     */
+    struct cx_iterator_base_s base;
+    /**
+     * The passes that are requested by this iterator.
+     * A combination of the flags #CX_TREE_ITERATOR_ENTER, #CX_TREE_ITERATOR_NEXT_CHILD, #CX_TREE_ITERATOR_EXIT.
+     *
+     * Changing the value after beginning the iteration is unspecified.
+     */
+    uint8_t requested_passes;
+    /**
+     * The current pass.
+     *
+     * @see CX_TREE_ITERATOR_ENTER
+     * @see CX_TREE_ITERATOR_NEXT_CHILD
+     * @see CX_TREE_ITERATOR_EXIT
+     */
+    uint8_t current_pass;
+    /**
+     * Offset in the node struct for the children linked list.
+     */
+    off_t loc_children;
+    /**
+     * Offset in the node struct for the next pointer.
+     */
+    off_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 node where we came from.
+     *
+     * - When entering the root node, this is \c NULL.
+     * - When entering another node, this is the node's parent.
+     * - When advancing to the next child, this is the previous child.
+     */
+    void *source;
+    /**
+     * Internal stack.
+     * Will be automatically freed once the iterator becomes invalid.
+     *
+     * If you want to discard the iterator before, you need to manually
+     * call cxTreeIteratorDispose().
+     */
+    void **stack;
+} CxTreeIterator;
+
+/**
+ * Releases internal memory of the given tree iterator.
+ * @param iter the iterator
+ */
+static inline void cxTreeIteratorDispose(CxTreeIterator *iter) {
+    free(iter->stack);
+}
 
 /**
  * Links a node to a (new) parent.