src/mc/explo/odpor/WakeupTreeIterator.cpp

   1 /* Copyright (c) 2008-2023. The SimGrid Team. All rights reserved.          */
   2
   3 /* This program is free software; you can redistribute it and/or modify it
   4  * under the terms of the license (GNU LGPL) which comes with this package. */
   5
   6 #include "src/mc/explo/odpor/WakeupTreeIterator.hpp"
   7 #include "src/mc/explo/odpor/WakeupTree.hpp"
   8 #include "xbt/asserts.h"
   9
  10 namespace simgrid::mc::odpor {
  11
  12 WakeupTreeIterator::WakeupTreeIterator(const WakeupTree& tree) : root_list{tree.root_}
  13 {
  14   post_order_iteration.push(root_list.begin());
  15   push_until_left_most_found();
  16 }
  17
  18 void WakeupTreeIterator::push_until_left_most_found()
  19 {
  20   // INVARIANT: Since we are traversing over a tree,
  21   // there are no cycles. This means that at least
  22   // one node in the tree won't have any children,
  23   // so the loop will eventually terminate
  24   WakeupTreeNode* cur_top_node = *post_order_iteration.top();
  25   while (not cur_top_node->is_leaf()) {
  26     // INVARIANT: Since we push children in
  27     // reverse order (right-most to left-most),
  28     // we ensure that we'll always process left-most
  29     // children first
  30     auto& children = cur_top_node->children_;
  31     for (auto iter = children.rbegin(); iter != children.rend(); ++iter) {
  32       // iter.base() points one element past where we seek; that is,
  33       // we want the value one position forward
  34       post_order_iteration.push(std::prev(iter.base()));
  35     }
  36     has_added_children.push(cur_top_node);
  37     cur_top_node = *post_order_iteration.top();
  38   }
  39 }
  40
  41 void WakeupTreeIterator::increment()
  42 {
  43   // If there are no nodes in the stack, we've
  44   // completed the traversal: there's nothing left
  45   // to do
  46   if (post_order_iteration.empty()) {
  47     return;
  48   }
  49
  50   post_order_iteration.pop();
  51
  52   // If there are now no longer any nodes left,
  53   // we know that `prev_top` must be the original
  54   // root; that is, we were *just* pointing at the
  55   // original root, so we're done
  56   if (post_order_iteration.empty()) {
  57     return;
  58   }
  59
  60   xbt_assert(not has_added_children.empty(), "Invariant violated: There are more "
  61                                              "nodes in the iteration that we must search "
  62                                              "yet nobody has claimed to have added these nodes. "
  63                                              "This implies that the algorithm is not iterating over "
  64                                              "the wakeup tree is not following the post-fix order "
  65                                              "correctly");
  66
  67   // Otherwise, look at what is the new, current top node.
  68   // We're traversing the tree in
  69   //
  70   // If we've already added our children, we want
  71   // to be sure not to add them again; but we ALSO
  72   // want to be sure that we now start checking against
  73   // the the node that's next in line as "finished"
  74   //
  75   // INVARIANT: Since we're searching in post-fix order,
  76   // it always suffices to compare the current node
  77   // with the top of the stack of nodes which have added their
  78   // children
  79   if (*post_order_iteration.top() == has_added_children.top()) {
  80     has_added_children.pop();
  81   } else {
  82     push_until_left_most_found();
  83   }
  84 }
  85
  86 } // namespace simgrid::mc::odpor