1.1 --- a/src/tree.c Sat Feb 17 20:51:27 2024 +0100
1.2 +++ b/src/tree.c Sun Feb 18 12:24:04 2024 +0100
1.3 @@ -169,3 +169,111 @@
1.4 free(work);
1.5 return ret;
1.6 }
1.7 +
1.8 +static bool cx_tree_iter_valid(void const *it) {
1.9 + struct cx_tree_iterator_s const *iter = it;
1.10 + return iter->node != NULL;
1.11 +}
1.12 +
1.13 +static void *cx_tree_iter_current(void const *it) {
1.14 + struct cx_tree_iterator_s const *iter = it;
1.15 + return iter->node;
1.16 +}
1.17 +
1.18 +static void cx_tree_iter_stack_add(
1.19 + struct cx_tree_iterator_s *iter,
1.20 + void *node
1.21 +) {
1.22 + cx_array_add(&iter->stack, &iter->depth, &iter->stack_capacity,
1.23 + sizeof(void*), &node, cx_array_default_reallocator);
1.24 +}
1.25 +
1.26 +static void cx_tree_iter_next(void *it) {
1.27 + struct cx_tree_iterator_s *iter = it;
1.28 + // TODO: support mutating iterator
1.29 +
1.30 + // TODO: implement
1.31 +}
1.32 +
1.33 +
1.34 +CxTreeIterator cx_tree_iterator(
1.35 + void *root,
1.36 + int passes,
1.37 + ptrdiff_t loc_children,
1.38 + ptrdiff_t loc_next
1.39 +) {
1.40 + CxTreeIterator iter;
1.41 + iter.loc_children = loc_children;
1.42 + iter.loc_next = loc_next;
1.43 + iter.requested_passes = passes;
1.44 +
1.45 + // invalidate iterator immediately when passes is invalid
1.46 + if ((passes & (CX_TREE_ITERATOR_ENTER |
1.47 + CX_TREE_ITERATOR_NEXT_CHILD |
1.48 + CX_TREE_ITERATOR_EXIT)) == 0) {
1.49 + iter.stack = NULL;
1.50 + iter.node = NULL;
1.51 + return iter;
1.52 + }
1.53 +
1.54 + // allocate stack
1.55 + iter.stack_capacity = 16;
1.56 + iter.stack = malloc(sizeof(void *) * 16);
1.57 + iter.depth = 0;
1.58 +
1.59 + // determine start
1.60 + if ((passes & CX_TREE_ITERATOR_ENTER) == 0) {
1.61 + // we have to skip the first "entering" passes
1.62 + void *s = NULL;
1.63 + void *n = root;
1.64 + iter.counter = 0;
1.65 + do {
1.66 + iter.counter++;
1.67 + iter.source = s;
1.68 + iter.node = n;
1.69 + cx_tree_iter_stack_add(&iter, n);
1.70 + s = n;
1.71 + n = tree_children(n);
1.72 + } while (n != NULL);
1.73 + // found a leaf node s (might be root itself if it has no children)
1.74 +
1.75 + // check if there is a sibling
1.76 + n = tree_next(s);
1.77 +
1.78 + if (n == NULL) {
1.79 + // no sibling found, exit back to parent node
1.80 + // TODO: implement
1.81 + } else {
1.82 + // there is a sibling
1.83 + if ((passes & CX_TREE_ITERATOR_EXIT) == 0) {
1.84 + // no exit requested, conclude that only next_child is requested
1.85 + iter.source = s;
1.86 + iter.node = n;
1.87 + iter.counter++;
1.88 + iter.current_pass = CX_TREE_ITERATOR_NEXT_CHILD;
1.89 + } else {
1.90 + // exit requested, so we have found our first pass
1.91 + // iter.node and iter.source are still correct
1.92 + iter.current_pass = CX_TREE_ITERATOR_EXIT;
1.93 + }
1.94 + }
1.95 + } else {
1.96 + // enter passes are requested, we can start by entering the root node
1.97 + iter.source = NULL;
1.98 + iter.node = root;
1.99 + iter.current_pass = CX_TREE_ITERATOR_ENTER;
1.100 + iter.counter = 1;
1.101 + iter.depth = 1;
1.102 + iter.stack[0] = root;
1.103 + }
1.104 +
1.105 + // assign base iterator functions
1.106 + iter.base.mutating = false;
1.107 + iter.base.remove = false;
1.108 + iter.base.current_impl = NULL;
1.109 + iter.base.valid = cx_tree_iter_valid;
1.110 + iter.base.next = cx_tree_iter_next;
1.111 + iter.base.current = cx_tree_iter_current;
1.112 +
1.113 + return iter;
1.114 +}
