Mercurial > hg > ucx / changeset

--- a/src/Makefile	Sun Feb 18 13:16:38 2024 +0100
+++ b/src/Makefile	Sun Feb 18 13:38:42 2024 +0100
@@ -124,7 +124,8 @@
 	@echo "Compiling $<"
 	$(CC) -o $@ $(CFLAGS) -c $<
 
-$(build_dir)/tree$(OBJ_EXT): tree.c cx/tree.h cx/common.h
+$(build_dir)/tree$(OBJ_EXT): tree.c cx/tree.h cx/common.h cx/iterator.h \
+ cx/array_list.h cx/list.h cx/collection.h cx/allocator.h
 	@echo "Compiling $<"
 	$(CC) -o $@ $(CFLAGS) -c $<
 

--- a/src/cx/tree.h	Sun Feb 18 13:16:38 2024 +0100
+++ b/src/cx/tree.h	Sun Feb 18 13:38:42 2024 +0100
@@ -45,28 +45,6 @@
 #endif
 
 /**
- * When entering a node.
- *
- * When this is the first sibling, source is the parent, otherwise it is the previous child.
- */
-#define CX_TREE_ITERATOR_ENTER      0x1
-/**
- * When advancing to the next child.
- *
- * The visited node is the next child and the source is the previous child.
- * This pass is triggered after exiting the previous child and before entering the next child.
- */
-#define CX_TREE_ITERATOR_NEXT_CHILD 0x2
-/**
- * When exiting the node.
- *
- * The visited node is the node being exited and source is the previously entered node
- * (usually the last child of the exited node, unless it has no children, in which case it is the node itself).
- * When advancing to the next child in a list of siblings, the previous child is exited, first.
- */
-#define CX_TREE_ITERATOR_EXIT       0x4
-
-/**
  * Tree iterator.
  *
  * This iterator is not position-aware in a strict sense, as it does not assume a particular order of elements in the
@@ -74,9 +52,8 @@
  * Each node, regardless of the number of passes, is counted only once.
  *
  * @note Objects that are pointed to by an iterator are mutable through that iterator. However, if the
- * iterator is based on a collection and the underlying collection is mutated by other means than this iterator
- * (e.g. elements added or removed), the iterator becomes invalid (regardless of what cxIteratorValid() returns)
- * and MUST be re-obtained from the collection.
+ * underlying data structure is mutated by other means than this iterator (e.g. elements added or removed),
+ * the iterator becomes invalid (regardless of what cxIteratorValid() returns).
  *
  * @see CxIterator
  */
@@ -86,20 +63,14 @@
      */
     struct cx_iterator_base_s base;
     /**
-     * The passes that are requested by this iterator.
-     * A combination of the flags #CX_TREE_ITERATOR_ENTER, #CX_TREE_ITERATOR_NEXT_CHILD, #CX_TREE_ITERATOR_EXIT.
-     *
-     * Changing the value after beginning the iteration is unspecified.
+     * Set to true, when the iterator shall visit a node again
+     * when all it's children have been processed.
      */
-    uint8_t requested_passes;
+    bool visit_on_exit;
     /**
-     * The current pass.
-     *
-     * @see CX_TREE_ITERATOR_ENTER
-     * @see CX_TREE_ITERATOR_NEXT_CHILD
-     * @see CX_TREE_ITERATOR_EXIT
+     * True, if this iterator is currently leaving the node.
      */
-    uint8_t current_pass;
+    bool exiting;
     /**
      * Offset in the node struct for the children linked list.
      */
@@ -119,14 +90,6 @@
      */
     void *node;
     /**
-     * The node where we came from.
-     *
-     * - When entering the root node, this is \c NULL.
-     * - When entering another node, this is the node's parent.
-     * - When advancing to the next child, this is the previous child.
-     */
-    void *source;
-    /**
      * Internal stack.
      * Will be automatically freed once the iterator becomes invalid.
      *
@@ -138,10 +101,16 @@
      * Internal capacity of the stack.
      */
     size_t stack_capacity;
