Mercurial > hg > ucx / file comparison

comparison: src/tree.c

src/tree.c

changeset 1681
56e76fbac167
parent 1675
36c0fb2b60b2
equal deleted inserted replaced
1680:1aa21afb8763 1681:56e76fbac167
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 (cxReallocArrayDefault(&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_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.use_dfs = false;
462 ret.loc_children = loc_children;
463 ret.loc_next = loc_next;
499 464
500 // initialize members 465 // initialize members
501 iter.skip = false; 466 ret.skip = false;
502 iter.queue_next = NULL; 467 ret.queue_next = NULL;
503 iter.queue_last = NULL; 468 ret.queue_last = NULL;
504 469
505 // assign base iterator functions 470 // assign base iterator functions
506 iter.base.allow_remove = false; 471 ret.base.allow_remove = false;
507 iter.base.remove = false; 472 ret.base.remove = false;
508 iter.base.current_impl = NULL; 473 ret.base.current_impl = NULL;
509 iter.base.valid = cx_tree_visitor_valid; 474 ret.base.valid = cx_tree_visitor_valid;
510 iter.base.next = cx_tree_visitor_next; 475 ret.base.next = cx_tree_visitor_next;
511 iter.base.current = cx_tree_visitor_current; 476 ret.base.current = cx_tree_visitor_current;
512 477
513 // visit the root node 478 // visit the root node
514 iter.node = root; 479 ret.node = root;
515 if (root != NULL) { 480 if (root != NULL) {
516 iter.counter = 1; 481 ret.counter = 1;
517 iter.depth = 1; 482 ret.depth = 1;
518 } else { 483 } else {
519 iter.counter = 0; 484 ret.counter = 0;
520 iter.depth = 0; 485 ret.depth = 0;
521 } 486 }
522 487
523 return iter; 488 return ret;
524 } 489 }
525 490
526 static void cx_tree_add_link_duplicate( 491 size_t cx_tree_size(void *root, ptrdiff_t loc_children, ptrdiff_t loc_next) {
527 void *original, void *duplicate, 492 CxTreeIterator iter = cx_tree_iterator(root, false, loc_children, loc_next);
493 while (cxIteratorValid(iter)) {
494 cxIteratorNext(iter);
495 }
496 return iter.counter;
497 }
498
499 size_t cx_tree_depth(void *root, ptrdiff_t loc_children, ptrdiff_t loc_next) {
500 CxTreeIterator iter = cx_tree_iterator(root, false, loc_children, loc_next);
501 size_t depth = 0;
502 while (cxIteratorValid(iter)) {
503 if (iter.depth > depth) {
504 depth = iter.depth;
505 }
506 cxIteratorNext(iter);
507 }
508 return depth;
509 }
510
511 CxTree *cxTreeCreate(const CxAllocator *allocator,
512 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, 513 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
529 ptrdiff_t loc_prev, ptrdiff_t loc_next 514 ptrdiff_t loc_prev, ptrdiff_t loc_next) {
530 ) { 515
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) { 516 if (allocator == NULL) {
822 allocator = cxDefaultAllocator; 517 allocator = cxDefaultAllocator;
823 } 518 }
824 assert(create_func != NULL);
825 assert(search_func != NULL);
826 assert(search_data_func != NULL);
827 519
828 CxTree *tree = cxZalloc(allocator, sizeof(CxTree)); 520 CxTree *tree = cxZalloc(allocator, sizeof(CxTree));
829 if (tree == NULL) return NULL; // LCOV_EXCL_LINE 521 if (tree == NULL) return NULL; // LCOV_EXCL_LINE
830
831 tree->cl = &cx_tree_default_class;
832 tree->collection.allocator = allocator; 522 tree->collection.allocator = allocator;
833 tree->node_create = create_func; 523
834 tree->search = search_func; 524 if (elem_size == CX_STORE_POINTERS) {
835 tree->search_data = search_data_func; 525 tree->collection.store_pointer = true;
836 tree->collection.advanced_destructor = (cx_destructor_func2) cxFree; 526 tree->collection.elem_size = sizeof(void*);
837 tree->collection.destructor_data = (void *) allocator; 527 } else {
528 tree->collection.elem_size = elem_size;
529 }
530
531 tree->root = root;
532 tree->node_size = node_size;
838 tree->loc_parent = loc_parent; 533 tree->loc_parent = loc_parent;
839 tree->loc_children = loc_children; 534 tree->loc_children = loc_children;
840 tree->loc_last_child = loc_last_child; 535 tree->loc_last_child = loc_last_child;
841 tree->loc_prev = loc_prev; 536 tree->loc_prev = loc_prev;
842 tree->loc_next = loc_next; 537 tree->loc_next = loc_next;
538 tree->loc_data = loc_data;
539
540 if (root == NULL) {
541 cxSetAdvancedDestructor(tree, cxFree, (void*)allocator);
542 } else {
543 tree->collection.size = cx_tree_size(root, loc_children, loc_next);
544 }
843 545
844 return tree; 546 return tree;
845 } 547 }
846 548
847 void cxTreeFree(CxTree *tree) { 549 void cxTreeFree(CxTree *tree) {
850 cxTreeClear(tree); 552 cxTreeClear(tree);
851 } 553 }
852 cxFree(tree->collection.allocator, tree); 554 cxFree(tree->collection.allocator, tree);
853 } 555 }
854 556
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) { 557 void cxTreeSetParent(CxTree *tree, void *parent, void *child) {
880 size_t loc_parent = tree->loc_parent; 558 size_t loc_parent = tree->loc_parent;
881 if (tree_parent(child) == NULL) { 559 if (tree_parent(child) == NULL) {
882 tree->collection.size++; 560 tree->collection.size++;
883 } 561 }
884 cx_tree_link(parent, child, cx_tree_node_layout(tree)); 562 cx_tree_add(parent, child, tree_layout(tree));
885 } 563 }
886 564
887 void cxTreeAddChildNode(CxTree *tree, void *parent, void *child) { 565 void cxTreeAddNode(CxTree *tree, void *parent, void *child) {
888 cx_tree_link(parent, child, cx_tree_node_layout(tree)); 566 cx_tree_add(parent, child, tree_layout(tree));
889 tree->collection.size++; 567 tree->collection.size++;
890 } 568 }
891 569
892 int cxTreeAddChild(CxTree *tree, void *parent, const void *data) { 570 void *cxTreeAddData(CxTree *tree, void *parent, const void *data) {
893 void *node = tree->node_create(data, tree); 571 void *node = cxZalloc(tree->collection.allocator, tree->node_size);
894 if (node == NULL) return 1; // LCOV_EXCL_LINE 572 if (node == NULL) return NULL; // LCOV_EXCL_LINE
895 cx_tree_zero_pointers(node, cx_tree_node_layout(tree)); 573
896 cx_tree_link(parent, node, cx_tree_node_layout(tree)); 574 char *dst = node;
575 dst += tree->loc_data;
576 const void *src = cxCollectionStoresPointers(tree) ? (const void*)&data : data;
577 memcpy(dst, src, tree->collection.elem_size);
578
579 cx_tree_add(parent, node, tree_layout(tree));
897 tree->collection.size++; 580 tree->collection.size++;
898 return 0; 581 return node;
899 } 582 }
900 583
901 int cxTreeInsert(CxTree *tree, const void *data) { 584 void *cxTreeCreateRoot(CxTree *tree) {
902 return tree->cl->insert_element(tree, data); 585 if (tree->root != NULL) {
903 } 586 return tree->root;
904 587 }
905 size_t cxTreeInsertIter(CxTree *tree, CxIteratorBase *iter, size_t n) { 588
906 return tree->cl->insert_many(tree, iter, n); 589 void *node = cxZalloc(tree->collection.allocator, tree->node_size);
907 } 590 if (node == NULL) return NULL; // LCOV_EXCL_LINE
908 591 tree->root = node;
909 size_t cxTreeInsertArray(CxTree *tree, const void *data, size_t elem_size, size_t n) { 592 tree->collection.size = 1;
910 if (n == 0) return 0; 593 return node;
911 if (n == 1) return 0 == cxTreeInsert(tree, data) ? 1 : 0; 594 }
912 CxIterator iter = cxIterator(data, elem_size, n); 595
913 return cxTreeInsertIter(tree, cxIteratorRef(iter), n); 596 void *cxTreeCreateRootData(CxTree *tree, const void *data) {
914 } 597 if (tree->loc_data < 0) return NULL;
915 598
916 void *cxTreeFind( CxTree *tree, const void *data) { 599 void *node = cxTreeCreateRoot(tree);
917 return tree->cl->find(tree, tree->root, data, 0); 600 if (node == NULL) return NULL; // LCOV_EXCL_LINE
918 } 601
919 602 char *dst = node;
920 void *cxTreeFindInSubtree(CxTree *tree, const void *data, void *subtree_root, size_t max_depth) { 603 dst += tree->loc_data;
921 return tree->cl->find(tree, subtree_root, data, max_depth); 604 const void *src = cxCollectionStoresPointers(tree) ? (const void*)&data : data;
605 memcpy(dst, src, tree->collection.elem_size);
606
607 return node;
608 }
609
610 void *cxTreeSetRoot(CxTree *tree, void *new_root) {
611 void *old_root = tree->root;
612 tree->root = new_root;
613 return old_root;
614 }
615
616 void *cxTreeFindInSubtree(CxTree *tree, const void *data,
617 void *subtree_root, size_t max_depth, bool use_dfs) {
618 if (tree->loc_data < 0 || subtree_root == NULL) {
619 return NULL;
620 }
621
622 CxTreeIterator iter = use_dfs
623 ? cx_tree_iterator(subtree_root, false, tree->loc_children, tree->loc_next)
624 : cx_tree_visitor(subtree_root, tree->loc_children, tree->loc_next);
625
626 cx_foreach(char*, node, iter) {
627 char *node_data = node + tree->loc_data;
628 if (cxCollectionStoresPointers(tree)) {
629 node_data = *(void**)node_data;
630 }
631 if (cx_invoke_compare_func(tree, node_data, data) == 0) {
632 cxTreeIteratorDispose(&iter);
633 return node;
634 }
635 if (iter.depth == max_depth) {
636 cxTreeIteratorContinue(iter);
637 }
638 }
639 return NULL;
640 }
641
642 void *cxTreeFindFastInSubtree(CxTree *tree, const void *data,
643 cx_tree_search_func sfunc, void *root, size_t max_depth) {
644 void *result;
645 int ret = cx_tree_search(root, max_depth, data, sfunc, &result,
646 tree->loc_children, tree->loc_next);
647 if (ret == 0) {
648 return result;
649 } else {
650 return NULL;
651 }
922 } 652 }
923 653
924 size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root) { 654 size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root) {
925 CxTreeVisitor visitor = cx_tree_visitor( 655 if (subtree_root == tree->root) {
926 subtree_root, 656 return tree->collection.size;
927 tree->loc_children, 657 }
928 tree->loc_next 658 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 } 659 }
935 660
936 size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root) { 661 size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root) {
937 CxTreeVisitor visitor = cx_tree_visitor( 662 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 } 663 }
947 664
948 size_t cxTreeSize(CxTree *tree) { 665 size_t cxTreeSize(CxTree *tree) {
949 return tree->collection.size; 666 return tree->collection.size;
950 } 667 }
951 668
952 size_t cxTreeDepth(CxTree *tree) { 669 size_t cxTreeDepth(CxTree *tree) {
953 CxTreeVisitor visitor = cx_tree_visitor( 670 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 } 671 }
961 672
962 int cxTreeRemoveNode( 673 int cxTreeRemoveNode(
963 CxTree *tree, 674 CxTree *tree,
964 void *node, 675 void *node,
969 // determine the new parent 680 // determine the new parent
970 ptrdiff_t loc_parent = tree->loc_parent; 681 ptrdiff_t loc_parent = tree->loc_parent;
971 void *new_parent = tree_parent(node); 682 void *new_parent = tree_parent(node);
972 683
973 // first, unlink from the parent 684 // first, unlink from the parent
974 cx_tree_unlink(node, cx_tree_node_layout(tree)); 685 cx_tree_remove(node, tree_layout(tree));
975 686
976 // then relink each child 687 // then relink each child
977 ptrdiff_t loc_children = tree->loc_children; 688 ptrdiff_t loc_children = tree->loc_children;
978 ptrdiff_t loc_next = tree->loc_next; 689 ptrdiff_t loc_next = tree->loc_next;
979 void *child = tree_children(node); 690 void *child = tree_children(node);
986 if (relink_func != NULL) { 697 if (relink_func != NULL) {
987 relink_func(child, node, new_parent); 698 relink_func(child, node, new_parent);
988 } 699 }
989 700
990 // link to new parent 701 // link to new parent
991 cx_tree_link(new_parent, child, cx_tree_node_layout(tree)); 702 cx_tree_add(new_parent, child, tree_layout(tree));
992 703
993 // proceed to next child 704 // proceed to next child
994 child = tree_next(child); 705 child = tree_next(child);
995 } 706 }
996 707
1010 tree->root = NULL; 721 tree->root = NULL;
1011 tree->collection.size = 0; 722 tree->collection.size = 0;
1012 return; 723 return;
1013 } 724 }
1014 size_t subtree_size = cxTreeSubtreeSize(tree, node); 725 size_t subtree_size = cxTreeSubtreeSize(tree, node);
1015 cx_tree_unlink(node, cx_tree_node_layout(tree)); 726 cx_tree_remove(node, tree_layout(tree));
1016 tree->collection.size -= subtree_size; 727 tree->collection.size -= subtree_size;
1017 } 728 }
1018 729
1019 int cxTreeDestroyNode( 730 int cxTreeDestroyNode(
1020 CxTree *tree, 731 CxTree *tree,
1029 return result; 740 return result;
1030 } 741 }
1031 } 742 }
1032 743
1033 void cxTreeDestroySubtree(CxTree *tree, void *node) { 744 void cxTreeDestroySubtree(CxTree *tree, void *node) {
1034 cx_tree_unlink(node, cx_tree_node_layout(tree)); 745 cx_tree_remove(node, tree_layout(tree));
1035 CxTreeIterator iter = cx_tree_iterator( 746 CxTreeIterator iter = cx_tree_iterator(
1036 node, true, 747 node, true,
1037 tree->loc_children, tree->loc_next 748 tree->loc_children, tree->loc_next
1038 ); 749 );
1039 cx_foreach(void *, child, iter) { 750 cx_foreach(void *, child, iter) {
1046 tree->root = NULL; 757 tree->root = NULL;
1047 } 758 }
1048 } 759 }
1049 760
1050 void cxTreeIteratorDispose(CxTreeIterator *iter) { 761 void cxTreeIteratorDispose(CxTreeIterator *iter) {
1051 cxFreeDefault(iter->stack); 762 if (iter->use_dfs) {
1052 iter->stack = NULL; 763 cxFreeDefault(iter->stack);
1053 } 764 iter->stack = NULL;
1054 765 } else {
1055 void cxTreeVisitorDispose(CxTreeVisitor *visitor) { 766 struct cx_tree_visitor_queue_s *q = iter->queue_next;
1056 struct cx_tree_visitor_queue_s *q = visitor->queue_next; 767 while (q != NULL) {
1057 while (q != NULL) { 768 struct cx_tree_visitor_queue_s *next = q->next;
1058 struct cx_tree_visitor_queue_s *next = q->next; 769 cxFreeDefault(q);
1059 cxFreeDefault(q); 770 q = next;
1060 q = next; 771 }
1061 } 772 iter->queue_next = iter->queue_last = NULL;
1062 visitor->queue_next = visitor->queue_last = NULL; 773 }
1063 } 774 }
1064 775
1065 CxTreeIterator cxTreeIterateSubtree(CxTree *tree, void *node, bool visit_on_exit) { 776 CxTreeIterator cxTreeIterateSubtree(CxTree *tree, void *node, bool visit_on_exit) {
1066 return cx_tree_iterator( 777 return cx_tree_iterator(
1067 node, visit_on_exit, 778 node, visit_on_exit,
1068 tree->loc_children, tree->loc_next 779 tree->loc_children, tree->loc_next
1069 ); 780 );
1070 } 781 }
1071 782
1072 CxTreeVisitor cxTreeVisitSubtree(CxTree *tree, void *node) { 783 CxTreeIterator cxTreeVisitSubtree(CxTree *tree, void *node) {
1073 return cx_tree_visitor( 784 return cx_tree_visitor(
1074 node, tree->loc_children, tree->loc_next 785 node, tree->loc_children, tree->loc_next
1075 ); 786 );
1076 } 787 }
1077 788
1078 CxTreeIterator cxTreeIterate(CxTree *tree, bool visit_on_exit) { 789 CxTreeIterator cxTreeIterate(CxTree *tree, bool visit_on_exit) {
1079 return cxTreeIterateSubtree(tree, tree->root, visit_on_exit); 790 return cxTreeIterateSubtree(tree, tree->root, visit_on_exit);
1080 } 791 }
1081 792
1082 CxTreeVisitor cxTreeVisit(CxTree *tree) { 793 CxTreeIterator cxTreeVisit(CxTree *tree) {
1083 return cxTreeVisitSubtree(tree, tree->root); 794 return cxTreeVisitSubtree(tree, tree->root);
1084 } 795 }

Mercurial Repository: ucx

mercurial