comparison: src/tree.c
src/tree.c
- changeset 848
- 6456036bbb37
- parent 845
- 2615317311b7
- child 853
- d4baf4dd55c3
equal
deleted
inserted
replaced
| 847:a39e410a05e6 | 848:6456036bbb37 |
|---|---|
| 184 void *children; | 184 void *children; |
| 185 | 185 |
| 186 // check if we are currently exiting or entering nodes | 186 // check if we are currently exiting or entering nodes |
| 187 if (iter->exiting) { | 187 if (iter->exiting) { |
| 188 children = NULL; | 188 children = NULL; |
| 189 // skipping on exit is pointless, just clear the flag | |
| 190 iter->skip = false; | |
| 189 } else { | 191 } else { |
| 190 children = tree_children(iter->node); | 192 if (iter->skip) { |
| 193 // skip flag is set, pretend that there are no children | |
| 194 iter->skip = false; | |
| 195 children = NULL; | |
| 196 } else { | |
| 197 // try to enter the children (if any) | |
| 198 children = tree_children(iter->node); | |
| 199 } | |
| 191 } | 200 } |
| 192 | 201 |
| 193 if (children == NULL) { | 202 if (children == NULL) { |
| 194 // search for the next node | 203 // search for the next node |
| 195 void *next; | 204 void *next; |
| 261 iter.stack = malloc(sizeof(void *) * 16); | 270 iter.stack = malloc(sizeof(void *) * 16); |
| 262 iter.depth = 0; | 271 iter.depth = 0; |
| 263 | 272 |
| 264 // visit the root node | 273 // visit the root node |
| 265 iter.node = root; | 274 iter.node = root; |
| 275 iter.next = NULL; | |
| 266 iter.counter = 1; | 276 iter.counter = 1; |
| 267 iter.depth = 1; | 277 iter.depth = 1; |
| 268 iter.stack[0] = root; | 278 iter.stack[0] = root; |
| 269 iter.exiting = false; | 279 iter.exiting = false; |
| 280 iter.skip = false; | |
| 270 | 281 |
| 271 // assign base iterator functions | 282 // assign base iterator functions |
| 272 iter.base.mutating = false; | 283 iter.base.mutating = false; |
| 273 iter.base.remove = false; | 284 iter.base.remove = false; |
| 274 iter.base.current_impl = NULL; | 285 iter.base.current_impl = NULL; |
| 308 static void cx_tree_visitor_next(void *it) { | 319 static void cx_tree_visitor_next(void *it) { |
| 309 struct cx_tree_visitor_s *iter = it; | 320 struct cx_tree_visitor_s *iter = it; |
| 310 ptrdiff_t const loc_next = iter->loc_next; | 321 ptrdiff_t const loc_next = iter->loc_next; |
| 311 ptrdiff_t const loc_children = iter->loc_children; | 322 ptrdiff_t const loc_children = iter->loc_children; |
| 312 | 323 |
| 313 // check if there is a next node | 324 // add the children of the current node to the queue |
| 314 if (iter->queue_next == NULL) { | 325 // unless the skip flag is set |
| 315 iter->node = NULL; | 326 void *children; |
| 316 return; | 327 if (iter->skip) { |
| 317 } | 328 iter->skip = false; |
| 318 | 329 children = NULL; |
| 319 // dequeue the next node | 330 } else { |
| 320 iter->node = iter->queue_next->node; | 331 children = tree_children(iter->node); |
| 321 iter->depth = iter->queue_next->depth; | 332 } |
| 322 { | |
| 323 struct cx_tree_visitor_queue_s *q = iter->queue_next; | |
| 324 iter->queue_next = q->next; | |
| 325 if (iter->queue_next == NULL) { | |
| 326 assert(iter->queue_last == q); | |
| 327 iter->queue_last = NULL; | |
| 328 } | |
| 329 free(q); | |
| 330 } | |
| 331 | |
| 332 // increment the node counter | |
| 333 iter->counter++; | |
| 334 | |
| 335 // add the children of the new node to the queue | |
| 336 void *children = tree_children(iter->node); | |
| 337 if (children != NULL) { | 333 if (children != NULL) { |
| 338 struct cx_tree_visitor_queue_s *q; | 334 struct cx_tree_visitor_queue_s *q; |
| 339 q = malloc(sizeof(struct cx_tree_visitor_queue_s)); | 335 q = malloc(sizeof(struct cx_tree_visitor_queue_s)); |
| 340 q->depth = iter->depth + 1; | 336 q->depth = iter->depth + 1; |
| 341 q->node = children; | 337 q->node = children; |
| 346 iter->queue_last->next = q; | 342 iter->queue_last->next = q; |
| 347 } | 343 } |
| 348 iter->queue_last = q; | 344 iter->queue_last = q; |
| 349 cx_tree_visitor_enqueue_siblings(iter, children, loc_next); | 345 cx_tree_visitor_enqueue_siblings(iter, children, loc_next); |
| 350 } | 346 } |
| 347 | |
| 348 // check if there is a next node | |
| 349 if (iter->queue_next == NULL) { | |
| 350 iter->node = NULL; | |
| 351 return; | |
| 352 } | |
| 353 | |
| 354 // dequeue the next node | |
| 355 iter->node = iter->queue_next->node; | |
| 356 iter->depth = iter->queue_next->depth; | |
| 357 { | |
| 358 struct cx_tree_visitor_queue_s *q = iter->queue_next; | |
| 359 iter->queue_next = q->next; | |
| 360 if (iter->queue_next == NULL) { | |
| 361 assert(iter->queue_last == q); | |
| 362 iter->queue_last = NULL; | |
| 363 } | |
| 364 free(q); | |
| 365 } | |
| 366 | |
| 367 // increment the node counter | |
| 368 iter->counter++; | |
| 351 } | 369 } |
| 352 | 370 |
| 353 CxTreeVisitor cx_tree_visitor( | 371 CxTreeVisitor cx_tree_visitor( |
| 354 void *root, | 372 void *root, |
| 355 ptrdiff_t loc_children, | 373 ptrdiff_t loc_children, |
| 364 | 382 |
| 365 // visit the root node | 383 // visit the root node |
| 366 iter.node = root; | 384 iter.node = root; |
| 367 iter.counter = 1; | 385 iter.counter = 1; |
| 368 iter.depth = 1; | 386 iter.depth = 1; |
| 369 | 387 iter.skip = false; |
| 370 // put all children of root into the queue | 388 iter.queue_next = NULL; |
| 371 void *children = tree_children(root); | 389 iter.queue_last = NULL; |
| 372 if (children == NULL) { | |
| 373 iter.queue_next = NULL; | |
| 374 iter.queue_last = NULL; | |
| 375 } else { | |
| 376 iter.queue_next = malloc(sizeof(struct cx_tree_visitor_queue_s)); | |
| 377 iter.queue_next->depth = 2; | |
| 378 iter.queue_next->node = children; | |
| 379 iter.queue_last = iter.queue_next; | |
| 380 cx_tree_visitor_enqueue_siblings(&iter, children, loc_next); | |
| 381 } | |
| 382 | 390 |
| 383 // assign base iterator functions | 391 // assign base iterator functions |
| 384 iter.base.mutating = false; | 392 iter.base.mutating = false; |
| 385 iter.base.remove = false; | 393 iter.base.remove = false; |
| 386 iter.base.current_impl = NULL; | 394 iter.base.current_impl = NULL; |
