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 tree_parent(node) CX_TREE_PTR(node, loc_parent)
37 #define tree_children(node) CX_TREE_PTR(node, loc_children)
38 #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_next(node) CX_TREE_PTR(node, loc_next)
41
42 #define cx_tree_ptr_locations \
43 loc_parent, loc_children, loc_last_child, loc_prev, loc_next
44
45 #define cx_tree_node_layout(tree) \
46 (tree)->loc_parent,\
47 (tree)->loc_children,\
48 (tree)->loc_last_child,\
49 (tree)->loc_prev, \
50 (tree)->loc_next
51
52 static void cx_tree_zero_pointers(
53 void *node,
54 ptrdiff_t loc_parent,
55 ptrdiff_t loc_children,
56 ptrdiff_t loc_last_child,
57 ptrdiff_t loc_prev,
58 ptrdiff_t loc_next
59 ) {
60 tree_parent(node) = NULL;
61 if (loc_prev >= 0) {
62 tree_prev(node) = NULL;
63 }
64 tree_next(node) = NULL;
65 tree_children(node) = NULL;
66 if (loc_last_child >= 0) {
67 tree_last_child(node) = NULL;
68 }
69 }
70
71 void cx_tree_link(
72 void *parent,
73 void *node,
74 ptrdiff_t loc_parent,
75 ptrdiff_t loc_children,
76 ptrdiff_t loc_last_child,
77 ptrdiff_t loc_prev,
78 ptrdiff_t loc_next
79 ) {
80 assert(loc_parent >= 0);
81 assert(loc_children >= 0);
82 assert(loc_next >= 0);
83
84 void *current_parent = tree_parent(node);
85 if (current_parent == parent) return;
86 if (current_parent != NULL) {
87 cx_tree_unlink(node, cx_tree_ptr_locations);
88 }
89
90 if (tree_children(parent) == NULL) {
91 tree_children(parent) = node;
92 if (loc_last_child >= 0) {
93 tree_last_child(parent) = node;
94 }
95 } else {
96 void *child;
97 if (loc_last_child >= 0) {
98 child = tree_last_child(parent);
99 tree_last_child(parent) = node;
100 } else {
101 child = tree_children(parent);
102 void *next;
103 while ((next = tree_next(child)) != NULL) {
104 child = next;
105 }
106 }
107 if (loc_prev >= 0) {
108 tree_prev(node) = child;
109 }
110 tree_next(child) = node;
111 }
112 tree_parent(node) = parent;
113 }
114
115 static void *cx_tree_node_prev(
116 ptrdiff_t loc_parent,
117 ptrdiff_t loc_children,
118 ptrdiff_t loc_next,
119 const void *node
120 ) {
121 void *parent = tree_parent(node);
122 void *begin = tree_children(parent);
123 if (begin == node) return NULL;
124 const void *cur = begin;
125 const void *next;
126 while (1) {
127 next = tree_next(cur);
128 if (next == node) return (void *) cur;
129 cur = next;
130 }
131 }
132
133 void cx_tree_unlink(
134 void *node,
135 ptrdiff_t loc_parent,
136 ptrdiff_t loc_children,
137 ptrdiff_t loc_last_child,
138 ptrdiff_t loc_prev,
139 ptrdiff_t loc_next
140 ) {
141 if (tree_parent(node) == NULL) return;
142
143 assert(loc_children >= 0);
144 assert(loc_next >= 0);
145 assert(loc_parent >= 0);
146 void *left;
147 if (loc_prev >= 0) {
148 left = tree_prev(node);
149 } else {
150 left = cx_tree_node_prev(loc_parent, loc_children, loc_next, node);
151 }
152 void *right = tree_next(node);
153 void *parent = tree_parent(node);
154 assert(left == NULL || tree_children(parent) != node);
155 assert(right == NULL || loc_last_child < 0 ||
156 tree_last_child(parent) != node);
157
158 if (left == NULL) {
159 tree_children(parent) = right;
160 } else {
161 tree_next(left) = right;
162 }
163 if (right == NULL) {
164 if (loc_last_child >= 0) {
165 tree_last_child(parent) = left;
166 }
167 } else {
168 if (loc_prev >= 0) {
169 tree_prev(right) = left;
170 }
171 }
172
173 tree_parent(node) = NULL;
174 tree_next(node) = NULL;
175 if (loc_prev >= 0) {
176 tree_prev(node) = NULL;
177 }
178 }
179
180 int cx_tree_search(
181 const void *root,
182 size_t depth,
183 const void *node,
184 cx_tree_search_func sfunc,
185 void **result,
186 ptrdiff_t loc_children,
187 ptrdiff_t loc_next
188 ) {
189 // help avoiding bugs due to uninitialized memory
190 assert(result != NULL);
191 *result = NULL;
192
193 // remember return value for best match
194 int ret = sfunc(root, node);
195 if (ret < 0) {
196 // not contained, exit
197 return -1;
198 }
199 *result = (void*) root;
200 // if root is already exact match, exit
201 if (ret == 0) {
202 return 0;
203 }
204
205 // when depth is one, we are already done
206 if (depth == 1) {
207 return ret;
208 }
209
210 // special case: indefinite depth
211 if (depth == 0) {
212 depth = SIZE_MAX;
213 }
214
215 // create an iterator
216 CxTreeIterator iter = cx_tree_iterator(
217 (void*) root, false, loc_children, loc_next
218 );
219
220 // skip root, we already handled it
221 cxIteratorNext(iter);
222
223 // loop through the remaining tree
224 cx_foreach(void *, elem, iter) {
225 // investigate the current node
226 int ret_elem = sfunc(elem, node);
227 if (ret_elem == 0) {
228 // if found, exit the search
229 *result = elem;
230 ret = 0;
231 break;
232 } else if (ret_elem > 0 && ret_elem < ret) {
233 // new distance is better
234 *result = elem;
235 ret = ret_elem;
236 } else if (ret_elem < 0 || ret_elem > ret) {
237 // not contained or distance is worse, skip entire subtree
238 cxTreeIteratorContinue(iter);
239 }
240
241 // when we reached the max depth, skip the subtree
242 if (iter.depth == depth) {
243 cxTreeIteratorContinue(iter);
244 }
245 }
246
247 // dispose the iterator as we might have exited the loop early
248 cxTreeIteratorDispose(&iter);
249
250 assert(ret < 0 || *result != NULL);
251 return ret;
252 }
253
254 int cx_tree_search_data(
255 const void *root,
256 size_t depth,
257 const void *data,
258 cx_tree_search_data_func sfunc,
259 void **result,
260 ptrdiff_t loc_children,
261 ptrdiff_t loc_next
262 ) {
263 // it is basically the same implementation
264 return cx_tree_search(
265 root, depth, data,
266 (cx_tree_search_func) sfunc,
267 result,
268 loc_children, loc_next);
269 }
270
271 static bool cx_tree_iter_valid(const void *it) {
272 const struct cx_tree_iterator_s *iter = it;
273 return iter->node != NULL;
274 }
275
276 static void *cx_tree_iter_current(const void *it) {
277 const struct cx_tree_iterator_s *iter = it;
278 return iter->node;
279 }
280
281 static void cx_tree_iter_next(void *it) {
282 struct cx_tree_iterator_s *iter = it;
283 ptrdiff_t const loc_next = iter->loc_next;
284 ptrdiff_t const loc_children = iter->loc_children;
285 // protect us from misuse
286 if (!iter->base.valid(iter)) return;
287
288 void *children;
289
290 // check if we are currently exiting or entering nodes
291 if (iter->exiting) {
292 children = NULL;
293 // skipping on exit is pointless, just clear the flag
294 iter->skip = false;
295 } else {
296 if (iter->skip) {
297 // skip flag is set, pretend that there are no children
298 iter->skip = false;
299 children = NULL;
300 } else {
301 // try to enter the children (if any)
302 children = tree_children(iter->node);
303 }
304 }
305
306 if (children == NULL) {
307 // search for the next node
308 void *next = NULL;
309 cx_tree_iter_search_next:
310 // check if there is a sibling, but only if we are not a (subtree-)root
311 if (iter->exiting) {
312 next = iter->node_next;
313 } else if (iter->depth > 1) {
314 next = tree_next(iter->node);
315 iter->node_next = next;
316 }
317 if (next == NULL) {
318 // no sibling, we are done with this node and exit
319 if (iter->visit_on_exit && !iter->exiting) {
320 // iter is supposed to visit the node again
321 iter->exiting = true;
322 } else {
323 iter->exiting = false;
324 if (iter->depth == 1) {
325 // there is no parent - we have iterated the entire tree
326 // invalidate the iterator and free the node stack
327 iter->node = iter->node_next = NULL;
328 iter->stack_capacity = iter->depth = 0;
329 cxFreeDefault(iter->stack);
330 iter->stack = NULL;
331 } else {
332 // the parent node can be obtained from the top of stack
333 // this way we can avoid the loc_parent in the iterator
334 iter->depth--;
335 iter->node = iter->stack[iter->depth - 1];
336 // retry with the parent node to find a sibling
337 goto cx_tree_iter_search_next;
338 }
339 }
340 } else {
341 if (iter->visit_on_exit && !iter->exiting) {
342 // iter is supposed to visit the node again
343 iter->exiting = true;
344 } else {
345 iter->exiting = false;
346 // move to the sibling
347 iter->counter++;
348 iter->node = next;
349 // new top of stack is the sibling
350 iter->stack[iter->depth - 1] = next;
351 }
352 }
353 } else {
354 // node has children, push the first child onto the stack and enter it
355 cx_array_simple_add(iter->stack, children);
356 iter->node = children;
357 iter->counter++;
358 }
359 }
360
361 CxTreeIterator cx_tree_iterator(
362 void *root,
363 bool visit_on_exit,
364 ptrdiff_t loc_children,
365 ptrdiff_t loc_next
366 ) {
367 CxTreeIterator iter;
368 iter.loc_children = loc_children;
369 iter.loc_next = loc_next;
370 iter.visit_on_exit = visit_on_exit;
371
372 // initialize members
373 iter.node_next = NULL;
374 iter.exiting = false;
375 iter.skip = false;
376
377 // assign base iterator functions
378 iter.base.allow_remove = false;
379 iter.base.remove = false;
380 iter.base.current_impl = NULL;
381 iter.base.valid = cx_tree_iter_valid;
382 iter.base.next = cx_tree_iter_next;
383 iter.base.current = cx_tree_iter_current;
384
385 // visit the root node
386 iter.node = root;
387 if (root != NULL) {
388 iter.stack_capacity = 16;
389 iter.stack = cxMallocDefault(sizeof(void *) * 16);
390 iter.stack[0] = root;
391 iter.counter = 1;
392 iter.depth = 1;
393 } else {
394 iter.stack_capacity = 0;
395 iter.stack = NULL;
396 iter.counter = 0;
397 iter.depth = 0;
398 }
399
400 return iter;
401 }
402
403 static bool cx_tree_visitor_valid(const void *it) {
404 const struct cx_tree_visitor_s *iter = it;
405 return iter->node != NULL;
406 }
407
408 static void *cx_tree_visitor_current(const void *it) {
409 const struct cx_tree_visitor_s *iter = it;
410 return iter->node;
411 }
412
413 cx_attr_nonnull
414 static void cx_tree_visitor_enqueue_siblings(
415 struct cx_tree_visitor_s *iter, void *node, ptrdiff_t loc_next) {
416 node = tree_next(node);
417 while (node != NULL) {
418 struct cx_tree_visitor_queue_s *q;
419 q = cxMallocDefault(sizeof(struct cx_tree_visitor_queue_s));
420 q->depth = iter->queue_last->depth;
421 q->node = node;
422 iter->queue_last->next = q;
423 iter->queue_last = q;
424 node = tree_next(node);
425 }
426 iter->queue_last->next = NULL;
427 }
428
429 static void cx_tree_visitor_next(void *it) {
430 struct cx_tree_visitor_s *iter = it;
431 // protect us from misuse
432 if (!iter->base.valid(iter)) return;
433
434 ptrdiff_t const loc_next = iter->loc_next;
435 ptrdiff_t const loc_children = iter->loc_children;
436
437 // add the children of the current node to the queue
438 // unless the skip flag is set
439 void *children;
440 if (iter->skip) {
441 iter->skip = false;
442 children = NULL;
443 } else {
444 children = tree_children(iter->node);
445 }
446 if (children != NULL) {
447 struct cx_tree_visitor_queue_s *q;
448 q = cxMallocDefault(sizeof(struct cx_tree_visitor_queue_s));
449 q->depth = iter->depth + 1;
450 q->node = children;
451 if (iter->queue_last == NULL) {
452 assert(iter->queue_next == NULL);
453 iter->queue_next = q;
454 } else {
455 iter->queue_last->next = q;
456 }
457 iter->queue_last = q;
458 cx_tree_visitor_enqueue_siblings(iter, children, loc_next);
459 }
460
461 // check if there is a next node
462 if (iter->queue_next == NULL) {
463 iter->node = NULL;
464 return;
465 }
466
467 // dequeue the next node
468 iter->node = iter->queue_next->node;
469 iter->depth = iter->queue_next->depth;
470 {
471 struct cx_tree_visitor_queue_s *q = iter->queue_next;
472 iter->queue_next = q->next;
473 if (iter->queue_next == NULL) {
474 assert(iter->queue_last == q);
475 iter->queue_last = NULL;
476 }
477 cxFreeDefault(q);
478 }
479
480 // increment the node counter
481 iter->counter++;
482 }
483
484 CxTreeVisitor cx_tree_visitor(
485 void *root,
486 ptrdiff_t loc_children,
487 ptrdiff_t loc_next
488 ) {
489 CxTreeVisitor iter;
490 iter.loc_children = loc_children;
491 iter.loc_next = loc_next;
492
493 // initialize members
494 iter.skip = false;
495 iter.queue_next = NULL;
496 iter.queue_last = NULL;
497
498 // assign base iterator functions
499 iter.base.allow_remove = false;
500 iter.base.remove = false;
501 iter.base.current_impl = NULL;
502 iter.base.valid = cx_tree_visitor_valid;
503 iter.base.next = cx_tree_visitor_next;
504 iter.base.current = cx_tree_visitor_current;
505
506 // visit the root node
507 iter.node = root;
508 if (root != NULL) {
509 iter.counter = 1;
510 iter.depth = 1;
511 } else {
512 iter.counter = 0;
513 iter.depth = 0;
514 }
515
516 return iter;
517 }
518
519 static void cx_tree_add_link_duplicate(
520 void *original, void *duplicate,
521 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
522 ptrdiff_t loc_prev, ptrdiff_t loc_next
523 ) {
524 void *shared_parent = tree_parent(original);
525 if (shared_parent == NULL) {
526 cx_tree_link(original, duplicate, cx_tree_ptr_locations);
527 } else {
528 cx_tree_link(shared_parent, duplicate, cx_tree_ptr_locations);
529 }
530 }
531
532 static void cx_tree_add_link_new(
533 void *parent, void *node, cx_tree_search_func sfunc,
534 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
535 ptrdiff_t loc_prev, ptrdiff_t loc_next
536 ) {
537 // check the current children one by one,
538 // if they could be children of the new node
539 void *child = tree_children(parent);
540 while (child != NULL) {
541 void *next = tree_next(child);
542
543 if (sfunc(node, child) > 0) {
544 // the sibling could be a child -> re-link
545 cx_tree_link(node, child, cx_tree_ptr_locations);
546 }
547
548 child = next;
549 }
550
551 // add new node as new child
552 cx_tree_link(parent, node, cx_tree_ptr_locations);
553 }
554
555 int cx_tree_add(
556 const void *src,
557 cx_tree_search_func sfunc,
558 cx_tree_node_create_func cfunc,
559 void *cdata,
560 void **cnode,
561 void *root,
562 ptrdiff_t loc_parent,
563 ptrdiff_t loc_children,
564 ptrdiff_t loc_last_child,
565 ptrdiff_t loc_prev,
566 ptrdiff_t loc_next
567 ) {
568 *cnode = cfunc(src, cdata);
569 if (*cnode == NULL) return 1; // LCOV_EXCL_LINE
570 cx_tree_zero_pointers(*cnode, cx_tree_ptr_locations);
571
572 void *match = NULL;
573 int result = cx_tree_search(
574 root,
575 0,
576 *cnode,
577 sfunc,
578 &match,
579 loc_children,
580 loc_next
581 );
582
583 if (result < 0) {
584 // node does not fit into the tree - return non-zero value
585 return 1;
586 } else if (result == 0) {
587 // data already found in the tree, link duplicate
588 cx_tree_add_link_duplicate(match, *cnode, cx_tree_ptr_locations);
589 } else {
590 // closest match found, add new node
591 cx_tree_add_link_new(match, *cnode, sfunc, cx_tree_ptr_locations);
592 }
593
594 return 0;
595 }
596
597 unsigned int cx_tree_add_look_around_depth = 3;
598
599 size_t cx_tree_add_iter(
600 struct cx_iterator_base_s *iter,
601 size_t num,
602 cx_tree_search_func sfunc,
603 cx_tree_node_create_func cfunc,
604 void *cdata,
605 void **failed,
606 void *root,
607 ptrdiff_t loc_parent,
608 ptrdiff_t loc_children,
609 ptrdiff_t loc_last_child,
610 ptrdiff_t loc_prev,
611 ptrdiff_t loc_next
612 ) {
613 // erase the failed pointer
614 *failed = NULL;
615
616 // iter not valid? cancel...
617 if (!iter->valid(iter)) return 0;
618
619 size_t processed = 0;
620 void *current_node = root;
621 const void *elem;
622
623 for (void **eptr; processed < num &&
624 iter->valid(iter) && (eptr = iter->current(iter)) != NULL;
625 iter->next(iter)) {
626 elem = *eptr;
627
628 // create the new node
629 void *new_node = cfunc(elem, cdata);
630 if (new_node == NULL) return processed; // LCOV_EXCL_LINE
631 cx_tree_zero_pointers(new_node, cx_tree_ptr_locations);
632
633 // start searching from current node
634 void *match;
635 int result;
636 unsigned int look_around_retries = cx_tree_add_look_around_depth;
637 cx_tree_add_look_around_retry:
638 result = cx_tree_search(
639 current_node,
640 0,
641 new_node,
642 sfunc,
643 &match,
644 loc_children,
645 loc_next
646 );
647
648 if (result < 0) {
649 // traverse upwards and try to find better parents
650 void *parent = tree_parent(current_node);
651 if (parent != NULL) {
652 if (look_around_retries > 0) {
653 look_around_retries--;
654 current_node = parent;
655 } else {
656 // look around retries exhausted, start from the root
657 current_node = root;
658 }
659 goto cx_tree_add_look_around_retry;
660 } else {
661 // no parents. so we failed
662 *failed = new_node;
663 return processed;
664 }
665 } else if (result == 0) {
666 // data already found in the tree, link duplicate
667 cx_tree_add_link_duplicate(match, new_node, cx_tree_ptr_locations);
668 // but stick with the original match, in case we needed a new root
669 current_node = match;
670 } else {
671 // closest match found, add new node as child
672 cx_tree_add_link_new(match, new_node, sfunc,
673 cx_tree_ptr_locations);
674 current_node = match;
675 }
676
677 processed++;
678 }
679 return processed;
680 }
681
682 size_t cx_tree_add_array(
683 const void *src,
684 size_t num,
685 size_t elem_size,
686 cx_tree_search_func sfunc,
687 cx_tree_node_create_func cfunc,
688 void *cdata,
689 void **failed,
690 void *root,
691 ptrdiff_t loc_parent,
692 ptrdiff_t loc_children,
693 ptrdiff_t loc_last_child,
694 ptrdiff_t loc_prev,
695 ptrdiff_t loc_next
696 ) {
697 // erase failed pointer
698 *failed = NULL;
699
700 // super special case: zero elements
701 if (num == 0) {
702 return 0;
703 }
704
705 // special case: one element does not need an iterator
706 if (num == 1) {
707 void *node;
708 if (0 == cx_tree_add(
709 src, sfunc, cfunc, cdata, &node, root,
710 loc_parent, loc_children, loc_last_child,
711 loc_prev, loc_next)) {
712 return 1;
713 } else {
714 *failed = node;
715 return 0;
716 }
717 }
718
719 // otherwise, create iterator and hand over to other function
720 CxIterator iter = cxIterator(src, elem_size, num, false);
721 return cx_tree_add_iter(cxIteratorRef(iter), num, sfunc,
722 cfunc, cdata, failed, root,
723 loc_parent, loc_children, loc_last_child,
724 loc_prev, loc_next);
725 }
726
727 static int cx_tree_default_insert_element(
728 CxTree *tree,
729 const void *data
730 ) {
731 void *node;
732 if (tree->root == NULL) {
733 node = tree->node_create(data, tree);
734 if (node == NULL) return 1; // LCOV_EXCL_LINE
735 cx_tree_zero_pointers(node, cx_tree_node_layout(tree));
736 tree->root = node;
737 tree->size = 1;
738 return 0;
739 }
740 int result = cx_tree_add(data, tree->search, tree->node_create,
741 tree, &node, tree->root, cx_tree_node_layout(tree));
742 if (0 == result) {
743 tree->size++;
744 } else {
745 cxFree(tree->allocator, node);
746 }
747 return result;
748 }
749
750 static size_t cx_tree_default_insert_many(
751 CxTree *tree,
752 CxIteratorBase *iter,
753 size_t n
754 ) {
755 size_t ins = 0;
756 if (!iter->valid(iter)) return 0;
757 if (tree->root == NULL) {
758 // use the first element from the iter to create the root node
759 void **eptr = iter->current(iter);
760 void *node = tree->node_create(*eptr, tree);
761 if (node == NULL) return 0; // LCOV_EXCL_LINE
762 cx_tree_zero_pointers(node, cx_tree_node_layout(tree));
763 tree->root = node;
764 ins = 1;
765 iter->next(iter);
766 }
767 void *failed;
768 ins += cx_tree_add_iter(iter, n, tree->search, tree->node_create,
769 tree, &failed, tree->root, cx_tree_node_layout(tree));
770 tree->size += ins;
771 if (ins < n) {
772 cxFree(tree->allocator, failed);
773 }
774 return ins;
775 }
776
777 static void *cx_tree_default_find(
778 CxTree *tree,
779 const void *subtree,
780 const void *data,
781 size_t depth
782 ) {
783 if (tree->root == NULL) return NULL; // LCOV_EXCL_LINE
784
785 void *found;
786 if (0 == cx_tree_search_data(
787 subtree,
788 depth,
789 data,
790 tree->search_data,
791 &found,
792 tree->loc_children,
793 tree->loc_next
794 )) {
795 return found;
796 } else {
797 return NULL;
798 }
799 }
800
801 static cx_tree_class cx_tree_default_class = {
802 cx_tree_default_insert_element,
803 cx_tree_default_insert_many,
804 cx_tree_default_find
805 };
806
807 CxTree *cxTreeCreate(const CxAllocator *allocator,
808 cx_tree_node_create_func create_func,
809 cx_tree_search_func search_func,
810 cx_tree_search_data_func search_data_func,
811 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
812 ptrdiff_t loc_prev, ptrdiff_t loc_next
813 ) {
814 if (allocator == NULL) {
815 allocator = cxDefaultAllocator;
816 }
817 assert(create_func != NULL);
818 assert(search_func != NULL);
819 assert(search_data_func != NULL);
820
821 CxTree *tree = cxMalloc(allocator, sizeof(CxTree));
822 if (tree == NULL) return NULL; // LCOV_EXCL_LINE
823
824 tree->cl = &cx_tree_default_class;
825 tree->allocator = allocator;
826 tree->node_create = create_func;
827 tree->search = search_func;
828 tree->search_data = search_data_func;
829 tree->simple_destructor = NULL;
830 tree->advanced_destructor = (cx_destructor_func2) cxFree;
831 tree->destructor_data = (void *) allocator;
832 tree->loc_parent = loc_parent;
833 tree->loc_children = loc_children;
834 tree->loc_last_child = loc_last_child;
835 tree->loc_prev = loc_prev;
836 tree->loc_next = loc_next;
837 tree->root = NULL;
838 tree->size = 0;
839
840 return tree;
841 }
842
843 void cxTreeFree(CxTree *tree) {
844 if (tree == NULL) return;
845 if (tree->root != NULL) {
846 cxTreeClear(tree);
847 }
848 cxFree(tree->allocator, tree);
849 }
850
851 CxTree *cxTreeCreateWrapped(const CxAllocator *allocator, void *root,
852 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
853 ptrdiff_t loc_prev, ptrdiff_t loc_next) {
854 if (allocator == NULL) {
855 allocator = cxDefaultAllocator;
856 }
857 assert(root != NULL);
858
859 CxTree *tree = cxMalloc(allocator, sizeof(CxTree));
860 if (tree == NULL) return NULL; // LCOV_EXCL_LINE
861
862 tree->cl = &cx_tree_default_class;
863 // set the allocator anyway, just in case...
864 tree->allocator = allocator;
865 tree->node_create = NULL;
866 tree->search = NULL;
867 tree->search_data = NULL;
868 tree->simple_destructor = NULL;
869 tree->advanced_destructor = NULL;
870 tree->destructor_data = NULL;
871 tree->loc_parent = loc_parent;
872 tree->loc_children = loc_children;
873 tree->loc_last_child = loc_last_child;
874 tree->loc_prev = loc_prev;
875 tree->loc_next = loc_next;
876 tree->root = root;
877 tree->size = cxTreeSubtreeSize(tree, root);
878 return tree;
879 }
880
881 void cxTreeSetParent(CxTree *tree, void *parent, void *child) {
882 size_t loc_parent = tree->loc_parent;
883 if (tree_parent(child) == NULL) {
884 tree->size++;
885 }
886 cx_tree_link(parent, child, cx_tree_node_layout(tree));
887 }
888
889 void cxTreeAddChildNode(CxTree *tree, void *parent, void *child) {
890 cx_tree_link(parent, child, cx_tree_node_layout(tree));
891 tree->size++;
892 }
893
894 int cxTreeAddChild(CxTree *tree, void *parent, const void *data) {
895 void *node = tree->node_create(data, tree);
896 if (node == NULL) return 1; // LCOV_EXCL_LINE
897 cx_tree_zero_pointers(node, cx_tree_node_layout(tree));
898 cx_tree_link(parent, node, cx_tree_node_layout(tree));
899 tree->size++;
900 return 0;
901 }
902
903 int cxTreeInsert(CxTree *tree, const void *data) {
904 return tree->cl->insert_element(tree, data);
905 }
906
907 size_t cxTreeInsertIter(CxTree *tree, CxIteratorBase *iter, size_t n) {
908 return tree->cl->insert_many(tree, iter, n);
909 }
910
911 size_t cxTreeInsertArray(CxTree *tree, const void *data, size_t elem_size, size_t n) {
912 if (n == 0) return 0;
913 if (n == 1) return 0 == cxTreeInsert(tree, data) ? 1 : 0;
914 CxIterator iter = cxIterator(data, elem_size, n, false);
915 return cxTreeInsertIter(tree, cxIteratorRef(iter), n);
916 }
917
918 void *cxTreeFind( CxTree *tree, const void *data) {
919 return tree->cl->find(tree, tree->root, data, 0);
920 }
921
922 void *cxTreeFindInSubtree(CxTree *tree, const void *data, void *subtree_root, size_t max_depth) {
923 return tree->cl->find(tree, subtree_root, data, max_depth);
924 }
925
926 size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root) {
927 CxTreeVisitor visitor = cx_tree_visitor(
928 subtree_root,
929 tree->loc_children,
930 tree->loc_next
931 );
932 while (cxIteratorValid(visitor)) {
933 cxIteratorNext(visitor);
934 }
935 return visitor.counter;
936 }
937
938 size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root) {
939 CxTreeVisitor visitor = cx_tree_visitor(
940 subtree_root,
941 tree->loc_children,
942 tree->loc_next
943 );
944 while (cxIteratorValid(visitor)) {
945 cxIteratorNext(visitor);
946 }
947 return visitor.depth;
948 }
949
950 size_t cxTreeSize(CxTree *tree) {
951 return tree->size;
952 }
953
954 size_t cxTreeDepth(CxTree *tree) {
955 CxTreeVisitor visitor = cx_tree_visitor(
956 tree->root, tree->loc_children, tree->loc_next
957 );
958 while (cxIteratorValid(visitor)) {
959 cxIteratorNext(visitor);
960 }
961 return visitor.depth;
962 }
963
964 int cxTreeRemoveNode(
965 CxTree *tree,
966 void *node,
967 cx_tree_relink_func relink_func
968 ) {
969 if (node == tree->root) return 1;
970
971 // determine the new parent
972 ptrdiff_t loc_parent = tree->loc_parent;
973 void *new_parent = tree_parent(node);
974
975 // first, unlink from the parent
976 cx_tree_unlink(node, cx_tree_node_layout(tree));
977
978 // then relink each child
979 ptrdiff_t loc_children = tree->loc_children;
980 ptrdiff_t loc_next = tree->loc_next;
981 void *child = tree_children(node);
982 while (child != NULL) {
983 // forcibly set the parent to NULL - we do not use the unlink function
984 // because that would unnecessarily modify the children linked list
985 tree_parent(child) = NULL;
986
987 // update contents, if required
988 if (relink_func != NULL) {
989 relink_func(child, node, new_parent);
990 }
991
992 // link to new parent
993 cx_tree_link(new_parent, child, cx_tree_node_layout(tree));
994
995 // proceed to next child
996 child = tree_next(child);
997 }
998
999 // clear the linked list of the removed node
1000 tree_children(node) = NULL;
1001 ptrdiff_t loc_last_child = tree->loc_last_child;
1002 if (loc_last_child >= 0) tree_last_child(node) = NULL;
1003
1004 // the tree now has one member less
1005 tree->size--;
1006
1007 return 0;
1008 }
1009
1010 void cxTreeRemoveSubtree(CxTree *tree, void *node) {
1011 if (node == tree->root) {
1012 tree->root = NULL;
1013 tree->size = 0;
1014 return;
1015 }
1016 size_t subtree_size = cxTreeSubtreeSize(tree, node);
1017 cx_tree_unlink(node, cx_tree_node_layout(tree));
1018 tree->size -= subtree_size;
1019 }
1020
1021 int cxTreeDestroyNode(
1022 CxTree *tree,
1023 void *node,
1024 cx_tree_relink_func relink_func
1025 ) {
1026 int result = cxTreeRemoveNode(tree, node, relink_func);
1027 if (result == 0) {
1028 if (tree->simple_destructor) {
1029 tree->simple_destructor(node);
1030 }
1031 if (tree->advanced_destructor) {
1032 tree->advanced_destructor(tree->destructor_data, node);
1033 }
1034 return 0;
1035 } else {
1036 return result;
1037 }
1038 }
1039
1040 void cxTreeDestroySubtree(CxTree *tree, void *node) {
1041 cx_tree_unlink(node, cx_tree_node_layout(tree));
1042 CxTreeIterator iter = cx_tree_iterator(
1043 node, true,
1044 tree->loc_children, tree->loc_next
1045 );
1046 cx_foreach(void *, child, iter) {
1047 if (iter.exiting) {
1048 if (tree->simple_destructor) {
1049 tree->simple_destructor(child);
1050 }
1051 if (tree->advanced_destructor) {
1052 tree->advanced_destructor(tree->destructor_data, child);
1053 }
1054 }
1055 }
1056 tree->size -= iter.counter;
1057 if (node == tree->root) {
1058 tree->root = NULL;
1059 }
1060 }
1061
1062 void cxTreeIteratorDispose(CxTreeIterator *iter) {
1063 cxFreeDefault(iter->stack);
1064 iter->stack = NULL;
1065 }
1066
1067 void cxTreeVisitorDispose(CxTreeVisitor *visitor) {
1068 struct cx_tree_visitor_queue_s *q = visitor->queue_next;
1069 while (q != NULL) {
1070 struct cx_tree_visitor_queue_s *next = q->next;
1071 cxFreeDefault(q);
1072 q = next;
1073 }
1074 visitor->queue_next = visitor->queue_last = NULL;
1075 }
1076
1077 CxTreeIterator cxTreeIterateSubtree(CxTree *tree, void *node, bool visit_on_exit) {
1078 return cx_tree_iterator(
1079 node, visit_on_exit,
1080 tree->loc_children, tree->loc_next
1081 );
1082 }
1083
1084 CxTreeVisitor cxTreeVisitSubtree(CxTree *tree, void *node) {
1085 return cx_tree_visitor(
1086 node, tree->loc_children, tree->loc_next
1087 );
1088 }
1089
1090 CxTreeIterator cxTreeIterate(CxTree *tree, bool visit_on_exit) {
1091 return cxTreeIterateSubtree(tree, tree->root, visit_on_exit);
1092 }
1093
1094 CxTreeVisitor cxTreeVisit(CxTree *tree) {
1095 return cxTreeVisitSubtree(tree, tree->root);
1096 }
1097