1.1 --- a/src/tree.c Thu Mar 14 22:07:19 2024 +0100
1.2 +++ b/src/tree.c Wed Mar 20 23:31:41 2024 +0100
1.3 @@ -178,10 +178,8 @@
1.4
1.5 static void cx_tree_iter_next(void *it) {
1.6 struct cx_tree_iterator_s *iter = it;
1.7 - off_t const loc_next = iter->loc_next;
1.8 - off_t const loc_children = iter->loc_children;
1.9 -
1.10 - // TODO: support mutating iterator
1.11 + ptrdiff_t const loc_next = iter->loc_next;
1.12 + ptrdiff_t const loc_children = iter->loc_children;
1.13
1.14 void *children;
1.15
1.16 @@ -280,3 +278,116 @@
1.17
1.18 return iter;
1.19 }
1.20 +
1.21 +static bool cx_tree_visitor_valid(void const *it) {
1.22 + struct cx_tree_visitor_s const *iter = it;
1.23 + return iter->node != NULL;
1.24 +}
1.25 +
1.26 +static void *cx_tree_visitor_current(void const *it) {
1.27 + struct cx_tree_visitor_s const *iter = it;
1.28 + return iter->node;
1.29 +}
1.30 +
1.31 +__attribute__((__nonnull__))
1.32 +static void cx_tree_visitor_enqueue_siblings(
1.33 + struct cx_tree_visitor_s *iter, void *node, ptrdiff_t loc_next) {
1.34 + node = tree_next(node);
1.35 + while (node != NULL) {
1.36 + struct cx_tree_visitor_queue_s *q;
1.37 + q = malloc(sizeof(struct cx_tree_visitor_queue_s));
1.38 + q->depth = iter->queue_last->depth;
1.39 + q->node = node;
1.40 + iter->queue_last->next = q;
1.41 + iter->queue_last = q;
1.42 + node = tree_next(node);
1.43 + }
1.44 + iter->queue_last->next = NULL;
1.45 +}
1.46 +
1.47 +static void cx_tree_visitor_next(void *it) {
1.48 + struct cx_tree_visitor_s *iter = it;
1.49 + ptrdiff_t const loc_next = iter->loc_next;
1.50 + ptrdiff_t const loc_children = iter->loc_children;
1.51 +
1.52 + // check if there is a next node
1.53 + if (iter->queue_next == NULL) {
1.54 + iter->node = NULL;
1.55 + return;
1.56 + }
1.57 +
1.58 + // dequeue the next node
1.59 + iter->node = iter->queue_next->node;
1.60 + iter->depth = iter->queue_next->depth;
1.61 + {
1.62 + struct cx_tree_visitor_queue_s *q = iter->queue_next;
1.63 + iter->queue_next = q->next;
1.64 + if (iter->queue_next == NULL) {
1.65 + assert(iter->queue_last == q);
1.66 + iter->queue_last = NULL;
1.67 + }
1.68 + free(q);
1.69 + }
1.70 +
1.71 + // increment the node counter
1.72 + iter->counter++;
1.73 +
1.74 + // add the children of the new node to the queue
1.75 + void *children = tree_children(iter->node);
1.76 + if (children != NULL) {
1.77 + struct cx_tree_visitor_queue_s *q;
1.78 + q = malloc(sizeof(struct cx_tree_visitor_queue_s));
1.79 + q->depth = iter->depth + 1;
1.80 + q->node = children;
1.81 + if (iter->queue_last == NULL) {
1.82 + assert(iter->queue_next == NULL);
1.83 + iter->queue_next = q;
1.84 + } else {
1.85 + iter->queue_last->next = q;
1.86 + }
1.87 + iter->queue_last = q;
1.88 + cx_tree_visitor_enqueue_siblings(iter, children, loc_next);
1.89 + }
1.90 +}
1.91 +
1.92 +CxTreeVisitor cx_tree_visitor(
1.93 + void *root,
1.94 + ptrdiff_t loc_children,
1.95 + ptrdiff_t loc_next
1.96 +) {
1.97 + CxTreeVisitor iter;
1.98 + iter.loc_children = loc_children;
1.99 + iter.loc_next = loc_next;
1.100 +
1.101 + // allocate stack
1.102 + iter.depth = 0;
1.103 +
1.104 + // visit the root node
1.105 + iter.node = root;
1.106 + iter.counter = 1;
1.107 + iter.depth = 1;
1.108 +
1.109 + // put all children of root into the queue
1.110 + void *children = tree_children(root);
1.111 + if (children == NULL) {
1.112 + iter.queue_next = NULL;
1.113 + iter.queue_last = NULL;
1.114 + } else {
1.115 + iter.queue_next = malloc(sizeof(struct cx_tree_visitor_queue_s));
1.116 + iter.queue_next->depth = 2;
1.117 + iter.queue_next->node = children;
1.118 + iter.queue_last = iter.queue_next;
1.119 + cx_tree_visitor_enqueue_siblings(&iter, children, loc_next);
1.120 + }
1.121 +
1.122 + // assign base iterator functions
1.123 + iter.base.mutating = false;
1.124 + iter.base.remove = false;
1.125 + iter.base.current_impl = NULL;
1.126 + iter.base.valid = cx_tree_visitor_valid;
1.127 + iter.base.next = cx_tree_visitor_next;
1.128 + iter.base.current = cx_tree_visitor_current;
1.129 +
1.130 + return iter;
1.131 +}
1.132 +
