444 |
459 |
445 return iter; |
460 return iter; |
446 } |
461 } |
447 |
462 |
448 static void cx_tree_add_link_duplicate( |
463 static void cx_tree_add_link_duplicate( |
449 void **root, void *original, void *duplicate, |
464 void *original, void *duplicate, |
450 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child, |
465 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child, |
451 ptrdiff_t loc_prev, ptrdiff_t loc_next |
466 ptrdiff_t loc_prev, ptrdiff_t loc_next |
452 ) { |
467 ) { |
453 cx_tree_zero_pointers(duplicate, cx_tree_ptr_locations); |
|
454 void *shared_parent = tree_parent(original); |
468 void *shared_parent = tree_parent(original); |
455 if (shared_parent == NULL) { |
469 if (shared_parent == NULL) { |
456 cx_tree_link(duplicate, original, cx_tree_ptr_locations); |
470 cx_tree_link(original, duplicate, cx_tree_ptr_locations); |
457 *root = duplicate; |
|
458 } else { |
471 } else { |
459 cx_tree_link(shared_parent, duplicate, cx_tree_ptr_locations); |
472 cx_tree_link(shared_parent, duplicate, cx_tree_ptr_locations); |
460 } |
473 } |
461 } |
474 } |
462 |
475 |
463 void *cx_tree_add( |
476 static void cx_tree_add_link_new( |
|
477 void *parent, void *node, cx_tree_search_func sfunc, |
|
478 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child, |
|
479 ptrdiff_t loc_prev, ptrdiff_t loc_next |
|
480 ) { |
|
481 // check the current children one by one, |
|
482 // if they could be children of the new node |
|
483 void *child = tree_children(parent); |
|
484 while (child != NULL) { |
|
485 void *next = tree_next(child); |
|
486 |
|
487 if (sfunc(node, child) > 0) { |
|
488 // the sibling could be a child -> re-link |
|
489 cx_tree_link(node, child, cx_tree_ptr_locations); |
|
490 } |
|
491 |
|
492 child = next; |
|
493 } |
|
494 |
|
495 // add new node as new child |
|
496 cx_tree_link(parent, node, cx_tree_ptr_locations); |
|
497 } |
|
498 |
|
499 int cx_tree_add( |
464 void const *src, |
500 void const *src, |
465 cx_tree_search_func sfunc, |
501 cx_tree_search_func sfunc, |
466 cx_tree_node_create_func cfunc, |
502 cx_tree_node_create_func cfunc, |
467 void *cdata, |
503 void *cdata, |
468 void **root, |
504 void **cnode, |
|
505 void *root, |
469 ptrdiff_t loc_parent, |
506 ptrdiff_t loc_parent, |
470 ptrdiff_t loc_children, |
507 ptrdiff_t loc_children, |
471 ptrdiff_t loc_last_child, |
508 ptrdiff_t loc_last_child, |
472 ptrdiff_t loc_prev, |
509 ptrdiff_t loc_prev, |
473 ptrdiff_t loc_next |
510 ptrdiff_t loc_next |
474 ) { |
511 ) { |
475 if (*root == NULL) { |
512 *cnode = cfunc(src, cdata); |
476 void *node = cfunc(src, NULL, cdata); |
513 if (*cnode == NULL) return 1; |
477 if (node == NULL) return NULL; |
514 cx_tree_zero_pointers(*cnode, cx_tree_ptr_locations); |
478 cx_tree_zero_pointers(node, cx_tree_ptr_locations); |
|
479 *root = node; |
|
480 return node; |
|
481 } |
|
482 |
515 |
483 void *match = NULL; |
516 void *match = NULL; |
484 int result = cx_tree_search( |
517 int result = cx_tree_search( |
485 *root, |
518 root, |
486 src, |
519 *cnode, |
487 sfunc, |
520 sfunc, |
488 &match, |
521 &match, |
489 loc_children, |
522 loc_children, |
490 loc_next |
523 loc_next |
491 ); |
524 ); |
492 |
525 |
493 void *node; |
|
494 if (result < 0) { |
526 if (result < 0) { |
495 // new node is created as new parent |
527 // node does not fit into the tree - return non-zero value |
496 node = cfunc(src, NULL, cdata); |
528 return 1; |
497 if (node == NULL) return NULL; |
|
498 cx_tree_zero_pointers(node, cx_tree_ptr_locations); |
|
499 cx_tree_link(node, *root, cx_tree_ptr_locations); |
|
500 *root = node; |
|
501 } else if (result == 0) { |
529 } else if (result == 0) { |
502 // data already found in the tree, let cfunc decide |
530 // data already found in the tree, link duplicate |
503 node = cfunc(src, match, cdata); |
531 cx_tree_add_link_duplicate(match, *cnode, cx_tree_ptr_locations); |
504 if (node == NULL) return NULL; |
532 } else { |
505 if (node != match) { |
533 // closest match found, add new node |
506 cx_tree_add_link_duplicate( |
534 cx_tree_add_link_new(match, *cnode, sfunc, cx_tree_ptr_locations); |
507 root, match, node, cx_tree_ptr_locations); |
535 } |
508 } |
536 |
509 } else { |
537 return 0; |
510 // closest match found, add new node as child |
|
511 node = cfunc(src, NULL, cdata); |
|
512 if (node == NULL) return NULL; |
|
513 cx_tree_zero_pointers(node, cx_tree_ptr_locations); |
|
514 cx_tree_link(match, node, cx_tree_ptr_locations); |
|
515 } |
|
516 |
|
517 return node; |
|
518 } |
538 } |
519 |
539 |
520 unsigned int cx_tree_add_look_around_depth = 3; |
540 unsigned int cx_tree_add_look_around_depth = 3; |
521 |
541 |
522 size_t cx_tree_add_iter( |
542 size_t cx_tree_add_iter( |
523 struct cx_iterator_base_s *iter, |
543 struct cx_iterator_base_s *iter, |
524 cx_tree_search_func sfunc, |
544 cx_tree_search_func sfunc, |
525 cx_tree_node_create_func cfunc, |
545 cx_tree_node_create_func cfunc, |
526 void *cdata, |
546 void *cdata, |
527 void **root, |
547 void **failed, |
|
548 void *root, |
528 ptrdiff_t loc_parent, |
549 ptrdiff_t loc_parent, |
529 ptrdiff_t loc_children, |
550 ptrdiff_t loc_children, |
530 ptrdiff_t loc_last_child, |
551 ptrdiff_t loc_last_child, |
531 ptrdiff_t loc_prev, |
552 ptrdiff_t loc_prev, |
532 ptrdiff_t loc_next |
553 ptrdiff_t loc_next |
533 ) { |
554 ) { |
|
555 // erase the failed pointer |
|
556 *failed = NULL; |
|
557 |
534 // iter not valid? cancel... |
558 // iter not valid? cancel... |
535 if (!iter->valid(iter)) return 0; |
559 if (!iter->valid(iter)) return 0; |
536 |
560 |
537 size_t processed = 0; |
561 size_t processed = 0; |
538 void *current_node = *root; |
562 void *current_node = root; |
539 void *elem; |
563 void const *elem; |
540 |
|
541 // if there is no root, yet - process the first node from the iter |
|
542 // as the new root node |
|
543 if (current_node == NULL) { |
|
544 elem = *(void **) (iter->current(iter)); |
|
545 // no node in tree, yet - add a new one |
|
546 current_node = cfunc(elem, NULL, cdata); |
|
547 // node creation failed - stop processing |
|
548 if (current_node == NULL) return 0; |
|
549 cx_tree_zero_pointers(current_node, cx_tree_ptr_locations); |
|
550 *root = current_node; |
|
551 processed++; |
|
552 iter->next(iter); |
|
553 } |
|
554 |
564 |
555 for (void **eptr; |
565 for (void **eptr; |
556 iter->valid(iter) && (eptr = iter->current(iter)) != NULL; |
566 iter->valid(iter) && (eptr = iter->current(iter)) != NULL; |
557 iter->next(iter)) { |
567 iter->next(iter)) { |
558 elem = *eptr; |
568 elem = *eptr; |
|
569 |
|
570 // create the new node |
|
571 void *new_node = cfunc(elem, cdata); |
|
572 if (new_node == NULL) return processed; |
|
573 cx_tree_zero_pointers(new_node, cx_tree_ptr_locations); |
559 |
574 |
560 // start searching from current node |
575 // start searching from current node |
561 void *match; |
576 void *match; |
562 int result; |
577 int result; |
563 unsigned int look_around_retries = cx_tree_add_look_around_depth; |
578 unsigned int look_around_retries = cx_tree_add_look_around_depth; |
564 cx_tree_add_look_around_retry: |
579 cx_tree_add_look_around_retry: |
565 result = cx_tree_search( |
580 result = cx_tree_search( |
566 current_node, |
581 current_node, |
567 elem, |
582 new_node, |
568 sfunc, |
583 sfunc, |
569 &match, |
584 &match, |
570 loc_children, |
585 loc_children, |
571 loc_next |
586 loc_next |
572 ); |
587 ); |
573 |
588 |
574 void *node; |
|
575 if (result < 0) { |
589 if (result < 0) { |
576 // traverse upwards and try to find better parents |
590 // traverse upwards and try to find better parents |
577 void *parent = tree_parent(current_node); |
591 void *parent = tree_parent(current_node); |
578 if (parent != NULL) { |
592 if (parent != NULL) { |
579 if (look_around_retries > 0) { |
593 if (look_around_retries > 0) { |
580 look_around_retries--; |
594 look_around_retries--; |
581 current_node = parent; |
595 current_node = parent; |
582 } else { |
596 } else { |
583 // look around retries exhausted, start from the root |
597 // look around retries exhausted, start from the root |
584 current_node = *root; |
598 current_node = root; |
585 } |
599 } |
586 goto cx_tree_add_look_around_retry; |
600 goto cx_tree_add_look_around_retry; |
587 } else { |
601 } else { |
588 // no parents. so we (try to) create a new root node |
602 // no parents. so we failed |
589 void *new_root = cfunc(elem, NULL, cdata); |
603 *failed = new_node; |
590 if (new_root == NULL) return processed; |
604 return processed; |
591 cx_tree_zero_pointers(new_root, cx_tree_ptr_locations); |
|
592 cx_tree_link(new_root, current_node, cx_tree_ptr_locations); |
|
593 current_node = new_root; |
|
594 *root = new_root; |
|
595 } |
605 } |
596 } else if (result == 0) { |
606 } else if (result == 0) { |
597 // data already found in the tree, let cfunc decide |
607 // data already found in the tree, link duplicate |
598 node = cfunc(elem, match, cdata); |
608 cx_tree_add_link_duplicate(match, new_node, cx_tree_ptr_locations); |
599 if (node == NULL) return processed; |
609 // but stick with the original match, in case we needed a new root |
600 if (node != match) { |
610 current_node = match; |
601 cx_tree_add_link_duplicate( |
|
602 root, match, node, cx_tree_ptr_locations); |
|
603 } |
|
604 current_node = node; |
|
605 } else { |
611 } else { |
606 // closest match found, add new node as child |
612 // closest match found, add new node as child |
607 node = cfunc(elem, NULL, cdata); |
613 cx_tree_add_link_new(match, new_node, sfunc, |
608 if (node == NULL) return processed; |
614 cx_tree_ptr_locations); |
609 cx_tree_zero_pointers(node, cx_tree_ptr_locations); |
|
610 cx_tree_link(match, node, cx_tree_ptr_locations); |
|
611 // but make the match current and not the new node |
|
612 // (usually saves one traversal when a lot of siblings are added) |
|
613 current_node = match; |
615 current_node = match; |
614 } |
616 } |
615 |
617 |
616 processed++; |
618 processed++; |
617 } |
619 } |
623 size_t num, |
625 size_t num, |
624 size_t elem_size, |
626 size_t elem_size, |
625 cx_tree_search_func sfunc, |
627 cx_tree_search_func sfunc, |
626 cx_tree_node_create_func cfunc, |
628 cx_tree_node_create_func cfunc, |
627 void *cdata, |
629 void *cdata, |
628 void **root, |
630 void **failed, |
|
631 void *root, |
629 ptrdiff_t loc_parent, |
632 ptrdiff_t loc_parent, |
630 ptrdiff_t loc_children, |
633 ptrdiff_t loc_children, |
631 ptrdiff_t loc_last_child, |
634 ptrdiff_t loc_last_child, |
632 ptrdiff_t loc_prev, |
635 ptrdiff_t loc_prev, |
633 ptrdiff_t loc_next |
636 ptrdiff_t loc_next |
634 ) { |
637 ) { |
|
638 // erase failed pointer |
|
639 *failed = NULL; |
|
640 |
635 // super special case: zero elements |
641 // super special case: zero elements |
636 if (num == 0) { |
642 if (num == 0) { |
637 return 0; |
643 return 0; |
638 } |
644 } |
639 |
645 |
640 // special case: one element does not need an iterator |
646 // special case: one element does not need an iterator |
641 if (num == 1) { |
647 if (num == 1) { |
642 if (NULL != cx_tree_add( |
648 void *node; |
643 src, sfunc, cfunc, cdata, root, |
649 if (0 == cx_tree_add( |
|
650 src, sfunc, cfunc, cdata, &node, root, |
644 loc_parent, loc_children, loc_last_child, |
651 loc_parent, loc_children, loc_last_child, |
645 loc_prev, loc_next)) { |
652 loc_prev, loc_next)) { |
646 return 1; |
653 return 1; |
647 } else { |
654 } else { |
|
655 *failed = node; |
648 return 0; |
656 return 0; |
649 } |
657 } |
650 } |
658 } |
651 |
659 |
652 // otherwise, create iterator and hand over to other function |
660 // otherwise, create iterator and hand over to other function |
653 CxIterator iter = cxIterator(src, elem_size, num); |
661 CxIterator iter = cxIterator(src, elem_size, num); |
654 return cx_tree_add_iter(cxIteratorRef(iter), sfunc, cfunc, cdata, root, |
662 return cx_tree_add_iter(cxIteratorRef(iter), sfunc, |
|
663 cfunc, cdata, failed, root, |
655 loc_parent, loc_children, loc_last_child, |
664 loc_parent, loc_children, loc_last_child, |
656 loc_prev, loc_next); |
665 loc_prev, loc_next); |
657 } |
666 } |
658 |
667 |