Mercurial > hg > toolkit / file comparison

comparison: ucx/tree.c

ucx/tree.c

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

Mercurial Repository: toolkit

mercurial