|
1 /* |
|
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. |
|
3 * |
|
4 * Copyright 2024 Mike Becker, Olaf Wintermann All rights reserved. |
|
5 * |
|
6 * Redistribution and use in source and binary forms, with or without |
|
7 * modification, are permitted provided that the following conditions are met: |
|
8 * |
|
9 * 1. Redistributions of source code must retain the above copyright |
|
10 * notice, this list of conditions and the following disclaimer. |
|
11 * |
|
12 * 2. Redistributions in binary form must reproduce the above copyright |
|
13 * notice, this list of conditions and the following disclaimer in the |
|
14 * documentation and/or other materials provided with the distribution. |
|
15 * |
|
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
|
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
|
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
|
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE |
|
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
|
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
|
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
|
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
|
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
|
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
|
26 * POSSIBILITY OF SUCH DAMAGE. |
|
27 */ |
|
28 |
|
29 #include "cx/tree.h" |
|
30 |
|
31 #include "cx/array_list.h" |
|
32 |
|
33 #include <assert.h> |
|
34 |
|
35 #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) |
|
38 #define tree_children(node) CX_TREE_PTR(node, loc_children) |
|
39 #define tree_prev(node) CX_TREE_PTR(node, loc_prev) |
|
40 #define tree_next(node) CX_TREE_PTR(node, loc_next) |
|
41 |
|
42 void cx_tree_link( |
|
43 void *restrict parent, |
|
44 void *restrict node, |
|
45 ptrdiff_t loc_parent, |
|
46 ptrdiff_t loc_children, |
|
47 ptrdiff_t loc_prev, |
|
48 ptrdiff_t loc_next |
|
49 ) { |
|
50 void *current_parent = tree_parent(node); |
|
51 if (current_parent == parent) return; |
|
52 if (current_parent != NULL) { |
|
53 cx_tree_unlink(node, loc_parent, loc_children, |
|
54 loc_prev, loc_next); |
|
55 } |
|
56 |
|
57 if (tree_children(parent) == NULL) { |
|
58 tree_children(parent) = node; |
|
59 } else { |
|
60 void *children = tree_children(parent); |
|
61 tree_prev(children) = node; |
|
62 tree_next(node) = children; |
|
63 tree_children(parent) = node; |
|
64 } |
|
65 tree_parent(node) = parent; |
|
66 } |
|
67 |
|
68 void cx_tree_unlink( |
|
69 void *node, |
|
70 ptrdiff_t loc_parent, |
|
71 ptrdiff_t loc_children, |
|
72 ptrdiff_t loc_prev, |
|
73 ptrdiff_t loc_next |
|
74 ) { |
|
75 if (tree_parent(node) == NULL) return; |
|
76 |
|
77 void *left = tree_prev(node); |
|
78 void *right = tree_next(node); |
|
79 assert(left == NULL || tree_children(tree_parent(node)) != node); |
|
80 if (left == NULL) { |
|
81 tree_children(tree_parent(node)) = right; |
|
82 } else { |
|
83 tree_next(left) = right; |
|
84 } |
|
85 if (right != NULL) tree_prev(right) = left; |
|
86 tree_parent(node) = NULL; |
|
87 tree_prev(node) = NULL; |
|
88 tree_next(node) = NULL; |
|
89 } |
|
90 |
|
91 int cx_tree_search( |
|
92 void const *root, |
|
93 void const *data, |
|
94 cx_tree_search_func sfunc, |
|
95 void **result, |
|
96 ptrdiff_t loc_children, |
|
97 ptrdiff_t loc_next |
|
98 ) { |
|
99 int ret; |
|
100 *result = NULL; |
|
101 |
|
102 // shortcut: compare root before doing anything else |
|
103 ret = sfunc(root, data); |
|
104 if (ret < 0) { |
|
105 return ret; |
|
106 } else if (ret == 0 || tree_children(root) == NULL) { |
|
107 *result = (void*)root; |
|
108 return ret; |
|
109 } |
|
110 |
|
111 // create a working stack |
|
112 CX_ARRAY_DECLARE(void const*, work); |
|
113 cx_array_initialize(work, 32); |
|
114 |
|
115 // add the children of root to the working stack |
|
116 { |
|
117 void *c = tree_children(root); |
|
118 while (c != NULL) { |
|
119 cx_array_simple_add(work, c); |
|
120 c = tree_next(c); |
|
121 } |
|
122 } |
|
123 |
|
124 // remember a candidate for adding the data |
|
125 // also remember the exact return code from sfunc |
|
126 void *candidate = NULL; |
|
127 int ret_candidate = -1; |
|
128 |
|
129 // process the working stack |
|
130 while (work_size > 0) { |
|
131 // pop element |
|
132 void const *node = work[--work_size]; |
|
133 |
|
134 // apply the search function |
|
135 ret = sfunc(node, data); |
|
136 |
|
137 if (ret == 0) { |
|
138 // if found, exit the search |
|
139 *result = (void*) node; |
|
140 work_size = 0; |
|
141 break; |
|
142 } else if (ret > 0) { |
|
143 // if children might contain the data, add them to the stack |
|
144 void *c = tree_children(node); |
|
145 while (c != NULL) { |
|
146 cx_array_simple_add(work, c); |
|
147 c = tree_next(c); |
|
148 } |
|
149 |
|
150 // remember this node in case no child is suitable |
|
151 if (ret_candidate < 0 || ret < ret_candidate) { |
|
152 candidate = (void *) node; |
|
153 ret_candidate = ret; |
|
154 } |
|
155 } |
|
156 } |
|
157 |
|
158 // not found, but was there a candidate? |
|
159 if (ret != 0 && candidate != NULL) { |
|
160 ret = ret_candidate; |
|
161 *result = candidate; |
|
162 } |
|
163 |
|
164 // free the working queue and return |
|
165 free(work); |
|
166 return ret; |
|
167 } |
|
168 |
|
169 static bool cx_tree_iter_valid(void const *it) { |
|
170 struct cx_tree_iterator_s const *iter = it; |
|
171 return iter->node != NULL; |
|
172 } |
|
173 |
|
174 static void *cx_tree_iter_current(void const *it) { |
|
175 struct cx_tree_iterator_s const *iter = it; |
|
176 return iter->node; |
|
177 } |
|
178 |
|
179 static void cx_tree_iter_next(void *it) { |
|
180 struct cx_tree_iterator_s *iter = it; |
|
181 ptrdiff_t const loc_next = iter->loc_next; |
|
182 ptrdiff_t const loc_children = iter->loc_children; |
|
183 |
|
184 void *children; |
|
185 |
|
186 // check if we are currently exiting or entering nodes |
|
187 if (iter->exiting) { |
|
188 children = NULL; |
|
189 // skipping on exit is pointless, just clear the flag |
|
190 iter->skip = false; |
|
191 } else { |
|
192 if (iter->skip) { |
|
193 // skip flag is set, pretend that there are no children |
|
194 iter->skip = false; |
|
195 children = NULL; |
|
196 } else { |
|
197 // try to enter the children (if any) |
|
198 children = tree_children(iter->node); |
|
199 } |
|
200 } |
|
201 |
|
202 if (children == NULL) { |
|
203 // search for the next node |
|
204 void *next; |
|
205 cx_tree_iter_search_next: |
|
206 // check if there is a sibling |
|
207 if (iter->exiting) { |
|
208 next = iter->node_next; |
|
209 } else { |
|
210 next = tree_next(iter->node); |
|
211 iter->node_next = next; |
|
212 } |
|
213 if (next == NULL) { |
|
214 // no sibling, we are done with this node and exit |
|
215 if (iter->visit_on_exit && !iter->exiting) { |
|
216 // iter is supposed to visit the node again |
|
217 iter->exiting = true; |
|
218 } else { |
|
219 iter->exiting = false; |
|
220 if (iter->depth == 1) { |
|
221 // there is no parent - we have iterated the entire tree |
|
222 // invalidate the iterator and free the node stack |
|
223 iter->node = iter->node_next = NULL; |
|
224 iter->stack_capacity = iter->depth = 0; |
|
225 free(iter->stack); |
|
226 iter->stack = NULL; |
|
227 } else { |
|
228 // the parent node can be obtained from the top of stack |
|
229 // this way we can avoid the loc_parent in the iterator |
|
230 iter->depth--; |
|
231 iter->node = iter->stack[iter->depth - 1]; |
|
232 // retry with the parent node to find a sibling |
|
233 goto cx_tree_iter_search_next; |
|
234 } |
|
235 } |
|
236 } else { |
|
237 if (iter->visit_on_exit && !iter->exiting) { |
|
238 // iter is supposed to visit the node again |
|
239 iter->exiting = true; |
|
240 } else { |
|
241 iter->exiting = false; |
|
242 // move to the sibling |
|
243 iter->counter++; |
|
244 iter->node = next; |
|
245 // new top of stack is the sibling |
|
246 iter->stack[iter->depth - 1] = next; |
|
247 } |
|
248 } |
|
249 } else { |
|
250 // node has children, push the first child onto the stack and enter it |
|
251 cx_array_simple_add(iter->stack, children); |
|
252 iter->node = children; |
|
253 iter->counter++; |
|
254 } |
|
255 } |
|
256 |
|
257 CxTreeIterator cx_tree_iterator( |
|
258 void *root, |
|
259 bool visit_on_exit, |
|
260 ptrdiff_t loc_children, |
|
261 ptrdiff_t loc_next |
|
262 ) { |
|
263 CxTreeIterator iter; |
|
264 iter.loc_children = loc_children; |
|
265 iter.loc_next = loc_next; |
|
266 iter.visit_on_exit = visit_on_exit; |
|
267 |
|
268 // allocate stack |
|
269 iter.stack_capacity = 16; |
|
270 iter.stack = malloc(sizeof(void *) * 16); |
|
271 iter.depth = 0; |
|
272 |
|
273 // visit the root node |
|
274 iter.node = root; |
|
275 iter.node_next = NULL; |
|
276 iter.counter = 1; |
|
277 iter.depth = 1; |
|
278 iter.stack[0] = root; |
|
279 iter.exiting = false; |
|
280 iter.skip = false; |
|
281 |
|
282 // assign base iterator functions |
|
283 iter.base.mutating = false; |
|
284 iter.base.remove = false; |
|
285 iter.base.current_impl = NULL; |
|
286 iter.base.valid = cx_tree_iter_valid; |
|
287 iter.base.next = cx_tree_iter_next; |
|
288 iter.base.current = cx_tree_iter_current; |
|
289 |
|
290 return iter; |
|
291 } |
|
292 |
|
293 static bool cx_tree_visitor_valid(void const *it) { |
|
294 struct cx_tree_visitor_s const *iter = it; |
|
295 return iter->node != NULL; |
|
296 } |
|
297 |
|
298 static void *cx_tree_visitor_current(void const *it) { |
|
299 struct cx_tree_visitor_s const *iter = it; |
|
300 return iter->node; |
|
301 } |
|
302 |
|
303 __attribute__((__nonnull__)) |
|
304 static void cx_tree_visitor_enqueue_siblings( |
|
305 struct cx_tree_visitor_s *iter, void *node, ptrdiff_t loc_next) { |
|
306 node = tree_next(node); |
|
307 while (node != NULL) { |
|
308 struct cx_tree_visitor_queue_s *q; |
|
309 q = malloc(sizeof(struct cx_tree_visitor_queue_s)); |
|
310 q->depth = iter->queue_last->depth; |
|
311 q->node = node; |
|
312 iter->queue_last->next = q; |
|
313 iter->queue_last = q; |
|
314 node = tree_next(node); |
|
315 } |
|
316 iter->queue_last->next = NULL; |
|
317 } |
|
318 |
|
319 static void cx_tree_visitor_next(void *it) { |
|
320 struct cx_tree_visitor_s *iter = it; |
|
321 ptrdiff_t const loc_next = iter->loc_next; |
|
322 ptrdiff_t const loc_children = iter->loc_children; |
|
323 |
|
324 // add the children of the current node to the queue |
|
325 // unless the skip flag is set |
|
326 void *children; |
|
327 if (iter->skip) { |
|
328 iter->skip = false; |
|
329 children = NULL; |
|
330 } else { |
|
331 children = tree_children(iter->node); |
|
332 } |
|
333 if (children != NULL) { |
|
334 struct cx_tree_visitor_queue_s *q; |
|
335 q = malloc(sizeof(struct cx_tree_visitor_queue_s)); |
|
336 q->depth = iter->depth + 1; |
|
337 q->node = children; |
|
338 if (iter->queue_last == NULL) { |
|
339 assert(iter->queue_next == NULL); |
|
340 iter->queue_next = q; |
|
341 } else { |
|
342 iter->queue_last->next = q; |
|
343 } |
|
344 iter->queue_last = q; |
|
345 cx_tree_visitor_enqueue_siblings(iter, children, loc_next); |
|
346 } |
|
347 |
|
348 // check if there is a next node |
|
349 if (iter->queue_next == NULL) { |
|
350 iter->node = NULL; |
|
351 return; |
|
352 } |
|
353 |
|
354 // dequeue the next node |
|
355 iter->node = iter->queue_next->node; |
|
356 iter->depth = iter->queue_next->depth; |
|
357 { |
|
358 struct cx_tree_visitor_queue_s *q = iter->queue_next; |
|
359 iter->queue_next = q->next; |
|
360 if (iter->queue_next == NULL) { |
|
361 assert(iter->queue_last == q); |
|
362 iter->queue_last = NULL; |
|
363 } |
|
364 free(q); |
|
365 } |
|
366 |
|
367 // increment the node counter |
|
368 iter->counter++; |
|
369 } |
|
370 |
|
371 CxTreeVisitor cx_tree_visitor( |
|
372 void *root, |
|
373 ptrdiff_t loc_children, |
|
374 ptrdiff_t loc_next |
|
375 ) { |
|
376 CxTreeVisitor iter; |
|
377 iter.loc_children = loc_children; |
|
378 iter.loc_next = loc_next; |
|
379 |
|
380 // allocate stack |
|
381 iter.depth = 0; |
|
382 |
|
383 // visit the root node |
|
384 iter.node = root; |
|
385 iter.counter = 1; |
|
386 iter.depth = 1; |
|
387 iter.skip = false; |
|
388 iter.queue_next = NULL; |
|
389 iter.queue_last = NULL; |
|
390 |
|
391 // assign base iterator functions |
|
392 iter.base.mutating = false; |
|
393 iter.base.remove = false; |
|
394 iter.base.current_impl = NULL; |
|
395 iter.base.valid = cx_tree_visitor_valid; |
|
396 iter.base.next = cx_tree_visitor_next; |
|
397 iter.base.current = cx_tree_visitor_current; |
|
398 |
|
399 return iter; |
|
400 } |
|
401 |