Mercurial > hg > ucx / changeset

     1.1 --- a/src/cx/tree.h	Wed Mar 20 23:35:32 2024 +0100
     1.2 +++ b/src/cx/tree.h	Wed Apr 03 21:22:23 2024 +0200
     1.3 @@ -63,6 +63,10 @@
     1.4       */
     1.5      struct cx_iterator_base_s base;
     1.6      /**
     1.7 +     * Indicates whether the subtree below the current node shall be skipped.
     1.8 +     */
     1.9 +    bool skip;
    1.10 +    /**
    1.11       * Set to true, when the iterator shall visit a node again
    1.12       * when all it's children have been processed.
    1.13       */
    1.14 @@ -158,6 +162,10 @@
    1.15       */
    1.16      struct cx_iterator_base_s base;
    1.17      /**
    1.18 +     * Indicates whether the subtree below the current node shall be skipped.
    1.19 +     */
    1.20 +    bool skip;
    1.21 +    /**
    1.22       * Offset in the node struct for the children linked list.
    1.23       */
    1.24      ptrdiff_t loc_children;
    1.25 @@ -214,6 +222,22 @@
    1.26  }
    1.27  
    1.28  /**
    1.29 + * Advises the iterator to skip the subtree below the current node and
    1.30 + * also continues the current loop.
    1.31 + *
    1.32 + * @param iterator the iterator
    1.33 + */
    1.34 +#define cxTreeIteratorContinue(iterator) (iterator).skip = true; continue
    1.35 +
    1.36 +/**
    1.37 + * Advises the visitor to skip the subtree below the current node and
    1.38 + * also continues the current loop.
    1.39 + *
    1.40 + * @param visitor the visitor
    1.41 + */
    1.42 +#define cxTreeVisitorContinue(visitor) cxTreeIteratorContinue(visitor)
    1.43 +
    1.44 +/**
    1.45   * Links a node to a (new) parent.
    1.46   *
    1.47   * If the node has already a parent, it is unlinked, first.

     2.1 --- a/src/tree.c	Wed Mar 20 23:35:32 2024 +0100
     2.2 +++ b/src/tree.c	Wed Apr 03 21:22:23 2024 +0200
     2.3 @@ -186,8 +186,17 @@
     2.4      // check if we are currently exiting or entering nodes
     2.5      if (iter->exiting) {
     2.6          children = NULL;
     2.7 +        // skipping on exit is pointless, just clear the flag
     2.8 +        iter->skip = false;
     2.9      } else {
    2.10 -        children = tree_children(iter->node);
    2.11 +        if (iter->skip) {
    2.12 +            // skip flag is set, pretend that there are no children
    2.13 +            iter->skip = false;
    2.14 +            children = NULL;
    2.15 +        } else {
    2.16 +            // try to enter the children (if any)
    2.17 +            children = tree_children(iter->node);
    2.18 +        }
    2.19      }
    2.20  
    2.21      if (children == NULL) {
    2.22 @@ -263,10 +272,12 @@
    2.23  
    2.24      // visit the root node
    2.25      iter.node = root;
    2.26 +    iter.next = NULL;
    2.27      iter.counter = 1;
    2.28      iter.depth = 1;
    2.29      iter.stack[0] = root;
    2.30      iter.exiting = false;
    2.31 +    iter.skip = false;
    2.32  
    2.33      // assign base iterator functions
    2.34      iter.base.mutating = false;
    2.35 @@ -310,6 +321,30 @@
    2.36      ptrdiff_t const loc_next = iter->loc_next;
    2.37      ptrdiff_t const loc_children = iter->loc_children;
    2.38  
    2.39 +    // add the children of the current node to the queue
    2.40 +    // unless the skip flag is set
    2.41 +    void *children;
    2.42 +    if (iter->skip) {
    2.43 +        iter->skip = false;
    2.44 +        children = NULL;
    2.45 +    } else {
    2.46 +        children = tree_children(iter->node);
    2.47 +    }
    2.48 +    if (children != NULL) {
    2.49 +        struct cx_tree_visitor_queue_s *q;
    2.50 +        q = malloc(sizeof(struct cx_tree_visitor_queue_s));
    2.51 +        q->depth = iter->depth + 1;
    2.52 +        q->node = children;
    2.53 +        if (iter->queue_last == NULL) {
    2.54 +            assert(iter->queue_next == NULL);
    2.55 +            iter->queue_next = q;
    2.56 +        } else {
    2.57 +            iter->queue_last->next = q;
    2.58 +        }
    2.59 +        iter->queue_last = q;
    2.60 +        cx_tree_visitor_enqueue_siblings(iter, children, loc_next);
    2.61 +    }
    2.62 +
    2.63      // check if there is a next node
    2.64      if (iter->queue_next == NULL) {
    2.65          iter->node = NULL;
    2.66 @@ -331,23 +366,6 @@
    2.67  
    2.68      // increment the node counter
    2.69      iter->counter++;
    2.70 -
    2.71 -    // add the children of the new node to the queue
    2.72 -    void *children = tree_children(iter->node);
    2.73 -    if (children != NULL) {
    2.74 -        struct cx_tree_visitor_queue_s *q;
    2.75 -        q = malloc(sizeof(struct cx_tree_visitor_queue_s));
    2.76 -        q->depth = iter->depth + 1;
    2.77 -        q->node = children;
    2.78 -        if (iter->queue_last == NULL) {
    2.79 -            assert(iter->queue_next == NULL);
    2.80 -            iter->queue_next = q;
    2.81 -        } else {
    2.82 -            iter->queue_last->next = q;
    2.83 -        }
    2.84 -        iter->queue_last = q;
    2.85 -        cx_tree_visitor_enqueue_siblings(iter, children, loc_next);
    2.86 -    }
    2.87  }
    2.88  
    2.89  CxTreeVisitor cx_tree_visitor(
    2.90 @@ -366,19 +384,9 @@
    2.91      iter.node = root;
    2.92      iter.counter = 1;
    2.93      iter.depth = 1;
    2.94 -
    2.95 -    // put all children of root into the queue
    2.96 -    void *children = tree_children(root);
    2.97 -    if (children == NULL) {
    2.98 -        iter.queue_next = NULL;
    2.99 -        iter.queue_last = NULL;
   2.100 -    } else {
   2.101 -        iter.queue_next = malloc(sizeof(struct cx_tree_visitor_queue_s));
   2.102 -        iter.queue_next->depth = 2;
   2.103 -        iter.queue_next->node = children;
   2.104 -        iter.queue_last = iter.queue_next;
   2.105 -        cx_tree_visitor_enqueue_siblings(&iter, children, loc_next);
   2.106 -    }
   2.107 +    iter.skip = false;
   2.108 +    iter.queue_next = NULL;
   2.109 +    iter.queue_last = NULL;
   2.110  
   2.111      // assign base iterator functions
   2.112      iter.base.mutating = false;

     3.1 --- a/tests/test_tree.c	Wed Mar 20 23:35:32 2024 +0100
     3.2 +++ b/tests/test_tree.c	Wed Apr 03 21:22:23 2024 +0200
     3.3 @@ -644,6 +644,196 @@
     3.4      }
     3.5  }
     3.6  
     3.7 +CX_TEST(test_tree_visitor_continue) {
     3.8 +    tree_node root = {0};
     3.9 +    tree_node a = {0};
    3.10 +    tree_node b = {0};
    3.11 +    tree_node c = {0};
    3.12 +    tree_node aa = {0};
    3.13 +    tree_node ab = {0};
    3.14 +    tree_node ba = {0};
    3.15 +    tree_node ca = {0};
    3.16 +    tree_node cb = {0};
    3.17 +    tree_node cc = {0};
    3.18 +    tree_node cba = {0};
    3.19 +
    3.20 +    tree_node* expected_order[] = {
    3.21 +            &root,
    3.22 +            &c, &b, &a,
    3.23 +            &ba, &ab, &aa
    3.24 +    };
    3.25 +    tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong
    3.26 +
    3.27 +    cx_tree_link(&root, &a, tree_node_layout);
    3.28 +    cx_tree_link(&root, &b, tree_node_layout);
    3.29 +    cx_tree_link(&root, &c, tree_node_layout);
    3.30 +    cx_tree_link(&a, &aa, tree_node_layout);
    3.31 +    cx_tree_link(&a, &ab, tree_node_layout);
    3.32 +    cx_tree_link(&b, &ba, tree_node_layout);
    3.33 +    cx_tree_link(&c, &ca, tree_node_layout);
    3.34 +    cx_tree_link(&c, &cb, tree_node_layout);
    3.35 +    cx_tree_link(&c, &cc, tree_node_layout);
    3.36 +    cx_tree_link(&cb, &cba, tree_node_layout);
    3.37 +    CX_TEST_DO {
    3.38 +        CxTreeVisitor iter = cx_tree_visitor(&root, tree_child_list);
    3.39 +        unsigned chk = 0;
    3.40 +        cx_foreach(tree_node*, node, iter) {
    3.41 +            CX_TEST_ASSERT(node->data == 0);
    3.42 +            node->data++;
    3.43 +            actual_order[chk] = node;
    3.44 +            chk++;
    3.45 +            CX_TEST_ASSERT(node == iter.node);
    3.46 +            if (node == &root) {
    3.47 +                CX_TEST_ASSERT(iter.depth == 1);
    3.48 +            } else if (node == &a || node == &b || node == &c) {
    3.49 +                CX_TEST_ASSERT(iter.depth == 2);
    3.50 +            } else {
    3.51 +                CX_TEST_ASSERT(iter.depth == 3);
    3.52 +            }
    3.53 +            if (node == &c) {
    3.54 +                cxTreeVisitorContinue(iter);
    3.55 +            }
    3.56 +        }
    3.57 +        CX_TEST_ASSERT(iter.counter == 7);
    3.58 +        CX_TEST_ASSERT(chk == 7);
    3.59 +        for (unsigned i = 0 ; i < chk ; i++) {
    3.60 +            CX_TEST_ASSERT(actual_order[i] == expected_order[i]);
    3.61 +            CX_TEST_ASSERT(actual_order[i]->data == 1);
    3.62 +        }
    3.63 +        CX_TEST_ASSERT(ca.data == 0);
    3.64 +        CX_TEST_ASSERT(cb.data == 0);
    3.65 +        CX_TEST_ASSERT(cc.data == 0);
    3.66 +        CX_TEST_ASSERT(cba.data == 0);
    3.67 +        CX_TEST_ASSERT(iter.queue_next == NULL);
    3.68 +        CX_TEST_ASSERT(iter.queue_last == NULL);
    3.69 +    }
    3.70 +}
    3.71 +
    3.72 +CX_TEST(test_tree_iterator_continue) {
    3.73 +    tree_node root = {0};
    3.74 +    tree_node a = {0};
    3.75 +    tree_node b = {0};
    3.76 +    tree_node c = {0};
    3.77 +    tree_node aa = {0};
    3.78 +    tree_node ab = {0};
    3.79 +    tree_node ba = {0};
    3.80 +    tree_node ca = {0};
    3.81 +    tree_node cb = {0};
    3.82 +    tree_node cc = {0};
    3.83 +    tree_node cba = {0};
    3.84 +
    3.85 +    tree_node* expected_order[] = {
    3.86 +            &root,
    3.87 +            &c,
    3.88 +            &b, &ba,
    3.89 +            &a, &ab, &aa,
    3.90 +    };
    3.91 +    tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong
    3.92 +
    3.93 +    cx_tree_link(&root, &a, tree_node_layout);
    3.94 +    cx_tree_link(&root, &b, tree_node_layout);
    3.95 +    cx_tree_link(&root, &c, tree_node_layout);
    3.96 +    cx_tree_link(&a, &aa, tree_node_layout);
    3.97 +    cx_tree_link(&a, &ab, tree_node_layout);
    3.98 +    cx_tree_link(&b, &ba, tree_node_layout);
    3.99 +    cx_tree_link(&c, &ca, tree_node_layout);
   3.100 +    cx_tree_link(&c, &cb, tree_node_layout);
   3.101 +    cx_tree_link(&c, &cc, tree_node_layout);
   3.102 +    cx_tree_link(&cb, &cba, tree_node_layout);
   3.103 +    CX_TEST_DO {
   3.104 +        CxTreeIterator iter = cx_tree_iterator(&root, false, tree_child_list);
   3.105 +        unsigned chk = 0;
   3.106 +        cx_foreach(tree_node*, node, iter) {
   3.107 +            CX_TEST_ASSERT(node->data == 0);
   3.108 +            node->data++;
   3.109 +            actual_order[chk] = node;
   3.110 +            chk++;
   3.111 +            CX_TEST_ASSERT(node == iter.node);
   3.112 +            CX_TEST_ASSERT(!iter.exiting);
   3.113 +            if (node == &root) {
   3.114 +                CX_TEST_ASSERT(iter.depth == 1);
   3.115 +            } else if (node == &a || node == &b || node == &c) {
   3.116 +                CX_TEST_ASSERT(iter.depth == 2);
   3.117 +            } else {
   3.118 +                CX_TEST_ASSERT(iter.depth == 3);
   3.119 +            }
   3.120 +            if (node == &c) {
   3.121 +                cxTreeIteratorContinue(iter);
   3.122 +            }
   3.123 +        }
   3.124 +        CX_TEST_ASSERT(iter.counter == 7);
   3.125 +        CX_TEST_ASSERT(chk == 7);
   3.126 +        for (unsigned i = 0 ; i < chk ; i++) {
   3.127 +            CX_TEST_ASSERT(actual_order[i] == expected_order[i]);
   3.128 +            CX_TEST_ASSERT(actual_order[i]->data == 1);
   3.129 +        }
   3.130 +        CX_TEST_ASSERT(ca.data == 0);
   3.131 +        CX_TEST_ASSERT(cb.data == 0);
   3.132 +        CX_TEST_ASSERT(cc.data == 0);
   3.133 +        CX_TEST_ASSERT(cba.data == 0);
   3.134 +        CX_TEST_ASSERT(iter.stack == NULL);
   3.135 +    }
   3.136 +}
   3.137 +
   3.138 +CX_TEST(test_tree_iterator_continue_with_exit) {
   3.139 +    tree_node root = {0};
   3.140 +    tree_node a = {0};
   3.141 +    tree_node b = {0};
   3.142 +    tree_node c = {0};
   3.143 +    tree_node aa = {0};
   3.144 +    tree_node ab = {0};
   3.145 +    tree_node ba = {0};
   3.146 +    tree_node ca = {0};
   3.147 +    tree_node cb = {0};
   3.148 +    tree_node cc = {0};
   3.149 +    tree_node cba = {0};
   3.150 +
   3.151 +    cx_tree_link(&root, &a, tree_node_layout);
   3.152 +    cx_tree_link(&root, &b, tree_node_layout);
   3.153 +    cx_tree_link(&root, &c, tree_node_layout);
   3.154 +    cx_tree_link(&a, &aa, tree_node_layout);
   3.155 +    cx_tree_link(&a, &ab, tree_node_layout);
   3.156 +    cx_tree_link(&b, &ba, tree_node_layout);
   3.157 +    cx_tree_link(&c, &ca, tree_node_layout);
   3.158 +    cx_tree_link(&c, &cb, tree_node_layout);
   3.159 +    cx_tree_link(&c, &cc, tree_node_layout);
   3.160 +    cx_tree_link(&cb, &cba, tree_node_layout);
   3.161 +    CX_TEST_DO {
   3.162 +        CxTreeIterator iter = cx_tree_iterator(&root, true, tree_child_list);
   3.163 +        unsigned chk = 0;
   3.164 +        cx_foreach(tree_node*, node, iter) {
   3.165 +            CX_TEST_ASSERT(iter.exiting || node->data == 0);
   3.166 +            node->data++;
   3.167 +            chk++;
   3.168 +            CX_TEST_ASSERT(node == iter.node);
   3.169 +            if (node == &root) {
   3.170 +                CX_TEST_ASSERT(iter.depth == 1);
   3.171 +            } else if (node == &a || node == &b || node == &c) {
   3.172 +                CX_TEST_ASSERT(iter.depth == 2);
   3.173 +            } else {
   3.174 +                CX_TEST_ASSERT(iter.depth == 3);
   3.175 +            }
   3.176 +            if (node == &c) {
   3.177 +                cxTreeIteratorContinue(iter);
   3.178 +            }
   3.179 +        }
   3.180 +        CX_TEST_ASSERT(iter.counter == 7);
   3.181 +        CX_TEST_ASSERT(chk == 14);
   3.182 +        CX_TEST_ASSERT(iter.stack == NULL);
   3.183 +        CX_TEST_ASSERT(root.data == 2);
   3.184 +        CX_TEST_ASSERT(a.data == 2);
   3.185 +        CX_TEST_ASSERT(b.data == 2);
   3.186 +        CX_TEST_ASSERT(c.data == 2);
   3.187 +        CX_TEST_ASSERT(aa.data == 2);
   3.188 +        CX_TEST_ASSERT(ab.data == 2);
   3.189 +        CX_TEST_ASSERT(ba.data == 2);
   3.190 +        CX_TEST_ASSERT(ca.data == 0);
   3.191 +        CX_TEST_ASSERT(cb.data == 0);
   3.192 +        CX_TEST_ASSERT(cc.data == 0);
   3.193 +        CX_TEST_ASSERT(cba.data == 0);
   3.194 +    }
   3.195 +}
   3.196 +
   3.197  CxTestSuite *cx_test_suite_tree_low_level(void) {
   3.198      CxTestSuite *suite = cx_test_suite_new("tree (low level)");
   3.199  
   3.200 @@ -660,6 +850,9 @@
   3.201      cx_test_register(suite, test_tree_visitor);
   3.202      cx_test_register(suite, test_tree_visitor_no_children);
   3.203      cx_test_register(suite, test_tree_visitor_no_branching);
   3.204 +    cx_test_register(suite, test_tree_visitor_continue);
   3.205 +    cx_test_register(suite, test_tree_iterator_continue);
   3.206 +    cx_test_register(suite, test_tree_iterator_continue_with_exit);
   3.207  
   3.208      return suite;
   3.209  }