ucx: comparison src/tree.c

-:192a440b99df
+:6540096c17b7
 }
 }
 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
+// remember return value for best match
-ret = sfunc(root, node);
+int ret = sfunc(root, node);
 if (ret < 0) {
+// 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;
-} else if (ret == 0 || tree_children(root) == NULL) {
+}
-*result = (void*)root;
-return ret;
+// special case: indefinite depth
-}
+if (depth == 0) {
+depth = SIZE_MAX;
-// create a working stack
+}
-CX_ARRAY_DECLARE(const void *, work);
-cx_array_initialize(work, 32);
+// create an iterator
+CxTreeIterator iter = cx_tree_iterator(
-// add the children of root to the working stack
+(void*) root, false, loc_children, loc_next
-{
+);
-void *c = tree_children(root);
-while (c != NULL) {
+// skip root, we already handled it
-cx_array_simple_add(work, c);
+cxIteratorNext(iter);
-c = tree_next(c);
-}
+// loop through the remaining tree
-}
+cx_foreach(void *, elem, iter) {
+// investigate the current node
-// remember a candidate for adding the data
+int ret_elem = sfunc(elem, node);
-// also remember the exact return code from sfunc
+if (ret_elem == 0) {
-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);
-if (ret == 0) {
 // if found, exit the search
 *result = (void *) elem;
-work_size = 0;
+ret = 0;
 break;
-} else if (ret > 0) {
+} else if (ret_elem > 0 && ret_elem < ret) {
-// if children might contain the data, add them to the stack
+// new distance is better
-void *c = tree_children(elem);
+*result = elem;
-while (c != NULL) {
+ret = ret_elem;
-cx_array_simple_add(work, c);
+} else {
-c = tree_next(c);
+// not contained or distance is worse, skip entire subtree
-}
+cxTreeIteratorContinue(iter);
+}
-// remember this node in case no child is suitable
-if (ret < ret_candidate) {
+// when we reached the max depth, skip the subtree
-candidate = (void *) elem;
+if (iter.depth == depth) {
-ret_candidate = ret;
+cxTreeIteratorContinue(iter);
 }
 }
-}
+// dispose the iterator as we might have exited the loop early
-// not found, but was there a candidate?
+cxTreeIteratorDispose(&iter);
-if (ret != 0 && candidate != NULL) {
-ret = ret_candidate;
+assert(ret < 0 || *result != NULL);
-*result = candidate;
-}
-// free the working queue and return
-free(work);
 return ret;
 }
 int cx_tree_search_data(
 const void *root,
+size_t depth,
 const void *data,
 cx_tree_search_data_func sfunc,
 void **result,
 ptrdiff_t loc_children,
 ptrdiff_t loc_next
 ) {
 // 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);
 }
 cx_tree_zero_pointers(*cnode, cx_tree_ptr_locations);
 void *match = NULL;
 int result = cx_tree_search(
 root,
+0,
 *cnode,
 sfunc,
 &match,
 loc_children,
 loc_next
 int result;
 unsigned int look_around_retries = cx_tree_add_look_around_depth;
 cx_tree_add_look_around_retry:
 result = cx_tree_search(
 current_node,
+0,
 new_node,
 sfunc,
 &match,
 loc_children,
 loc_next
 }
 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,
 tree->loc_children,
 tree->loc_next

Mercurial > hg > ucx / file comparison

comparison: src/tree.c

src/tree.c