Mercurial > hg > ucx / file diff

--- a/src/tree.c	Sun Jul 07 14:20:28 2024 +0200
+++ b/src/tree.c	Sun Jul 07 14:56:44 2024 +0200
@@ -36,6 +36,7 @@
 #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)
 
@@ -44,23 +45,37 @@
         void *restrict node,
         ptrdiff_t loc_parent,
         ptrdiff_t loc_children,
+        ptrdiff_t loc_last_child,
         ptrdiff_t loc_prev,
         ptrdiff_t loc_next
 ) {
     void *current_parent = tree_parent(node);
     if (current_parent == parent) return;
     if (current_parent != NULL) {
-        cx_tree_unlink(node, loc_parent, loc_children,
+        cx_tree_unlink(node, loc_parent, loc_children, loc_last_child,
                        loc_prev, loc_next);
     }
 
     if (tree_children(parent) == NULL) {
         tree_children(parent) = node;
+        if (loc_last_child >= 0) {
+            tree_last_child(parent) = node;
+        }
     } else {
-        void *children = tree_children(parent);
-        tree_prev(children) = node;
-        tree_next(node) = children;
-        tree_children(parent) = node;
+        if (loc_last_child >= 0) {
+            void *child = tree_last_child(parent);
+            tree_prev(node) = child;
+            tree_next(child) = node;
+            tree_last_child(parent) = node;
+        } else {
+            void *child = tree_children(parent);
+            void *next;
+            while ((next = tree_next(child)) != NULL) {
+                child = next;
+            }
+            tree_prev(node) = child;
+            tree_next(child) = node;
+        }
     }
     tree_parent(node) = parent;
 }
@@ -69,6 +84,7 @@
         void *node,
         ptrdiff_t loc_parent,
         ptrdiff_t loc_children,
+        ptrdiff_t loc_last_child,
         ptrdiff_t loc_prev,
         ptrdiff_t loc_next
 ) {
@@ -76,13 +92,24 @@
 
     void *left = tree_prev(node);
     void *right = tree_next(node);
-    assert(left == NULL || tree_children(tree_parent(node)) != node);
+    void *parent = tree_parent(node);
+    assert(left == NULL || tree_children(parent) != node);
+    assert(right == NULL || loc_last_child < 0 ||
+           tree_last_child(parent) != node);
+
     if (left == NULL) {
-        tree_children(tree_parent(node)) = right;
+        tree_children(parent) = right;
     } else {
         tree_next(left) = right;
     }
-    if (right != NULL) tree_prev(right) = left;
+    if (right == NULL) {
+        if (loc_last_child >= 0) {
+            tree_last_child(parent) = left;
+        }
+    } else {
+        tree_prev(right) = left;
+    }
+
     tree_parent(node) = NULL;
     tree_prev(node) = NULL;
     tree_next(node) = NULL;