--- a/src/tree.c Sun Oct 13 16:47:14 2024 +0200
+++ b/src/tree.c Sat Oct 19 13:08:06 2024 +0200
@@ -172,84 +172,81 @@
int cx_tree_search(
const void *root,
+ size_t depth,
const void *node,
cx_tree_search_func sfunc,
void **result,
ptrdiff_t loc_children,
ptrdiff_t loc_next
) {
- int ret;
+ // help avoiding bugs due to uninitialized memory
+ assert(result != NULL);
*result = NULL;
- // shortcut: compare root before doing anything else
- ret = sfunc(root, node);
+ // remember return value for best match
+ int ret = sfunc(root, node);
if (ret < 0) {
- return ret;
- } else if (ret == 0 || tree_children(root) == NULL) {
- *result = (void*)root;
+ // not contained, exit
+ return -1;
+ }
+ *result = (void*) root;
+ // if root is already exact match, exit
+ if (ret == 0) {
+ return 0;
+ }
+
+ // when depth is one, we are already done
+ if (depth == 1) {
return ret;
}
- // create a working stack
- CX_ARRAY_DECLARE(const void *, work);
- cx_array_initialize(work, 32);
+ // special case: indefinite depth
+ if (depth == 0) {
+ depth = SIZE_MAX;
+ }
+
+ // create an iterator
+ CxTreeIterator iter = cx_tree_iterator(
+ (void*) root, false, loc_children, loc_next
+ );
+
+ // skip root, we already handled it
+ cxIteratorNext(iter);
- // add the children of root to the working stack
- {
- void *c = tree_children(root);
- while (c != NULL) {
- cx_array_simple_add(work, c);
- c = tree_next(c);
+ // loop through the remaining tree
+ cx_foreach(void *, elem, iter) {
+ // investigate the current node
+ int ret_elem = sfunc(elem, node);
+ if (ret_elem == 0) {
+ // if found, exit the search
+ *result = (void *) elem;
+ ret = 0;
+ break;
+ } else if (ret_elem > 0 && ret_elem < ret) {
+ // new distance is better
+ *result = elem;
+ ret = ret_elem;
+ } else {
+ // not contained or distance is worse, skip entire subtree
+ cxTreeIteratorContinue(iter);
+ }
+
+ // when we reached the max depth, skip the subtree
+ if (iter.depth == depth) {
+ cxTreeIteratorContinue(iter);
}
}
- // remember a candidate for adding the data
- // also remember the exact return code from sfunc
- void *candidate = (void *) root;
- int ret_candidate = ret;
-
- // process the working stack
- while (work_size > 0) {
- // pop element
- const void *elem = work[--work_size];
-
- // apply the search function
- ret = sfunc(elem, node);
+ // dispose the iterator as we might have exited the loop early
+ cxTreeIteratorDispose(&iter);
- if (ret == 0) {
- // if found, exit the search
- *result = (void *) elem;
- work_size = 0;
- break;
- } else if (ret > 0) {
- // if children might contain the data, add them to the stack
- void *c = tree_children(elem);
- while (c != NULL) {
- cx_array_simple_add(work, c);
- c = tree_next(c);
- }
-
- // remember this node in case no child is suitable
- if (ret < ret_candidate) {
- candidate = (void *) elem;
- ret_candidate = ret;
- }
- }
- }
-
- // not found, but was there a candidate?
- if (ret != 0 && candidate != NULL) {
- ret = ret_candidate;
- *result = candidate;
- }
-
- // free the working queue and return
- free(work);
+ assert(ret < 0 || *result != NULL);
return ret;
}
int cx_tree_search_data(
const void *root,
+ size_t depth,
const void *data,
cx_tree_search_data_func sfunc,
void **result,
@@ -258,7 +255,7 @@
) {
// it is basically the same implementation
return cx_tree_search(
- root, data,
+ root, depth, data,
(cx_tree_search_func) sfunc,
result,
loc_children, loc_next);
@@ -568,6 +565,7 @@
void *match = NULL;
int result = cx_tree_search(
root,
+ 0,
*cnode,
sfunc,
&match,
@@ -632,6 +630,7 @@
cx_tree_add_look_around_retry:
result = cx_tree_search(
current_node,
+ 0,
new_node,
sfunc,
&match,
@@ -771,13 +770,15 @@
static void *cx_tree_default_find(
CxTree *tree,
const void *subtree,
- const void *data
+ const void *data,
+ size_t depth
) {
if (tree->root == NULL) return NULL;
void *found;
if (0 == cx_tree_search_data(
subtree,
+ depth,
data,
tree->search_data,
&found,