1 /* Copyright (c) 2008-2023. The SimGrid Team. All rights reserved. */
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. */
6 #include "src/mc/explo/odpor/WakeupTree.hpp"
7 #include "src/mc/explo/odpor/Execution.hpp"
11 namespace simgrid::mc::odpor {
13 WakeupTree::WakeupTree() : root(nullptr) {}
15 WakeupTreeNode* WakeupTree::make_node(const ProcessSequence& u)
17 auto node = std::unique_ptr<WakeupTreeNode>(new WakeupTreeNode(u));
18 auto* node_handle = node.get();
19 this->nodes_[node.get()] = std::move(node);
23 void WakeupTree::insert(const Execution& E, const ExecutionSequence& w)
25 // See section 6.2 of Abdulla. et al.'s 2017 ODPOR paper for details
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);
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 "<"
45 } // namespace simgrid::mc::odpor