-    /**
-     * Current depth.
-     */
-    size_t depth;
+    union {
+        /**
+         * Internal stack size.
+         */
+        size_t stack_size;
+        /**
+         * The current depth in the tree.
+         */
+        size_t depth;
+    };
 } CxTreeIterator;
 
 /**
@@ -261,17 +230,6 @@
 /**
  * Creates an iterator for a tree with the specified root node.
  *
- * The \p passes argument is supposed to be a combination of the flags
- * #CX_TREE_ITERATOR_ENTER, #CX_TREE_ITERATOR_NEXT_CHILD, and #CX_TREE_ITERATOR_EXIT.
- * Alternatively, the integer 1 is equivalent to just specifying #CX_TREE_ITERATOR_ENTER
- * which will cause the iterator to pass every node only once (when entering the node).
- *
- * When #CX_TREE_ITERATOR_EXIT is set, the iterator will visit a parent node again,
- * when \em every of it's children has been visited (including the case when the node does not have any children).
- *
- * When #CX_TREE_ITERATOR_NEXT_CHILD is set, the iterator will visit a parent node again,
- * when advancing from one child to the next.
- *
  * @note A tree iterator needs to maintain a stack of visited nodes, which is allocated using stdlib malloc().
  * When the iterator becomes invalid, this memory is automatically released. However, if you wish to cancel the
  * iteration before the iterator becomes invalid by itself, you MUST call cxTreeIteratorDispose() manually to release
@@ -280,7 +238,7 @@
  * @remark At the moment, the returned iterator does not support cxIteratorFlagRemoval().
  *
  * @param root the root node
- * @param passes the passes this iterator shall perform
+ * @param visit_on_exit set to true, when the iterator shall visit a node again after processing all children
  * @param loc_children offset in the node struct for the children linked list
  * @param loc_next offset in the node struct for the next pointer
  * @return the new tree iterator
@@ -289,7 +247,7 @@
 __attribute__((__nonnull__))
 CxTreeIterator cx_tree_iterator(
         void *root,
-        int passes,
+        bool visit_on_exit,
         ptrdiff_t loc_children,
         ptrdiff_t loc_next
 );

--- a/src/tree.c	Sun Feb 18 13:16:38 2024 +0100
+++ b/src/tree.c	Sun Feb 18 13:38:42 2024 +0100
@@ -109,17 +109,14 @@
     }
 
     // create a working stack
-    size_t work_cap = 32;
-    size_t work_size = 0;
-    void const **work = malloc(sizeof(void*) * work_cap);
-    #define work_add(node) cx_array_add(&work, &work_size, &work_cap, \
-        sizeof(void*), &(node), cx_array_default_reallocator)
+    cx_array_declare(void const*, work);
+    cx_array_initialize(work, 32);
 
     // add the children of root to the working stack
     {
         void *c = tree_children(root);
         while (c != NULL) {
-            work_add(c);
+            cx_array_simple_add(work, c);
             c = tree_next(c);
         }
     }
@@ -146,7 +143,7 @@
             // if children might contain the data, add them to the stack
             void *c = tree_children(node);
             while (c != NULL) {
-                work_add(c);
+                cx_array_simple_add(work, c);
                 c = tree_next(c);
             }
 
@@ -165,7 +162,6 @@
     }
 
     // free the working queue and return
-    #undef workq_add
     free(work);
     return ret;
 }
@@ -180,14 +176,6 @@
     return iter->node;
 }
 
-static void cx_tree_iter_stack_add(
-        struct cx_tree_iterator_s *iter,
-        void *node
-) {
-    cx_array_add(&iter->stack, &iter->depth, &iter->stack_capacity,
-        sizeof(void*), &node, cx_array_default_reallocator);
-}
-
 static void cx_tree_iter_next(void *it) {
     struct cx_tree_iterator_s *iter = it;
     // TODO: support mutating iterator
@@ -195,77 +183,28 @@
     // TODO: implement
 }
 
-
 CxTreeIterator cx_tree_iterator(
         void *root,
-        int passes,
+        bool visit_on_exit,
         ptrdiff_t loc_children,
         ptrdiff_t loc_next
 ) {
     CxTreeIterator iter;
     iter.loc_children = loc_children;
     iter.loc_next = loc_next;
-    iter.requested_passes = passes;
-
-    // invalidate iterator immediately when passes is invalid
-    if ((passes & (CX_TREE_ITERATOR_ENTER |
-                   CX_TREE_ITERATOR_NEXT_CHILD |
-                   CX_TREE_ITERATOR_EXIT)) == 0) {
-        iter.stack = NULL;
-        iter.node = NULL;
-        return iter;
-    }
+    iter.visit_on_exit = visit_on_exit;
 
     // allocate stack
     iter.stack_capacity = 16;
     iter.stack = malloc(sizeof(void *) * 16);
     iter.depth = 0;
 
-    // determine start
-    if ((passes & CX_TREE_ITERATOR_ENTER) == 0) {
-        // we have to skip the first "entering" passes
-        void *s = NULL;
-        void *n = root;
-        iter.counter = 0;
-        do {
-            iter.counter++;
-            iter.source = s;
-            iter.node = n;
-            cx_tree_iter_stack_add(&iter, n);
-            s = n;
-            n = tree_children(n);
-        } while (n != NULL);
-        // found a leaf node s (might be root itself if it has no children)
-
-        // check if there is a sibling
-        n = tree_next(s);
-
-        if (n == NULL) {
-            // no sibling found, exit back to parent node
-            // TODO: implement
-        } else {
-            // there is a sibling
-            if ((passes & CX_TREE_ITERATOR_EXIT) == 0) {
-                // no exit requested, conclude that only next_child is requested
-                iter.source = s;
-                iter.node = n;
-                iter.counter++;
-                iter.current_pass = CX_TREE_ITERATOR_NEXT_CHILD;
-            } else {
-                // exit requested, so we have found our first pass
-                // iter.node and iter.source are still correct
-                iter.current_pass = CX_TREE_ITERATOR_EXIT;
-            }
-        }
-    } else {
-        // enter passes are requested, we can start by entering the root node
-        iter.source = NULL;
-        iter.node = root;
-        iter.current_pass = CX_TREE_ITERATOR_ENTER;
-        iter.counter = 1;
-        iter.depth = 1;
-        iter.stack[0] = root;
-    }
+    // visit the root node
+    iter.node = root;
+    iter.counter = 1;
+    iter.depth = 1;
+    iter.stack[0] = root;
+    iter.exiting = false;
 
     // assign base iterator functions
     iter.base.mutating = false;

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

--- a/tests/test_tree.c	Sun Feb 18 13:16:38 2024 +0100
+++ b/tests/test_tree.c	Sun Feb 18 13:38:42 2024 +0100
@@ -250,6 +250,25 @@
     }
 }
 
+CX_TEST(test_tree_iterator_create) {
+    tree_node root;
+    CX_TEST_DO {
+        CxTreeIterator iter = cx_tree_iterator(&root, false, tree_child_list);
+        CX_TEST_ASSERT(!iter.visit_on_exit);
+        CX_TEST_ASSERT(!iter.exiting);
+        CX_TEST_ASSERT(iter.counter == 1);
+        CX_TEST_ASSERT(iter.node == &root);
+        CX_TEST_ASSERT(!iter.base.mutating);
+        CX_TEST_ASSERT(!iter.base.remove);
+        CX_TEST_ASSERT(iter.stack != NULL);
+        CX_TEST_ASSERT(iter.stack_capacity > 0);
+        CX_TEST_ASSERT(iter.stack_size == 1);
+        CX_TEST_ASSERT(iter.depth == 1);
+        CX_TEST_ASSERT(iter.loc_next == offsetof(tree_node, next));
+        CX_TEST_ASSERT(iter.loc_children == offsetof(tree_node, children));
+    }
+}
+
 CxTestSuite *cx_test_suite_tree_low_level(void) {
     CxTestSuite *suite = cx_test_suite_new("tree (low level)");
 
@@ -258,6 +277,7 @@
     cx_test_register(suite, test_tree_link_move_to_other_parent);
     cx_test_register(suite, test_tree_unlink);
     cx_test_register(suite, test_tree_search);
+    cx_test_register(suite, test_tree_iterator_create);
 
     return suite;
 }