Mercurial > hg > dav / file comparison

comparison: ucx/tree.c

ucx/tree.c

changeset 852
83fdf679df99
parent 816
839fefbdedc7
equal deleted inserted replaced
850:bbe2925eb590 852:83fdf679df99
31 #include "cx/array_list.h" 31 #include "cx/array_list.h"
32 32
33 #include <assert.h> 33 #include <assert.h>
34 34
35 #define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off))) 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) 36 #define tree_parent(node) CX_TREE_PTR(node, loc_parent)
38 #define tree_children(node) CX_TREE_PTR(node, loc_children) 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) 39 #define tree_prev(node) CX_TREE_PTR(node, loc_prev)
40 #define tree_next(node) CX_TREE_PTR(node, loc_next) 40 #define tree_next(node) CX_TREE_PTR(node, loc_next)
41 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
42 void cx_tree_link( 71 void cx_tree_link(
43 void *restrict parent, 72 void *parent,
44 void *restrict node, 73 void *node,
45 ptrdiff_t loc_parent, 74 ptrdiff_t loc_parent,
46 ptrdiff_t loc_children, 75 ptrdiff_t loc_children,
76 ptrdiff_t loc_last_child,
47 ptrdiff_t loc_prev, 77 ptrdiff_t loc_prev,
48 ptrdiff_t loc_next 78 ptrdiff_t loc_next
49 ) { 79 ) {
80 assert(loc_parent >= 0);
81 assert(loc_children >= 0);
82 assert(loc_next >= 0);
83
50 void *current_parent = tree_parent(node); 84 void *current_parent = tree_parent(node);
51 if (current_parent == parent) return; 85 if (current_parent == parent) return;
52 if (current_parent != NULL) { 86 if (current_parent != NULL) {
53 cx_tree_unlink(node, loc_parent, loc_children, 87 cx_tree_unlink(node, cx_tree_ptr_locations);
54 loc_prev, loc_next);
55 } 88 }
56 89
57 if (tree_children(parent) == NULL) { 90 if (tree_children(parent) == NULL) {
58 tree_children(parent) = node; 91 tree_children(parent) = node;
59 } else { 92 if (loc_last_child >= 0) {
60 void *children = tree_children(parent); 93 tree_last_child(parent) = node;
61 tree_prev(children) = node; 94 }
62 tree_next(node) = children; 95 } else {
63 tree_children(parent) = node; 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;
64 } 111 }
65 tree_parent(node) = parent; 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 }
66 } 131 }
67 132
68 void cx_tree_unlink( 133 void cx_tree_unlink(
69 void *node, 134 void *node,
70 ptrdiff_t loc_parent, 135 ptrdiff_t loc_parent,
71 ptrdiff_t loc_children, 136 ptrdiff_t loc_children,
137 ptrdiff_t loc_last_child,
72 ptrdiff_t loc_prev, 138 ptrdiff_t loc_prev,
73 ptrdiff_t loc_next 139 ptrdiff_t loc_next
74 ) { 140 ) {
75 if (tree_parent(node) == NULL) return; 141 if (tree_parent(node) == NULL) return;
76 142
77 void *left = tree_prev(node); 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 }
78 void *right = tree_next(node); 152 void *right = tree_next(node);
79 assert(left == NULL || tree_children(tree_parent(node)) != 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
80 if (left == NULL) { 158 if (left == NULL) {
81 tree_children(tree_parent(node)) = right; 159 tree_children(parent) = right;
82 } else { 160 } else {
83 tree_next(left) = right; 161 tree_next(left) = right;
84 } 162 }
85 if (right != NULL) tree_prev(right) = left; 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
86 tree_parent(node) = NULL; 173 tree_parent(node) = NULL;
87 tree_prev(node) = NULL;
88 tree_next(node) = NULL; 174 tree_next(node) = NULL;
175 if (loc_prev >= 0) {
176 tree_prev(node) = NULL;
177 }
89 } 178 }
90 179
91 int cx_tree_search( 180 int cx_tree_search(
92 void const *root, 181 const void *root,
93 void const *data, 182 size_t depth,
183 const void *node,
94 cx_tree_search_func sfunc, 184 cx_tree_search_func sfunc,
95 void **result, 185 void **result,
96 ptrdiff_t loc_children, 186 ptrdiff_t loc_children,
97 ptrdiff_t loc_next 187 ptrdiff_t loc_next
98 ) { 188 ) {
99 int ret; 189 // help avoiding bugs due to uninitialized memory
190 assert(result != NULL);
100 *result = NULL; 191 *result = NULL;
101 192
102 // shortcut: compare root before doing anything else 193 // remember return value for best match
103 ret = sfunc(root, data); 194 int ret = sfunc(root, node);
104 if (ret < 0) { 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) {
105 return ret; 207 return ret;
106 } else if (ret == 0 || tree_children(root) == NULL) { 208 }
107 *result = (void*)root; 209
108 return ret; 210 // special case: indefinite depth
109 } 211 if (depth == 0) {
110 212 depth = SIZE_MAX;
111 // create a working stack 213 }
112 CX_ARRAY_DECLARE(void const*, work); 214
113 cx_array_initialize(work, 32); 215 // create an iterator
114 216 CxTreeIterator iter = cx_tree_iterator(
115 // add the children of root to the working stack 217 (void*) root, false, loc_children, loc_next
116 { 218 );
117 void *c = tree_children(root); 219
118 while (c != NULL) { 220 // skip root, we already handled it
119 cx_array_simple_add(work, c); 221 cxIteratorNext(iter);
120 c = tree_next(c); 222
121 } 223 // loop through the remaining tree
122 } 224 cx_foreach(void *, elem, iter) {
123 225 // investigate the current node
124 // remember a candidate for adding the data 226 int ret_elem = sfunc(elem, node);
125 // also remember the exact return code from sfunc 227 if (ret_elem == 0) {
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 228 // if found, exit the search
139 *result = (void*) node; 229 *result = (void *) elem;
140 work_size = 0; 230 ret = 0;
141 break; 231 break;
142 } else if (ret > 0) { 232 } else if (ret_elem > 0 && ret_elem < ret) {
143 // if children might contain the data, add them to the stack 233 // new distance is better
144 void *c = tree_children(node); 234 *result = elem;
145 while (c != NULL) { 235 ret = ret_elem;
146 cx_array_simple_add(work, c); 236 } else {
147 c = tree_next(c); 237 // not contained or distance is worse, skip entire subtree
148 } 238 cxTreeIteratorContinue(iter);
149 239 }
150 // remember this node in case no child is suitable 240
151 if (ret_candidate < 0 || ret < ret_candidate) { 241 // when we reached the max depth, skip the subtree
152 candidate = (void *) node; 242 if (iter.depth == depth) {
153 ret_candidate = ret; 243 cxTreeIteratorContinue(iter);
154 } 244 }
155 } 245 }
156 } 246
157 247 // dispose the iterator as we might have exited the loop early
158 // not found, but was there a candidate? 248 cxTreeIteratorDispose(&iter);
159 if (ret != 0 && candidate != NULL) { 249
160 ret = ret_candidate; 250 assert(ret < 0 || *result != NULL);
161 *result = candidate;
162 }
163
164 // free the working queue and return
165 free(work);
166 return ret; 251 return ret;
167 } 252 }
168 253
169 static bool cx_tree_iter_valid(void const *it) { 254 int cx_tree_search_data(
170 struct cx_tree_iterator_s const *iter = it; 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;
171 return iter->node != NULL; 273 return iter->node != NULL;
172 } 274 }
173 275
174 static void *cx_tree_iter_current(void const *it) { 276 static void *cx_tree_iter_current(const void *it) {
175 struct cx_tree_iterator_s const *iter = it; 277 const struct cx_tree_iterator_s *iter = it;
176 return iter->node; 278 return iter->node;
177 } 279 }
178 280
179 static void cx_tree_iter_next(void *it) { 281 static void cx_tree_iter_next(void *it) {
180 struct cx_tree_iterator_s *iter = it; 282 struct cx_tree_iterator_s *iter = it;
181 ptrdiff_t const loc_next = iter->loc_next; 283 ptrdiff_t const loc_next = iter->loc_next;
182 ptrdiff_t const loc_children = iter->loc_children; 284 ptrdiff_t const loc_children = iter->loc_children;
285 // protect us from misuse
286 if (!iter->base.valid(iter)) return;
183 287
184 void *children; 288 void *children;
185 289
186 // check if we are currently exiting or entering nodes 290 // check if we are currently exiting or entering nodes
187 if (iter->exiting) { 291 if (iter->exiting) {
263 CxTreeIterator iter; 367 CxTreeIterator iter;
264 iter.loc_children = loc_children; 368 iter.loc_children = loc_children;
265 iter.loc_next = loc_next; 369 iter.loc_next = loc_next;
266 iter.visit_on_exit = visit_on_exit; 370 iter.visit_on_exit = visit_on_exit;
267 371
268 // allocate stack 372 // initialize members
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; 373 iter.node_next = NULL;
276 iter.counter = 1;
277 iter.depth = 1;
278 iter.stack[0] = root;
279 iter.exiting = false; 374 iter.exiting = false;
280 iter.skip = false; 375 iter.skip = false;
281 376
282 // assign base iterator functions 377 // assign base iterator functions
283 iter.base.mutating = false; 378 iter.base.mutating = false;
285 iter.base.current_impl = NULL; 380 iter.base.current_impl = NULL;
286 iter.base.valid = cx_tree_iter_valid; 381 iter.base.valid = cx_tree_iter_valid;
287 iter.base.next = cx_tree_iter_next; 382 iter.base.next = cx_tree_iter_next;
288 iter.base.current = cx_tree_iter_current; 383 iter.base.current = cx_tree_iter_current;
289 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
290 return iter; 400 return iter;
291 } 401 }
292 402
293 static bool cx_tree_visitor_valid(void const *it) { 403 static bool cx_tree_visitor_valid(const void *it) {
294 struct cx_tree_visitor_s const *iter = it; 404 const struct cx_tree_visitor_s *iter = it;
295 return iter->node != NULL; 405 return iter->node != NULL;
296 } 406 }
297 407
298 static void *cx_tree_visitor_current(void const *it) { 408 static void *cx_tree_visitor_current(const void *it) {
299 struct cx_tree_visitor_s const *iter = it; 409 const struct cx_tree_visitor_s *iter = it;
300 return iter->node; 410 return iter->node;
301 } 411 }
302 412
303 __attribute__((__nonnull__)) 413 cx_attr_nonnull
304 static void cx_tree_visitor_enqueue_siblings( 414 static void cx_tree_visitor_enqueue_siblings(
305 struct cx_tree_visitor_s *iter, void *node, ptrdiff_t loc_next) { 415 struct cx_tree_visitor_s *iter, void *node, ptrdiff_t loc_next) {
306 node = tree_next(node); 416 node = tree_next(node);
307 while (node != NULL) { 417 while (node != NULL) {
308 struct cx_tree_visitor_queue_s *q; 418 struct cx_tree_visitor_queue_s *q;
316 iter->queue_last->next = NULL; 426 iter->queue_last->next = NULL;
317 } 427 }
318 428
319 static void cx_tree_visitor_next(void *it) { 429 static void cx_tree_visitor_next(void *it) {
320 struct cx_tree_visitor_s *iter = it; 430 struct cx_tree_visitor_s *iter = it;
431 // protect us from misuse
432 if (!iter->base.valid(iter)) return;
433
321 ptrdiff_t const loc_next = iter->loc_next; 434 ptrdiff_t const loc_next = iter->loc_next;
322 ptrdiff_t const loc_children = iter->loc_children; 435 ptrdiff_t const loc_children = iter->loc_children;
323 436
324 // add the children of the current node to the queue 437 // add the children of the current node to the queue
325 // unless the skip flag is set 438 // unless the skip flag is set
375 ) { 488 ) {
376 CxTreeVisitor iter; 489 CxTreeVisitor iter;
377 iter.loc_children = loc_children; 490 iter.loc_children = loc_children;
378 iter.loc_next = loc_next; 491 iter.loc_next = loc_next;
379 492
380 // allocate stack 493 // initialize members
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; 494 iter.skip = false;
388 iter.queue_next = NULL; 495 iter.queue_next = NULL;
389 iter.queue_last = NULL; 496 iter.queue_last = NULL;
390 497
391 // assign base iterator functions 498 // assign base iterator functions
394 iter.base.current_impl = NULL; 501 iter.base.current_impl = NULL;
395 iter.base.valid = cx_tree_visitor_valid; 502 iter.base.valid = cx_tree_visitor_valid;
396 iter.base.next = cx_tree_visitor_next; 503 iter.base.next = cx_tree_visitor_next;
397 iter.base.current = cx_tree_visitor_current; 504 iter.base.current = cx_tree_visitor_current;
398 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
399 return iter; 516 return iter;
400 } 517 }
401 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 struct cx_iterator_base_s *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: dav

mercurial