802 cx_tree_default_insert_element, |
802 cx_tree_default_insert_element, |
803 cx_tree_default_insert_many, |
803 cx_tree_default_insert_many, |
804 cx_tree_default_find |
804 cx_tree_default_find |
805 }; |
805 }; |
806 |
806 |
807 CxTree *cxTreeCreate( |
807 CxTree *cxTreeCreate(const CxAllocator *allocator, |
808 const CxAllocator *allocator, |
|
809 cx_tree_node_create_func create_func, |
808 cx_tree_node_create_func create_func, |
810 cx_tree_search_func search_func, |
809 cx_tree_search_func search_func, |
811 cx_tree_search_data_func search_data_func, |
810 cx_tree_search_data_func search_data_func, |
812 ptrdiff_t loc_parent, |
811 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child, |
813 ptrdiff_t loc_children, |
812 ptrdiff_t loc_prev, ptrdiff_t loc_next |
814 ptrdiff_t loc_last_child, |
|
815 ptrdiff_t loc_prev, |
|
816 ptrdiff_t loc_next |
|
817 ) { |
813 ) { |
818 if (allocator == NULL) { |
814 if (allocator == NULL) { |
819 allocator = cxDefaultAllocator; |
815 allocator = cxDefaultAllocator; |
820 } |
816 } |
821 assert(create_func != NULL); |
817 assert(create_func != NULL); |
850 cxTreeClear(tree); |
846 cxTreeClear(tree); |
851 } |
847 } |
852 cxFree(tree->allocator, tree); |
848 cxFree(tree->allocator, tree); |
853 } |
849 } |
854 |
850 |
855 CxTree *cxTreeCreateWrapped( |
851 CxTree *cxTreeCreateWrapped(const CxAllocator *allocator, void *root, |
856 const CxAllocator *allocator, |
852 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child, |
857 void *root, |
853 ptrdiff_t loc_prev, ptrdiff_t loc_next) { |
858 ptrdiff_t loc_parent, |
|
859 ptrdiff_t loc_children, |
|
860 ptrdiff_t loc_last_child, |
|
861 ptrdiff_t loc_prev, |
|
862 ptrdiff_t loc_next |
|
863 ) { |
|
864 if (allocator == NULL) { |
854 if (allocator == NULL) { |
865 allocator = cxDefaultAllocator; |
855 allocator = cxDefaultAllocator; |
866 } |
856 } |
867 assert(root != NULL); |
857 assert(root != NULL); |
868 |
858 |
886 tree->root = root; |
876 tree->root = root; |
887 tree->size = cxTreeSubtreeSize(tree, root); |
877 tree->size = cxTreeSubtreeSize(tree, root); |
888 return tree; |
878 return tree; |
889 } |
879 } |
890 |
880 |
891 void cxTreeSetParent( |
881 void cxTreeSetParent(CxTree *tree, void *parent, void *child) { |
892 CxTree *tree, |
|
893 void *parent, |
|
894 void *child |
|
895 ) { |
|
896 size_t loc_parent = tree->loc_parent; |
882 size_t loc_parent = tree->loc_parent; |
897 if (tree_parent(child) == NULL) { |
883 if (tree_parent(child) == NULL) { |
898 tree->size++; |
884 tree->size++; |
899 } |
885 } |
900 cx_tree_link(parent, child, cx_tree_node_layout(tree)); |
886 cx_tree_link(parent, child, cx_tree_node_layout(tree)); |
901 } |
887 } |
902 |
888 |
903 void cxTreeAddChildNode( |
889 void cxTreeAddChildNode(CxTree *tree, void *parent, void *child) { |
904 CxTree *tree, |
|
905 void *parent, |
|
906 void *child |
|
907 ) { |
|
908 cx_tree_link(parent, child, cx_tree_node_layout(tree)); |
890 cx_tree_link(parent, child, cx_tree_node_layout(tree)); |
909 tree->size++; |
891 tree->size++; |
910 } |
892 } |
911 |
893 |
912 int cxTreeAddChild( |
894 int cxTreeAddChild(CxTree *tree, void *parent, const void *data) { |
913 CxTree *tree, |
|
914 void *parent, |
|
915 const void *data) { |
|
916 void *node = tree->node_create(data, tree); |
895 void *node = tree->node_create(data, tree); |
917 if (node == NULL) return 1; |
896 if (node == NULL) return 1; |
918 cx_tree_zero_pointers(node, cx_tree_node_layout(tree)); |
897 cx_tree_zero_pointers(node, cx_tree_node_layout(tree)); |
919 cx_tree_link(parent, node, cx_tree_node_layout(tree)); |
898 cx_tree_link(parent, node, cx_tree_node_layout(tree)); |
920 tree->size++; |
899 tree->size++; |
921 return 0; |
900 return 0; |
|
901 } |
|
902 |
|
903 int cxTreeInsert(CxTree *tree, const void *data) { |
|
904 return tree->cl->insert_element(tree, data); |
|
905 } |
|
906 |
|
907 size_t cxTreeInsertIter(CxTree *tree, CxIteratorBase *iter, size_t n) { |
|
908 return tree->cl->insert_many(tree, iter, n); |
|
909 } |
|
910 |
|
911 size_t cxTreeInsertArray(CxTree *tree, const void *data, size_t elem_size, size_t n) { |
|
912 if (n == 0) return 0; |
|
913 if (n == 1) return 0 == cxTreeInsert(tree, data) ? 1 : 0; |
|
914 CxIterator iter = cxIterator(data, elem_size, n); |
|
915 return cxTreeInsertIter(tree, cxIteratorRef(iter), n); |
|
916 } |
|
917 |
|
918 void *cxTreeFind( CxTree *tree, const void *data) { |
|
919 return tree->cl->find(tree, tree->root, data, 0); |
|
920 } |
|
921 |
|
922 void *cxTreeFindInSubtree(CxTree *tree, const void *data, void *subtree_root, size_t max_depth) { |
|
923 return tree->cl->find(tree, subtree_root, data, max_depth); |
922 } |
924 } |
923 |
925 |
924 size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root) { |
926 size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root) { |
925 CxTreeVisitor visitor = cx_tree_visitor( |
927 CxTreeVisitor visitor = cx_tree_visitor( |
926 subtree_root, |
928 subtree_root, |
941 ); |
943 ); |
942 while (cxIteratorValid(visitor)) { |
944 while (cxIteratorValid(visitor)) { |
943 cxIteratorNext(visitor); |
945 cxIteratorNext(visitor); |
944 } |
946 } |
945 return visitor.depth; |
947 return visitor.depth; |
|
948 } |
|
949 |
|
950 size_t cxTreeSize(CxTree *tree) { |
|
951 return tree->size; |
946 } |
952 } |
947 |
953 |
948 size_t cxTreeDepth(CxTree *tree) { |
954 size_t cxTreeDepth(CxTree *tree) { |
949 CxTreeVisitor visitor = cx_tree_visitor( |
955 CxTreeVisitor visitor = cx_tree_visitor( |
950 tree->root, tree->loc_children, tree->loc_next |
956 tree->root, tree->loc_children, tree->loc_next |
1050 tree->size -= iter.counter; |
1056 tree->size -= iter.counter; |
1051 if (node == tree->root) { |
1057 if (node == tree->root) { |
1052 tree->root = NULL; |
1058 tree->root = NULL; |
1053 } |
1059 } |
1054 } |
1060 } |
|
1061 |
|
1062 void cxTreeIteratorDispose(CxTreeIterator *iter) { |
|
1063 cxFreeDefault(iter->stack); |
|
1064 iter->stack = NULL; |
|
1065 } |
|
1066 |
|
1067 void cxTreeVisitorDispose(CxTreeVisitor *visitor) { |
|
1068 struct cx_tree_visitor_queue_s *q = visitor->queue_next; |
|
1069 while (q != NULL) { |
|
1070 struct cx_tree_visitor_queue_s *next = q->next; |
|
1071 cxFreeDefault(q); |
|
1072 q = next; |
|
1073 } |
|
1074 } |
|
1075 |
|
1076 CxTreeIterator cxTreeIterateSubtree(CxTree *tree, void *node, bool visit_on_exit) { |
|
1077 return cx_tree_iterator( |
|
1078 node, visit_on_exit, |
|
1079 tree->loc_children, tree->loc_next |
|
1080 ); |
|
1081 } |
|
1082 |
|
1083 CxTreeVisitor cxTreeVisitSubtree(CxTree *tree, void *node) { |
|
1084 return cx_tree_visitor( |
|
1085 node, tree->loc_children, tree->loc_next |
|
1086 ); |
|
1087 } |
|
1088 |
|
1089 CxTreeIterator cxTreeIterate(CxTree *tree, bool visit_on_exit) { |
|
1090 return cxTreeIterateSubtree(tree, tree->root, visit_on_exit); |
|
1091 } |
|
1092 |
|
1093 CxTreeVisitor cxTreeVisit(CxTree *tree) { |
|
1094 return cxTreeVisitSubtree(tree, tree->root); |
|
1095 } |