# HG changeset patch # User Mike Becker # Date 1708259922 -3600 # Node ID 5c926801f052ce849b4fd5fdbff00e3a1083c62b # Parent 97df2e4c68fbb1de5e6ea686f007b28fc156e554 vastly simplify tree iterators and add test for creating them relates to #371 diff -r 97df2e4c68fb -r 5c926801f052 src/Makefile --- 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 $< diff -r 97df2e4c68fb -r 5c926801f052 src/cx/tree.h --- 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 ); diff -r 97df2e4c68fb -r 5c926801f052 src/tree.c --- 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; diff -r 97df2e4c68fb -r 5c926801f052 tests/Makefile --- 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 $< diff -r 97df2e4c68fb -r 5c926801f052 tests/test_tree.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; }