Mercurial > hg > webserver / file comparison

comparison: src/ucx/tree.c

src/ucx/tree.c

changeset 579
e10457d74fe1
equal deleted inserted replaced
578:eb48f716b31c 579:e10457d74fe1
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 = (void *) 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 {
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;
309 cx_tree_iter_search_next:
310 // check if there is a sibling
311 if (iter->exiting) {
312 next = iter->node_next;
313 } else {
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 free(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.mutating = 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 = malloc(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 = malloc(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 = malloc(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 free(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.mutating = 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;
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;
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);
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;
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;
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;
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(
808 const CxAllocator *allocator,
809 cx_tree_node_create_func create_func,
810 cx_tree_search_func search_func,
811 cx_tree_search_data_func search_data_func,
812 ptrdiff_t loc_parent,
813 ptrdiff_t loc_children,
814 ptrdiff_t loc_last_child,
815 ptrdiff_t loc_prev,
816 ptrdiff_t loc_next
817 ) {
818 if (allocator == NULL) {
819 allocator = cxDefaultAllocator;
820 }
821 assert(create_func != NULL);
822 assert(search_func != NULL);
823 assert(search_data_func != NULL);
824
825 CxTree *tree = cxMalloc(allocator, sizeof(CxTree));
826 if (tree == NULL) return NULL;
827
828 tree->cl = &cx_tree_default_class;
829 tree->allocator = allocator;
830 tree->node_create = create_func;
831 tree->search = search_func;
832 tree->search_data = search_data_func;
833 tree->simple_destructor = NULL;
834 tree->advanced_destructor = (cx_destructor_func2) cxFree;
835 tree->destructor_data = (void *) allocator;
836 tree->loc_parent = loc_parent;
837 tree->loc_children = loc_children;
838 tree->loc_last_child = loc_last_child;
839 tree->loc_prev = loc_prev;
840 tree->loc_next = loc_next;
841 tree->root = NULL;
842 tree->size = 0;
843
844 return tree;
845 }
846
847 void cxTreeFree(CxTree *tree) {
848 if (tree == NULL) return;
849 if (tree->root != NULL) {
850 cxTreeClear(tree);
851 }
852 cxFree(tree->allocator, tree);
853 }
854
855 CxTree *cxTreeCreateWrapped(
856 const CxAllocator *allocator,
857 void *root,
858 ptrdiff_t loc_parent,
859 ptrdiff_t loc_children,
860 ptrdiff_t loc_last_child,
861 ptrdiff_t loc_prev,
862 ptrdiff_t loc_next
863 ) {
864 if (allocator == NULL) {
865 allocator = cxDefaultAllocator;
866 }
867 assert(root != NULL);
868
869 CxTree *tree = cxMalloc(allocator, sizeof(CxTree));
870 if (tree == NULL) return NULL;
871
872 tree->cl = &cx_tree_default_class;
873 // set the allocator anyway, just in case...
874 tree->allocator = allocator;
875 tree->node_create = NULL;
876 tree->search = NULL;
877 tree->search_data = NULL;
878 tree->simple_destructor = NULL;
879 tree->advanced_destructor = NULL;
880 tree->destructor_data = NULL;
881 tree->loc_parent = loc_parent;
882 tree->loc_children = loc_children;
883 tree->loc_last_child = loc_last_child;
884 tree->loc_prev = loc_prev;
885 tree->loc_next = loc_next;
886 tree->root = root;
887 tree->size = cxTreeSubtreeSize(tree, root);
888 return tree;
889 }
890
891 void cxTreeSetParent(
892 CxTree *tree,
893 void *parent,
894 void *child
895 ) {
896 size_t loc_parent = tree->loc_parent;
897 if (tree_parent(child) == NULL) {
898 tree->size++;
899 }
900 cx_tree_link(parent, child, cx_tree_node_layout(tree));
901 }
902
903 void cxTreeAddChildNode(
904 CxTree *tree,
905 void *parent,
906 void *child
907 ) {
908 cx_tree_link(parent, child, cx_tree_node_layout(tree));
909 tree->size++;
910 }
911
912 int cxTreeAddChild(
913 CxTree *tree,
914 void *parent,
915 const void *data) {
916 void *node = tree->node_create(data, tree);
917 if (node == NULL) return 1;
918 cx_tree_zero_pointers(node, cx_tree_node_layout(tree));
919 cx_tree_link(parent, node, cx_tree_node_layout(tree));
920 tree->size++;
921 return 0;
922 }
923
924 size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root) {
925 CxTreeVisitor visitor = cx_tree_visitor(
926 subtree_root,
927 tree->loc_children,
928 tree->loc_next
929 );
930 while (cxIteratorValid(visitor)) {
931 cxIteratorNext(visitor);
932 }
933 return visitor.counter;
934 }
935
936 size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root) {
937 CxTreeVisitor visitor = cx_tree_visitor(
938 subtree_root,
939 tree->loc_children,
940 tree->loc_next
941 );
942 while (cxIteratorValid(visitor)) {
943 cxIteratorNext(visitor);
944 }
945 return visitor.depth;
946 }
947
948 size_t cxTreeDepth(CxTree *tree) {
949 CxTreeVisitor visitor = cx_tree_visitor(
950 tree->root, tree->loc_children, tree->loc_next
951 );
952 while (cxIteratorValid(visitor)) {
953 cxIteratorNext(visitor);
954 }
955 return visitor.depth;
956 }
957
958 int cxTreeRemoveNode(
959 CxTree *tree,
960 void *node,
961 cx_tree_relink_func relink_func
962 ) {
963 if (node == tree->root) return 1;
964
965 // determine the new parent
966 ptrdiff_t loc_parent = tree->loc_parent;
967 void *new_parent = tree_parent(node);
968
969 // first, unlink from the parent
970 cx_tree_unlink(node, cx_tree_node_layout(tree));
971
972 // then relink each child
973 ptrdiff_t loc_children = tree->loc_children;
974 ptrdiff_t loc_next = tree->loc_next;
975 void *child = tree_children(node);
976 while (child != NULL) {
977 // forcibly set the parent to NULL - we do not use the unlink function
978 // because that would unnecessarily modify the children linked list
979 tree_parent(child) = NULL;
980
981 // update contents, if required
982 if (relink_func != NULL) {
983 relink_func(child, node, new_parent);
984 }
985
986 // link to new parent
987 cx_tree_link(new_parent, child, cx_tree_node_layout(tree));
988
989 // proceed to next child
990 child = tree_next(child);
991 }
992
993 // clear the linked list of the removed node
994 tree_children(node) = NULL;
995 ptrdiff_t loc_last_child = tree->loc_last_child;
996 if (loc_last_child >= 0) tree_last_child(node) = NULL;
997
998 // the tree now has one member less
999 tree->size--;
1000
1001 return 0;
1002 }
1003
1004 void cxTreeRemoveSubtree(CxTree *tree, void *node) {
1005 if (node == tree->root) {
1006 tree->root = NULL;
1007 tree->size = 0;
1008 return;
1009 }
1010 size_t subtree_size = cxTreeSubtreeSize(tree, node);
1011 cx_tree_unlink(node, cx_tree_node_layout(tree));
1012 tree->size -= subtree_size;
1013 }
1014
1015 int cxTreeDestroyNode(
1016 CxTree *tree,
1017 void *node,
1018 cx_tree_relink_func relink_func
1019 ) {
1020 int result = cxTreeRemoveNode(tree, node, relink_func);
1021 if (result == 0) {
1022 if (tree->simple_destructor) {
1023 tree->simple_destructor(node);
1024 }
1025 if (tree->advanced_destructor) {
1026 tree->advanced_destructor(tree->destructor_data, node);
1027 }
1028 return 0;
1029 } else {
1030 return result;
1031 }
1032 }
1033
1034 void cxTreeDestroySubtree(CxTree *tree, void *node) {
1035 cx_tree_unlink(node, cx_tree_node_layout(tree));
1036 CxTreeIterator iter = cx_tree_iterator(
1037 node, true,
1038 tree->loc_children, tree->loc_next
1039 );
1040 cx_foreach(void *, child, iter) {
1041 if (iter.exiting) {
1042 if (tree->simple_destructor) {
1043 tree->simple_destructor(child);
1044 }
1045 if (tree->advanced_destructor) {
1046 tree->advanced_destructor(tree->destructor_data, child);
1047 }
1048 }
1049 }
1050 tree->size -= iter.counter;
1051 if (node == tree->root) {
1052 tree->root = NULL;
1053 }
1054 }

Mercurial Repository: webserver

mercurial