Mercurial > hg > ucx / file diff

--- a/src/tree.c	Thu Oct 03 16:31:09 2024 +0200
+++ b/src/tree.c	Thu Oct 03 17:39:21 2024 +0200
@@ -241,6 +241,8 @@
     struct cx_tree_iterator_s *iter = it;
     ptrdiff_t const loc_next = iter->loc_next;
     ptrdiff_t const loc_children = iter->loc_children;
+    // protect us from misuse
+    if (!iter->base.valid(iter)) return;
 
     void *children;
 
@@ -326,17 +328,8 @@
     iter.loc_next = loc_next;
     iter.visit_on_exit = visit_on_exit;
 
-    // allocate stack
-    iter.stack_capacity = 16;
-    iter.stack = malloc(sizeof(void *) * 16);
-    iter.depth = 0;
-
-    // visit the root node
-    iter.node = root;
+    // initialize members
     iter.node_next = NULL;
-    iter.counter = 1;
-    iter.depth = 1;
-    iter.stack[0] = root;
     iter.exiting = false;
     iter.skip = false;
 
@@ -348,6 +341,21 @@
     iter.base.next = cx_tree_iter_next;
     iter.base.current = cx_tree_iter_current;
 
+    // visit the root node
+    iter.node = root;
+    if (root != NULL) {
+        iter.stack_capacity = 16;
+        iter.stack = malloc(sizeof(void *) * 16);
+        iter.stack[0] = root;
+        iter.counter = 1;
+        iter.depth = 1;
+    } else {
+        iter.stack_capacity = 0;
+        iter.stack = NULL;
+        iter.counter = 0;
+        iter.depth = 0;
+    }
+
     return iter;
 }
 
@@ -379,6 +387,9 @@
 
 static void cx_tree_visitor_next(void *it) {
     struct cx_tree_visitor_s *iter = it;
+    // protect us from misuse
+    if (!iter->base.valid(iter)) return;
+
     ptrdiff_t const loc_next = iter->loc_next;
     ptrdiff_t const loc_children = iter->loc_children;
 
@@ -438,13 +449,7 @@
     iter.loc_children = loc_children;
     iter.loc_next = loc_next;
 
-    // allocate stack
-    iter.depth = 0;
-
-    // visit the root node
-    iter.node = root;
-    iter.counter = 1;
-    iter.depth = 1;
+    // initialize members
     iter.skip = false;
     iter.queue_next = NULL;
     iter.queue_last = NULL;
@@ -457,6 +462,16 @@
     iter.base.next = cx_tree_visitor_next;
     iter.base.current = cx_tree_visitor_current;
 
+    // visit the root node
+    iter.node = root;
+    if (root != NULL) {
+        iter.counter = 1;
+        iter.depth = 1;
+    } else {
+        iter.counter = 0;
+        iter.depth = 0;
+    }
+
     return iter;
 }
 
@@ -747,11 +762,33 @@
     return ins;
 }
 
+static void *cx_tree_default_find(
+        CxTree *tree,
+        const void *subtree,
+        const void *data
+) {
+    if (tree->root == NULL) return NULL;
+
+    void *found;
+    if (0 == cx_tree_search_data(
+            subtree,
+            data,
+            tree->search_data,
+            &found,
+            tree->loc_children,
+            tree->loc_next
+    )) {
+        return found;
+    } else {
+        return NULL;
+    }
+}
+
 static cx_tree_class cx_tree_default_class = {
         cx_tree_default_destructor,
         cx_tree_default_insert_element,
         cx_tree_default_insert_many,
-        NULL,
+        cx_tree_default_find,
         cx_tree_default_iterator,
         cx_tree_default_visitor
 };
@@ -760,6 +797,7 @@
         const CxAllocator *allocator,
         cx_tree_node_create_func create_func,
         cx_tree_search_func search_func,
+        cx_tree_search_data_func search_data_func,
         ptrdiff_t loc_parent,
         ptrdiff_t loc_children,
         ptrdiff_t loc_last_child,
@@ -773,6 +811,7 @@
     tree->allocator = allocator;
     tree->node_create = create_func;
     tree->search = search_func;
+    tree->search_data = search_data_func;
     tree->advanced_destructor = (cx_destructor_func2) cxFree;
     tree->destructor_data = (void *) allocator;
     tree->loc_parent = loc_parent;
@@ -787,6 +826,7 @@
 }
 
 CxTree *cxTreeCreateWrapped(
+        const CxAllocator *allocator,
         void *root,
         ptrdiff_t loc_parent,
         ptrdiff_t loc_children,
@@ -794,14 +834,16 @@
         ptrdiff_t loc_prev,
         ptrdiff_t loc_next
 ) {
-    CxTree *tree = malloc(sizeof(CxTree));
+    CxTree *tree = cxMalloc(allocator, sizeof(CxTree));
     if (tree == NULL) return NULL;
 
     tree->cl = &cx_tree_default_class;
     // set the allocator anyway, just in case...
-    tree->allocator = cxDefaultAllocator;
+    tree->allocator = allocator;
     tree->node_create = NULL;
     tree->search = NULL;
+    tree->search_data = NULL;
+    tree->simple_destructor = NULL;
     tree->advanced_destructor = NULL;
     tree->destructor_data = NULL;
     tree->loc_parent = loc_parent;
@@ -849,3 +891,17 @@
     }
     return visitor.depth;
 }
+
+size_t cxTreeDepth(CxTree *tree) {
+    CxTreeVisitor visitor = tree->cl->visitor(tree);
+    while (cxIteratorValid(visitor)) {
+        cxIteratorNext(visitor);
+    }
+    return visitor.depth;
+}
+
+void cxTreeRemove(CxTree *tree, void *node) {
+    size_t subtree_size = cxTreeSubtreeSize(tree, node);
+    cx_tree_unlink(node, cx_tree_node_layout(tree));
+    tree->size -= subtree_size;
+}