comparison: src/tree.c
src/tree.c
- changeset 890
- 54565fd74e74
- parent 871
- e29c1f96646d
- child 893
- 0a2b328f5b91
equal
deleted
inserted
replaced
| 889:f549fd9fbd8f | 890:54565fd74e74 |
|---|---|
| 132 tree_prev(node) = NULL; | 132 tree_prev(node) = NULL; |
| 133 tree_next(node) = NULL; | 133 tree_next(node) = NULL; |
| 134 } | 134 } |
| 135 | 135 |
| 136 int cx_tree_search( | 136 int cx_tree_search( |
| 137 void const *root, | 137 const void *root, |
| 138 void const *node, | 138 const void *node, |
| 139 cx_tree_search_func sfunc, | 139 cx_tree_search_func sfunc, |
| 140 void **result, | 140 void **result, |
| 141 ptrdiff_t loc_children, | 141 ptrdiff_t loc_children, |
| 142 ptrdiff_t loc_next | 142 ptrdiff_t loc_next |
| 143 ) { | 143 ) { |
| 152 *result = (void*)root; | 152 *result = (void*)root; |
| 153 return ret; | 153 return ret; |
| 154 } | 154 } |
| 155 | 155 |
| 156 // create a working stack | 156 // create a working stack |
| 157 CX_ARRAY_DECLARE(void const*, work); | 157 CX_ARRAY_DECLARE(const void *, work); |
| 158 cx_array_initialize(work, 32); | 158 cx_array_initialize(work, 32); |
| 159 | 159 |
| 160 // add the children of root to the working stack | 160 // add the children of root to the working stack |
| 161 { | 161 { |
| 162 void *c = tree_children(root); | 162 void *c = tree_children(root); |
| 172 int ret_candidate = ret; | 172 int ret_candidate = ret; |
| 173 | 173 |
| 174 // process the working stack | 174 // process the working stack |
| 175 while (work_size > 0) { | 175 while (work_size > 0) { |
| 176 // pop element | 176 // pop element |
| 177 void const *elem = work[--work_size]; | 177 const void *elem = work[--work_size]; |
| 178 | 178 |
| 179 // apply the search function | 179 // apply the search function |
| 180 ret = sfunc(elem, node); | 180 ret = sfunc(elem, node); |
| 181 | 181 |
| 182 if (ret == 0) { | 182 if (ret == 0) { |
| 210 free(work); | 210 free(work); |
| 211 return ret; | 211 return ret; |
| 212 } | 212 } |
| 213 | 213 |
| 214 int cx_tree_search_data( | 214 int cx_tree_search_data( |
| 215 void const *root, | 215 const void *root, |
| 216 void const *data, | 216 const void *data, |
| 217 cx_tree_search_data_func sfunc, | 217 cx_tree_search_data_func sfunc, |
| 218 void **result, | 218 void **result, |
| 219 ptrdiff_t loc_children, | 219 ptrdiff_t loc_children, |
| 220 ptrdiff_t loc_next | 220 ptrdiff_t loc_next |
| 221 ) { | 221 ) { |
| 225 (cx_tree_search_func) sfunc, | 225 (cx_tree_search_func) sfunc, |
| 226 result, | 226 result, |
| 227 loc_children, loc_next); | 227 loc_children, loc_next); |
| 228 } | 228 } |
| 229 | 229 |
| 230 static bool cx_tree_iter_valid(void const *it) { | 230 static bool cx_tree_iter_valid(const void *it) { |
| 231 struct cx_tree_iterator_s const *iter = it; | 231 const struct cx_tree_iterator_s *iter = it; |
| 232 return iter->node != NULL; | 232 return iter->node != NULL; |
| 233 } | 233 } |
| 234 | 234 |
| 235 static void *cx_tree_iter_current(void const *it) { | 235 static void *cx_tree_iter_current(const void *it) { |
| 236 struct cx_tree_iterator_s const *iter = it; | 236 const struct cx_tree_iterator_s *iter = it; |
| 237 return iter->node; | 237 return iter->node; |
| 238 } | 238 } |
| 239 | 239 |
| 240 static void cx_tree_iter_next(void *it) { | 240 static void cx_tree_iter_next(void *it) { |
| 241 struct cx_tree_iterator_s *iter = it; | 241 struct cx_tree_iterator_s *iter = it; |
| 349 iter.base.current = cx_tree_iter_current; | 349 iter.base.current = cx_tree_iter_current; |
| 350 | 350 |
| 351 return iter; | 351 return iter; |
| 352 } | 352 } |
| 353 | 353 |
| 354 static bool cx_tree_visitor_valid(void const *it) { | 354 static bool cx_tree_visitor_valid(const void *it) { |
| 355 struct cx_tree_visitor_s const *iter = it; | 355 const struct cx_tree_visitor_s *iter = it; |
| 356 return iter->node != NULL; | 356 return iter->node != NULL; |
| 357 } | 357 } |
| 358 | 358 |
| 359 static void *cx_tree_visitor_current(void const *it) { | 359 static void *cx_tree_visitor_current(const void *it) { |
| 360 struct cx_tree_visitor_s const *iter = it; | 360 const struct cx_tree_visitor_s *iter = it; |
| 361 return iter->node; | 361 return iter->node; |
| 362 } | 362 } |
| 363 | 363 |
| 364 __attribute__((__nonnull__)) | 364 __attribute__((__nonnull__)) |
| 365 static void cx_tree_visitor_enqueue_siblings( | 365 static void cx_tree_visitor_enqueue_siblings( |
| 495 // add new node as new child | 495 // add new node as new child |
| 496 cx_tree_link(parent, node, cx_tree_ptr_locations); | 496 cx_tree_link(parent, node, cx_tree_ptr_locations); |
| 497 } | 497 } |
| 498 | 498 |
| 499 int cx_tree_add( | 499 int cx_tree_add( |
| 500 void const *src, | 500 const void *src, |
| 501 cx_tree_search_func sfunc, | 501 cx_tree_search_func sfunc, |
| 502 cx_tree_node_create_func cfunc, | 502 cx_tree_node_create_func cfunc, |
| 503 void *cdata, | 503 void *cdata, |
| 504 void **cnode, | 504 void **cnode, |
| 505 void *root, | 505 void *root, |
| 558 // iter not valid? cancel... | 558 // iter not valid? cancel... |
| 559 if (!iter->valid(iter)) return 0; | 559 if (!iter->valid(iter)) return 0; |
| 560 | 560 |
| 561 size_t processed = 0; | 561 size_t processed = 0; |
| 562 void *current_node = root; | 562 void *current_node = root; |
| 563 void const *elem; | 563 const void *elem; |
| 564 | 564 |
| 565 for (void **eptr; | 565 for (void **eptr; |
| 566 iter->valid(iter) && (eptr = iter->current(iter)) != NULL; | 566 iter->valid(iter) && (eptr = iter->current(iter)) != NULL; |
| 567 iter->next(iter)) { | 567 iter->next(iter)) { |
| 568 elem = *eptr; | 568 elem = *eptr; |
| 619 } | 619 } |
| 620 return processed; | 620 return processed; |
| 621 } | 621 } |
| 622 | 622 |
| 623 size_t cx_tree_add_array( | 623 size_t cx_tree_add_array( |
| 624 void const *src, | 624 const void *src, |
| 625 size_t num, | 625 size_t num, |
| 626 size_t elem_size, | 626 size_t elem_size, |
| 627 cx_tree_search_func sfunc, | 627 cx_tree_search_func sfunc, |
| 628 cx_tree_node_create_func cfunc, | 628 cx_tree_node_create_func cfunc, |
| 629 void *cdata, | 629 void *cdata, |
