ucx: comparison src/tree.c

-:af0092d8789a
+:e29c1f96646d
 #include "cx/array_list.h"
 #include <assert.h>
 #define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off)))
-#define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off)))
 #define tree_parent(node) CX_TREE_PTR(node, loc_parent)
 #define tree_children(node) CX_TREE_PTR(node, loc_children)
 #define tree_last_child(node) CX_TREE_PTR(node, loc_last_child)
 #define tree_prev(node) CX_TREE_PTR(node, loc_prev)
 #define tree_next(node) CX_TREE_PTR(node, loc_next)
 tree_next(node) = NULL;
 }
 int cx_tree_search(
 void const *root,
-void const *data,
+void const *node,
 cx_tree_search_func sfunc,
 void **result,
 ptrdiff_t loc_children,
 ptrdiff_t loc_next
 ) {
 int ret;
 *result = NULL;
 // shortcut: compare root before doing anything else
-ret = sfunc(root, data);
+ret = sfunc(root, node);
 if (ret < 0) {
 return ret;
 } else if (ret == 0 || tree_children(root) == NULL) {
 *result = (void*)root;
 return ret;
 int ret_candidate = ret;
 // process the working stack
 while (work_size > 0) {
 // pop element
-void const *node = work[--work_size];
+void const *elem = work[--work_size];
 // apply the search function
-ret = sfunc(node, data);
+ret = sfunc(elem, node);
 if (ret == 0) {
 // if found, exit the search
-*result = (void*) node;
+*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(node);
+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 *) node;
+candidate = (void *) elem;
 ret_candidate = ret;
 }
 }
 }
 }
 // free the working queue and return
 free(work);
 return ret;
+}
+int cx_tree_search_data(
+void const *root,
+void const *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,
+(cx_tree_search_func) sfunc,
+result,
+loc_children, loc_next);
 }
 static bool cx_tree_iter_valid(void const *it) {
 struct cx_tree_iterator_s const *iter = it;
 return iter->node != NULL;
 return iter;
 }
 static void cx_tree_add_link_duplicate(
-void **root, void *original, void *duplicate,
+void *original, void *duplicate,
 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
 ptrdiff_t loc_prev, ptrdiff_t loc_next
 ) {
-cx_tree_zero_pointers(duplicate, cx_tree_ptr_locations);
 void *shared_parent = tree_parent(original);
 if (shared_parent == NULL) {
-cx_tree_link(duplicate, original, cx_tree_ptr_locations);
+cx_tree_link(original, duplicate, cx_tree_ptr_locations);
-*root = duplicate;
 } else {
 cx_tree_link(shared_parent, duplicate, cx_tree_ptr_locations);
 }
 }
