comparison: src/tree.c
src/tree.c
- changeset 845
- 2615317311b7
- parent 840
- 4f02995ce44e
- child 848
- 6456036bbb37
equal
deleted
inserted
replaced
| 844:3270ea9e41ef | 845:2615317311b7 |
|---|---|
| 176 return iter->node; | 176 return iter->node; |
| 177 } | 177 } |
| 178 | 178 |
| 179 static void cx_tree_iter_next(void *it) { | 179 static void cx_tree_iter_next(void *it) { |
| 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 ptrdiff_t const loc_next = iter->loc_next; |
| 182 off_t const loc_children = iter->loc_children; | 182 ptrdiff_t const loc_children = iter->loc_children; |
| 183 | |
| 184 // TODO: support mutating iterator | |
| 185 | 183 |
| 186 void *children; | 184 void *children; |
| 187 | 185 |
| 188 // check if we are currently exiting or entering nodes | 186 // check if we are currently exiting or entering nodes |
| 189 if (iter->exiting) { | 187 if (iter->exiting) { |
| 278 iter.base.next = cx_tree_iter_next; | 276 iter.base.next = cx_tree_iter_next; |
| 279 iter.base.current = cx_tree_iter_current; | 277 iter.base.current = cx_tree_iter_current; |
| 280 | 278 |
| 281 return iter; | 279 return iter; |
| 282 } | 280 } |
| 281 | |
| 282 static bool cx_tree_visitor_valid(void const *it) { | |
| 283 struct cx_tree_visitor_s const *iter = it; | |
| 284 return iter->node != NULL; | |
| 285 } | |
| 286 | |
| 287 static void *cx_tree_visitor_current(void const *it) { | |
| 288 struct cx_tree_visitor_s const *iter = it; | |
| 289 return iter->node; | |
| 290 } | |
| 291 | |
| 292 __attribute__((__nonnull__)) | |
| 293 static void cx_tree_visitor_enqueue_siblings( | |
| 294 struct cx_tree_visitor_s *iter, void *node, ptrdiff_t loc_next) { | |
| 295 node = tree_next(node); | |
| 296 while (node != NULL) { | |
| 297 struct cx_tree_visitor_queue_s *q; | |
| 298 q = malloc(sizeof(struct cx_tree_visitor_queue_s)); | |
| 299 q->depth = iter->queue_last->depth; | |
| 300 q->node = node; | |
| 301 iter->queue_last->next = q; | |
| 302 iter->queue_last = q; | |
| 303 node = tree_next(node); | |
| 304 } | |
| 305 iter->queue_last->next = NULL; | |
| 306 } | |
| 307 | |
| 308 static void cx_tree_visitor_next(void *it) { | |
| 309 struct cx_tree_visitor_s *iter = it; | |
| 310 ptrdiff_t const loc_next = iter->loc_next; | |
| 311 ptrdiff_t const loc_children = iter->loc_children; | |
| 312 | |
| 313 // check if there is a next node | |
| 314 if (iter->queue_next == NULL) { | |
| 315 iter->node = NULL; | |
| 316 return; | |
| 317 } | |
| 318 | |
| 319 // dequeue the next node | |
| 320 iter->node = iter->queue_next->node; | |
| 321 iter->depth = iter->queue_next->depth; | |
| 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) { | |
| 338 struct cx_tree_visitor_queue_s *q; | |
| 339 q = malloc(sizeof(struct cx_tree_visitor_queue_s)); | |
| 340 q->depth = iter->depth + 1; | |
| 341 q->node = children; | |
| 342 if (iter->queue_last == NULL) { | |
| 343 assert(iter->queue_next == NULL); | |
| 344 iter->queue_next = q; | |
| 345 } else { | |
| 346 iter->queue_last->next = q; | |
| 347 } | |
| 348 iter->queue_last = q; | |
| 349 cx_tree_visitor_enqueue_siblings(iter, children, loc_next); | |
| 350 } | |
| 351 } | |
| 352 | |
| 353 CxTreeVisitor cx_tree_visitor( | |
| 354 void *root, | |
| 355 ptrdiff_t loc_children, | |
| 356 ptrdiff_t loc_next | |
| 357 ) { | |
| 358 CxTreeVisitor iter; | |
| 359 iter.loc_children = loc_children; | |
| 360 iter.loc_next = loc_next; | |
| 361 | |
| 362 // allocate stack | |
| 363 iter.depth = 0; | |
| 364 | |
| 365 // visit the root node | |
| 366 iter.node = root; | |
| 367 iter.counter = 1; | |
| 368 iter.depth = 1; | |
| 369 | |
| 370 // put all children of root into the queue | |
| 371 void *children = tree_children(root); | |
| 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 | |
| 383 // assign base iterator functions | |
| 384 iter.base.mutating = false; | |
| 385 iter.base.remove = false; | |
| 386 iter.base.current_impl = NULL; | |
| 387 iter.base.valid = cx_tree_visitor_valid; | |
| 388 iter.base.next = cx_tree_visitor_next; | |
| 389 iter.base.current = cx_tree_visitor_current; | |
| 390 | |
| 391 return iter; | |
| 392 } | |
| 393 |
