Mercurial > hg > ucx / changeset

     1.1 --- a/src/cx/tree.h	Sat Feb 17 20:51:27 2024 +0100
     1.2 +++ b/src/cx/tree.h	Sun Feb 18 12:24:04 2024 +0100
     1.3 @@ -46,14 +46,23 @@
     1.4  
     1.5  /**
     1.6   * When entering a node.
     1.7 + *
     1.8 + * When this is the first sibling, source is the parent, otherwise it is the previous child.
     1.9   */
    1.10  #define CX_TREE_ITERATOR_ENTER      0x1
    1.11  /**
    1.12   * When advancing to the next child.
    1.13 + *
    1.14 + * The visited node is the next child and the source is the previous child.
    1.15 + * This pass is triggered after exiting the previous child and before entering the next child.
    1.16   */
    1.17  #define CX_TREE_ITERATOR_NEXT_CHILD 0x2
    1.18  /**
    1.19   * When exiting the node.
    1.20 + *
    1.21 + * The visited node is the node being exited and source is the previously entered node
    1.22 + * (usually the last child of the exited node, unless it has no children, in which case it is the node itself).
    1.23 + * When advancing to the next child in a list of siblings, the previous child is exited, first.
    1.24   */
    1.25  #define CX_TREE_ITERATOR_EXIT       0x4
    1.26  
    1.27 @@ -278,8 +287,8 @@
    1.28   * @see cxTreeIteratorDispose()
    1.29   */
    1.30  __attribute__((__nonnull__))
    1.31 -CxTreeIterator cx_tree_iterate(
    1.32 -        void const *root,
    1.33 +CxTreeIterator cx_tree_iterator(
    1.34 +        void *root,
    1.35          int passes,
    1.36          ptrdiff_t loc_children,
    1.37          ptrdiff_t loc_next

     2.1 --- a/src/tree.c	Sat Feb 17 20:51:27 2024 +0100
     2.2 +++ b/src/tree.c	Sun Feb 18 12:24:04 2024 +0100
     2.3 @@ -169,3 +169,111 @@
     2.4      free(work);
     2.5      return ret;
     2.6  }
     2.7 +
     2.8 +static bool cx_tree_iter_valid(void const *it) {
     2.9 +    struct cx_tree_iterator_s const *iter = it;
    2.10 +    return iter->node != NULL;
    2.11 +}
    2.12 +
    2.13 +static void *cx_tree_iter_current(void const *it) {
    2.14 +    struct cx_tree_iterator_s const *iter = it;
    2.15 +    return iter->node;
    2.16 +}
    2.17 +
    2.18 +static void cx_tree_iter_stack_add(
    2.19 +        struct cx_tree_iterator_s *iter,
    2.20 +        void *node
    2.21 +) {
    2.22 +    cx_array_add(&iter->stack, &iter->depth, &iter->stack_capacity,
    2.23 +        sizeof(void*), &node, cx_array_default_reallocator);
    2.24 +}
    2.25 +
    2.26 +static void cx_tree_iter_next(void *it) {
    2.27 +    struct cx_tree_iterator_s *iter = it;
    2.28 +    // TODO: support mutating iterator
    2.29 +
    2.30 +    // TODO: implement
    2.31 +}
    2.32 +
    2.33 +
    2.34 +CxTreeIterator cx_tree_iterator(
    2.35 +        void *root,
    2.36 +        int passes,
    2.37 +        ptrdiff_t loc_children,
    2.38 +        ptrdiff_t loc_next
    2.39 +) {
    2.40 +    CxTreeIterator iter;
    2.41 +    iter.loc_children = loc_children;
    2.42 +    iter.loc_next = loc_next;
    2.43 +    iter.requested_passes = passes;
    2.44 +
    2.45 +    // invalidate iterator immediately when passes is invalid
    2.46 +    if ((passes & (CX_TREE_ITERATOR_ENTER |
    2.47 +                   CX_TREE_ITERATOR_NEXT_CHILD |
    2.48 +                   CX_TREE_ITERATOR_EXIT)) == 0) {
    2.49 +        iter.stack = NULL;
    2.50 +        iter.node = NULL;
    2.51 +        return iter;
    2.52 +    }
    2.53 +
    2.54 +    // allocate stack
    2.55 +    iter.stack_capacity = 16;
    2.56 +    iter.stack = malloc(sizeof(void *) * 16);
    2.57 +    iter.depth = 0;
    2.58 +
    2.59 +    // determine start
    2.60 +    if ((passes & CX_TREE_ITERATOR_ENTER) == 0) {
    2.61 +        // we have to skip the first "entering" passes
    2.62 +        void *s = NULL;
    2.63 +        void *n = root;
    2.64 +        iter.counter = 0;
    2.65 +        do {
    2.66 +            iter.counter++;
    2.67 +            iter.source = s;
    2.68 +            iter.node = n;
    2.69 +            cx_tree_iter_stack_add(&iter, n);
    2.70 +            s = n;
    2.71 +            n = tree_children(n);
    2.72 +        } while (n != NULL);
    2.73 +        // found a leaf node s (might be root itself if it has no children)
    2.74 +
    2.75 +        // check if there is a sibling
    2.76 +        n = tree_next(s);
    2.77 +
    2.78 +        if (n == NULL) {
    2.79 +            // no sibling found, exit back to parent node
    2.80 +            // TODO: implement
    2.81 +        } else {
    2.82 +            // there is a sibling
    2.83 +            if ((passes & CX_TREE_ITERATOR_EXIT) == 0) {
    2.84 +                // no exit requested, conclude that only next_child is requested
    2.85 +                iter.source = s;
    2.86 +                iter.node = n;
    2.87 +                iter.counter++;
    2.88 +                iter.current_pass = CX_TREE_ITERATOR_NEXT_CHILD;
    2.89 +            } else {
    2.90 +                // exit requested, so we have found our first pass
    2.91 +                // iter.node and iter.source are still correct
    2.92 +                iter.current_pass = CX_TREE_ITERATOR_EXIT;
    2.93 +            }
    2.94 +        }
    2.95 +    } else {
    2.96 +        // enter passes are requested, we can start by entering the root node
    2.97 +        iter.source = NULL;
    2.98 +        iter.node = root;
    2.99 +        iter.current_pass = CX_TREE_ITERATOR_ENTER;
   2.100 +        iter.counter = 1;
   2.101 +        iter.depth = 1;
   2.102 +        iter.stack[0] = root;
   2.103 +    }
   2.104 +
   2.105 +    // assign base iterator functions
   2.106 +    iter.base.mutating = false;
   2.107 +    iter.base.remove = false;
   2.108 +    iter.base.current_impl = NULL;
   2.109 +    iter.base.valid = cx_tree_iter_valid;
   2.110 +    iter.base.next = cx_tree_iter_next;
   2.111 +    iter.base.current = cx_tree_iter_current;
   2.112 +
   2.113 +    return iter;
   2.114 +}