--- a/ucx/tree.c Sun Jan 05 17:41:39 2025 +0100 +++ b/ucx/tree.c Sun Jan 05 22:00:39 2025 +0100 @@ -42,6 +42,13 @@ #define cx_tree_ptr_locations \ loc_parent, loc_children, loc_last_child, loc_prev, loc_next +#define cx_tree_node_layout(tree) \ + (tree)->loc_parent,\ + (tree)->loc_children,\ + (tree)->loc_last_child,\ + (tree)->loc_prev, \ + (tree)->loc_next + static void cx_tree_zero_pointers( void *node, ptrdiff_t loc_parent, @@ -51,7 +58,9 @@ ptrdiff_t loc_next ) { tree_parent(node) = NULL; - tree_prev(node) = NULL; + if (loc_prev >= 0) { + tree_prev(node) = NULL; + } tree_next(node) = NULL; tree_children(node) = NULL; if (loc_last_child >= 0) { @@ -60,14 +69,18 @@ } void cx_tree_link( - void *restrict parent, - void *restrict node, + void *parent, + void *node, ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child, ptrdiff_t loc_prev, ptrdiff_t loc_next ) { + assert(loc_parent >= 0); + assert(loc_children >= 0); + assert(loc_next >= 0); + void *current_parent = tree_parent(node); if (current_parent == parent) return; if (current_parent != NULL) { @@ -80,24 +93,43 @@ tree_last_child(parent) = node; } } else { + void *child; if (loc_last_child >= 0) { - void *child = tree_last_child(parent); - tree_prev(node) = child; - tree_next(child) = node; + child = tree_last_child(parent); tree_last_child(parent) = node; } else { - void *child = tree_children(parent); + child = tree_children(parent); void *next; while ((next = tree_next(child)) != NULL) { child = next; } + } + if (loc_prev >= 0) { tree_prev(node) = child; - tree_next(child) = node; } + tree_next(child) = node; } tree_parent(node) = parent; } +static void *cx_tree_node_prev( + ptrdiff_t loc_parent, + ptrdiff_t loc_children, + ptrdiff_t loc_next, + const void *node +) { + void *parent = tree_parent(node); + void *begin = tree_children(parent); + if (begin == node) return NULL; + const void *cur = begin; + const void *next; + while (1) { + next = tree_next(cur); + if (next == node) return (void *) cur; + cur = next; + } +} + void cx_tree_unlink( void *node, ptrdiff_t loc_parent, @@ -108,7 +140,15 @@ ) { if (tree_parent(node) == NULL) return; - void *left = tree_prev(node); + assert(loc_children >= 0); + assert(loc_next >= 0); + assert(loc_parent >= 0); + void *left; + if (loc_prev >= 0) { + left = tree_prev(node); + } else { + left = cx_tree_node_prev(loc_parent, loc_children, loc_next, node); + } void *right = tree_next(node); void *parent = tree_parent(node); assert(left == NULL || tree_children(parent) != node); @@ -125,94 +165,95 @@ tree_last_child(parent) = left; } } else { - tree_prev(right) = left; + if (loc_prev >= 0) { + tree_prev(right) = left; + } } tree_parent(node) = NULL; - tree_prev(node) = NULL; tree_next(node) = NULL; + if (loc_prev >= 0) { + tree_prev(node) = NULL; + } } 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, @@ -221,7 +262,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); @@ -369,7 +410,7 @@ return iter->node; } -__attribute__((__nonnull__)) +cx_attr_nonnull static void cx_tree_visitor_enqueue_siblings( struct cx_tree_visitor_s *iter, void *node, ptrdiff_t loc_next) { node = tree_next(node); @@ -531,6 +572,7 @@ void *match = NULL; int result = cx_tree_search( root, + 0, *cnode, sfunc, &match, @@ -595,6 +637,7 @@ cx_tree_add_look_around_retry: result = cx_tree_search( current_node, + 0, new_node, sfunc, &match, @@ -681,37 +724,6 @@ loc_prev, loc_next); } -static void cx_tree_default_destructor(CxTree *tree) { - if (tree->simple_destructor != NULL || tree->advanced_destructor != NULL) { - CxTreeIterator iter = tree->cl->iterator(tree, true); - cx_foreach(void *, node, iter) { - if (iter.exiting) { - if (tree->simple_destructor) { - tree->simple_destructor(node); - } - if (tree->advanced_destructor) { - tree->advanced_destructor(tree->destructor_data, node); - } - } - } - } - cxFree(tree->allocator, tree); -} - -static CxTreeIterator cx_tree_default_iterator( - CxTree *tree, - bool visit_on_exit -) { - return cx_tree_iterator( - tree->root, visit_on_exit, - tree->loc_children, tree->loc_next - ); -} - -static CxTreeVisitor cx_tree_default_visitor(CxTree *tree) { - return cx_tree_visitor(tree->root, tree->loc_children, tree->loc_next); -} - static int cx_tree_default_insert_element( CxTree *tree, const void *data @@ -765,13 +777,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, @@ -785,12 +799,9 @@ } static cx_tree_class cx_tree_default_class = { - cx_tree_default_destructor, cx_tree_default_insert_element, cx_tree_default_insert_many, - cx_tree_default_find, - cx_tree_default_iterator, - cx_tree_default_visitor + cx_tree_default_find }; CxTree *cxTreeCreate( @@ -804,6 +815,13 @@ ptrdiff_t loc_prev, ptrdiff_t loc_next ) { + if (allocator == NULL) { + allocator = cxDefaultAllocator; + } + assert(create_func != NULL); + assert(search_func != NULL); + assert(search_data_func != NULL); + CxTree *tree = cxMalloc(allocator, sizeof(CxTree)); if (tree == NULL) return NULL; @@ -812,6 +830,7 @@ tree->node_create = create_func; tree->search = search_func; tree->search_data = search_data_func; + tree->simple_destructor = NULL; tree->advanced_destructor = (cx_destructor_func2) cxFree; tree->destructor_data = (void *) allocator; tree->loc_parent = loc_parent; @@ -825,6 +844,14 @@ return tree; } +void cxTreeFree(CxTree *tree) { + if (tree == NULL) return; + if (tree->root != NULL) { + cxTreeClear(tree); + } + cxFree(tree->allocator, tree); +} + CxTree *cxTreeCreateWrapped( const CxAllocator *allocator, void *root, @@ -834,6 +861,11 @@ ptrdiff_t loc_prev, ptrdiff_t loc_next ) { + if (allocator == NULL) { + allocator = cxDefaultAllocator; + } + assert(root != NULL); + CxTree *tree = cxMalloc(allocator, sizeof(CxTree)); if (tree == NULL) return NULL; @@ -856,6 +888,27 @@ return tree; } +void cxTreeSetParent( + CxTree *tree, + void *parent, + void *child +) { + size_t loc_parent = tree->loc_parent; + if (tree_parent(child) == NULL) { + tree->size++; + } + cx_tree_link(parent, child, cx_tree_node_layout(tree)); +} + +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, @@ -893,14 +946,16 @@ } size_t cxTreeDepth(CxTree *tree) { - CxTreeVisitor visitor = tree->cl->visitor(tree); + CxTreeVisitor visitor = cx_tree_visitor( + tree->root, tree->loc_children, tree->loc_next + ); while (cxIteratorValid(visitor)) { cxIteratorNext(visitor); } return visitor.depth; } -int cxTreeRemove( +int cxTreeRemoveNode( CxTree *tree, void *node, cx_tree_relink_func relink_func @@ -956,3 +1011,44 @@ cx_tree_unlink(node, cx_tree_node_layout(tree)); tree->size -= subtree_size; } + +int cxTreeDestroyNode( + CxTree *tree, + void *node, + cx_tree_relink_func relink_func +) { + int result = cxTreeRemoveNode(tree, node, relink_func); + if (result == 0) { + if (tree->simple_destructor) { + tree->simple_destructor(node); + } + if (tree->advanced_destructor) { + tree->advanced_destructor(tree->destructor_data, node); + } + return 0; + } else { + return result; + } +} + +void cxTreeDestroySubtree(CxTree *tree, void *node) { + cx_tree_unlink(node, cx_tree_node_layout(tree)); + CxTreeIterator iter = cx_tree_iterator( + node, true, + tree->loc_children, tree->loc_next + ); + cx_foreach(void *, child, iter) { + if (iter.exiting) { + if (tree->simple_destructor) { + tree->simple_destructor(child); + } + if (tree->advanced_destructor) { + tree->advanced_destructor(tree->destructor_data, child); + } + } + } + tree->size -= iter.counter; + if (node == tree->root) { + tree->root = NULL; + } +}