Mercurial > hg > ucx / changeset

--- a/src/cx/tree.h	Tue Oct 08 18:32:48 2024 +0200
+++ b/src/cx/tree.h	Tue Oct 08 18:47:45 2024 +0200
@@ -258,7 +258,7 @@
  * @param loc_children offset in the node struct for the children linked list
  * @param loc_last_child optional offset in the node struct for the pointer to
  * the last child in the linked list (negative if there is no such pointer)
- * @param loc_prev offset in the node struct for the prev pointer
+ * @param loc_prev optional offset in the node struct for the prev pointer
  * @param loc_next offset in the node struct for the next pointer
  * @see cx_tree_unlink()
  */
@@ -283,7 +283,7 @@
  * @param loc_children offset in the node struct for the children linked list
  * @param loc_last_child optional offset in the node struct for the pointer to
  * the last child in the linked list (negative if there is no such pointer)
- * @param loc_prev offset in the node struct for the prev pointer
+ * @param loc_prev optional offset in the node struct for the prev pointer
  * @param loc_next offset in the node struct for the next pointer
  * @see cx_tree_link()
  */
@@ -520,7 +520,7 @@
  * @param loc_children offset in the node struct for the children linked list
  * @param loc_last_child optional offset in the node struct for the pointer to
  * the last child in the linked list (negative if there is no such pointer)
- * @param loc_prev offset in the node struct for the prev pointer
+ * @param loc_prev optional offset in the node struct for the prev pointer
  * @param loc_next offset in the node struct for the next pointer
  * @return the number of nodes created and added
  * @see cx_tree_add()
@@ -573,7 +573,7 @@
  * @param loc_children offset in the node struct for the children linked list
  * @param loc_last_child optional offset in the node struct for the pointer to
  * the last child in the linked list (negative if there is no such pointer)
- * @param loc_prev offset in the node struct for the prev pointer
+ * @param loc_prev optional offset in the node struct for the prev pointer
  * @param loc_next offset in the node struct for the next pointer
  * @return the number of array elements successfully processed
  * @see cx_tree_add()
@@ -635,7 +635,7 @@
  * @param loc_children offset in the node struct for the children linked list
  * @param loc_last_child optional offset in the node struct for the pointer to
  * the last child in the linked list (negative if there is no such pointer)
- * @param loc_prev offset in the node struct for the prev pointer
+ * @param loc_prev optional offset in the node struct for the prev pointer
  * @param loc_next offset in the node struct for the next pointer
  * @return zero when a new node was created and added to the tree,
  * non-zero otherwise
@@ -865,7 +865,7 @@
  * @param loc_children offset in the node struct for the children linked list
  * @param loc_last_child optional offset in the node struct for the pointer to
  * the last child in the linked list (negative if there is no such pointer)
- * @param loc_prev offset in the node struct for the prev pointer
+ * @param loc_prev optional offset in the node struct for the prev pointer
  * @param loc_next offset in the node struct for the next pointer
  * @return the new tree
  * @see cxTreeCreateSimple()
@@ -932,7 +932,7 @@
  * @param loc_children offset in the node struct for the children linked list
  * @param loc_last_child optional offset in the node struct for the pointer to
  * the last child in the linked list (negative if there is no such pointer)
- * @param loc_prev offset in the node struct for the prev pointer
+ * @param loc_prev optional offset in the node struct for the prev pointer
  * @param loc_next offset in the node struct for the next pointer
  * @return the new tree
  * @see cxTreeCreate()

--- a/src/tree.c	Tue Oct 08 18:32:48 2024 +0200
+++ b/src/tree.c	Tue Oct 08 18:47:45 2024 +0200
@@ -51,7 +51,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) {
@@ -68,6 +70,10 @@
         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 +86,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 +133,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,12 +158,16 @@
             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(