Mercurial > hg > ucx / file comparison

comparison: src/tree.c

src/tree.c

changeset 862
387414a7afd8
parent 854
fe0d69d72bcd
child 863
4a220afebad0
equal deleted inserted replaced
861:bab51b32fcb1 862:387414a7afd8
34 34
35 #define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off))) 35 #define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off)))
36 #define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off))) 36 #define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off)))
37 #define tree_parent(node) CX_TREE_PTR(node, loc_parent) 37 #define tree_parent(node) CX_TREE_PTR(node, loc_parent)
38 #define tree_children(node) CX_TREE_PTR(node, loc_children) 38 #define tree_children(node) CX_TREE_PTR(node, loc_children)
39 #define tree_last_child(node) CX_TREE_PTR(node, loc_last_child)
39 #define tree_prev(node) CX_TREE_PTR(node, loc_prev) 40 #define tree_prev(node) CX_TREE_PTR(node, loc_prev)
40 #define tree_next(node) CX_TREE_PTR(node, loc_next) 41 #define tree_next(node) CX_TREE_PTR(node, loc_next)
41 42
42 void cx_tree_link( 43 void cx_tree_link(
43 void *restrict parent, 44 void *restrict parent,
44 void *restrict node, 45 void *restrict node,
45 ptrdiff_t loc_parent, 46 ptrdiff_t loc_parent,
46 ptrdiff_t loc_children, 47 ptrdiff_t loc_children,
48 ptrdiff_t loc_last_child,
47 ptrdiff_t loc_prev, 49 ptrdiff_t loc_prev,
48 ptrdiff_t loc_next 50 ptrdiff_t loc_next
49 ) { 51 ) {
50 void *current_parent = tree_parent(node); 52 void *current_parent = tree_parent(node);
51 if (current_parent == parent) return; 53 if (current_parent == parent) return;
52 if (current_parent != NULL) { 54 if (current_parent != NULL) {
53 cx_tree_unlink(node, loc_parent, loc_children, 55 cx_tree_unlink(node, loc_parent, loc_children, loc_last_child,
54 loc_prev, loc_next); 56 loc_prev, loc_next);
55 } 57 }
56 58
57 if (tree_children(parent) == NULL) { 59 if (tree_children(parent) == NULL) {
58 tree_children(parent) = node; 60 tree_children(parent) = node;
59 } else { 61 if (loc_last_child >= 0) {
60 void *children = tree_children(parent); 62 tree_last_child(parent) = node;
61 tree_prev(children) = node; 63 }
62 tree_next(node) = children; 64 } else {
63 tree_children(parent) = node; 65 if (loc_last_child >= 0) {
66 void *child = tree_last_child(parent);
67 tree_prev(node) = child;
68 tree_next(child) = node;
69 tree_last_child(parent) = node;
70 } else {
71 void *child = tree_children(parent);
72 void *next;
73 while ((next = tree_next(child)) != NULL) {
74 child = next;
75 }
76 tree_prev(node) = child;
77 tree_next(child) = node;
78 }
64 } 79 }
65 tree_parent(node) = parent; 80 tree_parent(node) = parent;
66 } 81 }
67 82
68 void cx_tree_unlink( 83 void cx_tree_unlink(
69 void *node, 84 void *node,
70 ptrdiff_t loc_parent, 85 ptrdiff_t loc_parent,
71 ptrdiff_t loc_children, 86 ptrdiff_t loc_children,
87 ptrdiff_t loc_last_child,
72 ptrdiff_t loc_prev, 88 ptrdiff_t loc_prev,
73 ptrdiff_t loc_next 89 ptrdiff_t loc_next
74 ) { 90 ) {
75 if (tree_parent(node) == NULL) return; 91 if (tree_parent(node) == NULL) return;
76 92
77 void *left = tree_prev(node); 93 void *left = tree_prev(node);
78 void *right = tree_next(node); 94 void *right = tree_next(node);
79 assert(left == NULL || tree_children(tree_parent(node)) != node); 95 void *parent = tree_parent(node);
96 assert(left == NULL || tree_children(parent) != node);
97 assert(right == NULL || loc_last_child < 0 ||
98 tree_last_child(parent) != node);
99
80 if (left == NULL) { 100 if (left == NULL) {
81 tree_children(tree_parent(node)) = right; 101 tree_children(parent) = right;
82 } else { 102 } else {
83 tree_next(left) = right; 103 tree_next(left) = right;
84 } 104 }
85 if (right != NULL) tree_prev(right) = left; 105 if (right == NULL) {
106 if (loc_last_child >= 0) {
107 tree_last_child(parent) = left;
108 }
109 } else {
110 tree_prev(right) = left;
111 }
112
86 tree_parent(node) = NULL; 113 tree_parent(node) = NULL;
87 tree_prev(node) = NULL; 114 tree_prev(node) = NULL;
88 tree_next(node) = NULL; 115 tree_next(node) = NULL;
89 } 116 }
90 117

Mercurial Repository: ucx

mercurial