Mercurial > hg > ucx / changeset

     1.1 --- a/src/Makefile	Sun Feb 18 13:16:38 2024 +0100
     1.2 +++ b/src/Makefile	Sun Feb 18 13:38:42 2024 +0100
     1.3 @@ -124,7 +124,8 @@
     1.4  	@echo "Compiling $<"
     1.5  	$(CC) -o $@ $(CFLAGS) -c $<
     1.6  
     1.7 -$(build_dir)/tree$(OBJ_EXT): tree.c cx/tree.h cx/common.h
     1.8 +$(build_dir)/tree$(OBJ_EXT): tree.c cx/tree.h cx/common.h cx/iterator.h \
     1.9 + cx/array_list.h cx/list.h cx/collection.h cx/allocator.h
    1.10  	@echo "Compiling $<"
    1.11  	$(CC) -o $@ $(CFLAGS) -c $<
    1.12  

     2.1 --- a/src/cx/tree.h	Sun Feb 18 13:16:38 2024 +0100
     2.2 +++ b/src/cx/tree.h	Sun Feb 18 13:38:42 2024 +0100
     2.3 @@ -45,28 +45,6 @@
     2.4  #endif
     2.5  
     2.6  /**
     2.7 - * When entering a node.
     2.8 - *
     2.9 - * When this is the first sibling, source is the parent, otherwise it is the previous child.
    2.10 - */
    2.11 -#define CX_TREE_ITERATOR_ENTER      0x1
    2.12 -/**
    2.13 - * When advancing to the next child.
    2.14 - *
    2.15 - * The visited node is the next child and the source is the previous child.
    2.16 - * This pass is triggered after exiting the previous child and before entering the next child.
    2.17 - */
    2.18 -#define CX_TREE_ITERATOR_NEXT_CHILD 0x2
    2.19 -/**
    2.20 - * When exiting the node.
    2.21 - *
    2.22 - * The visited node is the node being exited and source is the previously entered node
    2.23 - * (usually the last child of the exited node, unless it has no children, in which case it is the node itself).
    2.24 - * When advancing to the next child in a list of siblings, the previous child is exited, first.
    2.25 - */
    2.26 -#define CX_TREE_ITERATOR_EXIT       0x4
    2.27 -
    2.28 -/**
    2.29   * Tree iterator.
    2.30   *
    2.31   * This iterator is not position-aware in a strict sense, as it does not assume a particular order of elements in the
    2.32 @@ -74,9 +52,8 @@
    2.33   * Each node, regardless of the number of passes, is counted only once.
    2.34   *
    2.35   * @note Objects that are pointed to by an iterator are mutable through that iterator. However, if the
    2.36 - * iterator is based on a collection and the underlying collection is mutated by other means than this iterator
    2.37 - * (e.g. elements added or removed), the iterator becomes invalid (regardless of what cxIteratorValid() returns)
    2.38 - * and MUST be re-obtained from the collection.
    2.39 + * underlying data structure is mutated by other means than this iterator (e.g. elements added or removed),
    2.40 + * the iterator becomes invalid (regardless of what cxIteratorValid() returns).
    2.41   *
    2.42   * @see CxIterator
    2.43   */
    2.44 @@ -86,20 +63,14 @@
    2.45       */
    2.46      struct cx_iterator_base_s base;
    2.47      /**
    2.48 -     * The passes that are requested by this iterator.
    2.49 -     * A combination of the flags #CX_TREE_ITERATOR_ENTER, #CX_TREE_ITERATOR_NEXT_CHILD, #CX_TREE_ITERATOR_EXIT.
    2.50 -     *
    2.51 -     * Changing the value after beginning the iteration is unspecified.
    2.52 +     * Set to true, when the iterator shall visit a node again
    2.53 +     * when all it's children have been processed.
    2.54       */
    2.55 -    uint8_t requested_passes;
    2.56 +    bool visit_on_exit;
    2.57      /**
    2.58 -     * The current pass.
    2.59 -     *
    2.60 -     * @see CX_TREE_ITERATOR_ENTER
    2.61 -     * @see CX_TREE_ITERATOR_NEXT_CHILD
    2.62 -     * @see CX_TREE_ITERATOR_EXIT
    2.63 +     * True, if this iterator is currently leaving the node.
    2.64       */
    2.65 -    uint8_t current_pass;
    2.66 +    bool exiting;
    2.67      /**
    2.68       * Offset in the node struct for the children linked list.
    2.69       */
    2.70 @@ -119,14 +90,6 @@
    2.71       */
    2.72      void *node;
    2.73      /**
    2.74 -     * The node where we came from.
    2.75 -     *
    2.76 -     * - When entering the root node, this is \c NULL.
    2.77 -     * - When entering another node, this is the node's parent.
    2.78 -     * - When advancing to the next child, this is the previous child.
    2.79 -     */
    2.80 -    void *source;
    2.81 -    /**
    2.82       * Internal stack.
    2.83       * Will be automatically freed once the iterator becomes invalid.
    2.84       *
    2.85 @@ -138,10 +101,16 @@
    2.86       * Internal capacity of the stack.
    2.87       */
    2.88      size_t stack_capacity;
    2.89 -    /**
    2.90 -     * Current depth.
    2.91 -     */
    2.92 -    size_t depth;
    2.93 +    union {
    2.94 +        /**
    2.95 +         * Internal stack size.
    2.96 +         */
    2.97 +        size_t stack_size;
    2.98 +        /**
    2.99 +         * The current depth in the tree.
   2.100 +         */
   2.101 +        size_t depth;
   2.102 +    };
   2.103  } CxTreeIterator;
   2.104  
   2.105  /**
   2.106 @@ -261,17 +230,6 @@
   2.107  /**
   2.108   * Creates an iterator for a tree with the specified root node.
   2.109   *
   2.110 - * The \p passes argument is supposed to be a combination of the flags
   2.111 - * #CX_TREE_ITERATOR_ENTER, #CX_TREE_ITERATOR_NEXT_CHILD, and #CX_TREE_ITERATOR_EXIT.
   2.112 - * Alternatively, the integer 1 is equivalent to just specifying #CX_TREE_ITERATOR_ENTER
   2.113 - * which will cause the iterator to pass every node only once (when entering the node).
   2.114 - *
   2.115 - * When #CX_TREE_ITERATOR_EXIT is set, the iterator will visit a parent node again,
   2.116 - * when \em every of it's children has been visited (including the case when the node does not have any children).
   2.117 - *
   2.118 - * When #CX_TREE_ITERATOR_NEXT_CHILD is set, the iterator will visit a parent node again,
   2.119 - * when advancing from one child to the next.
   2.120 - *
   2.121   * @note A tree iterator needs to maintain a stack of visited nodes, which is allocated using stdlib malloc().
   2.122   * When the iterator becomes invalid, this memory is automatically released. However, if you wish to cancel the
   2.123   * iteration before the iterator becomes invalid by itself, you MUST call cxTreeIteratorDispose() manually to release
   2.124 @@ -280,7 +238,7 @@
   2.125   * @remark At the moment, the returned iterator does not support cxIteratorFlagRemoval().
   2.126   *
   2.127   * @param root the root node
   2.128 - * @param passes the passes this iterator shall perform
   2.129 + * @param visit_on_exit set to true, when the iterator shall visit a node again after processing all children
   2.130   * @param loc_children offset in the node struct for the children linked list
   2.131   * @param loc_next offset in the node struct for the next pointer
   2.132   * @return the new tree iterator
   2.133 @@ -289,7 +247,7 @@
   2.134  __attribute__((__nonnull__))
   2.135  CxTreeIterator cx_tree_iterator(
   2.136          void *root,
   2.137 -        int passes,
   2.138 +        bool visit_on_exit,
   2.139          ptrdiff_t loc_children,
   2.140          ptrdiff_t loc_next
   2.141  );

     3.1 --- a/src/tree.c	Sun Feb 18 13:16:38 2024 +0100
     3.2 +++ b/src/tree.c	Sun Feb 18 13:38:42 2024 +0100
     3.3 @@ -109,17 +109,14 @@
     3.4      }
     3.5  
     3.6      // create a working stack
     3.7 -    size_t work_cap = 32;
     3.8 -    size_t work_size = 0;
     3.9 -    void const **work = malloc(sizeof(void*) * work_cap);
    3.10 -    #define work_add(node) cx_array_add(&work, &work_size, &work_cap, \
    3.11 -        sizeof(void*), &(node), cx_array_default_reallocator)
    3.12 +    cx_array_declare(void const*, work);
    3.13 +    cx_array_initialize(work, 32);
    3.14  
    3.15      // add the children of root to the working stack
    3.16      {
    3.17          void *c = tree_children(root);
    3.18          while (c != NULL) {
    3.19 -            work_add(c);
    3.20 +            cx_array_simple_add(work, c);
    3.21              c = tree_next(c);
    3.22          }
    3.23      }
    3.24 @@ -146,7 +143,7 @@
    3.25              // if children might contain the data, add them to the stack
    3.26              void *c = tree_children(node);
    3.27              while (c != NULL) {
    3.28 -                work_add(c);
    3.29 +                cx_array_simple_add(work, c);
    3.30                  c = tree_next(c);
    3.31              }
    3.32  
    3.33 @@ -165,7 +162,6 @@
    3.34      }
    3.35  
    3.36      // free the working queue and return
    3.37 -    #undef workq_add
    3.38      free(work);
    3.39      return ret;
    3.40  }
    3.41 @@ -180,14 +176,6 @@
    3.42      return iter->node;
    3.43  }
    3.44  
    3.45 -static void cx_tree_iter_stack_add(
    3.46 -        struct cx_tree_iterator_s *iter,
    3.47 -        void *node
    3.48 -) {
    3.49 -    cx_array_add(&iter->stack, &iter->depth, &iter->stack_capacity,
    3.50 -        sizeof(void*), &node, cx_array_default_reallocator);
    3.51 -}
    3.52 -
    3.53  static void cx_tree_iter_next(void *it) {
    3.54      struct cx_tree_iterator_s *iter = it;
    3.55      // TODO: support mutating iterator
    3.56 @@ -195,77 +183,28 @@
    3.57      // TODO: implement
    3.58  }
    3.59  
    3.60 -
    3.61  CxTreeIterator cx_tree_iterator(
    3.62          void *root,
    3.63 -        int passes,
    3.64 +        bool visit_on_exit,
    3.65          ptrdiff_t loc_children,
    3.66          ptrdiff_t loc_next
    3.67  ) {
    3.68      CxTreeIterator iter;
    3.69      iter.loc_children = loc_children;
    3.70      iter.loc_next = loc_next;
    3.71 -    iter.requested_passes = passes;
    3.72 -
    3.73 -    // invalidate iterator immediately when passes is invalid
    3.74 -    if ((passes & (CX_TREE_ITERATOR_ENTER |
    3.75 -                   CX_TREE_ITERATOR_NEXT_CHILD |
    3.76 -                   CX_TREE_ITERATOR_EXIT)) == 0) {
    3.77 -        iter.stack = NULL;
    3.78 -        iter.node = NULL;
    3.79 -        return iter;
    3.80 -    }
    3.81 +    iter.visit_on_exit = visit_on_exit;
    3.82  
    3.83      // allocate stack
    3.84      iter.stack_capacity = 16;
    3.85      iter.stack = malloc(sizeof(void *) * 16);
    3.86      iter.depth = 0;
    3.87  
    3.88 -    // determine start
    3.89 -    if ((passes & CX_TREE_ITERATOR_ENTER) == 0) {
    3.90 -        // we have to skip the first "entering" passes
    3.91 -        void *s = NULL;
    3.92 -        void *n = root;
    3.93 -        iter.counter = 0;
    3.94 -        do {
    3.95 -            iter.counter++;
    3.96 -            iter.source = s;
    3.97 -            iter.node = n;
    3.98 -            cx_tree_iter_stack_add(&iter, n);
    3.99 -            s = n;
   3.100 -            n = tree_children(n);
   3.101 -        } while (n != NULL);
   3.102 -        // found a leaf node s (might be root itself if it has no children)
   3.103 -
   3.104 -        // check if there is a sibling
   3.105 -        n = tree_next(s);
   3.106 -
   3.107 -        if (n == NULL) {
   3.108 -            // no sibling found, exit back to parent node
   3.109 -            // TODO: implement
   3.110 -        } else {
   3.111 -            // there is a sibling
   3.112 -            if ((passes & CX_TREE_ITERATOR_EXIT) == 0) {
   3.113 -                // no exit requested, conclude that only next_child is requested
   3.114 -                iter.source = s;
   3.115 -                iter.node = n;
   3.116 -                iter.counter++;
   3.117 -                iter.current_pass = CX_TREE_ITERATOR_NEXT_CHILD;
   3.118 -            } else {
   3.119 -                // exit requested, so we have found our first pass
   3.120 -                // iter.node and iter.source are still correct
   3.121 -                iter.current_pass = CX_TREE_ITERATOR_EXIT;
   3.122 -            }
   3.123 -        }
   3.124 -    } else {
   3.125 -        // enter passes are requested, we can start by entering the root node
   3.126 -        iter.source = NULL;
   3.127 -        iter.node = root;
   3.128 -        iter.current_pass = CX_TREE_ITERATOR_ENTER;
   3.129 -        iter.counter = 1;
   3.130 -        iter.depth = 1;
   3.131 -        iter.stack[0] = root;
   3.132 -    }
   3.133 +    // visit the root node
   3.134 +    iter.node = root;
   3.135 +    iter.counter = 1;
   3.136 +    iter.depth = 1;
   3.137 +    iter.stack[0] = root;
   3.138 +    iter.exiting = false;
   3.139  
   3.140      // assign base iterator functions
   3.141      iter.base.mutating = false;

     4.1 --- a/tests/Makefile	Sun Feb 18 13:16:38 2024 +0100
     4.2 +++ b/tests/Makefile	Sun Feb 18 13:38:42 2024 +0100
     4.3 @@ -105,7 +105,7 @@
     4.4  	$(CC) -o $@ $(CFLAGS) -c $<
     4.5  
     4.6  $(TEST_DIR)/test_tree$(OBJ_EXT): test_tree.c ../src/cx/tree.h \
     4.7 - ../src/cx/common.h ../src/cx/test.h
     4.8 + ../src/cx/common.h ../src/cx/iterator.h ../src/cx/test.h
     4.9  	@echo "Compiling $<"
    4.10  	$(CC) -o $@ $(CFLAGS) -c $<
    4.11  

     5.1 --- a/tests/test_tree.c	Sun Feb 18 13:16:38 2024 +0100
     5.2 +++ b/tests/test_tree.c	Sun Feb 18 13:38:42 2024 +0100
     5.3 @@ -250,6 +250,25 @@
     5.4      }
     5.5  }
     5.6  
     5.7 +CX_TEST(test_tree_iterator_create) {
     5.8 +    tree_node root;
     5.9 +    CX_TEST_DO {
    5.10 +        CxTreeIterator iter = cx_tree_iterator(&root, false, tree_child_list);
    5.11 +        CX_TEST_ASSERT(!iter.visit_on_exit);
    5.12 +        CX_TEST_ASSERT(!iter.exiting);
    5.13 +        CX_TEST_ASSERT(iter.counter == 1);
    5.14 +        CX_TEST_ASSERT(iter.node == &root);
    5.15 +        CX_TEST_ASSERT(!iter.base.mutating);
    5.16 +        CX_TEST_ASSERT(!iter.base.remove);
    5.17 +        CX_TEST_ASSERT(iter.stack != NULL);
    5.18 +        CX_TEST_ASSERT(iter.stack_capacity > 0);
    5.19 +        CX_TEST_ASSERT(iter.stack_size == 1);
    5.20 +        CX_TEST_ASSERT(iter.depth == 1);
    5.21 +        CX_TEST_ASSERT(iter.loc_next == offsetof(tree_node, next));
    5.22 +        CX_TEST_ASSERT(iter.loc_children == offsetof(tree_node, children));
    5.23 +    }
    5.24 +}
    5.25 +
    5.26  CxTestSuite *cx_test_suite_tree_low_level(void) {
    5.27      CxTestSuite *suite = cx_test_suite_new("tree (low level)");
    5.28  
    5.29 @@ -258,6 +277,7 @@
    5.30      cx_test_register(suite, test_tree_link_move_to_other_parent);
    5.31      cx_test_register(suite, test_tree_unlink);
    5.32      cx_test_register(suite, test_tree_search);
    5.33 +    cx_test_register(suite, test_tree_iterator_create);
    5.34  
    5.35      return suite;
    5.36  }