--- a/ucx/tree.c Sun Dec 07 20:16:59 2025 +0100
+++ b/ucx/tree.c Fri Dec 19 17:53:18 2025 +0100
@@ -28,8 +28,6 @@
#include "cx/tree.h"
-#include "cx/array_list.h"
-
#include <assert.h>
#define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off)))
@@ -352,7 +350,16 @@
}
} else {
// node has children, push the first child onto the stack and enter it
- cx_array_simple_add(iter->stack, children);
+ if (iter->stack_size >= iter->stack_capacity) {
+ const size_t newcap = iter->stack_capacity + 8;
+ if (cxReallocArrayDefault(&iter->stack, newcap, sizeof(void*))) {
+ // we cannot return an error in this function
+ abort(); // LCOV_EXCL_LINE
+ }
+ iter->stack_capacity = newcap;
+ }
+ iter->stack[iter->stack_size] = children;
+ iter->stack_size++;
iter->node = children;
iter->counter++;
}
@@ -566,7 +573,7 @@
ptrdiff_t loc_next
) {
*cnode = cfunc(src, cdata);
- if (*cnode == NULL) return 1;
+ if (*cnode == NULL) return 1; // LCOV_EXCL_LINE
cx_tree_zero_pointers(*cnode, cx_tree_ptr_locations);
void *match = NULL;
@@ -627,7 +634,7 @@
// create the new node
void *new_node = cfunc(elem, cdata);
- if (new_node == NULL) return processed;
+ if (new_node == NULL) return processed; // LCOV_EXCL_LINE
cx_tree_zero_pointers(new_node, cx_tree_ptr_locations);
// start searching from current node
@@ -717,7 +724,7 @@
}
// otherwise, create iterator and hand over to other function
- CxIterator iter = cxIterator(src, elem_size, num, false);
+ CxIterator iter = cxIterator(src, elem_size, num);
return cx_tree_add_iter(cxIteratorRef(iter), num, sfunc,
cfunc, cdata, failed, root,
loc_parent, loc_children, loc_last_child,
@@ -731,18 +738,18 @@
void *node;
if (tree->root == NULL) {
node = tree->node_create(data, tree);
- if (node == NULL) return 1;
+ if (node == NULL) return 1; // LCOV_EXCL_LINE
cx_tree_zero_pointers(node, cx_tree_node_layout(tree));
tree->root = node;
- tree->size = 1;
+ tree->collection.size = 1;
return 0;
}
int result = cx_tree_add(data, tree->search, tree->node_create,
tree, &node, tree->root, cx_tree_node_layout(tree));
if (0 == result) {
- tree->size++;
+ tree->collection.size++;
} else {
- cxFree(tree->allocator, node);
+ cxFree(tree->collection.allocator, node);
}
return result;
}
@@ -758,7 +765,7 @@
// use the first element from the iter to create the root node
void **eptr = iter->current(iter);
void *node = tree->node_create(*eptr, tree);
- if (node == NULL) return 0;
+ if (node == NULL) return 0; // LCOV_EXCL_LINE
cx_tree_zero_pointers(node, cx_tree_node_layout(tree));
tree->root = node;
ins = 1;
@@ -767,9 +774,9 @@
void *failed;
ins += cx_tree_add_iter(iter, n, tree->search, tree->node_create,
tree, &failed, tree->root, cx_tree_node_layout(tree));
- tree->size += ins;
+ tree->collection.size += ins;
if (ins < n) {
- cxFree(tree->allocator, failed);
+ cxFree(tree->collection.allocator, failed);
}
return ins;
}
@@ -780,7 +787,7 @@
const void *data,
size_t depth
) {
- if (tree->root == NULL) return NULL;
+ if (tree->root == NULL) return NULL; // LCOV_EXCL_LINE
void *found;
if (0 == cx_tree_search_data(
@@ -818,24 +825,21 @@
assert(search_func != NULL);
assert(search_data_func != NULL);
- CxTree *tree = cxMalloc(allocator, sizeof(CxTree));
- if (tree == NULL) return NULL;
+ CxTree *tree = cxZalloc(allocator, sizeof(CxTree));
+ if (tree == NULL) return NULL; // LCOV_EXCL_LINE
tree->cl = &cx_tree_default_class;
- tree->allocator = allocator;
+ tree->collection.allocator = allocator;
tree->node_create = create_func;
tree->search = search_func;
tree->search_data = search_data_func;
- tree->simple_destructor = NULL;
- tree->advanced_destructor = (cx_destructor_func2) cxFree;
- tree->destructor_data = (void *) allocator;
+ tree->collection.advanced_destructor = (cx_destructor_func2) cxFree;
+ tree->collection.destructor_data = (void *) allocator;
tree->loc_parent = loc_parent;
tree->loc_children = loc_children;
tree->loc_last_child = loc_last_child;
tree->loc_prev = loc_prev;
tree->loc_next = loc_next;
- tree->root = NULL;
- tree->size = 0;
return tree;
}
@@ -845,7 +849,7 @@
if (tree->root != NULL) {
cxTreeClear(tree);
}
- cxFree(tree->allocator, tree);
+ cxFree(tree->collection.allocator, tree);
}
CxTree *cxTreeCreateWrapped(const CxAllocator *allocator, void *root,
@@ -856,47 +860,41 @@
}
assert(root != NULL);
- CxTree *tree = cxMalloc(allocator, sizeof(CxTree));
- if (tree == NULL) return NULL;
+ CxTree *tree = cxZalloc(allocator, sizeof(CxTree));
+ if (tree == NULL) return NULL; // LCOV_EXCL_LINE
tree->cl = &cx_tree_default_class;
// set the allocator anyway, just in case...
- 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->collection.allocator = allocator;
tree->loc_parent = loc_parent;
tree->loc_children = loc_children;
tree->loc_last_child = loc_last_child;
tree->loc_prev = loc_prev;
tree->loc_next = loc_next;
tree->root = root;
- tree->size = cxTreeSubtreeSize(tree, root);
+ tree->collection.size = cxTreeSubtreeSize(tree, root);
return tree;
}
void cxTreeSetParent(CxTree *tree, void *parent, void *child) {
size_t loc_parent = tree->loc_parent;
if (tree_parent(child) == NULL) {
- tree->size++;
+ tree->collection.size++;
}
cx_tree_link(parent, child, cx_tree_node_layout(tree));
}
void cxTreeAddChildNode(CxTree *tree, void *parent, void *child) {
cx_tree_link(parent, child, cx_tree_node_layout(tree));
- tree->size++;
+ tree->collection.size++;
}
int cxTreeAddChild(CxTree *tree, void *parent, const void *data) {
void *node = tree->node_create(data, tree);
- if (node == NULL) return 1;
+ if (node == NULL) return 1; // LCOV_EXCL_LINE
cx_tree_zero_pointers(node, cx_tree_node_layout(tree));
cx_tree_link(parent, node, cx_tree_node_layout(tree));
- tree->size++;
+ tree->collection.size++;
return 0;
}
@@ -911,7 +909,7 @@
size_t cxTreeInsertArray(CxTree *tree, const void *data, size_t elem_size, size_t n) {
if (n == 0) return 0;
if (n == 1) return 0 == cxTreeInsert(tree, data) ? 1 : 0;
- CxIterator iter = cxIterator(data, elem_size, n, false);
+ CxIterator iter = cxIterator(data, elem_size, n);
return cxTreeInsertIter(tree, cxIteratorRef(iter), n);
}
@@ -948,7 +946,7 @@
}
size_t cxTreeSize(CxTree *tree) {
- return tree->size;
+ return tree->collection.size;
}
size_t cxTreeDepth(CxTree *tree) {
@@ -1002,7 +1000,7 @@
if (loc_last_child >= 0) tree_last_child(node) = NULL;
// the tree now has one member less
- tree->size--;
+ tree->collection.size--;
return 0;
}
@@ -1010,12 +1008,12 @@
void cxTreeRemoveSubtree(CxTree *tree, void *node) {
if (node == tree->root) {
tree->root = NULL;
- tree->size = 0;
+ tree->collection.size = 0;
return;
}
size_t subtree_size = cxTreeSubtreeSize(tree, node);
cx_tree_unlink(node, cx_tree_node_layout(tree));
- tree->size -= subtree_size;
+ tree->collection.size -= subtree_size;
}
int cxTreeDestroyNode(
@@ -1025,12 +1023,7 @@
) {
int result = cxTreeRemoveNode(tree, node, relink_func);
if (result == 0) {
- if (tree->simple_destructor) {
- tree->simple_destructor(node);
- }
- if (tree->advanced_destructor) {
- tree->advanced_destructor(tree->destructor_data, node);
- }
+ cx_invoke_destructor(tree, node);
return 0;
} else {
return result;
@@ -1045,15 +1038,10 @@
);
cx_foreach(void *, child, iter) {
if (iter.exiting) {
- if (tree->simple_destructor) {
- tree->simple_destructor(child);
- }
- if (tree->advanced_destructor) {
- tree->advanced_destructor(tree->destructor_data, child);
- }
+ cx_invoke_destructor(tree, child);
}
}
- tree->size -= iter.counter;
+ tree->collection.size -= iter.counter;
if (node == tree->root) {
tree->root = NULL;
}
@@ -1071,6 +1059,7 @@
cxFreeDefault(q);
q = next;
}
+ visitor->queue_next = visitor->queue_last = NULL;
}
CxTreeIterator cxTreeIterateSubtree(CxTree *tree, void *node, bool visit_on_exit) {