Mercurial > hg > toolkit / file comparison

comparison: ucx/tree.c

ucx/tree.c

changeset 440
7c4b9cba09ca
parent 324
ce13a778654a
equal deleted inserted replaced
439:bf7084544cb1 440:7c4b9cba09ca
40 #define tree_next(node) CX_TREE_PTR(node, loc_next) 40 #define tree_next(node) CX_TREE_PTR(node, loc_next)
41 41
42 #define cx_tree_ptr_locations \ 42 #define cx_tree_ptr_locations \
43 loc_parent, loc_children, loc_last_child, loc_prev, loc_next 43 loc_parent, loc_children, loc_last_child, loc_prev, loc_next
44 44
45 #define cx_tree_node_layout(tree) \
46 (tree)->loc_parent,\
47 (tree)->loc_children,\
48 (tree)->loc_last_child,\
49 (tree)->loc_prev, \
50 (tree)->loc_next
51
45 static void cx_tree_zero_pointers( 52 static void cx_tree_zero_pointers(
46 void *node, 53 void *node,
47 ptrdiff_t loc_parent, 54 ptrdiff_t loc_parent,
48 ptrdiff_t loc_children, 55 ptrdiff_t loc_children,
49 ptrdiff_t loc_last_child, 56 ptrdiff_t loc_last_child,
50 ptrdiff_t loc_prev, 57 ptrdiff_t loc_prev,
51 ptrdiff_t loc_next 58 ptrdiff_t loc_next
52 ) { 59 ) {
53 tree_parent(node) = NULL; 60 tree_parent(node) = NULL;
54 tree_prev(node) = NULL; 61 if (loc_prev >= 0) {
62 tree_prev(node) = NULL;
63 }
55 tree_next(node) = NULL; 64 tree_next(node) = NULL;
56 tree_children(node) = NULL; 65 tree_children(node) = NULL;
57 if (loc_last_child >= 0) { 66 if (loc_last_child >= 0) {
58 tree_last_child(node) = NULL; 67 tree_last_child(node) = NULL;
59 } 68 }
60 } 69 }
61 70
62 void cx_tree_link( 71 void cx_tree_link(
63 void *restrict parent, 72 void *parent,
64 void *restrict node, 73 void *node,
65 ptrdiff_t loc_parent, 74 ptrdiff_t loc_parent,
66 ptrdiff_t loc_children, 75 ptrdiff_t loc_children,
67 ptrdiff_t loc_last_child, 76 ptrdiff_t loc_last_child,
68 ptrdiff_t loc_prev, 77 ptrdiff_t loc_prev,
69 ptrdiff_t loc_next 78 ptrdiff_t loc_next
70 ) { 79 ) {
80 assert(loc_parent >= 0);
81 assert(loc_children >= 0);
82 assert(loc_next >= 0);
83
71 void *current_parent = tree_parent(node); 84 void *current_parent = tree_parent(node);
72 if (current_parent == parent) return; 85 if (current_parent == parent) return;
73 if (current_parent != NULL) { 86 if (current_parent != NULL) {
74 cx_tree_unlink(node, cx_tree_ptr_locations); 87 cx_tree_unlink(node, cx_tree_ptr_locations);
75 } 88 }
78 tree_children(parent) = node; 91 tree_children(parent) = node;
79 if (loc_last_child >= 0) { 92 if (loc_last_child >= 0) {
80 tree_last_child(parent) = node; 93 tree_last_child(parent) = node;
81 } 94 }
82 } else { 95 } else {
96 void *child;
83 if (loc_last_child >= 0) { 97 if (loc_last_child >= 0) {
84 void *child = tree_last_child(parent); 98 child = tree_last_child(parent);
85 tree_prev(node) = child;
86 tree_next(child) = node;
87 tree_last_child(parent) = node; 99 tree_last_child(parent) = node;
88 } else { 100 } else {
89 void *child = tree_children(parent); 101 child = tree_children(parent);
90 void *next; 102 void *next;
91 while ((next = tree_next(child)) != NULL) { 103 while ((next = tree_next(child)) != NULL) {
92 child = next; 104 child = next;
93 } 105 }
106 }
107 if (loc_prev >= 0) {
94 tree_prev(node) = child; 108 tree_prev(node) = child;
95 tree_next(child) = node; 109 }
96 } 110 tree_next(child) = node;
97 } 111 }
98 tree_parent(node) = parent; 112 tree_parent(node) = parent;
113 }
114
115 static void *cx_tree_node_prev(
116 ptrdiff_t loc_parent,
117 ptrdiff_t loc_children,
118 ptrdiff_t loc_next,
119 const void *node
120 ) {
121 void *parent = tree_parent(node);
122 void *begin = tree_children(parent);
123 if (begin == node) return NULL;
124 const void *cur = begin;
125 const void *next;
126 while (1) {
127 next = tree_next(cur);
128 if (next == node) return (void *) cur;
129 cur = next;
130 }
99 } 131 }
100 132
101 void cx_tree_unlink( 133 void cx_tree_unlink(
102 void *node, 134 void *node,
103 ptrdiff_t loc_parent, 135 ptrdiff_t loc_parent,
106 ptrdiff_t loc_prev, 138 ptrdiff_t loc_prev,
107 ptrdiff_t loc_next 139 ptrdiff_t loc_next
108 ) { 140 ) {
109 if (tree_parent(node) == NULL) return; 141 if (tree_parent(node) == NULL) return;
110 142
111 void *left = tree_prev(node); 143 assert(loc_children >= 0);
144 assert(loc_next >= 0);
145 assert(loc_parent >= 0);
146 void *left;
147 if (loc_prev >= 0) {
148 left = tree_prev(node);
149 } else {
150 left = cx_tree_node_prev(loc_parent, loc_children, loc_next, node);
151 }
112 void *right = tree_next(node); 152 void *right = tree_next(node);
113 void *parent = tree_parent(node); 153 void *parent = tree_parent(node);
114 assert(left == NULL || tree_children(parent) != node); 154 assert(left == NULL || tree_children(parent) != node);
115 assert(right == NULL || loc_last_child < 0 || 155 assert(right == NULL || loc_last_child < 0 ||
116 tree_last_child(parent) != node); 156 tree_last_child(parent) != node);
123 if (right == NULL) { 163 if (right == NULL) {
124 if (loc_last_child >= 0) { 164 if (loc_last_child >= 0) {
125 tree_last_child(parent) = left; 165 tree_last_child(parent) = left;
126 } 166 }
127 } else { 167 } else {
128 tree_prev(right) = left; 168 if (loc_prev >= 0) {
169 tree_prev(right) = left;
170 }
129 } 171 }
130 172
131 tree_parent(node) = NULL; 173 tree_parent(node) = NULL;
132 tree_prev(node) = NULL;
133 tree_next(node) = NULL; 174 tree_next(node) = NULL;
175 if (loc_prev >= 0) {
176 tree_prev(node) = NULL;
177 }
134 } 178 }
135 179
136 int cx_tree_search( 180 int cx_tree_search(
137 const void *root, 181 const void *root,
182 size_t depth,
138 const void *node, 183 const void *node,
139 cx_tree_search_func sfunc, 184 cx_tree_search_func sfunc,
140 void **result, 185 void **result,
141 ptrdiff_t loc_children, 186 ptrdiff_t loc_children,
142 ptrdiff_t loc_next 187 ptrdiff_t loc_next
143 ) { 188 ) {
144 int ret; 189 // help avoiding bugs due to uninitialized memory
190 assert(result != NULL);
145 *result = NULL; 191 *result = NULL;
146 192
147 // shortcut: compare root before doing anything else 193 // remember return value for best match
148 ret = sfunc(root, node); 194 int ret = sfunc(root, node);
149 if (ret < 0) { 195 if (ret < 0) {
196 // not contained, exit
197 return -1;
198 }
199 *result = (void*) root;
200 // if root is already exact match, exit
201 if (ret == 0) {
202 return 0;
203 }
204
205 // when depth is one, we are already done
206 if (depth == 1) {
150 return ret; 207 return ret;
151 } else if (ret == 0 || tree_children(root) == NULL) { 208 }
152 *result = (void*)root; 209
153 return ret; 210 // special case: indefinite depth
154 } 211 if (depth == 0) {
155 212 depth = SIZE_MAX;
156 // create a working stack 213 }
157 CX_ARRAY_DECLARE(const void *, work); 214
158 cx_array_initialize(work, 32); 215 // create an iterator
159 216 CxTreeIterator iter = cx_tree_iterator(
160 // add the children of root to the working stack 217 (void*) root, false, loc_children, loc_next
161 { 218 );
162 void *c = tree_children(root); 219
163 while (c != NULL) { 220 // skip root, we already handled it
164 cx_array_simple_add(work, c); 221 cxIteratorNext(iter);
165 c = tree_next(c); 222
166 } 223 // loop through the remaining tree
167 } 224 cx_foreach(void *, elem, iter) {
168 225 // investigate the current node
169 // remember a candidate for adding the data 226 int ret_elem = sfunc(elem, node);
170 // also remember the exact return code from sfunc 227 if (ret_elem == 0) {
171 void *candidate = (void *) root;
172 int ret_candidate = ret;
173
174 // process the working stack
175 while (work_size > 0) {
176 // pop element
177 const void *elem = work[--work_size];
178
179 // apply the search function
180 ret = sfunc(elem, node);
181
182 if (ret == 0) {
183 // if found, exit the search 228 // if found, exit the search
184 *result = (void *) elem; 229 *result = (void *) elem;
185 work_size = 0; 230 ret = 0;
186 break; 231 break;
187 } else if (ret > 0) { 232 } else if (ret_elem > 0 && ret_elem < ret) {
188 // if children might contain the data, add them to the stack 233 // new distance is better
189 void *c = tree_children(elem); 234 *result = elem;
190 while (c != NULL) { 235 ret = ret_elem;
191 cx_array_simple_add(work, c); 236 } else {
192 c = tree_next(c); 237 // not contained or distance is worse, skip entire subtree
193 } 238 cxTreeIteratorContinue(iter);
194 239 }
195 // remember this node in case no child is suitable 240
196 if (ret < ret_candidate) { 241 // when we reached the max depth, skip the subtree
197 candidate = (void *) elem; 242 if (iter.depth == depth) {
198 ret_candidate = ret; 243 cxTreeIteratorContinue(iter);
199 } 244 }
200 } 245 }
201 } 246
202 247 // dispose the iterator as we might have exited the loop early
203 // not found, but was there a candidate? 248 cxTreeIteratorDispose(&iter);
204 if (ret != 0 && candidate != NULL) { 249
205 ret = ret_candidate; 250 assert(ret < 0 || *result != NULL);
206 *result = candidate;
207 }
208
209 // free the working queue and return
210 free(work);
211 return ret; 251 return ret;
212 } 252 }
213 253
214 int cx_tree_search_data( 254 int cx_tree_search_data(
215 const void *root, 255 const void *root,
256 size_t depth,
216 const void *data, 257 const void *data,
217 cx_tree_search_data_func sfunc, 258 cx_tree_search_data_func sfunc,
218 void **result, 259 void **result,
219 ptrdiff_t loc_children, 260 ptrdiff_t loc_children,
220 ptrdiff_t loc_next 261 ptrdiff_t loc_next
221 ) { 262 ) {
222 // it is basically the same implementation 263 // it is basically the same implementation
223 return cx_tree_search( 264 return cx_tree_search(
224 root, data, 265 root, depth, data,
225 (cx_tree_search_func) sfunc, 266 (cx_tree_search_func) sfunc,
226 result, 267 result,
227 loc_children, loc_next); 268 loc_children, loc_next);
228 } 269 }
229 270
367 static void *cx_tree_visitor_current(const void *it) { 408 static void *cx_tree_visitor_current(const void *it) {
368 const struct cx_tree_visitor_s *iter = it; 409 const struct cx_tree_visitor_s *iter = it;
369 return iter->node; 410 return iter->node;
370 } 411 }
371 412
372 __attribute__((__nonnull__)) 413 cx_attr_nonnull
373 static void cx_tree_visitor_enqueue_siblings( 414 static void cx_tree_visitor_enqueue_siblings(
374 struct cx_tree_visitor_s *iter, void *node, ptrdiff_t loc_next) { 415 struct cx_tree_visitor_s *iter, void *node, ptrdiff_t loc_next) {
375 node = tree_next(node); 416 node = tree_next(node);
376 while (node != NULL) { 417 while (node != NULL) {
377 struct cx_tree_visitor_queue_s *q; 418 struct cx_tree_visitor_queue_s *q;
529 cx_tree_zero_pointers(*cnode, cx_tree_ptr_locations); 570 cx_tree_zero_pointers(*cnode, cx_tree_ptr_locations);
530 571
531 void *match = NULL; 572 void *match = NULL;
532 int result = cx_tree_search( 573 int result = cx_tree_search(
533 root, 574 root,
575 0,
534 *cnode, 576 *cnode,
535 sfunc, 577 sfunc,
536 &match, 578 &match,
537 loc_children, 579 loc_children,
538 loc_next 580 loc_next
593 int result; 635 int result;
594 unsigned int look_around_retries = cx_tree_add_look_around_depth; 636 unsigned int look_around_retries = cx_tree_add_look_around_depth;
595 cx_tree_add_look_around_retry: 637 cx_tree_add_look_around_retry:
596 result = cx_tree_search( 638 result = cx_tree_search(
597 current_node, 639 current_node,
640 0,
598 new_node, 641 new_node,
599 sfunc, 642 sfunc,
600 &match, 643 &match,
601 loc_children, 644 loc_children,
602 loc_next 645 loc_next
679 cfunc, cdata, failed, root, 722 cfunc, cdata, failed, root,
680 loc_parent, loc_children, loc_last_child, 723 loc_parent, loc_children, loc_last_child,
681 loc_prev, loc_next); 724 loc_prev, loc_next);
682 } 725 }
683 726
684 static void cx_tree_default_destructor(CxTree *tree) {
685 if (tree->simple_destructor != NULL || tree->advanced_destructor != NULL) {
686 CxTreeIterator iter = tree->cl->iterator(tree, true);
687 cx_foreach(void *, node, iter) {
688 if (iter.exiting) {
689 if (tree->simple_destructor) {
690 tree->simple_destructor(node);
691 }
692 if (tree->advanced_destructor) {
693 tree->advanced_destructor(tree->destructor_data, node);
694 }
695 }
696 }
697 }
698 cxFree(tree->allocator, tree);
699 }
700
701 static CxTreeIterator cx_tree_default_iterator(
702 CxTree *tree,
703 bool visit_on_exit
704 ) {
705 return cx_tree_iterator(
706 tree->root, visit_on_exit,
707 tree->loc_children, tree->loc_next
708 );
709 }
710
711 static CxTreeVisitor cx_tree_default_visitor(CxTree *tree) {
712 return cx_tree_visitor(tree->root, tree->loc_children, tree->loc_next);
713 }
714
715 static int cx_tree_default_insert_element( 727 static int cx_tree_default_insert_element(
716 CxTree *tree, 728 CxTree *tree,
717 const void *data 729 const void *data
718 ) { 730 ) {
719 void *node; 731 void *node;
763 } 775 }
764 776
765 static void *cx_tree_default_find( 777 static void *cx_tree_default_find(
766 CxTree *tree, 778 CxTree *tree,
767 const void *subtree, 779 const void *subtree,
768 const void *data 780 const void *data,
781 size_t depth
769 ) { 782 ) {
770 if (tree->root == NULL) return NULL; 783 if (tree->root == NULL) return NULL;
771 784
772 void *found; 785 void *found;
773 if (0 == cx_tree_search_data( 786 if (0 == cx_tree_search_data(
774 subtree, 787 subtree,
788 depth,
775 data, 789 data,
776 tree->search_data, 790 tree->search_data,
777 &found, 791 &found,
778 tree->loc_children, 792 tree->loc_children,
779 tree->loc_next 793 tree->loc_next
783 return NULL; 797 return NULL;
784 } 798 }
785 } 799 }
786 800
787 static cx_tree_class cx_tree_default_class = { 801 static cx_tree_class cx_tree_default_class = {
788 cx_tree_default_destructor,
789 cx_tree_default_insert_element, 802 cx_tree_default_insert_element,
790 cx_tree_default_insert_many, 803 cx_tree_default_insert_many,
791 cx_tree_default_find, 804 cx_tree_default_find
792 cx_tree_default_iterator,
793 cx_tree_default_visitor
794 }; 805 };
795 806
796 CxTree *cxTreeCreate( 807 CxTree *cxTreeCreate(
797 const CxAllocator *allocator, 808 const CxAllocator *allocator,
798 cx_tree_node_create_func create_func, 809 cx_tree_node_create_func create_func,
802 ptrdiff_t loc_children, 813 ptrdiff_t loc_children,
803 ptrdiff_t loc_last_child, 814 ptrdiff_t loc_last_child,
804 ptrdiff_t loc_prev, 815 ptrdiff_t loc_prev,
805 ptrdiff_t loc_next 816 ptrdiff_t loc_next
806 ) { 817 ) {
818 if (allocator == NULL) {
819 allocator = cxDefaultAllocator;
820 }
821 assert(create_func != NULL);
822 assert(search_func != NULL);
823 assert(search_data_func != NULL);
824
807 CxTree *tree = cxMalloc(allocator, sizeof(CxTree)); 825 CxTree *tree = cxMalloc(allocator, sizeof(CxTree));
808 if (tree == NULL) return NULL; 826 if (tree == NULL) return NULL;
809 827
810 tree->cl = &cx_tree_default_class; 828 tree->cl = &cx_tree_default_class;
811 tree->allocator = allocator; 829 tree->allocator = allocator;
812 tree->node_create = create_func; 830 tree->node_create = create_func;
813 tree->search = search_func; 831 tree->search = search_func;
814 tree->search_data = search_data_func; 832 tree->search_data = search_data_func;
833 tree->simple_destructor = NULL;
815 tree->advanced_destructor = (cx_destructor_func2) cxFree; 834 tree->advanced_destructor = (cx_destructor_func2) cxFree;
816 tree->destructor_data = (void *) allocator; 835 tree->destructor_data = (void *) allocator;
817 tree->loc_parent = loc_parent; 836 tree->loc_parent = loc_parent;
818 tree->loc_children = loc_children; 837 tree->loc_children = loc_children;
819 tree->loc_last_child = loc_last_child; 838 tree->loc_last_child = loc_last_child;
823 tree->size = 0; 842 tree->size = 0;
824 843
825 return tree; 844 return tree;
826 } 845 }
827 846
847 void cxTreeFree(CxTree *tree) {
848 if (tree == NULL) return;
849 if (tree->root != NULL) {
850 cxTreeClear(tree);
851 }
852 cxFree(tree->allocator, tree);
853 }
854
828 CxTree *cxTreeCreateWrapped( 855 CxTree *cxTreeCreateWrapped(
829 const CxAllocator *allocator, 856 const CxAllocator *allocator,
830 void *root, 857 void *root,
831 ptrdiff_t loc_parent, 858 ptrdiff_t loc_parent,
832 ptrdiff_t loc_children, 859 ptrdiff_t loc_children,
833 ptrdiff_t loc_last_child, 860 ptrdiff_t loc_last_child,
834 ptrdiff_t loc_prev, 861 ptrdiff_t loc_prev,
835 ptrdiff_t loc_next 862 ptrdiff_t loc_next
836 ) { 863 ) {
864 if (allocator == NULL) {
865 allocator = cxDefaultAllocator;
866 }
867 assert(root != NULL);
868
837 CxTree *tree = cxMalloc(allocator, sizeof(CxTree)); 869 CxTree *tree = cxMalloc(allocator, sizeof(CxTree));
838 if (tree == NULL) return NULL; 870 if (tree == NULL) return NULL;
839 871
840 tree->cl = &cx_tree_default_class; 872 tree->cl = &cx_tree_default_class;
841 // set the allocator anyway, just in case... 873 // set the allocator anyway, just in case...
854 tree->root = root; 886 tree->root = root;
855 tree->size = cxTreeSubtreeSize(tree, root); 887 tree->size = cxTreeSubtreeSize(tree, root);
856 return tree; 888 return tree;
857 } 889 }
858 890
891 void cxTreeSetParent(
892 CxTree *tree,
893 void *parent,
894 void *child
895 ) {
896 size_t loc_parent = tree->loc_parent;
897 if (tree_parent(child) == NULL) {
898 tree->size++;
899 }
900 cx_tree_link(parent, child, cx_tree_node_layout(tree));
901 }
902
903 void cxTreeAddChildNode(
904 CxTree *tree,
905 void *parent,
906 void *child
907 ) {
908 cx_tree_link(parent, child, cx_tree_node_layout(tree));
909 tree->size++;
910 }
911
859 int cxTreeAddChild( 912 int cxTreeAddChild(
860 CxTree *tree, 913 CxTree *tree,
861 void *parent, 914 void *parent,
862 const void *data) { 915 const void *data) {
863 void *node = tree->node_create(data, tree); 916 void *node = tree->node_create(data, tree);
891 } 944 }
892 return visitor.depth; 945 return visitor.depth;
893 } 946 }
894 947
895 size_t cxTreeDepth(CxTree *tree) { 948 size_t cxTreeDepth(CxTree *tree) {
896 CxTreeVisitor visitor = tree->cl->visitor(tree); 949 CxTreeVisitor visitor = cx_tree_visitor(
950 tree->root, tree->loc_children, tree->loc_next
951 );
897 while (cxIteratorValid(visitor)) { 952 while (cxIteratorValid(visitor)) {
898 cxIteratorNext(visitor); 953 cxIteratorNext(visitor);
899 } 954 }
900 return visitor.depth; 955 return visitor.depth;
901 } 956 }
902 957
903 int cxTreeRemove( 958 int cxTreeRemoveNode(
904 CxTree *tree, 959 CxTree *tree,
905 void *node, 960 void *node,
906 cx_tree_relink_func relink_func 961 cx_tree_relink_func relink_func
907 ) { 962 ) {
908 if (node == tree->root) return 1; 963 if (node == tree->root) return 1;
954 } 1009 }
955 size_t subtree_size = cxTreeSubtreeSize(tree, node); 1010 size_t subtree_size = cxTreeSubtreeSize(tree, node);
956 cx_tree_unlink(node, cx_tree_node_layout(tree)); 1011 cx_tree_unlink(node, cx_tree_node_layout(tree));
957 tree->size -= subtree_size; 1012 tree->size -= subtree_size;
958 } 1013 }
1014
1015 int cxTreeDestroyNode(
1016 CxTree *tree,
1017 void *node,
1018 cx_tree_relink_func relink_func
1019 ) {
1020 int result = cxTreeRemoveNode(tree, node, relink_func);
1021 if (result == 0) {
1022 if (tree->simple_destructor) {
1023 tree->simple_destructor(node);
1024 }
1025 if (tree->advanced_destructor) {
1026 tree->advanced_destructor(tree->destructor_data, node);
1027 }
1028 return 0;
1029 } else {
1030 return result;
1031 }
1032 }
1033
1034 void cxTreeDestroySubtree(CxTree *tree, void *node) {
1035 cx_tree_unlink(node, cx_tree_node_layout(tree));
1036 CxTreeIterator iter = cx_tree_iterator(
1037 node, true,
1038 tree->loc_children, tree->loc_next
1039 );
1040 cx_foreach(void *, child, iter) {
1041 if (iter.exiting) {
1042 if (tree->simple_destructor) {
1043 tree->simple_destructor(child);
1044 }
1045 if (tree->advanced_destructor) {
1046 tree->advanced_destructor(tree->destructor_data, child);
1047 }
1048 }
1049 }
1050 tree->size -= iter.counter;
1051 if (node == tree->root) {
1052 tree->root = NULL;
1053 }
1054 }

Mercurial Repository: toolkit

mercurial