comparison: src/tree.c
src/tree.c
- changeset 838
- 1ce90ab4fab9
- parent 836
- 2672a2f79484
- child 840
- 4f02995ce44e
equal
deleted
inserted
replaced
| 837:7c15fea5cbea | 838:1ce90ab4fab9 |
|---|---|
| 180 struct cx_tree_iterator_s *iter = it; | 180 struct cx_tree_iterator_s *iter = it; |
| 181 off_t const loc_next = iter->loc_next; | 181 off_t const loc_next = iter->loc_next; |
| 182 off_t const loc_children = iter->loc_children; | 182 off_t const loc_children = iter->loc_children; |
| 183 | 183 |
| 184 // TODO: support mutating iterator | 184 // TODO: support mutating iterator |
| 185 // TODO: support visit_on_exit | 185 |
| 186 | 186 void *children; |
| 187 void *children = tree_children(iter->node); | 187 |
| 188 // check if we are currently exiting or entering nodes | |
| 189 if (iter->exiting) { | |
| 190 children = NULL; | |
| 191 } else { | |
| 192 children = tree_children(iter->node); | |
| 193 } | |
| 194 | |
| 188 if (children == NULL) { | 195 if (children == NULL) { |
| 189 // search for the next node | 196 // search for the next node |
| 190 void *current = iter->node; | 197 void *next; |
| 191 do { | 198 cx_tree_iter_search_next: |
| 192 // check if there is a sibling | 199 // check if there is a sibling |
| 193 void *next = tree_next(current); | 200 next = tree_next(iter->node); |
| 194 if (next == NULL) { | 201 if (next == NULL) { |
| 195 // no sibling, check again for parent node | 202 // no sibling, we are done with this node and exit |
| 196 --iter->depth; | 203 if (iter->visit_on_exit && !iter->exiting) { |
| 197 if (iter->depth == 0) { | 204 // iter is supposed to visit the node again |
| 205 iter->exiting = true; | |
| 206 } else { | |
| 207 iter->exiting = false; | |
| 208 if (iter->depth == 1) { | |
| 198 // there is no parent - we have iterated the entire tree | 209 // there is no parent - we have iterated the entire tree |
| 199 // invalidate the iterator and free the node stack | 210 // invalidate the iterator and free the node stack |
| 200 iter->node = NULL; | 211 iter->node = NULL; |
| 201 current = NULL; | 212 iter->stack_capacity = iter->depth = 0; |
| 202 iter->stack_capacity = 0; | |
| 203 free(iter->stack); | 213 free(iter->stack); |
| 204 iter->stack = NULL; | 214 iter->stack = NULL; |
| 205 } else { | 215 } else { |
| 206 // the parent node can be obtained from the top of stack | 216 // the parent node can be obtained from the top of stack |
| 207 // this way we can avoid the loc_parent in the iterator | 217 // this way we can avoid the loc_parent in the iterator |
| 208 current = iter->stack[iter->depth - 1]; | 218 iter->depth--; |
| 219 iter->node = iter->stack[iter->depth - 1]; | |
| 220 // retry with the parent node to find a sibling | |
| 221 goto cx_tree_iter_search_next; | |
| 209 } | 222 } |
| 223 } | |
| 224 } else { | |
| 225 if (iter->visit_on_exit && !iter->exiting) { | |
| 226 // iter is supposed to visit the node again | |
| 227 iter->exiting = true; | |
| 210 } else { | 228 } else { |
| 211 // move to the sibling and break the loop | 229 iter->exiting = false; |
| 212 current = NULL; | 230 // move to the sibling |
| 213 iter->counter++; | 231 iter->counter++; |
| 214 iter->node = next; | 232 iter->node = next; |
| 215 // new top of stack is the sibling | 233 // new top of stack is the sibling |
| 216 iter->stack[iter->depth - 1] = next; | 234 iter->stack[iter->depth - 1] = next; |
| 217 } | 235 } |
| 218 } while (current != NULL); | 236 } |
| 219 } else { | 237 } else { |
| 220 // node has children, push the first child onto the stack and enter it | 238 // node has children, push the first child onto the stack and enter it |
| 221 cx_array_simple_add(iter->stack, children); | 239 cx_array_simple_add(iter->stack, children); |
| 222 iter->node = children; | 240 iter->node = children; |
| 223 iter->counter++; | 241 iter->counter++; |
