src/tree.c

changeset 1426
3a89b31f0724
parent 1319
aa1f580f8f59
child 1429
6e0c3a8a914a
equal deleted inserted replaced
1425:83284b289430 1426:3a89b31f0724
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 }

mercurial