1.1 --- a/src/tree.c Wed Feb 14 22:32:13 2024 +0100
1.2 +++ b/src/tree.c Thu Feb 15 21:54:43 2024 +0100
1.3 @@ -28,6 +28,8 @@
1.4
1.5 #include "cx/tree.h"
1.6
1.7 +#include "cx/array_list.h"
1.8 +
1.9 #include <assert.h>
1.10
1.11 #define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off)))
1.12 @@ -85,3 +87,85 @@
1.13 tree_prev(node) = NULL;
1.14 tree_next(node) = NULL;
1.15 }
1.16 +
1.17 +int cx_tree_search(
1.18 + void const *root,
1.19 + void const *data,
1.20 + cx_tree_search_func sfunc,
1.21 + void **result,
1.22 + ptrdiff_t loc_children,
1.23 + ptrdiff_t loc_next
1.24 +) {
1.25 + int ret;
1.26 + *result = NULL;
1.27 +
1.28 + // shortcut: compare root before doing anything else
1.29 + ret = sfunc(root, data);
1.30 + if (ret < 0) {
1.31 + return ret;
1.32 + } else if (ret == 0 || tree_children(root) == NULL) {
1.33 + *result = (void*)root;
1.34 + return ret;
1.35 + }
1.36 +
1.37 + // create a working stack
1.38 + size_t work_cap = 32;
1.39 + size_t work_size = 0;
1.40 + void const **work = malloc(sizeof(void*) * work_cap);
1.41 + #define work_add(node) cx_array_add(&work, &work_size, &work_cap, \
1.42 + sizeof(void*), &(node), cx_array_default_reallocator)
1.43 +
1.44 + // add the children of root to the working stack
1.45 + {
1.46 + void *c = tree_children(root);
1.47 + while (c != NULL) {
1.48 + work_add(c);
1.49 + c = tree_next(c);
1.50 + }
1.51 + }
1.52 +
1.53 + // remember a candidate for adding the data
1.54 + // also remember the exact return code from sfunc
1.55 + void *candidate = NULL;
1.56 + int ret_candidate = -1;
1.57 +
1.58 + // process the working stack
1.59 + while (work_size > 0) {
1.60 + // pop element
1.61 + void const *node = work[--work_size];
1.62 +
1.63 + // apply the search function
1.64 + ret = sfunc(node, data);
1.65 +
1.66 + if (ret == 0) {
1.67 + // if found, exit the search
1.68 + *result = (void*) node;
1.69 + work_size = 0;
1.70 + break;
1.71 + } else if (ret > 0) {
1.72 + // if children might contain the data, add them to the stack
1.73 + void *c = tree_children(node);
1.74 + while (c != NULL) {
1.75 + work_add(c);
1.76 + c = tree_next(c);
1.77 + }
1.78 +
1.79 + // remember this node in case no child is suitable
1.80 + if (ret_candidate < 0 || ret < ret_candidate) {
1.81 + candidate = (void *) node;
1.82 + ret_candidate = ret;
1.83 + }
1.84 + }
1.85 + }
1.86 +
1.87 + // not found, but was there a candidate?
1.88 + if (ret != 0 && candidate != NULL) {
1.89 + ret = ret_candidate;
1.90 + *result = candidate;
1.91 + }
1.92 +
1.93 + // free the working queue and return
1.94 + #undef workq_add
1.95 + free(work);
1.96 + return ret;
1.97 +}
