Mercurial > hg > ucx / changeset

     1.1 --- a/src/cx/tree.h	Thu Feb 15 21:54:43 2024 +0100
     1.2 +++ b/src/cx/tree.h	Fri Feb 16 20:23:48 2024 +0100
     1.3 @@ -38,10 +38,102 @@
     1.4  
     1.5  #include "common.h"
     1.6  
     1.7 +#include "iterator.h"
     1.8 +
     1.9  #ifdef __cplusplus
    1.10  extern "C" {
    1.11  #endif
    1.12  
    1.13 +/**
    1.14 + * When entering a node.
    1.15 + */
    1.16 +#define CX_TREE_ITERATOR_ENTER      0x1
    1.17 +/**
    1.18 + * When advancing to the next child.
    1.19 + */
    1.20 +#define CX_TREE_ITERATOR_NEXT_CHILD 0x2
    1.21 +/**
    1.22 + * When exiting the node.
    1.23 + */
    1.24 +#define CX_TREE_ITERATOR_EXIT       0x4
    1.25 +
    1.26 +/**
    1.27 + * Tree iterator.
    1.28 + *
    1.29 + * This iterator is not position-aware in a strict sense, as it does not assume a particular order of elements in the
    1.30 + * tree. However, the iterator keeps track of the number of nodes it has passed in a counter variable.
    1.31 + * Each node, regardless of the number of passes, is counted only once.
    1.32 + *
    1.33 + * @note Objects that are pointed to by an iterator are mutable through that iterator. However, if the
    1.34 + * iterator is based on a collection and the underlying collection is mutated by other means than this iterator
    1.35 + * (e.g. elements added or removed), the iterator becomes invalid (regardless of what cxIteratorValid() returns)
    1.36 + * and MUST be re-obtained from the collection.
    1.37 + *
    1.38 + * @see CxIterator
    1.39 + */
    1.40 +typedef struct cx_tree_iterator_s {
    1.41 +    /**
    1.42 +     * The base properties of this iterator.
    1.43 +     */
    1.44 +    struct cx_iterator_base_s base;
    1.45 +    /**
    1.46 +     * The passes that are requested by this iterator.
    1.47 +     * A combination of the flags #CX_TREE_ITERATOR_ENTER, #CX_TREE_ITERATOR_NEXT_CHILD, #CX_TREE_ITERATOR_EXIT.
    1.48 +     *
    1.49 +     * Changing the value after beginning the iteration is unspecified.
    1.50 +     */
    1.51 +    uint8_t requested_passes;
    1.52 +    /**
    1.53 +     * The current pass.
    1.54 +     *
    1.55 +     * @see CX_TREE_ITERATOR_ENTER
    1.56 +     * @see CX_TREE_ITERATOR_NEXT_CHILD
    1.57 +     * @see CX_TREE_ITERATOR_EXIT
    1.58 +     */
    1.59 +    uint8_t current_pass;
    1.60 +    /**
    1.61 +     * Offset in the node struct for the children linked list.
    1.62 +     */
    1.63 +    off_t loc_children;
    1.64 +    /**
    1.65 +     * Offset in the node struct for the next pointer.
    1.66 +     */
    1.67 +    off_t loc_next;
    1.68 +    /**
    1.69 +     * The total number of distinct nodes that have been passed so far.
    1.70 +     */
    1.71 +    size_t counter;
    1.72 +    /**
    1.73 +     * The currently observed node.
    1.74 +     *
    1.75 +     * This is the same what cxIteratorCurrent() would return.
    1.76 +     */
    1.77 +    void *node;
    1.78 +    /**
    1.79 +     * The node where we came from.
    1.80 +     *
    1.81 +     * - When entering the root node, this is \c NULL.
    1.82 +     * - When entering another node, this is the node's parent.
    1.83 +     * - When advancing to the next child, this is the previous child.
    1.84 +     */
    1.85 +    void *source;
    1.86 +    /**
    1.87 +     * Internal stack.
    1.88 +     * Will be automatically freed once the iterator becomes invalid.
    1.89 +     *
    1.90 +     * If you want to discard the iterator before, you need to manually
    1.91 +     * call cxTreeIteratorDispose().
    1.92 +     */
    1.93 +    void **stack;
    1.94 +} CxTreeIterator;
    1.95 +
    1.96 +/**
    1.97 + * Releases internal memory of the given tree iterator.
    1.98 + * @param iter the iterator
    1.99 + */
   1.100 +static inline void cxTreeIteratorDispose(CxTreeIterator *iter) {
   1.101 +    free(iter->stack);
   1.102 +}
   1.103  
   1.104  /**
   1.105   * Links a node to a (new) parent.