49 ptrdiff_t loc_last_child, |
49 ptrdiff_t loc_last_child, |
50 ptrdiff_t loc_prev, |
50 ptrdiff_t loc_prev, |
51 ptrdiff_t loc_next |
51 ptrdiff_t loc_next |
52 ) { |
52 ) { |
53 tree_parent(node) = NULL; |
53 tree_parent(node) = NULL; |
54 tree_prev(node) = NULL; |
54 if (loc_prev >= 0) { |
|
55 tree_prev(node) = NULL; |
|
56 } |
55 tree_next(node) = NULL; |
57 tree_next(node) = NULL; |
56 tree_children(node) = NULL; |
58 tree_children(node) = NULL; |
57 if (loc_last_child >= 0) { |
59 if (loc_last_child >= 0) { |
58 tree_last_child(node) = NULL; |
60 tree_last_child(node) = NULL; |
59 } |
61 } |
66 ptrdiff_t loc_children, |
68 ptrdiff_t loc_children, |
67 ptrdiff_t loc_last_child, |
69 ptrdiff_t loc_last_child, |
68 ptrdiff_t loc_prev, |
70 ptrdiff_t loc_prev, |
69 ptrdiff_t loc_next |
71 ptrdiff_t loc_next |
70 ) { |
72 ) { |
|
73 assert(loc_parent >= 0); |
|
74 assert(loc_children >= 0); |
|
75 assert(loc_next >= 0); |
|
76 |
71 void *current_parent = tree_parent(node); |
77 void *current_parent = tree_parent(node); |
72 if (current_parent == parent) return; |
78 if (current_parent == parent) return; |
73 if (current_parent != NULL) { |
79 if (current_parent != NULL) { |
74 cx_tree_unlink(node, cx_tree_ptr_locations); |
80 cx_tree_unlink(node, cx_tree_ptr_locations); |
75 } |
81 } |
78 tree_children(parent) = node; |
84 tree_children(parent) = node; |
79 if (loc_last_child >= 0) { |
85 if (loc_last_child >= 0) { |
80 tree_last_child(parent) = node; |
86 tree_last_child(parent) = node; |
81 } |
87 } |
82 } else { |
88 } else { |
|
89 void *child; |
83 if (loc_last_child >= 0) { |
90 if (loc_last_child >= 0) { |
84 void *child = tree_last_child(parent); |
91 child = tree_last_child(parent); |
85 tree_prev(node) = child; |
|
86 tree_next(child) = node; |
|
87 tree_last_child(parent) = node; |
92 tree_last_child(parent) = node; |
88 } else { |
93 } else { |
89 void *child = tree_children(parent); |
94 child = tree_children(parent); |
90 void *next; |
95 void *next; |
91 while ((next = tree_next(child)) != NULL) { |
96 while ((next = tree_next(child)) != NULL) { |
92 child = next; |
97 child = next; |
93 } |
98 } |
|
99 } |
|
100 if (loc_prev >= 0) { |
94 tree_prev(node) = child; |
101 tree_prev(node) = child; |
95 tree_next(child) = node; |
102 } |
96 } |
103 tree_next(child) = node; |
97 } |
104 } |
98 tree_parent(node) = parent; |
105 tree_parent(node) = parent; |
|
106 } |
|
107 |
|
108 static void *cx_tree_node_prev( |
|
109 ptrdiff_t loc_parent, |
|
110 ptrdiff_t loc_children, |
|
111 ptrdiff_t loc_next, |
|
112 const void *node |
|
113 ) { |
|
114 void *parent = tree_parent(node); |
|
115 void *begin = tree_children(parent); |
|
116 if (begin == node) return NULL; |
|
117 const void *cur = begin; |
|
118 const void *next; |
|
119 while (1) { |
|
120 next = tree_next(cur); |
|
121 if (next == node) return (void *) cur; |
|
122 cur = next; |
|
123 } |
99 } |
124 } |
100 |
125 |
101 void cx_tree_unlink( |
126 void cx_tree_unlink( |
102 void *node, |
127 void *node, |
103 ptrdiff_t loc_parent, |
128 ptrdiff_t loc_parent, |
106 ptrdiff_t loc_prev, |
131 ptrdiff_t loc_prev, |
107 ptrdiff_t loc_next |
132 ptrdiff_t loc_next |
108 ) { |
133 ) { |
109 if (tree_parent(node) == NULL) return; |
134 if (tree_parent(node) == NULL) return; |
110 |
135 |
111 void *left = tree_prev(node); |
136 assert(loc_children >= 0); |
|
137 assert(loc_next >= 0); |
|
138 assert(loc_parent >= 0); |
|
139 void *left; |
|
140 if (loc_prev >= 0) { |
|
141 left = tree_prev(node); |
|
142 } else { |
|
143 left = cx_tree_node_prev(loc_parent, loc_children, loc_next, node); |
|
144 } |
112 void *right = tree_next(node); |
145 void *right = tree_next(node); |
113 void *parent = tree_parent(node); |
146 void *parent = tree_parent(node); |
114 assert(left == NULL || tree_children(parent) != node); |
147 assert(left == NULL || tree_children(parent) != node); |
115 assert(right == NULL || loc_last_child < 0 || |
148 assert(right == NULL || loc_last_child < 0 || |
116 tree_last_child(parent) != node); |
149 tree_last_child(parent) != node); |
123 if (right == NULL) { |
156 if (right == NULL) { |
124 if (loc_last_child >= 0) { |
157 if (loc_last_child >= 0) { |
125 tree_last_child(parent) = left; |
158 tree_last_child(parent) = left; |
126 } |
159 } |
127 } else { |
160 } else { |
128 tree_prev(right) = left; |
161 if (loc_prev >= 0) { |
|
162 tree_prev(right) = left; |
|
163 } |
129 } |
164 } |
130 |
165 |
131 tree_parent(node) = NULL; |
166 tree_parent(node) = NULL; |
132 tree_prev(node) = NULL; |
|
133 tree_next(node) = NULL; |
167 tree_next(node) = NULL; |
|
168 if (loc_prev >= 0) { |
|
169 tree_prev(node) = NULL; |
|
170 } |
134 } |
171 } |
135 |
172 |
136 int cx_tree_search( |
173 int cx_tree_search( |
137 const void *root, |
174 const void *root, |
138 const void *node, |
175 const void *node, |