Mercurial > hg > ucx / file comparison

comparison: src/tree.c

src/tree.c

changeset 1549
72ad8a78378a
parent 1505
ce23605058d9
equal deleted inserted replaced
1548:12315ee158ad 1549:72ad8a78378a
732 if (tree->root == NULL) { 732 if (tree->root == NULL) {
733 node = tree->node_create(data, tree); 733 node = tree->node_create(data, tree);
734 if (node == NULL) return 1; // LCOV_EXCL_LINE 734 if (node == NULL) return 1; // LCOV_EXCL_LINE
735 cx_tree_zero_pointers(node, cx_tree_node_layout(tree)); 735 cx_tree_zero_pointers(node, cx_tree_node_layout(tree));
736 tree->root = node; 736 tree->root = node;
737 tree->size = 1; 737 tree->collection.size = 1;
738 return 0; 738 return 0;
739 } 739 }
740 int result = cx_tree_add(data, tree->search, tree->node_create, 740 int result = cx_tree_add(data, tree->search, tree->node_create,
741 tree, &node, tree->root, cx_tree_node_layout(tree)); 741 tree, &node, tree->root, cx_tree_node_layout(tree));
742 if (0 == result) { 742 if (0 == result) {
743 tree->size++; 743 tree->collection.size++;
744 } else { 744 } else {
745 cxFree(tree->allocator, node); 745 cxFree(tree->collection.allocator, node);
746 } 746 }
747 return result; 747 return result;
748 } 748 }
749 749
750 static size_t cx_tree_default_insert_many( 750 static size_t cx_tree_default_insert_many(
765 iter->next(iter); 765 iter->next(iter);
766 } 766 }
767 void *failed; 767 void *failed;
768 ins += cx_tree_add_iter(iter, n, tree->search, tree->node_create, 768 ins += cx_tree_add_iter(iter, n, tree->search, tree->node_create,
769 tree, &failed, tree->root, cx_tree_node_layout(tree)); 769 tree, &failed, tree->root, cx_tree_node_layout(tree));
770 tree->size += ins; 770 tree->collection.size += ins;
771 if (ins < n) { 771 if (ins < n) {
772 cxFree(tree->allocator, failed); 772 cxFree(tree->collection.allocator, failed);
773 } 773 }
774 return ins; 774 return ins;
775 } 775 }
776 776
777 static void *cx_tree_default_find( 777 static void *cx_tree_default_find(
816 } 816 }
817 assert(create_func != NULL); 817 assert(create_func != NULL);
818 assert(search_func != NULL); 818 assert(search_func != NULL);
819 assert(search_data_func != NULL); 819 assert(search_data_func != NULL);
820 820
821 CxTree *tree = cxMalloc(allocator, sizeof(CxTree)); 821 CxTree *tree = cxZalloc(allocator, sizeof(CxTree));
822 if (tree == NULL) return NULL; // LCOV_EXCL_LINE 822 if (tree == NULL) return NULL; // LCOV_EXCL_LINE
823 823
824 tree->cl = &cx_tree_default_class; 824 tree->cl = &cx_tree_default_class;
825 tree->allocator = allocator; 825 tree->collection.allocator = allocator;
826 tree->node_create = create_func; 826 tree->node_create = create_func;
827 tree->search = search_func; 827 tree->search = search_func;
828 tree->search_data = search_data_func; 828 tree->search_data = search_data_func;
829 tree->simple_destructor = NULL; 829 tree->collection.advanced_destructor = (cx_destructor_func2) cxFree;
830 tree->advanced_destructor = (cx_destructor_func2) cxFree; 830 tree->collection.destructor_data = (void *) allocator;
831 tree->destructor_data = (void *) allocator;
832 tree->loc_parent = loc_parent; 831 tree->loc_parent = loc_parent;
833 tree->loc_children = loc_children; 832 tree->loc_children = loc_children;
834 tree->loc_last_child = loc_last_child; 833 tree->loc_last_child = loc_last_child;
835 tree->loc_prev = loc_prev; 834 tree->loc_prev = loc_prev;
836 tree->loc_next = loc_next; 835 tree->loc_next = loc_next;
837 tree->root = NULL;
838 tree->size = 0;
839 836
840 return tree; 837 return tree;
841 } 838 }
842 839
843 void cxTreeFree(CxTree *tree) { 840 void cxTreeFree(CxTree *tree) {
844 if (tree == NULL) return; 841 if (tree == NULL) return;
845 if (tree->root != NULL) { 842 if (tree->root != NULL) {
846 cxTreeClear(tree); 843 cxTreeClear(tree);
847 } 844 }
848 cxFree(tree->allocator, tree); 845 cxFree(tree->collection.allocator, tree);
849 } 846 }
850 847
851 CxTree *cxTreeCreateWrapped(const CxAllocator *allocator, void *root, 848 CxTree *cxTreeCreateWrapped(const CxAllocator *allocator, void *root,
852 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child, 849 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
853 ptrdiff_t loc_prev, ptrdiff_t loc_next) { 850 ptrdiff_t loc_prev, ptrdiff_t loc_next) {
854 if (allocator == NULL) { 851 if (allocator == NULL) {
855 allocator = cxDefaultAllocator; 852 allocator = cxDefaultAllocator;
856 } 853 }
857 assert(root != NULL); 854 assert(root != NULL);
858 855
859 CxTree *tree = cxMalloc(allocator, sizeof(CxTree)); 856 CxTree *tree = cxZalloc(allocator, sizeof(CxTree));
860 if (tree == NULL) return NULL; // LCOV_EXCL_LINE 857 if (tree == NULL) return NULL; // LCOV_EXCL_LINE
861 858
862 tree->cl = &cx_tree_default_class; 859 tree->cl = &cx_tree_default_class;
863 // set the allocator anyway, just in case... 860 // set the allocator anyway, just in case...
864 tree->allocator = allocator; 861 tree->collection.allocator = allocator;
865 tree->node_create = NULL;
866 tree->search = NULL;
867 tree->search_data = NULL;
868 tree->simple_destructor = NULL;
869 tree->advanced_destructor = NULL;
870 tree->destructor_data = NULL;
871 tree->loc_parent = loc_parent; 862 tree->loc_parent = loc_parent;
872 tree->loc_children = loc_children; 863 tree->loc_children = loc_children;
873 tree->loc_last_child = loc_last_child; 864 tree->loc_last_child = loc_last_child;
874 tree->loc_prev = loc_prev; 865 tree->loc_prev = loc_prev;
875 tree->loc_next = loc_next; 866 tree->loc_next = loc_next;
876 tree->root = root; 867 tree->root = root;
877 tree->size = cxTreeSubtreeSize(tree, root); 868 tree->collection.size = cxTreeSubtreeSize(tree, root);
878 return tree; 869 return tree;
879 } 870 }
880 871
881 void cxTreeSetParent(CxTree *tree, void *parent, void *child) { 872 void cxTreeSetParent(CxTree *tree, void *parent, void *child) {
882 size_t loc_parent = tree->loc_parent; 873 size_t loc_parent = tree->loc_parent;
883 if (tree_parent(child) == NULL) { 874 if (tree_parent(child) == NULL) {
884 tree->size++; 875 tree->collection.size++;
885 } 876 }
886 cx_tree_link(parent, child, cx_tree_node_layout(tree)); 877 cx_tree_link(parent, child, cx_tree_node_layout(tree));
887 } 878 }
888 879
889 void cxTreeAddChildNode(CxTree *tree, void *parent, void *child) { 880 void cxTreeAddChildNode(CxTree *tree, void *parent, void *child) {
890 cx_tree_link(parent, child, cx_tree_node_layout(tree)); 881 cx_tree_link(parent, child, cx_tree_node_layout(tree));
891 tree->size++; 882 tree->collection.size++;
892 } 883 }
893 884
894 int cxTreeAddChild(CxTree *tree, void *parent, const void *data) { 885 int cxTreeAddChild(CxTree *tree, void *parent, const void *data) {
895 void *node = tree->node_create(data, tree); 886 void *node = tree->node_create(data, tree);
896 if (node == NULL) return 1; // LCOV_EXCL_LINE 887 if (node == NULL) return 1; // LCOV_EXCL_LINE
897 cx_tree_zero_pointers(node, cx_tree_node_layout(tree)); 888 cx_tree_zero_pointers(node, cx_tree_node_layout(tree));
898 cx_tree_link(parent, node, cx_tree_node_layout(tree)); 889 cx_tree_link(parent, node, cx_tree_node_layout(tree));
899 tree->size++; 890 tree->collection.size++;
900 return 0; 891 return 0;
901 } 892 }
902 893
903 int cxTreeInsert(CxTree *tree, const void *data) { 894 int cxTreeInsert(CxTree *tree, const void *data) {
904 return tree->cl->insert_element(tree, data); 895 return tree->cl->insert_element(tree, data);
946 } 937 }
947 return visitor.depth; 938 return visitor.depth;
948 } 939 }
949 940
950 size_t cxTreeSize(CxTree *tree) { 941 size_t cxTreeSize(CxTree *tree) {
951 return tree->size; 942 return tree->collection.size;
952 } 943 }
953 944
954 size_t cxTreeDepth(CxTree *tree) { 945 size_t cxTreeDepth(CxTree *tree) {
955 CxTreeVisitor visitor = cx_tree_visitor( 946 CxTreeVisitor visitor = cx_tree_visitor(
956 tree->root, tree->loc_children, tree->loc_next 947 tree->root, tree->loc_children, tree->loc_next
1000 tree_children(node) = NULL; 991 tree_children(node) = NULL;
1001 ptrdiff_t loc_last_child = tree->loc_last_child; 992 ptrdiff_t loc_last_child = tree->loc_last_child;
1002 if (loc_last_child >= 0) tree_last_child(node) = NULL; 993 if (loc_last_child >= 0) tree_last_child(node) = NULL;
1003 994
1004 // the tree now has one member less 995 // the tree now has one member less
1005 tree->size--; 996 tree->collection.size--;
1006 997
1007 return 0; 998 return 0;
1008 } 999 }
1009 1000
1010 void cxTreeRemoveSubtree(CxTree *tree, void *node) { 1001 void cxTreeRemoveSubtree(CxTree *tree, void *node) {
1011 if (node == tree->root) { 1002 if (node == tree->root) {
1012 tree->root = NULL; 1003 tree->root = NULL;
1013 tree->size = 0; 1004 tree->collection.size = 0;
1014 return; 1005 return;
1015 } 1006 }
1016 size_t subtree_size = cxTreeSubtreeSize(tree, node); 1007 size_t subtree_size = cxTreeSubtreeSize(tree, node);
1017 cx_tree_unlink(node, cx_tree_node_layout(tree)); 1008 cx_tree_unlink(node, cx_tree_node_layout(tree));
1018 tree->size -= subtree_size; 1009 tree->collection.size -= subtree_size;
1019 } 1010 }
1020 1011
1021 int cxTreeDestroyNode( 1012 int cxTreeDestroyNode(
1022 CxTree *tree, 1013 CxTree *tree,
1023 void *node, 1014 void *node,
1024 cx_tree_relink_func relink_func 1015 cx_tree_relink_func relink_func
1025 ) { 1016 ) {
1026 int result = cxTreeRemoveNode(tree, node, relink_func); 1017 int result = cxTreeRemoveNode(tree, node, relink_func);
1027 if (result == 0) { 1018 if (result == 0) {
1028 if (tree->simple_destructor) { 1019 cx_invoke_destructor(tree, node);
1029 tree->simple_destructor(node);
1030 }
1031 if (tree->advanced_destructor) {
1032 tree->advanced_destructor(tree->destructor_data, node);
1033 }
1034 return 0; 1020 return 0;
1035 } else { 1021 } else {
1036 return result; 1022 return result;
1037 } 1023 }
1038 } 1024 }
1043 node, true, 1029 node, true,
1044 tree->loc_children, tree->loc_next 1030 tree->loc_children, tree->loc_next
1045 ); 1031 );
1046 cx_foreach(void *, child, iter) { 1032 cx_foreach(void *, child, iter) {
1047 if (iter.exiting) { 1033 if (iter.exiting) {
1048 if (tree->simple_destructor) { 1034 cx_invoke_destructor(tree, child);
1049 tree->simple_destructor(child); 1035 }
1050 } 1036 }
1051 if (tree->advanced_destructor) { 1037 tree->collection.size -= iter.counter;
1052 tree->advanced_destructor(tree->destructor_data, child);
1053 }
1054 }
1055 }
1056 tree->size -= iter.counter;
1057 if (node == tree->root) { 1038 if (node == tree->root) {
1058 tree->root = NULL; 1039 tree->root = NULL;
1059 } 1040 }
1060 } 1041 }
1061 1042

Mercurial Repository: ucx

mercurial