--- 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;