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