comparison: src/cx/tree.h
src/cx/tree.h
- changeset 894
- 89cd8dfdc3c2
- parent 893
- 0a2b328f5b91
- child 895
- ea1ac0e8225c
equal
deleted
inserted
replaced
| 893:0a2b328f5b91 | 894:89cd8dfdc3c2 |
|---|---|
| 36 #ifndef UCX_TREE_H | 36 #ifndef UCX_TREE_H |
| 37 #define UCX_TREE_H | 37 #define UCX_TREE_H |
| 38 | 38 |
| 39 #include "common.h" | 39 #include "common.h" |
| 40 | 40 |
| 41 #include "iterator.h" | 41 #include "collection.h" |
| 42 | 42 |
| 43 #ifdef __cplusplus | 43 #ifdef __cplusplus |
| 44 extern "C" { | 44 extern "C" { |
| 45 #endif | 45 #endif |
| 46 | 46 |
| 655 ptrdiff_t loc_last_child, | 655 ptrdiff_t loc_last_child, |
| 656 ptrdiff_t loc_prev, | 656 ptrdiff_t loc_prev, |
| 657 ptrdiff_t loc_next | 657 ptrdiff_t loc_next |
| 658 ); | 658 ); |
| 659 | 659 |
| 660 | |
| 661 /** | |
| 662 * Tree class type. | |
| 663 */ | |
| 664 typedef struct cx_tree_class_s cx_tree_class; | |
| 665 | |
| 666 /** | |
| 667 * Structure for holding the base data of a tree. | |
| 668 */ | |
| 669 struct cx_tree_s { | |
| 670 /** | |
| 671 * The tree class definition. | |
| 672 */ | |
| 673 const cx_tree_class *cl; | |
| 674 | |
| 675 /** | |
| 676 * A function to create new nodes. | |
| 677 */ | |
| 678 cx_tree_node_create_func node_create; | |
| 679 | |
| 680 /** | |
| 681 * The pointer to additional data that is passed to the create function. | |
| 682 */ | |
| 683 void *create_data; | |
| 684 | |
| 685 /** | |
| 686 * An optional simple destructor for the tree nodes. | |
| 687 */ | |
| 688 cx_destructor_func simple_destructor; | |
| 689 | |
| 690 /** | |
| 691 * An optional advanced destructor for the tree nodes. | |
| 692 */ | |
| 693 cx_destructor_func2 advanced_destructor; | |
| 694 | |
| 695 /** | |
| 696 * The pointer to additional data that is passed to the advanced destructor. | |
| 697 */ | |
| 698 void *destructor_data; | |
| 699 | |
| 700 /** | |
| 701 * A function to compare two nodes. | |
| 702 */ | |
| 703 cx_tree_search_func search; | |
| 704 | |
| 705 /** | |
| 706 * The total size of a node, including the element size. | |
| 707 */ | |
| 708 size_t node_size; | |
| 709 | |
| 710 /** | |
| 711 * The number of currently stored elements. | |
| 712 */ | |
| 713 size_t size; | |
| 714 }; | |
| 715 | |
| 716 /** | |
| 717 * The class definition for arbitrary trees. | |
| 718 */ | |
| 719 struct cx_tree_class_s { | |
| 720 /** | |
| 721 * Destructor function. | |
| 722 * | |
| 723 * Implementations SHALL invoke the node destructor functions if provided | |
| 724 * and SHALL deallocate the tree memory. | |
| 725 */ | |
| 726 void (*destructor)(struct cx_tree_s *); | |
| 727 | |
| 728 /** | |
| 729 * Member function for inserting a single element. | |
| 730 * | |
| 731 * Implementations SHALL NOT simply invoke \p insert_many as this comes | |
| 732 * with too much overhead. | |
| 733 */ | |
| 734 int (*insert_element)( | |
| 735 struct cx_tree_s *tree, | |
| 736 const void *data | |
| 737 ); | |
| 738 | |
| 739 /** | |
| 740 * Member function for inserting multiple elements. | |
| 741 * | |
| 742 * Implementations SHALL avoid to perform a full search in the tree for | |
| 743 * every element even though the source data MAY be unsorted. | |
| 744 */ | |
| 745 size_t (*insert_many)( | |
| 746 struct cx_tree_s *tree, | |
| 747 struct cx_iterator_base_s *iter, | |
| 748 size_t n | |
| 749 ); | |
| 750 | |
| 751 /** | |
| 752 * Member function for finding a node. | |
| 753 */ | |
| 754 void *(*find)( | |
| 755 struct cx_tree_s *tree, | |
| 756 const void *data | |
| 757 ); | |
| 758 | |
| 759 /** | |
| 760 * Member function for creating an iterator for the tree. | |
| 761 */ | |
| 762 CxTreeIterator (*iterator)( | |
| 763 struct cx_tree_s *tree, | |
| 764 bool visit_on_exit | |
| 765 ); | |
| 766 | |
| 767 /** | |
| 768 * Member function for creating a visitor for the tree. | |
| 769 */ | |
| 770 CxTreeVisitor (*visitor)(struct cx_tree_s *tree); | |
| 771 }; | |
| 772 | |
| 773 /** | |
| 774 * Common type for all tree implementations. | |
| 775 */ | |
| 776 typedef struct cx_tree_s CxTree; | |
| 777 | |
| 660 #ifdef __cplusplus | 778 #ifdef __cplusplus |
| 661 } // extern "C" | 779 } // extern "C" |
| 662 #endif | 780 #endif |
| 663 | 781 |
| 664 #endif //UCX_TREE_H | 782 #endif //UCX_TREE_H |
