Mercurial > hg > dbutils / file comparison

comparison: ucx/tree.c

ucx/tree.c

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

Mercurial Repository: dbutils

mercurial