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;

mercurial