Mercurial > hg > ucx / changeset

     1.1 --- a/src/cx/tree.h	Wed Feb 21 18:53:55 2024 +0100
     1.2 +++ b/src/cx/tree.h	Mon Feb 26 21:07:23 2024 +0100
     1.3 @@ -90,6 +90,11 @@
     1.4       */
     1.5      void *node;
     1.6      /**
     1.7 +     * Stores a copy of the next pointer of the visited node.
     1.8 +     * Allows freeing a node on exit without corrupting the iteration.
     1.9 +     */
    1.10 +    void *next;
    1.11 +    /**
    1.12       * Internal stack.
    1.13       * Will be automatically freed once the iterator becomes invalid.
    1.14       *

     2.1 --- a/src/tree.c	Wed Feb 21 18:53:55 2024 +0100
     2.2 +++ b/src/tree.c	Mon Feb 26 21:07:23 2024 +0100
     2.3 @@ -197,7 +197,12 @@
     2.4          void *next;
     2.5          cx_tree_iter_search_next:
     2.6          // check if there is a sibling
     2.7 -        next = tree_next(iter->node);
     2.8 +        if (iter->exiting) {
     2.9 +            next = iter->next;
    2.10 +        } else {
    2.11 +            next = tree_next(iter->node);
    2.12 +            iter->next = next;
    2.13 +        }
    2.14          if (next == NULL) {
    2.15              // no sibling, we are done with this node and exit
    2.16              if (iter->visit_on_exit && !iter->exiting) {
    2.17 @@ -208,7 +213,7 @@
    2.18                  if (iter->depth == 1) {
    2.19                      // there is no parent - we have iterated the entire tree
    2.20                      // invalidate the iterator and free the node stack
    2.21 -                    iter->node = NULL;
    2.22 +                    iter->node = iter->next = NULL;
    2.23                      iter->stack_capacity = iter->depth = 0;
    2.24                      free(iter->stack);
    2.25                      iter->stack = NULL;

     3.1 --- a/tests/test_tree.c	Wed Feb 21 18:53:55 2024 +0100
     3.2 +++ b/tests/test_tree.c	Mon Feb 26 21:07:23 2024 +0100
     3.3 @@ -30,6 +30,8 @@
     3.4  
     3.5  #include "cx/test.h"
     3.6  
     3.7 +#include "util_allocator.h"
     3.8 +
     3.9  typedef struct tree_node {
    3.10      struct tree_node *parent;
    3.11      struct tree_node *next;
    3.12 @@ -465,6 +467,46 @@
    3.13      free(actual);
    3.14  }
    3.15  
    3.16 +CX_TEST(test_tree_iterator_free_nodes) {
    3.17 +    CxTestingAllocator talloc;
    3.18 +    cx_testing_allocator_init(&talloc);
    3.19 +    CxAllocator *alloc = &talloc.base;
    3.20 +    CX_TEST_DO {
    3.21 +        tree_node *root = cxCalloc(alloc, 1, sizeof(tree_node));
    3.22 +        tree_node *a = cxCalloc(alloc, 1, sizeof(tree_node));
    3.23 +        tree_node *b = cxCalloc(alloc, 1, sizeof(tree_node));
    3.24 +        tree_node *c = cxCalloc(alloc, 1, sizeof(tree_node));
    3.25 +        tree_node *aa = cxCalloc(alloc, 1, sizeof(tree_node));
    3.26 +        tree_node *ab = cxCalloc(alloc, 1, sizeof(tree_node));
    3.27 +        tree_node *ba = cxCalloc(alloc, 1, sizeof(tree_node));
    3.28 +        tree_node *ca = cxCalloc(alloc, 1, sizeof(tree_node));
    3.29 +        tree_node *cb = cxCalloc(alloc, 1, sizeof(tree_node));
    3.30 +        tree_node *cc = cxCalloc(alloc, 1, sizeof(tree_node));
    3.31 +        tree_node *cba = cxCalloc(alloc, 1, sizeof(tree_node));
    3.32 +
    3.33 +        cx_tree_link(root, a, tree_node_layout);
    3.34 +        cx_tree_link(root, b, tree_node_layout);
    3.35 +        cx_tree_link(root, c, tree_node_layout);
    3.36 +        cx_tree_link(a, aa, tree_node_layout);
    3.37 +        cx_tree_link(a, ab, tree_node_layout);
    3.38 +        cx_tree_link(b, ba, tree_node_layout);
    3.39 +        cx_tree_link(c, ca, tree_node_layout);
    3.40 +        cx_tree_link(c, cb, tree_node_layout);
    3.41 +        cx_tree_link(c, cc, tree_node_layout);
    3.42 +        cx_tree_link(cb, cba, tree_node_layout);
    3.43 +
    3.44 +        CxTreeIterator iter = cx_tree_iterator(root, true, tree_child_list);
    3.45 +        cx_foreach(tree_node *, node, iter) {
    3.46 +            if (iter.exiting) {
    3.47 +                cxFree(alloc,node);
    3.48 +            }
    3.49 +        }
    3.50 +
    3.51 +        CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
    3.52 +    }
    3.53 +    cx_testing_allocator_destroy(&talloc);
    3.54 +}
    3.55 +
    3.56  CxTestSuite *cx_test_suite_tree_low_level(void) {
    3.57      CxTestSuite *suite = cx_test_suite_new("tree (low level)");
    3.58  
    3.59 @@ -477,6 +519,7 @@
    3.60      cx_test_register(suite, test_tree_iterator_basic_only_enter);
    3.61      cx_test_register(suite, test_tree_iterator_basic_enter_and_exit);
    3.62      cx_test_register(suite, test_tree_iterator_xml);
    3.63 +    cx_test_register(suite, test_tree_iterator_free_nodes);
    3.64  
    3.65      return suite;
    3.66  }