diff -r 1f40ca07ae1b -r 839fefbdedc7 ucx/cx/tree.h
--- a/ucx/cx/tree.h	Sat Apr 20 13:01:58 2024 +0200
+++ b/ucx/cx/tree.h	Thu May 23 22:35:45 2024 +0200
@@ -1,7 +1,7 @@
 /*
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
  *
- * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
+ * Copyright 2024 Mike Becker, Olaf Wintermann All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are met:
@@ -28,9 +28,8 @@
 /**
  * \file tree.h
  * \brief Interface for tree implementations.
+ * \author Mike Becker
  * \author Olaf Wintermann
- * \author Mike Becker
- * \version 3.0
  * \copyright 2-Clause BSD License
  */
 
@@ -38,99 +37,362 @@
 #define UCX_TREE_H
 
 #include "common.h"
-#include "allocator.h"
+
+#include "iterator.h"
 
 #ifdef __cplusplus
 extern "C" {
 #endif
 
 /**
- * Adds a sibling to the current tree node.
- *
- * In case your struct does not have a \p prev or a \p parent pointer,
- * specify a negative location. The location of the \p next pointer is
- * mandatory.
+ * A depth-first tree iterator.
  *
- * \attention Do not use this function to add siblings in a tree where the
- * nodes store a pointer to the last sibling because that would not be modified by this function.
+ * 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.
  *
- * \remark If yo do not provide a location to the parent pointer, a call to this function is
- * effectively the same as a call to cx_linked_list_add().
+ * @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).
  *
- * @param node a pointer to the node
- * @param loc_prev the location of a \c prev pointer within your node struct
- * @param loc_next the location of a \c next pointer within your node struct
- * @param loc_parent the location of a \c parent pointer within your node struct
- * @param new_node the new node that shall be added as a sibling
+ * @see CxIterator
+ */
+typedef struct cx_tree_iterator_s {
+    /**
+     * Base members.
+     */
+    CX_ITERATOR_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.
+     */
+    bool visit_on_exit;
+    /**
+     * True, if this iterator is currently leaving the node.
+     */
+    bool exiting;
+    /**
+     * 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;
+    /**
+     * Stores a copy of the next pointer of the visited node.
+     * Allows freeing a node on exit without corrupting the iteration.
+     */
+    void *node_next;
+    /**
+     * 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;
+    /**
+     * Internal capacity of the stack.
+     */
+    size_t stack_capacity;
+    union {
+        /**
+         * Internal stack size.
+         */
+        size_t stack_size;
+        /**
+         * The current depth in the tree.
+         */
+        size_t depth;
+    };
+} CxTreeIterator;
+
+/**
+ * An element in a visitor queue.
  */
-void cx_tree_add_sibling(void *node,
-                         ptrdiff_t loc_prev, ptrdiff_t loc_next,
-                         ptrdiff_t loc_parent,
-                         void *new_node)
-__attribute__((__nonnull__));
+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 {
+    /**
+     * Base members.
+     */
+    CX_ITERATOR_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;
+    /**
+     * 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;
+}
 
 /**
- * Adds a node to the list of children.
+ * 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;
+    }
+}
+
+/**
+ * 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.
+ * If the parent has children already, the node is \em prepended to the list
+ * of all currently existing children.
  *
- * \par Example with a full structure
- * A full tree node structure may look like this:
- * \code
- * typedef struct MyTreeNode MyTreeNode;
- * struct MyTreeNode {
- *   MyTreeNode* parent;
- *   MyTreeNode* first_child;
- *   MyTreeNode* last_child;
- *   MyTreeNode* prev_sibling;
- *   MyTreeNode* next_sibling;
- *   // ...contents...
- * }
- * \endcode
- * Adding a new child to a node with the above structure can be performed with the following call:
- * \code
- * MyTreeNode *node, *child; // given
- * cx_tree_add_child(&node->first_child, &node->last_child,
- *                   offsetof(MyTreeNode, prev_sibling), offsetof(MyTreeNode, next_sibling),
- *                   child, offsetof(MyTreeNode, parent), node);
- * \endcode
+ * @param parent the parent node
+ * @param node the node that shall be linked
+ * @param loc_parent offset in the node struct for the parent pointer
+ * @param loc_children offset in the node struct for the children linked list
+ * @param loc_prev offset in the node struct for the prev pointer
+ * @param loc_next offset in the node struct for the next pointer
+ * @see cx_tree_unlink()
+ */
+__attribute__((__nonnull__))
+void cx_tree_link(
+        void * restrict parent,
+        void * restrict node,
+        ptrdiff_t loc_parent,
+        ptrdiff_t loc_children,
+        ptrdiff_t loc_prev,
+        ptrdiff_t loc_next
+);
+
+/**
+ * Unlinks a node from its parent.
+ *
+ * If the node has no parent, this function does nothing.
+ *
+ * @param node the node that shall be unlinked from its parent
+ * @param loc_parent offset in the node struct for the parent pointer
+ * @param loc_children offset in the node struct for the children linked list
+ * @param loc_prev offset in the node struct for the prev pointer
+ * @param loc_next offset in the node struct for the next pointer
+ * @see cx_tree_link()
+ */
+__attribute__((__nonnull__))
+void cx_tree_unlink(
+        void *node,
+        ptrdiff_t loc_parent,
+        ptrdiff_t loc_children,
+        ptrdiff_t loc_prev,
+        ptrdiff_t loc_next
+);
+
+/**
+ * Function pointer for a search function.
+ *
+ * A function of this kind shall check if the specified \p node
+ * contains the given \p data or if one of the children might contain
+ * the data.
+ *
+ * The function should use the returned integer to indicate how close the
+ * match is, where a negative number means that it does not match at all.
  *
- * \par Example with a reduced structure
- * The minimal reasonable structure with parent pointer looks like this:
- * \code
- * typedef struct MyTreeNode MyTreeNode;
- * struct MyTreeNode {
- *   MyTreeNode* parent;
- *   MyTreeNode* children;
- *   MyTreeNode* next_sibling;
- *   // ...contents...
- * }
- * \endcode
- * This simplifies the function call to:
- * \code
- * MyTreeNode *node, *child; // given
- * cx_tree_add_child(&node->children, NULL, -1, offsetof(MyTreeNode, next_sibling),
- *                   child, offsetof(MyTreeNode, parent), node);
- * \endcode
+ * For example if a tree stores file path information, a node that is
+ * describing a parent directory of a filename that is searched, shall
+ * return a positive number to indicate that a child node might contain the
+ * searched item. On the other hand, if the node denotes a path that is not a
+ * prefix of the searched filename, the function would return -1 to indicate
+ * that * the search does not need to be continued in that branch.
+ *
+ * @param node the node that is currently investigated
+ * @param data the data that is searched for
+ *
+ * @return 0 if the node contains the data,
+ * positive if one of the children might contain the data,
+ * negative if neither the node, nor the children contains the data
+ */
+typedef int (*cx_tree_search_func)(void const *node, void const* data);
+
+
+/**
+ * Searches for data in a tree.
+ *
+ * When the data cannot be found exactly, the search function might return a
+ * closest result which might be a good starting point for adding a new node
+ * to the tree.
+ *
+ * Depending on the tree structure it is not necessarily guaranteed that the
+ * "closest" match is uniquely defined. This function will search for a node
+ * with the best match according to the \p sfunc (meaning: the return value of
+ * \p sfunc which is closest to zero). If that is also ambiguous, an arbitrary
+ * node matching the criteria is returned.
  *
- * \remark If your tree structure does not possess a parent pointer, a call to this function is
- * effectively the same as a call to cx_linked_list_add().
+ * @param root the root node
+ * @param data the data to search for
+ * @param sfunc the search function
+ * @param result where the result shall be stored
+ * @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 zero if the node was found exactly, positive if a node was found that
+ * could contain the node (but doesn't right now), negative if the tree does not
+ * contain any node that might be related to the searched data
+ */
+__attribute__((__nonnull__))
+int cx_tree_search(
+        void const *root,
+        void const *data,
+        cx_tree_search_func sfunc,
+        void **result,
+        ptrdiff_t loc_children,
+        ptrdiff_t loc_next
+);
+
+/**
+ * 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 The returned iterator does not support cxIteratorFlagRemoval().
  *
- * @param children_begin a pointer to the begin node pointer (if your list has one)
- * @param children_end a pointer to the end node pointer (if your list has one)
- * @param loc_prev the location of a \c prev pointer within your node struct
- * @param loc_next the location of a \c next pointer within your node struct
- * @param new_node a pointer to the node that shall be appended
- * @param loc_parent the location of a \c parent pointer within your node struct
- * @param parent the parent node
+ * @param root the root node
+ * @param visit_on_exit set to true, when the iterator shall visit a node again after processing all children
+ * @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 iterator
+ * @see cxTreeIteratorDispose()
  */
-void cx_tree_add_child(void **children_begin, void **children_end,
-                       ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node,
-                       ptrdiff_t loc_parent, void *parent)
-__attribute__((__nonnull__ (5)));
+__attribute__((__nonnull__))
+CxTreeIterator cx_tree_iterator(
+        void *root,
+        bool visit_on_exit,
+        ptrdiff_t loc_children,
+        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
 
-#endif // UCX_TREE_H
-
+#endif //UCX_TREE_H