src/mc/explo/odpor/WakeupTree.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/WakeupTree.hpp"
   7 #include "src/mc/explo/odpor/Execution.hpp"
   8
   9 #include <algorithm>
  10
  11 namespace simgrid::mc::odpor {
  12
  13 WakeupTree::WakeupTree() : root(nullptr) {}
  14
  15 WakeupTreeNode* WakeupTree::make_node(const ProcessSequence& u)
  16 {
  17   auto node                = std::unique_ptr<WakeupTreeNode>(new WakeupTreeNode(u));
  18   auto* node_handle        = node.get();
  19   this->nodes_[node.get()] = std::move(node);
  20   return node_handle;
  21 }
  22
  23 void WakeupTree::insert(const Execution& E, const ExecutionSequence& w)
  24 {
  25   // See section 6.2 of Abdulla. et al.'s 2017 ODPOR paper for details
  26
  27   // Find the first node `v` in the tree such that
  28   // `v ~_[E] w` and `v`  is not a leaf node
  29   for (WakeupTreeNode* node : *this) {
  30     if (const auto shortest_sequence = E.get_shortest_odpor_sq_subset_insertion(node->get_sequence(), w);
  31         shortest_sequence.has_value()) {
  32       // Insert the sequence as a child of `node`, but only
  33       // if the node is not already a leaf
  34       if (not node->is_leaf()) {
  35         WakeupTreeNode* new_node = this->make_node(shortest_sequence.value());
  36         node->add_child(new_node);
  37       }
  38       // Since we're following the post-order traversal of the tree,
  39       // the first such node we see is the smallest w.r.t "<"
  40       return;
  41     }
  42   }
  43 }
  44
  45 } // namespace simgrid::mc::odpor