--- a/ucx/tree.c Sun Aug 31 14:39:13 2025 +0200
+++ b/ucx/tree.c Sat Nov 08 23:06:11 2025 +0100
@@ -226,14 +226,14 @@
int ret_elem = sfunc(elem, node);
if (ret_elem == 0) {
// if found, exit the search
- *result = (void *) elem;
+ *result = elem;
ret = 0;
break;
} else if (ret_elem > 0 && ret_elem < ret) {
// new distance is better
*result = elem;
ret = ret_elem;
- } else {
+ } else if (ret_elem < 0 || ret_elem > ret) {
// not contained or distance is worse, skip entire subtree
cxTreeIteratorContinue(iter);
}
@@ -305,12 +305,12 @@
if (children == NULL) {
// search for the next node
- void *next;
+ void *next = NULL;
cx_tree_iter_search_next:
- // check if there is a sibling
+ // check if there is a sibling, but only if we are not a (subtree-)root
if (iter->exiting) {
next = iter->node_next;
- } else {
+ } else if (iter->depth > 1) {
next = tree_next(iter->node);
iter->node_next = next;
}
@@ -326,7 +326,7 @@
// invalidate the iterator and free the node stack
iter->node = iter->node_next = NULL;
iter->stack_capacity = iter->depth = 0;
- free(iter->stack);
+ cxFreeDefault(iter->stack);
iter->stack = NULL;
} else {
// the parent node can be obtained from the top of stack
@@ -375,7 +375,7 @@
iter.skip = false;
// assign base iterator functions
- iter.base.mutating = false;
+ iter.base.allow_remove = false;
iter.base.remove = false;
iter.base.current_impl = NULL;
iter.base.valid = cx_tree_iter_valid;
@@ -386,7 +386,7 @@
iter.node = root;
if (root != NULL) {
iter.stack_capacity = 16;
- iter.stack = malloc(sizeof(void *) * 16);
+ iter.stack = cxMallocDefault(sizeof(void *) * 16);
iter.stack[0] = root;
iter.counter = 1;
iter.depth = 1;
@@ -416,7 +416,7 @@
node = tree_next(node);
while (node != NULL) {
struct cx_tree_visitor_queue_s *q;
- q = malloc(sizeof(struct cx_tree_visitor_queue_s));
+ q = cxMallocDefault(sizeof(struct cx_tree_visitor_queue_s));
q->depth = iter->queue_last->depth;
q->node = node;
iter->queue_last->next = q;
@@ -445,7 +445,7 @@
}
if (children != NULL) {
struct cx_tree_visitor_queue_s *q;
- q = malloc(sizeof(struct cx_tree_visitor_queue_s));
+ q = cxMallocDefault(sizeof(struct cx_tree_visitor_queue_s));
q->depth = iter->depth + 1;
q->node = children;
if (iter->queue_last == NULL) {
@@ -474,7 +474,7 @@
assert(iter->queue_last == q);
iter->queue_last = NULL;
}
- free(q);
+ cxFreeDefault(q);
}
// increment the node counter
@@ -496,7 +496,7 @@
iter.queue_last = NULL;
// assign base iterator functions
- iter.base.mutating = false;
+ iter.base.allow_remove = false;
iter.base.remove = false;
iter.base.current_impl = NULL;
iter.base.valid = cx_tree_visitor_valid;
@@ -717,7 +717,7 @@
}
// otherwise, create iterator and hand over to other function
- CxIterator iter = cxIterator(src, elem_size, num);
+ CxIterator iter = cxIterator(src, elem_size, num, false);
return cx_tree_add_iter(cxIteratorRef(iter), num, sfunc,
cfunc, cdata, failed, root,
loc_parent, loc_children, loc_last_child,
@@ -804,16 +804,12 @@
cx_tree_default_find
};
-CxTree *cxTreeCreate(
- const CxAllocator *allocator,
+CxTree *cxTreeCreate(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,
- ptrdiff_t loc_prev,
- ptrdiff_t loc_next
+ ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
+ ptrdiff_t loc_prev, ptrdiff_t loc_next
) {
if (allocator == NULL) {
allocator = cxDefaultAllocator;
@@ -852,15 +848,9 @@
cxFree(tree->allocator, tree);
}
-CxTree *cxTreeCreateWrapped(
- const CxAllocator *allocator,
- void *root,
- ptrdiff_t loc_parent,
- ptrdiff_t loc_children,
- ptrdiff_t loc_last_child,
- ptrdiff_t loc_prev,
- ptrdiff_t loc_next
-) {
+CxTree *cxTreeCreateWrapped(const CxAllocator *allocator, void *root,
+ ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
+ ptrdiff_t loc_prev, ptrdiff_t loc_next) {
if (allocator == NULL) {
allocator = cxDefaultAllocator;
}
@@ -888,11 +878,7 @@
return tree;
}
-void cxTreeSetParent(
- CxTree *tree,
- void *parent,
- void *child
-) {
+void cxTreeSetParent(CxTree *tree, void *parent, void *child) {
size_t loc_parent = tree->loc_parent;
if (tree_parent(child) == NULL) {
tree->size++;
@@ -900,19 +886,12 @@
cx_tree_link(parent, child, cx_tree_node_layout(tree));
}
-void cxTreeAddChildNode(
- CxTree *tree,
- void *parent,
- void *child
-) {
+void cxTreeAddChildNode(CxTree *tree, void *parent, void *child) {
cx_tree_link(parent, child, cx_tree_node_layout(tree));
tree->size++;
}
-int cxTreeAddChild(
- CxTree *tree,
- void *parent,
- const void *data) {
+int cxTreeAddChild(CxTree *tree, void *parent, const void *data) {
void *node = tree->node_create(data, tree);
if (node == NULL) return 1;
cx_tree_zero_pointers(node, cx_tree_node_layout(tree));
@@ -921,6 +900,29 @@
return 0;
}
+int cxTreeInsert(CxTree *tree, const void *data) {
+ return tree->cl->insert_element(tree, data);
+}
+
+size_t cxTreeInsertIter(CxTree *tree, CxIteratorBase *iter, size_t n) {
+ return tree->cl->insert_many(tree, iter, n);
+}
+
+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);
+ return cxTreeInsertIter(tree, cxIteratorRef(iter), n);
+}
+
+void *cxTreeFind( CxTree *tree, const void *data) {
+ return tree->cl->find(tree, tree->root, data, 0);
+}
+
+void *cxTreeFindInSubtree(CxTree *tree, const void *data, void *subtree_root, size_t max_depth) {
+ return tree->cl->find(tree, subtree_root, data, max_depth);
+}
+
size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root) {
CxTreeVisitor visitor = cx_tree_visitor(
subtree_root,
@@ -945,6 +947,10 @@
return visitor.depth;
}
+size_t cxTreeSize(CxTree *tree) {
+ return tree->size;
+}
+
size_t cxTreeDepth(CxTree *tree) {
CxTreeVisitor visitor = cx_tree_visitor(
tree->root, tree->loc_children, tree->loc_next
@@ -1052,3 +1058,38 @@
tree->root = NULL;
}
}
+
+void cxTreeIteratorDispose(CxTreeIterator *iter) {
+ cxFreeDefault(iter->stack);
+ iter->stack = NULL;
+}
+
+void cxTreeVisitorDispose(CxTreeVisitor *visitor) {
+ struct cx_tree_visitor_queue_s *q = visitor->queue_next;
+ while (q != NULL) {
+ struct cx_tree_visitor_queue_s *next = q->next;
+ cxFreeDefault(q);
+ q = next;
+ }
+}
+
+CxTreeIterator cxTreeIterateSubtree(CxTree *tree, void *node, bool visit_on_exit) {
+ return cx_tree_iterator(
+ node, visit_on_exit,
+ tree->loc_children, tree->loc_next
+ );
+}
+
+CxTreeVisitor cxTreeVisitSubtree(CxTree *tree, void *node) {
+ return cx_tree_visitor(
+ node, tree->loc_children, tree->loc_next
+ );
+}
+
+CxTreeIterator cxTreeIterate(CxTree *tree, bool visit_on_exit) {
+ return cxTreeIterateSubtree(tree, tree->root, visit_on_exit);
+}
+
+CxTreeVisitor cxTreeVisit(CxTree *tree) {
+ return cxTreeVisitSubtree(tree, tree->root);
+}