#include <algorithm>
#include <exception>
+#include <memory>
#include <queue>
+XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_wut, mc, "Logging specific to ODPOR WakeupTrees");
+
namespace simgrid::mc::odpor {
void WakeupTreeNode::add_child(WakeupTreeNode* node)
node->parent_ = this;
}
+std::string WakeupTreeNode::string_of_whole_tree(int indentation_level) const
+{
+ std::string tabulations = "";
+ for (int i = 0; i < indentation_level; i++)
+ tabulations += " ";
+ std::string final_string = action_ == nullptr ? "<>\n"
+ : tabulations + "Actor " + std::to_string(action_->aid_) + ": " +
+ action_->to_string(true) + "\n";
+ for (auto node : children_)
+ final_string += node->string_of_whole_tree(indentation_level + 1);
+ return final_string;
+}
+
PartialExecution WakeupTreeNode::get_sequence() const
{
// TODO: Prevent having to compute this at the node level
// and instead track this with the iterator
PartialExecution seq_;
const WakeupTreeNode* cur_node = this;
- while (cur_node != nullptr and !cur_node->is_root()) {
+ while (cur_node != nullptr && not cur_node->is_root()) {
seq_.push_front(cur_node->action_);
cur_node = cur_node->parent_;
}
}
}
-WakeupTree::WakeupTree() : WakeupTree(std::unique_ptr<WakeupTreeNode>(new WakeupTreeNode({}))) {}
+WakeupTree::WakeupTree() : WakeupTree(std::make_unique<WakeupTreeNode>()) {}
WakeupTree::WakeupTree(std::unique_ptr<WakeupTreeNode> root) : root_(root.get())
{
this->insert_node(std::move(root));
{
std::vector<std::string> trace;
for (const auto* child : root_->children_) {
- const auto t = child->get_action();
- const auto message = xbt::string_printf("Actor %ld: %s", t->aid_, t->to_string(true).c_str());
- trace.push_back(std::move(message));
+ const auto t = child->get_action();
+ auto message = xbt::string_printf("Actor %ld: %s", t->aid_, t->to_string(true).c_str());
+ trace.emplace_back(std::move(message));
}
return trace;
}
return this->root_->children_.front();
}
+std::string WakeupTree::string_of_whole_tree() const
+{
+ return root_->string_of_whole_tree(0);
+}
+
WakeupTree WakeupTree::make_subtree_rooted_at(WakeupTreeNode* root)
{
// Perform a BFS search to perform a deep copy of the portion
std::list<WakeupTreeNode*> subtree_contents{root};
std::list<WakeupTreeNode*> frontier{root};
while (not frontier.empty()) {
- auto node = frontier.front();
+ const auto* node = frontier.front();
frontier.pop_front();
for (const auto& child : node->get_ordered_children()) {
frontier.push_back(child);
}
}
+void WakeupTree::remove_subtree_at_aid(aid_t proc)
+{
+ for (const auto& child : root_->get_ordered_children())
+ if (child->get_actor() == proc) {
+ this->remove_subtree_rooted_at(child);
+ break;
+ }
+}
+
void WakeupTree::remove_min_single_process_subtree()
{
if (const auto node = get_min_single_process_node(); node.has_value()) {
}
}
-bool WakeupTree::contains(WakeupTreeNode* node) const
+bool WakeupTree::contains(const WakeupTreeNode* node) const
{
return std::find_if(this->nodes_.begin(), this->nodes_.end(), [=](const auto& pair) { return pair.first == node; }) !=
this->nodes_.end();
WakeupTreeNode* WakeupTree::make_node(std::shared_ptr<Transition> u)
{
- auto node = std::unique_ptr<WakeupTreeNode>(new WakeupTreeNode(std::move(u)));
+ auto node = std::make_unique<WakeupTreeNode>(std::move(u));
auto* node_handle = node.get();
this->nodes_[node_handle] = std::move(node);
return node_handle;
this->nodes_.erase(node);
}
-void WakeupTree::insert(const Execution& E, const PartialExecution& w)
+WakeupTree::InsertionResult WakeupTree::insert(const Execution& E, const PartialExecution& w)
{
// See section 6.2 of Abdulla. et al.'s 2017 ODPOR paper for details
shortest_sequence.has_value()) {
// Insert the sequence as a child of `node`, but only
// if the node is not already a leaf
- if (not node->is_leaf() or node == this->root_) {
- xbt_assert(!shortest_sequence.value().empty(), "A successful insertion into an interior"
- "node of a wakeup tree should never involve "
- "an empty sequence (yet here we are, with an empty sequence)");
+ if (not node->is_leaf() || node == this->root_) {
+ // NOTE: It's entirely possible that the shortest
+ // sequence we are inserting is empty. Consider the
+ // following two cases:
+ //
+ // 1. `w` is itself empty. Evidently, insertion succeeds but nothing needs
+ // to happen
+ //
+ // 2. a leaf node in the tree already contains `w` exactly.
+ // In this case, the empty `w'` returned (viz. `shortest_seq`)
+ // such that `w [=_[E] v.w'` would be empty
this->insert_sequence_after(node, shortest_sequence.value());
+ return node == this->root_ ? InsertionResult::root : InsertionResult::interior_node;
}
// Since we're following the post-order traversal of the tree,
// the first such node we see is the smallest w.r.t "<"
- return;
+ return InsertionResult::leaf;
}
}
xbt_die("Insertion should always succeed with the root node (which contains no "
}
}
-} // namespace simgrid::mc::odpor
\ No newline at end of file
+} // namespace simgrid::mc::odpor