comparison: ucx/tree.c
ucx/tree.c
- branch
- dav-2
- changeset 886
- da79af4baec8
- parent 854
- 1c8401ece69e
- child 889
- 42cdbf9bbd49
equal
deleted
inserted
replaced
| 885:591377a27fa3 | 886:da79af4baec8 |
|---|---|
| 224 cx_foreach(void *, elem, iter) { | 224 cx_foreach(void *, elem, iter) { |
| 225 // investigate the current node | 225 // investigate the current node |
| 226 int ret_elem = sfunc(elem, node); | 226 int ret_elem = sfunc(elem, node); |
| 227 if (ret_elem == 0) { | 227 if (ret_elem == 0) { |
| 228 // if found, exit the search | 228 // if found, exit the search |
| 229 *result = (void *) elem; | 229 *result = elem; |
| 230 ret = 0; | 230 ret = 0; |
| 231 break; | 231 break; |
| 232 } else if (ret_elem > 0 && ret_elem < ret) { | 232 } else if (ret_elem > 0 && ret_elem < ret) { |
| 233 // new distance is better | 233 // new distance is better |
| 234 *result = elem; | 234 *result = elem; |
| 235 ret = ret_elem; | 235 ret = ret_elem; |
| 236 } else { | 236 } else if (ret_elem < 0 || ret_elem > ret) { |
| 237 // not contained or distance is worse, skip entire subtree | 237 // not contained or distance is worse, skip entire subtree |
| 238 cxTreeIteratorContinue(iter); | 238 cxTreeIteratorContinue(iter); |
| 239 } | 239 } |
| 240 | 240 |
| 241 // when we reached the max depth, skip the subtree | 241 // when we reached the max depth, skip the subtree |
| 303 } | 303 } |
| 304 } | 304 } |
| 305 | 305 |
| 306 if (children == NULL) { | 306 if (children == NULL) { |
| 307 // search for the next node | 307 // search for the next node |
| 308 void *next; | 308 void *next = NULL; |
| 309 cx_tree_iter_search_next: | 309 cx_tree_iter_search_next: |
| 310 // check if there is a sibling | 310 // check if there is a sibling, but only if we are not a (subtree-)root |
| 311 if (iter->exiting) { | 311 if (iter->exiting) { |
| 312 next = iter->node_next; | 312 next = iter->node_next; |
| 313 } else { | 313 } else if (iter->depth > 1) { |
| 314 next = tree_next(iter->node); | 314 next = tree_next(iter->node); |
| 315 iter->node_next = next; | 315 iter->node_next = next; |
| 316 } | 316 } |
| 317 if (next == NULL) { | 317 if (next == NULL) { |
| 318 // no sibling, we are done with this node and exit | 318 // no sibling, we are done with this node and exit |
| 324 if (iter->depth == 1) { | 324 if (iter->depth == 1) { |
| 325 // there is no parent - we have iterated the entire tree | 325 // there is no parent - we have iterated the entire tree |
| 326 // invalidate the iterator and free the node stack | 326 // invalidate the iterator and free the node stack |
| 327 iter->node = iter->node_next = NULL; | 327 iter->node = iter->node_next = NULL; |
| 328 iter->stack_capacity = iter->depth = 0; | 328 iter->stack_capacity = iter->depth = 0; |
| 329 free(iter->stack); | 329 cxFreeDefault(iter->stack); |
| 330 iter->stack = NULL; | 330 iter->stack = NULL; |
| 331 } else { | 331 } else { |
| 332 // the parent node can be obtained from the top of stack | 332 // the parent node can be obtained from the top of stack |
| 333 // this way we can avoid the loc_parent in the iterator | 333 // this way we can avoid the loc_parent in the iterator |
| 334 iter->depth--; | 334 iter->depth--; |
| 384 | 384 |
| 385 // visit the root node | 385 // visit the root node |
| 386 iter.node = root; | 386 iter.node = root; |
| 387 if (root != NULL) { | 387 if (root != NULL) { |
| 388 iter.stack_capacity = 16; | 388 iter.stack_capacity = 16; |
| 389 iter.stack = malloc(sizeof(void *) * 16); | 389 iter.stack = cxMallocDefault(sizeof(void *) * 16); |
| 390 iter.stack[0] = root; | 390 iter.stack[0] = root; |
| 391 iter.counter = 1; | 391 iter.counter = 1; |
| 392 iter.depth = 1; | 392 iter.depth = 1; |
| 393 } else { | 393 } else { |
| 394 iter.stack_capacity = 0; | 394 iter.stack_capacity = 0; |
| 414 static void cx_tree_visitor_enqueue_siblings( | 414 static void cx_tree_visitor_enqueue_siblings( |
| 415 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) { |
| 416 node = tree_next(node); | 416 node = tree_next(node); |
| 417 while (node != NULL) { | 417 while (node != NULL) { |
| 418 struct cx_tree_visitor_queue_s *q; | 418 struct cx_tree_visitor_queue_s *q; |
| 419 q = malloc(sizeof(struct cx_tree_visitor_queue_s)); | 419 q = cxMallocDefault(sizeof(struct cx_tree_visitor_queue_s)); |
| 420 q->depth = iter->queue_last->depth; | 420 q->depth = iter->queue_last->depth; |
| 421 q->node = node; | 421 q->node = node; |
| 422 iter->queue_last->next = q; | 422 iter->queue_last->next = q; |
| 423 iter->queue_last = q; | 423 iter->queue_last = q; |
| 424 node = tree_next(node); | 424 node = tree_next(node); |
| 443 } else { | 443 } else { |
| 444 children = tree_children(iter->node); | 444 children = tree_children(iter->node); |
| 445 } | 445 } |
| 446 if (children != NULL) { | 446 if (children != NULL) { |
| 447 struct cx_tree_visitor_queue_s *q; | 447 struct cx_tree_visitor_queue_s *q; |
| 448 q = malloc(sizeof(struct cx_tree_visitor_queue_s)); | 448 q = cxMallocDefault(sizeof(struct cx_tree_visitor_queue_s)); |
| 449 q->depth = iter->depth + 1; | 449 q->depth = iter->depth + 1; |
| 450 q->node = children; | 450 q->node = children; |
| 451 if (iter->queue_last == NULL) { | 451 if (iter->queue_last == NULL) { |
| 452 assert(iter->queue_next == NULL); | 452 assert(iter->queue_next == NULL); |
| 453 iter->queue_next = q; | 453 iter->queue_next = q; |
| 472 iter->queue_next = q->next; | 472 iter->queue_next = q->next; |
| 473 if (iter->queue_next == NULL) { | 473 if (iter->queue_next == NULL) { |
| 474 assert(iter->queue_last == q); | 474 assert(iter->queue_last == q); |
| 475 iter->queue_last = NULL; | 475 iter->queue_last = NULL; |
| 476 } | 476 } |
| 477 free(q); | 477 cxFreeDefault(q); |
| 478 } | 478 } |
| 479 | 479 |
| 480 // increment the node counter | 480 // increment the node counter |
| 481 iter->counter++; | 481 iter->counter++; |
| 482 } | 482 } |
