X-Git-Url: http://bilbo.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/edc5c089fec77e74e39c8887a640fe03226d8a3f..bc2253e2c879ee28ae5153f1d56497ab802aeea9:/src/mc/explo/odpor/WakeupTree.cpp diff --git a/src/mc/explo/odpor/WakeupTree.cpp b/src/mc/explo/odpor/WakeupTree.cpp index a07706e07d..73b2171894 100644 --- a/src/mc/explo/odpor/WakeupTree.cpp +++ b/src/mc/explo/odpor/WakeupTree.cpp @@ -10,8 +10,11 @@ #include #include +#include #include +XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_wut, mc, "Logging specific to ODPOR WakeupTrees"); + namespace simgrid::mc::odpor { void WakeupTreeNode::add_child(WakeupTreeNode* node) @@ -20,13 +23,26 @@ 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_; } @@ -46,7 +62,7 @@ void WakeupTreeNode::detatch_from_parent() } } -WakeupTree::WakeupTree() : WakeupTree(std::unique_ptr(new WakeupTreeNode({}))) {} +WakeupTree::WakeupTree() : WakeupTree(std::make_unique()) {} WakeupTree::WakeupTree(std::unique_ptr root) : root_(root.get()) { this->insert_node(std::move(root)); @@ -56,9 +72,9 @@ std::vector WakeupTree::get_single_process_texts() const { std::vector 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; } @@ -84,6 +100,11 @@ std::optional WakeupTree::get_min_single_process_node() const 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 @@ -120,7 +141,7 @@ void WakeupTree::remove_subtree_rooted_at(WakeupTreeNode* root) std::list subtree_contents{root}; std::list 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); @@ -138,6 +159,15 @@ void WakeupTree::remove_subtree_rooted_at(WakeupTreeNode* root) } } +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()) { @@ -145,7 +175,7 @@ void WakeupTree::remove_min_single_process_subtree() } } -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(); @@ -153,7 +183,7 @@ bool WakeupTree::contains(WakeupTreeNode* node) const WakeupTreeNode* WakeupTree::make_node(std::shared_ptr u) { - auto node = std::unique_ptr(new WakeupTreeNode(std::move(u))); + auto node = std::make_unique(std::move(u)); auto* node_handle = node.get(); this->nodes_[node_handle] = std::move(node); return node_handle; @@ -170,7 +200,7 @@ void WakeupTree::remove_node(WakeupTreeNode* node) 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 @@ -181,15 +211,23 @@ void WakeupTree::insert(const Execution& E, const PartialExecution& w) 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 " @@ -208,4 +246,4 @@ void WakeupTree::insert_sequence_after(WakeupTreeNode* node, const PartialExecut } } -} // namespace simgrid::mc::odpor \ No newline at end of file +} // namespace simgrid::mc::odpor