ucx: comparison src/cx/tree.h

-:3270ea9e41ef
+:2615317311b7
 #ifdef __cplusplus
 extern "C" {
 #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.
 * Each node, regardless of the number of passes, is counted only once.
 *
 */
 bool exiting;
 /**
 * 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.
 */
 size_t counter;
 /**
 size_t depth;
 };
 } 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
 * @param node the node that shall be linked
 * @param loc_parent offset in the node struct for the parent pointer
 ptrdiff_t loc_children,
 ptrdiff_t loc_next
 );
 /**
-* 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
 * @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
 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

Mercurial > hg > ucx / file comparison

comparison: src/cx/tree.h

src/cx/tree.h