-void *cx_tree_add(
+static void cx_tree_add_link_new(
+void *parent, void *node, cx_tree_search_func sfunc,
+ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
+ptrdiff_t loc_prev, ptrdiff_t loc_next
+) {
+// check the current children one by one,
+// if they could be children of the new node
+void *child = tree_children(parent);
+while (child != NULL) {
+void *next = tree_next(child);
+if (sfunc(node, child) > 0) {
+// the sibling could be a child -> re-link
+cx_tree_link(node, child, cx_tree_ptr_locations);
+}
+child = next;
+}
+// add new node as new child
+cx_tree_link(parent, node, cx_tree_ptr_locations);
+}
+int cx_tree_add(
 void const *src,
 cx_tree_search_func sfunc,
 cx_tree_node_create_func cfunc,
 void *cdata,
-void **root,
+void **cnode,
+void *root,
 ptrdiff_t loc_parent,
 ptrdiff_t loc_children,
 ptrdiff_t loc_last_child,
 ptrdiff_t loc_prev,
 ptrdiff_t loc_next
 ) {
-if (*root == NULL) {
+*cnode = cfunc(src, cdata);
-void *node = cfunc(src, NULL, cdata);
+if (*cnode == NULL) return 1;
-if (node == NULL) return NULL;
+cx_tree_zero_pointers(*cnode, cx_tree_ptr_locations);
-cx_tree_zero_pointers(node, cx_tree_ptr_locations);
-*root = node;
-return node;
-}
 void *match = NULL;
 int result = cx_tree_search(
-*root,
+root,
-src,
+*cnode,
 sfunc,
 &match,
 loc_children,
 loc_next
 );
-void *node;
 if (result < 0) {
-// new node is created as new parent
+// node does not fit into the tree - return non-zero value
-node = cfunc(src, NULL, cdata);
+return 1;
-if (node == NULL) return NULL;
-cx_tree_zero_pointers(node, cx_tree_ptr_locations);
-cx_tree_link(node, *root, cx_tree_ptr_locations);
-*root = node;
 } else if (result == 0) {
-// data already found in the tree, let cfunc decide
+// data already found in the tree, link duplicate
-node = cfunc(src, match, cdata);
+cx_tree_add_link_duplicate(match, *cnode, cx_tree_ptr_locations);
-if (node == NULL) return NULL;
+} else {
-if (node != match) {
+// closest match found, add new node
-cx_tree_add_link_duplicate(
+cx_tree_add_link_new(match, *cnode, sfunc, cx_tree_ptr_locations);
-root, match, node, cx_tree_ptr_locations);
+}
-}
-} else {
+return 0;
-// closest match found, add new node as child
-node = cfunc(src, NULL, cdata);
-if (node == NULL) return NULL;
-cx_tree_zero_pointers(node, cx_tree_ptr_locations);
-cx_tree_link(match, node, cx_tree_ptr_locations);
-}
-return node;
 }
 unsigned int cx_tree_add_look_around_depth = 3;
 size_t cx_tree_add_iter(
 struct cx_iterator_base_s *iter,
 cx_tree_search_func sfunc,
 cx_tree_node_create_func cfunc,
 void *cdata,
-void **root,
+void **failed,
+void *root,
 ptrdiff_t loc_parent,
 ptrdiff_t loc_children,
 ptrdiff_t loc_last_child,
 ptrdiff_t loc_prev,
 ptrdiff_t loc_next
 ) {
+// erase the failed pointer
+*failed = NULL;
 // iter not valid? cancel...
 if (!iter->valid(iter)) return 0;
 size_t processed = 0;
-void *current_node = *root;
+void *current_node = root;
-void *elem;
+void const *elem;
-// if there is no root, yet - process the first node from the iter
-// as the new root node
-if (current_node == NULL) {
-elem = *(void **) (iter->current(iter));
-// no node in tree, yet - add a new one
-current_node = cfunc(elem, NULL, cdata);
-// node creation failed - stop processing
-if (current_node == NULL) return 0;
-cx_tree_zero_pointers(current_node, cx_tree_ptr_locations);
-*root = current_node;
-processed++;
-iter->next(iter);
-}
 for (void **eptr;
 iter->valid(iter) && (eptr = iter->current(iter)) != NULL;
 iter->next(iter)) {
 elem = *eptr;
+// create the new node
+void *new_node = cfunc(elem, cdata);
+if (new_node == NULL) return processed;
+cx_tree_zero_pointers(new_node, cx_tree_ptr_locations);
 // start searching from current node
 void *match;
 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,
-elem,
+new_node,
 sfunc,
 &match,
 loc_children,
 loc_next
 );
-void *node;
 if (result < 0) {
 // traverse upwards and try to find better parents
 void *parent = tree_parent(current_node);
 if (parent != NULL) {
 if (look_around_retries > 0) {
 look_around_retries--;
 current_node = parent;
 } else {
 // look around retries exhausted, start from the root
-current_node = *root;
+current_node = root;
 }
 goto cx_tree_add_look_around_retry;
 } else {
-// no parents. so we (try to) create a new root node
+// no parents. so we failed
-void *new_root = cfunc(elem, NULL, cdata);
+*failed = new_node;
-if (new_root == NULL) return processed;
+return processed;
-cx_tree_zero_pointers(new_root, cx_tree_ptr_locations);
-cx_tree_link(new_root, current_node, cx_tree_ptr_locations);
-current_node = new_root;
-*root = new_root;
 }
 } else if (result == 0) {
-// data already found in the tree, let cfunc decide
+// data already found in the tree, link duplicate
-node = cfunc(elem, match, cdata);
+cx_tree_add_link_duplicate(match, new_node, cx_tree_ptr_locations);
-if (node == NULL) return processed;
+// but stick with the original match, in case we needed a new root
-if (node != match) {
+current_node = match;
-cx_tree_add_link_duplicate(
-root, match, node, cx_tree_ptr_locations);
-}
-current_node = node;
 } else {
 // closest match found, add new node as child
-node = cfunc(elem, NULL, cdata);
+cx_tree_add_link_new(match, new_node, sfunc,
-if (node == NULL) return processed;
+cx_tree_ptr_locations);
-cx_tree_zero_pointers(node, cx_tree_ptr_locations);
-cx_tree_link(match, node, cx_tree_ptr_locations);
-// but make the match current and not the new node
-// (usually saves one traversal when a lot of siblings are added)
 current_node = match;
 }
 processed++;
 }
 size_t num,
 size_t elem_size,
 cx_tree_search_func sfunc,
 cx_tree_node_create_func cfunc,
 void *cdata,
-void **root,
+void **failed,
+void *root,
 ptrdiff_t loc_parent,
 ptrdiff_t loc_children,
 ptrdiff_t loc_last_child,
 ptrdiff_t loc_prev,
 ptrdiff_t loc_next
 ) {
+// erase failed pointer
+*failed = NULL;
 // super special case: zero elements
 if (num == 0) {
 return 0;
 }
 // special case: one element does not need an iterator
 if (num == 1) {
-if (NULL != cx_tree_add(
+void *node;
-src, sfunc, cfunc, cdata, root,
+if (0 == cx_tree_add(
+src, sfunc, cfunc, cdata, &node, root,
 loc_parent, loc_children, loc_last_child,
 loc_prev, loc_next)) {
 return 1;
 } else {
+*failed = node;
 return 0;
 }
 }
 // otherwise, create iterator and hand over to other function
 CxIterator iter = cxIterator(src, elem_size, num);
-return cx_tree_add_iter(cxIteratorRef(iter), sfunc, cfunc, cdata, root,
+return cx_tree_add_iter(cxIteratorRef(iter), sfunc,
+cfunc, cdata, failed, root,
 loc_parent, loc_children, loc_last_child,
 loc_prev, loc_next);
 }

Mercurial > hg > ucx / file comparison

comparison: src/tree.c

src/tree.c