ucx/tree.c

changeset 440
7c4b9cba09ca
parent 324
ce13a778654a
--- 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;
+    }
+}

mercurial