1.1 --- a/src/cx/tree.h Thu Mar 14 22:07:19 2024 +0100
1.2 +++ b/src/cx/tree.h Wed Mar 20 23:31:41 2024 +0100
1.3 @@ -45,7 +45,7 @@
1.4 #endif
1.5
1.6 /**
1.7 - * Tree iterator.
1.8 + * A depth-first tree iterator.
1.9 *
1.10 * This iterator is not position-aware in a strict sense, as it does not assume a particular order of elements in the
1.11 * tree. However, the iterator keeps track of the number of nodes it has passed in a counter variable.
1.12 @@ -74,11 +74,11 @@
1.13 /**
1.14 * Offset in the node struct for the children linked list.
1.15 */
1.16 - off_t loc_children;
1.17 + ptrdiff_t loc_children;
1.18 /**
1.19 * Offset in the node struct for the next pointer.
1.20 */
1.21 - off_t loc_next;
1.22 + ptrdiff_t loc_next;
1.23 /**
1.24 * The total number of distinct nodes that have been passed so far.
1.25 */
1.26 @@ -119,19 +119,105 @@
1.27 } CxTreeIterator;
1.28
1.29 /**
1.30 + * An element in a visitor queue.
1.31 + */
1.32 +struct cx_tree_visitor_queue_s {
1.33 + /**
1.34 + * The tree node to visit.
1.35 + */
1.36 + void *node;
1.37 + /**
1.38 + * The depth of the node.
1.39 + */
1.40 + size_t depth;
1.41 + /**
1.42 + * The next element in the queue or \c NULL.
1.43 + */
1.44 + struct cx_tree_visitor_queue_s *next;
1.45 +};
1.46 +
1.47 +/**
1.48 + * A breadth-first tree iterator.
1.49 + *
1.50 + * This iterator needs to maintain a visitor queue that will be automatically freed once the iterator becomes invalid.
1.51 + * If you want to discard the iterator before, you MUST manually call cxTreeVisitorDispose().
1.52 + *
1.53 + * This iterator is not position-aware in a strict sense, as it does not assume a particular order of elements in the
1.54 + * tree. However, the iterator keeps track of the number of nodes it has passed in a counter variable.
1.55 + * Each node, regardless of the number of passes, is counted only once.
1.56 + *
1.57 + * @note Objects that are pointed to by an iterator are mutable through that iterator. However, if the
1.58 + * underlying data structure is mutated by other means than this iterator (e.g. elements added or removed),
1.59 + * the iterator becomes invalid (regardless of what cxIteratorValid() returns).
1.60 + *
1.61 + * @see CxIterator
1.62 + */
1.63 +typedef struct cx_tree_visitor_s {
1.64 + /**
1.65 + * The base properties of this iterator.
1.66 + */
1.67 + struct cx_iterator_base_s base;
1.68 + /**
1.69 + * Offset in the node struct for the children linked list.
1.70 + */
1.71 + ptrdiff_t loc_children;
1.72 + /**
1.73 + * Offset in the node struct for the next pointer.
1.74 + */
1.75 + ptrdiff_t loc_next;
1.76 + /**
1.77 + * The total number of distinct nodes that have been passed so far.
1.78 + */
1.79 + size_t counter;
1.80 + /**
1.81 + * The currently observed node.
1.82 + *
1.83 + * This is the same what cxIteratorCurrent() would return.
1.84 + */
1.85 + void *node;
1.86 + /**
1.87 + * The current depth in the tree.
1.88 + */
1.89 + size_t depth;
1.90 + /**
1.91 + * The next element in the visitor queue.
1.92 + */
1.93 + struct cx_tree_visitor_queue_s *queue_next;
1.94 + /**
1.95 + * The last element in the visitor queue.
1.96 + */
1.97 + struct cx_tree_visitor_queue_s *queue_last;
1.98 +} CxTreeVisitor;
1.99 +
1.100 +/**
1.101 * Releases internal memory of the given tree iterator.
1.102 * @param iter the iterator
1.103 */
1.104 + __attribute__((__nonnull__))
1.105 static inline void cxTreeIteratorDispose(CxTreeIterator *iter) {
1.106 free(iter->stack);
1.107 iter->stack = NULL;
1.108 }
1.109
1.110 /**
1.111 + * Releases internal memory of the given tree visitor.
1.112 + * @param visitor the visitor
1.113 + */
1.114 +__attribute__((__nonnull__))
1.115 +static inline void cxTreeVisitorDispose(CxTreeVisitor *visitor) {
1.116 + struct cx_tree_visitor_queue_s *q = visitor->queue_next;
1.117 + while (q != NULL) {
1.118 + struct cx_tree_visitor_queue_s *next = q->next;
1.119 + free(q);
1.120 + q = next;
1.121 + }
1.122 +}
1.123 +
1.124 +/**
1.125 * Links a node to a (new) parent.
1.126 *
1.127 * If the node has already a parent, it is unlinked, first.
1.128 - * If the parent has children already, the node is prepended to the list
1.129 + * If the parent has children already, the node is \em prepended to the list
1.130 * of all currently existing children.
1.131 *
1.132 * @param parent the parent node
1.133 @@ -234,14 +320,14 @@
1.134 );
1.135
1.136 /**
1.137 - * Creates an iterator for a tree with the specified root node.
1.138 + * Creates a depth-first iterator for a tree with the specified root node.
1.139 *
1.140 * @note A tree iterator needs to maintain a stack of visited nodes, which is allocated using stdlib malloc().
1.141 * When the iterator becomes invalid, this memory is automatically released. However, if you wish to cancel the
1.142 * iteration before the iterator becomes invalid by itself, you MUST call cxTreeIteratorDispose() manually to release
1.143 * the memory.
1.144 *
1.145 - * @remark At the moment, the returned iterator does not support cxIteratorFlagRemoval().
1.146 + * @remark The returned iterator does not support cxIteratorFlagRemoval().
1.147 *
1.148 * @param root the root node
1.149 * @param visit_on_exit set to true, when the iterator shall visit a node again after processing all children
1.150 @@ -258,6 +344,29 @@
1.151 ptrdiff_t loc_next
1.152 );
1.153
1.154 +/**
1.155 + * Creates a breadth-first iterator for a tree with the specified root node.
1.156 + *
1.157 + * @note A tree visitor needs to maintain a queue of to be visited nodes, which is allocated using stdlib malloc().
1.158 + * When the visitor becomes invalid, this memory is automatically released. However, if you wish to cancel the
1.159 + * iteration before the visitor becomes invalid by itself, you MUST call cxTreeVisitorDispose() manually to release
1.160 + * the memory.
1.161 + *
1.162 + * @remark The returned iterator does not support cxIteratorFlagRemoval().
1.163 + *
1.164 + * @param root the root node
1.165 + * @param loc_children offset in the node struct for the children linked list
1.166 + * @param loc_next offset in the node struct for the next pointer
1.167 + * @return the new tree visitor
1.168 + * @see cxTreeVisitorDispose()
1.169 + */
1.170 +__attribute__((__nonnull__))
1.171 +CxTreeVisitor cx_tree_visitor(
1.172 + void *root,
1.173 + ptrdiff_t loc_children,
1.174 + ptrdiff_t loc_next
1.175 +);
1.176 +
1.177 #ifdef __cplusplus
1.178 } // extern "C"
1.179 #endif
