Mercurial > hg > ucx / changeset

     1.1 --- a/src/cx/tree.h	Thu Mar 14 22:07:19 2024 +0100
     1.2 +++ b/src/cx/tree.h	Wed Mar 20 23:31:41 2024 +0100
     1.3 @@ -45,7 +45,7 @@
     1.4  #endif
     1.5  
     1.6  /**
     1.7 - * Tree iterator.
     1.8 + * A depth-first tree iterator.
     1.9   *
    1.10   * This iterator is not position-aware in a strict sense, as it does not assume a particular order of elements in the
    1.11   * tree. However, the iterator keeps track of the number of nodes it has passed in a counter variable.
    1.12 @@ -74,11 +74,11 @@
    1.13      /**
    1.14       * Offset in the node struct for the children linked list.
    1.15       */
    1.16 -    off_t loc_children;
    1.17 +    ptrdiff_t loc_children;
    1.18      /**
    1.19       * Offset in the node struct for the next pointer.
    1.20       */
    1.21 -    off_t loc_next;
    1.22 +    ptrdiff_t loc_next;
    1.23      /**
    1.24       * The total number of distinct nodes that have been passed so far.
    1.25       */
    1.26 @@ -119,19 +119,105 @@
    1.27  } CxTreeIterator;
    1.28  
    1.29  /**
    1.30 + * An element in a visitor queue.
    1.31 + */
    1.32 +struct cx_tree_visitor_queue_s {
    1.33 +    /**
    1.34 +     * The tree node to visit.
    1.35 +     */
    1.36 +    void *node;
    1.37 +    /**
    1.38 +     * The depth of the node.
    1.39 +     */
    1.40 +    size_t depth;
    1.41 +    /**
    1.42 +     * The next element in the queue or \c NULL.
    1.43 +     */
    1.44 +    struct cx_tree_visitor_queue_s *next;
    1.45 +};
    1.46 +
    1.47 +/**
    1.48 + * A breadth-first tree iterator.
    1.49 + *
    1.50 + * This iterator needs to maintain a visitor queue that will be automatically freed once the iterator becomes invalid.
    1.51 + * If you want to discard the iterator before, you MUST manually call cxTreeVisitorDispose().
    1.52 + *
    1.53 + * This iterator is not position-aware in a strict sense, as it does not assume a particular order of elements in the
    1.54 + * tree. However, the iterator keeps track of the number of nodes it has passed in a counter variable.
    1.55 + * Each node, regardless of the number of passes, is counted only once.
    1.56 + *
    1.57 + * @note Objects that are pointed to by an iterator are mutable through that iterator. However, if the
    1.58 + * underlying data structure is mutated by other means than this iterator (e.g. elements added or removed),
    1.59 + * the iterator becomes invalid (regardless of what cxIteratorValid() returns).
    1.60 + *
    1.61 + * @see CxIterator
    1.62 + */
    1.63 +typedef struct cx_tree_visitor_s {
    1.64 +    /**
    1.65 +     * The base properties of this iterator.
    1.66 +     */
    1.67 +    struct cx_iterator_base_s base;
    1.68 +    /**
    1.69 +     * Offset in the node struct for the children linked list.
    1.70 +     */
    1.71 +    ptrdiff_t loc_children;
    1.72 +    /**
    1.73 +     * Offset in the node struct for the next pointer.
    1.74 +     */
    1.75 +    ptrdiff_t loc_next;
    1.76 +    /**
    1.77 +     * The total number of distinct nodes that have been passed so far.
    1.78 +     */
    1.79 +    size_t counter;
    1.80 +    /**
    1.81 +     * The currently observed node.
    1.82 +     *
    1.83 +     * This is the same what cxIteratorCurrent() would return.
    1.84 +     */
    1.85 +    void *node;
    1.86 +    /**
    1.87 +     * The current depth in the tree.
    1.88 +     */
    1.89 +    size_t depth;
    1.90 +    /**
    1.91 +     * The next element in the visitor queue.
    1.92 +     */
    1.93 +    struct cx_tree_visitor_queue_s *queue_next;
    1.94 +    /**
    1.95 +     * The last element in the visitor queue.
    1.96 +     */
    1.97 +    struct cx_tree_visitor_queue_s *queue_last;
    1.98 +} CxTreeVisitor;
    1.99 +
   1.100 +/**
   1.101   * Releases internal memory of the given tree iterator.
   1.102   * @param iter the iterator
   1.103   */
   1.104 + __attribute__((__nonnull__))
   1.105  static inline void cxTreeIteratorDispose(CxTreeIterator *iter) {
   1.106      free(iter->stack);
   1.107      iter->stack = NULL;
   1.108  }
   1.109  
   1.110  /**
   1.111 + * Releases internal memory of the given tree visitor.
   1.112 + * @param visitor the visitor
   1.113 + */
   1.114 +__attribute__((__nonnull__))
   1.115 +static inline void cxTreeVisitorDispose(CxTreeVisitor *visitor) {
   1.116 +    struct cx_tree_visitor_queue_s *q = visitor->queue_next;
   1.117 +    while (q != NULL) {
   1.118 +        struct cx_tree_visitor_queue_s *next = q->next;
   1.119 +        free(q);
   1.120 +        q = next;
   1.121 +    }
   1.122 +}
   1.123 +
   1.124 +/**
   1.125   * Links a node to a (new) parent.
   1.126   *
   1.127   * If the node has already a parent, it is unlinked, first.
   1.128 - * If the parent has children already, the node is prepended to the list
   1.129 + * If the parent has children already, the node is \em prepended to the list
   1.130   * of all currently existing children.
   1.131   *
   1.132   * @param parent the parent node
   1.133 @@ -234,14 +320,14 @@
   1.134  );
   1.135  
   1.136  /**
   1.137 - * Creates an iterator for a tree with the specified root node.
   1.138 + * Creates a depth-first iterator for a tree with the specified root node.
   1.139   *
   1.140   * @note A tree iterator needs to maintain a stack of visited nodes, which is allocated using stdlib malloc().
   1.141   * When the iterator becomes invalid, this memory is automatically released. However, if you wish to cancel the
   1.142   * iteration before the iterator becomes invalid by itself, you MUST call cxTreeIteratorDispose() manually to release
   1.143   * the memory.
   1.144   *
   1.145 - * @remark At the moment, the returned iterator does not support cxIteratorFlagRemoval().
   1.146 + * @remark The returned iterator does not support cxIteratorFlagRemoval().
   1.147   *
   1.148   * @param root the root node
   1.149   * @param visit_on_exit set to true, when the iterator shall visit a node again after processing all children
   1.150 @@ -258,6 +344,29 @@
   1.151          ptrdiff_t loc_next
   1.152  );
   1.153  
   1.154 +/**
   1.155 + * Creates a breadth-first iterator for a tree with the specified root node.
   1.156 + *
   1.157 + * @note A tree visitor needs to maintain a queue of to be visited nodes, which is allocated using stdlib malloc().
   1.158 + * When the visitor becomes invalid, this memory is automatically released. However, if you wish to cancel the
   1.159 + * iteration before the visitor becomes invalid by itself, you MUST call cxTreeVisitorDispose() manually to release
   1.160 + * the memory.
   1.161 + *
   1.162 + * @remark The returned iterator does not support cxIteratorFlagRemoval().
   1.163 + *
   1.164 + * @param root the root node
   1.165 + * @param loc_children offset in the node struct for the children linked list
   1.166 + * @param loc_next offset in the node struct for the next pointer
   1.167 + * @return the new tree visitor
   1.168 + * @see cxTreeVisitorDispose()
   1.169 + */
   1.170 +__attribute__((__nonnull__))
   1.171 +CxTreeVisitor cx_tree_visitor(
   1.172 +        void *root,
   1.173 +        ptrdiff_t loc_children,
   1.174 +        ptrdiff_t loc_next
   1.175 +);
   1.176 +
   1.177  #ifdef __cplusplus
   1.178  } // extern "C"
   1.179  #endif

     2.1 --- a/src/tree.c	Thu Mar 14 22:07:19 2024 +0100
     2.2 +++ b/src/tree.c	Wed Mar 20 23:31:41 2024 +0100
     2.3 @@ -178,10 +178,8 @@
     2.4  
     2.5  static void cx_tree_iter_next(void *it) {
     2.6      struct cx_tree_iterator_s *iter = it;
     2.7 -    off_t const loc_next = iter->loc_next;
     2.8 -    off_t const loc_children = iter->loc_children;
     2.9 -
    2.10 -    // TODO: support mutating iterator
    2.11 +    ptrdiff_t const loc_next = iter->loc_next;
    2.12 +    ptrdiff_t const loc_children = iter->loc_children;
    2.13  
    2.14      void *children;
    2.15  
    2.16 @@ -280,3 +278,116 @@
    2.17  
    2.18      return iter;
    2.19  }
    2.20 +
    2.21 +static bool cx_tree_visitor_valid(void const *it) {
    2.22 +    struct cx_tree_visitor_s const *iter = it;
    2.23 +    return iter->node != NULL;
    2.24 +}
    2.25 +
    2.26 +static void *cx_tree_visitor_current(void const *it) {
    2.27 +    struct cx_tree_visitor_s const *iter = it;
    2.28 +    return iter->node;
    2.29 +}
    2.30 +
    2.31 +__attribute__((__nonnull__))
    2.32 +static void cx_tree_visitor_enqueue_siblings(
    2.33 +        struct cx_tree_visitor_s *iter, void *node, ptrdiff_t loc_next) {
    2.34 +    node = tree_next(node);
    2.35 +    while (node != NULL) {
    2.36 +        struct cx_tree_visitor_queue_s *q;
    2.37 +        q = malloc(sizeof(struct cx_tree_visitor_queue_s));
    2.38 +        q->depth = iter->queue_last->depth;
    2.39 +        q->node = node;
    2.40 +        iter->queue_last->next = q;
    2.41 +        iter->queue_last = q;
    2.42 +        node = tree_next(node);
    2.43 +    }
    2.44 +    iter->queue_last->next = NULL;
    2.45 +}
    2.46 +
    2.47 +static void cx_tree_visitor_next(void *it) {
    2.48 +    struct cx_tree_visitor_s *iter = it;
    2.49 +    ptrdiff_t const loc_next = iter->loc_next;
    2.50 +    ptrdiff_t const loc_children = iter->loc_children;
    2.51 +
    2.52 +    // check if there is a next node
    2.53 +    if (iter->queue_next == NULL) {
    2.54 +        iter->node = NULL;
    2.55 +        return;
    2.56 +    }
    2.57 +
    2.58 +    // dequeue the next node
    2.59 +    iter->node = iter->queue_next->node;
    2.60 +    iter->depth = iter->queue_next->depth;
    2.61 +    {
    2.62 +        struct cx_tree_visitor_queue_s *q = iter->queue_next;
    2.63 +        iter->queue_next = q->next;
    2.64 +        if (iter->queue_next == NULL) {
    2.65 +            assert(iter->queue_last == q);
    2.66 +            iter->queue_last = NULL;
    2.67 +        }
    2.68 +        free(q);
    2.69 +    }
    2.70 +
    2.71 +    // increment the node counter
    2.72 +    iter->counter++;
    2.73 +
    2.74 +    // add the children of the new node to the queue
    2.75 +    void *children = tree_children(iter->node);
    2.76 +    if (children != NULL) {
    2.77 +        struct cx_tree_visitor_queue_s *q;
    2.78 +        q = malloc(sizeof(struct cx_tree_visitor_queue_s));
    2.79 +        q->depth = iter->depth + 1;
    2.80 +        q->node = children;
    2.81 +        if (iter->queue_last == NULL) {
    2.82 +            assert(iter->queue_next == NULL);
    2.83 +            iter->queue_next = q;
    2.84 +        } else {
    2.85 +            iter->queue_last->next = q;
    2.86 +        }
    2.87 +        iter->queue_last = q;
    2.88 +        cx_tree_visitor_enqueue_siblings(iter, children, loc_next);
    2.89 +    }
    2.90 +}
    2.91 +
    2.92 +CxTreeVisitor cx_tree_visitor(
    2.93 +        void *root,
    2.94 +        ptrdiff_t loc_children,
    2.95 +        ptrdiff_t loc_next
    2.96 +) {
    2.97 +    CxTreeVisitor iter;
    2.98 +    iter.loc_children = loc_children;
    2.99 +    iter.loc_next = loc_next;
   2.100 +
   2.101 +    // allocate stack
   2.102 +    iter.depth = 0;
   2.103 +
   2.104 +    // visit the root node
   2.105 +    iter.node = root;
   2.106 +    iter.counter = 1;
   2.107 +    iter.depth = 1;
   2.108 +
   2.109 +    // put all children of root into the queue
   2.110 +    void *children = tree_children(root);
   2.111 +    if (children == NULL) {
   2.112 +        iter.queue_next = NULL;
   2.113 +        iter.queue_last = NULL;
   2.114 +    } else {
   2.115 +        iter.queue_next = malloc(sizeof(struct cx_tree_visitor_queue_s));
   2.116 +        iter.queue_next->depth = 2;
   2.117 +        iter.queue_next->node = children;
   2.118 +        iter.queue_last = iter.queue_next;
   2.119 +        cx_tree_visitor_enqueue_siblings(&iter, children, loc_next);
   2.120 +    }
   2.121 +
   2.122 +    // assign base iterator functions
   2.123 +    iter.base.mutating = false;
   2.124 +    iter.base.remove = false;
   2.125 +    iter.base.current_impl = NULL;
   2.126 +    iter.base.valid = cx_tree_visitor_valid;
   2.127 +    iter.base.next = cx_tree_visitor_next;
   2.128 +    iter.base.current = cx_tree_visitor_current;
   2.129 +
   2.130 +    return iter;
   2.131 +}
   2.132 +

     3.1 --- a/tests/test_tree.c	Thu Mar 14 22:07:19 2024 +0100
     3.2 +++ b/tests/test_tree.c	Wed Mar 20 23:31:41 2024 +0100
     3.3 @@ -286,6 +286,14 @@
     3.4      tree_node cc = {0};
     3.5      tree_node cba = {0};
     3.6  
     3.7 +    tree_node* expected_order[] = {
     3.8 +            &root,
     3.9 +            &c, &cc,&cb, &cba,&ca,
    3.10 +            &b, &ba,
    3.11 +            &a, &ab, &aa,
    3.12 +    };
    3.13 +    tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong
    3.14 +
    3.15      cx_tree_link(&root, &a, tree_node_layout);
    3.16      cx_tree_link(&root, &b, tree_node_layout);
    3.17      cx_tree_link(&root, &c, tree_node_layout);
    3.18 @@ -302,6 +310,7 @@
    3.19          cx_foreach(tree_node*, node, iter) {
    3.20              CX_TEST_ASSERT(node->data == 0);
    3.21              node->data++;
    3.22 +            actual_order[chk] = node;
    3.23              chk++;
    3.24              CX_TEST_ASSERT(node == iter.node);
    3.25              CX_TEST_ASSERT(!iter.exiting);
    3.26 @@ -317,18 +326,11 @@
    3.27          }
    3.28          CX_TEST_ASSERT(iter.counter == 11);
    3.29          CX_TEST_ASSERT(chk == 11);
    3.30 +        for (unsigned i = 0 ; i < chk ; i++) {
    3.31 +            CX_TEST_ASSERT(actual_order[i] == expected_order[i]);
    3.32 +            CX_TEST_ASSERT(actual_order[i]->data == 1);
    3.33 +        }
    3.34          CX_TEST_ASSERT(iter.stack == NULL);
    3.35 -        CX_TEST_ASSERT(root.data == 1);
    3.36 -        CX_TEST_ASSERT(a.data == 1);
    3.37 -        CX_TEST_ASSERT(b.data == 1);
    3.38 -        CX_TEST_ASSERT(c.data == 1);
    3.39 -        CX_TEST_ASSERT(aa.data == 1);
    3.40 -        CX_TEST_ASSERT(ab.data == 1);
    3.41 -        CX_TEST_ASSERT(ba.data == 1);
    3.42 -        CX_TEST_ASSERT(ca.data == 1);
    3.43 -        CX_TEST_ASSERT(cb.data == 1);
    3.44 -        CX_TEST_ASSERT(cc.data == 1);
    3.45 -        CX_TEST_ASSERT(cba.data == 1);
    3.46      }
    3.47  }
    3.48  
    3.49 @@ -507,6 +509,120 @@
    3.50      cx_testing_allocator_destroy(&talloc);
    3.51  }
    3.52  
    3.53 +CX_TEST(test_tree_visitor) {
    3.54 +    tree_node root = {0};
    3.55 +    tree_node a = {0};
    3.56 +    tree_node b = {0};
    3.57 +    tree_node c = {0};
    3.58 +    tree_node aa = {0};
    3.59 +    tree_node ab = {0};
    3.60 +    tree_node ba = {0};
    3.61 +    tree_node ca = {0};
    3.62 +    tree_node cb = {0};
    3.63 +    tree_node cc = {0};
    3.64 +    tree_node cba = {0};
    3.65 +
    3.66 +    tree_node* expected_order[] = {
    3.67 +            &root,
    3.68 +            &c, &b, &a,
    3.69 +            &cc, &cb, &ca, &ba, &ab, &aa,
    3.70 +            &cba
    3.71 +    };
    3.72 +    tree_node* actual_order[16]; // reserve more space in case s.t. goes wrong
    3.73 +
    3.74 +    cx_tree_link(&root, &a, tree_node_layout);
    3.75 +    cx_tree_link(&root, &b, tree_node_layout);
    3.76 +    cx_tree_link(&root, &c, tree_node_layout);
    3.77 +    cx_tree_link(&a, &aa, tree_node_layout);
    3.78 +    cx_tree_link(&a, &ab, tree_node_layout);
    3.79 +    cx_tree_link(&b, &ba, tree_node_layout);
    3.80 +    cx_tree_link(&c, &ca, tree_node_layout);
    3.81 +    cx_tree_link(&c, &cb, tree_node_layout);
    3.82 +    cx_tree_link(&c, &cc, tree_node_layout);
    3.83 +    cx_tree_link(&cb, &cba, tree_node_layout);
    3.84 +    CX_TEST_DO {
    3.85 +        CxTreeVisitor iter = cx_tree_visitor(&root, tree_child_list);
    3.86 +        unsigned chk = 0;
    3.87 +        cx_foreach(tree_node*, node, iter) {
    3.88 +            CX_TEST_ASSERT(node->data == 0);
    3.89 +            node->data++;
    3.90 +            actual_order[chk] = node;
    3.91 +            chk++;
    3.92 +            CX_TEST_ASSERT(node == iter.node);
    3.93 +            if (node == &root) {
    3.94 +                CX_TEST_ASSERT(iter.depth == 1);
    3.95 +            } else if (node == &a || node == &b || node == &c) {
    3.96 +                CX_TEST_ASSERT(iter.depth == 2);
    3.97 +            } else if (node == &cba) {
    3.98 +                CX_TEST_ASSERT(iter.depth == 4);
    3.99 +            } else {
   3.100 +                CX_TEST_ASSERT(iter.depth == 3);
   3.101 +            }
   3.102 +        }
   3.103 +        CX_TEST_ASSERT(iter.counter == 11);
   3.104 +        CX_TEST_ASSERT(chk == 11);
   3.105 +        for (unsigned i = 0 ; i < chk ; i++) {
   3.106 +            CX_TEST_ASSERT(actual_order[i] == expected_order[i]);
   3.107 +            CX_TEST_ASSERT(actual_order[i]->data == 1);
   3.108 +        }
   3.109 +        CX_TEST_ASSERT(iter.queue_next == NULL);
   3.110 +        CX_TEST_ASSERT(iter.queue_last == NULL);
   3.111 +    }
   3.112 +}
   3.113 +
   3.114 +CX_TEST(test_tree_visitor_no_children) {
   3.115 +    tree_node root = {0};
   3.116 +
   3.117 +    CX_TEST_DO {
   3.118 +        CxTreeVisitor iter = cx_tree_visitor(&root, tree_child_list);
   3.119 +        unsigned chk = 0;
   3.120 +        cx_foreach(tree_node*, node, iter) {
   3.121 +            CX_TEST_ASSERT(node == iter.node);
   3.122 +            chk++;
   3.123 +        }
   3.124 +        CX_TEST_ASSERT(iter.counter == 1);
   3.125 +        CX_TEST_ASSERT(chk == 1);
   3.126 +        CX_TEST_ASSERT(iter.queue_next == NULL);
   3.127 +        CX_TEST_ASSERT(iter.queue_last == NULL);
   3.128 +    }
   3.129 +}
   3.130 +
   3.131 +CX_TEST(test_tree_visitor_no_branching) {
   3.132 +    tree_node root = {0};
   3.133 +    tree_node a = {0};
   3.134 +    tree_node b = {0};
   3.135 +    tree_node c = {0};
   3.136 +
   3.137 +    tree_node* expected_order[] = {
   3.138 +            &root, &a, &b, &c
   3.139 +    };
   3.140 +    tree_node* actual_order[4];
   3.141 +
   3.142 +    cx_tree_link(&root, &a, tree_node_layout);
   3.143 +    cx_tree_link(&a, &b, tree_node_layout);
   3.144 +    cx_tree_link(&b, &c, tree_node_layout);
   3.145 +
   3.146 +    CX_TEST_DO {
   3.147 +        CxTreeVisitor iter = cx_tree_visitor(&root, tree_child_list);
   3.148 +        unsigned chk = 0;
   3.149 +        cx_foreach(tree_node*, node, iter) {
   3.150 +            CX_TEST_ASSERT(node == iter.node);
   3.151 +            CX_TEST_ASSERT(node->data == 0);
   3.152 +            node->data++;
   3.153 +            actual_order[chk] = node;
   3.154 +            chk++;
   3.155 +        }
   3.156 +        CX_TEST_ASSERT(iter.counter == 4);
   3.157 +        CX_TEST_ASSERT(chk == 4);
   3.158 +        CX_TEST_ASSERT(iter.queue_next == NULL);
   3.159 +        CX_TEST_ASSERT(iter.queue_last == NULL);
   3.160 +        for (unsigned i = 0 ; i < chk ; i++) {
   3.161 +            CX_TEST_ASSERT(actual_order[i] == expected_order[i]);
   3.162 +            CX_TEST_ASSERT(actual_order[i]->data == 1);
   3.163 +        }
   3.164 +    }
   3.165 +}
   3.166 +
   3.167  CxTestSuite *cx_test_suite_tree_low_level(void) {
   3.168      CxTestSuite *suite = cx_test_suite_new("tree (low level)");
   3.169  
   3.170 @@ -520,6 +636,9 @@
   3.171      cx_test_register(suite, test_tree_iterator_basic_enter_and_exit);
   3.172      cx_test_register(suite, test_tree_iterator_xml);
   3.173      cx_test_register(suite, test_tree_iterator_free_nodes);
   3.174 +    cx_test_register(suite, test_tree_visitor);
   3.175 +    cx_test_register(suite, test_tree_visitor_no_children);
   3.176 +    cx_test_register(suite, test_tree_visitor_no_branching);
   3.177  
   3.178      return suite;
   3.179  }