From: Maxwell Pirtle Date: Thu, 11 May 2023 12:18:56 +0000 (+0200) Subject: Automatically remove nodes from parents X-Git-Tag: v3.34~68^2~35 X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/commitdiff_plain/746a2035fbbf84f8647d0badac80115ea3b00be0 Automatically remove nodes from parents After removing a node from a WakeupTree, we need to be careful to also have any references to the node removed, viz. that held onto the parent of the node in the list of children. This commit adds a back reference to the parent node of a given WakeupTreeNode to allow removal from the parent when destroyed. Additionally, some bugs were fixed for creating subtrees and removing subtrees (we forgot to remove the root for example) --- diff --git a/src/mc/api/State.cpp b/src/mc/api/State.cpp index 7606d26ead..fb2a806d41 100644 --- a/src/mc/api/State.cpp +++ b/src/mc/api/State.cpp @@ -206,10 +206,10 @@ void State::sprout_tree_from_parent_state() xbt_assert(parent_state_ != nullptr, "Attempting to construct a wakeup tree for the root state " "(or what appears to be, rather for state without a parent defined)"); const auto p = parent_state_->get_transition_out()->aid_; - const auto branch = std::find_if(wakeup_tree_.begin(), wakeup_tree_.end(), [=](const odpor::WakeupTreeNode* node) { - return node->is_single_process() && node->get_first_actor() == p; - }); - xbt_assert(branch != wakeup_tree_.end(), + const auto branch = std::find_if( + parent_state_->wakeup_tree_.begin(), parent_state_->wakeup_tree_.end(), + [=](const odpor::WakeupTreeNode* node) { return node->is_single_process() && node->get_first_actor() == p; }); + xbt_assert(branch != parent_state_->wakeup_tree_.end(), "Attempted to create a subtree from the wakeup tree of the parent " "state using actor `%ld`, but no such subtree could be found. " "This implies that the wakeup tree management is broken, " diff --git a/src/mc/explo/odpor/WakeupTree.cpp b/src/mc/explo/odpor/WakeupTree.cpp index 9335c69b7f..33a0fb6362 100644 --- a/src/mc/explo/odpor/WakeupTree.cpp +++ b/src/mc/explo/odpor/WakeupTree.cpp @@ -23,6 +23,23 @@ aid_t WakeupTreeNode::get_first_actor() const return get_sequence().front()->aid_; } +void WakeupTreeNode::add_child(WakeupTreeNode* node) +{ + this->children_.push_back(node); + node->parent_ = this; +} + +WakeupTreeNode::~WakeupTreeNode() +{ + if (parent_ != nullptr) { + // TODO: We can probably be more clever here: when + // we add the child to a node, we could perhaps + // try instead to keep a reference to position of the + // child in the list of the parent. + parent_->children_.remove(this); + } +} + WakeupTree::WakeupTree() : WakeupTree(std::unique_ptr(new WakeupTreeNode({}))) {} WakeupTree::WakeupTree(std::unique_ptr root) : root_(root.get()) { @@ -35,17 +52,16 @@ WakeupTree WakeupTree::make_subtree_rooted_at(WakeupTreeNode* root) throw std::invalid_argument("Selecting subtrees is only defined for single-process nodes"); } - const aid_t p = (*(root->get_sequence().begin()))->aid_; + const aid_t p = root->get_first_actor(); // Perform a BFS search to perform a deep copy of the portion // of the tree underneath and including `root`. Note that `root` // is contained within the context of a *different* wakeup tree; // hence, we have to be careful to update each node's children // appropriately - auto subtree = WakeupTree(); - WakeupTreeNode* root_equivalent = subtree.make_node(root->get_sequence()); + auto subtree = WakeupTree(); - std::list> frontier{std::make_pair(root, root_equivalent)}; + std::list> frontier{std::make_pair(root, subtree.root_)}; while (not frontier.empty()) { auto [node_in_other_tree, subtree_equivalent] = frontier.front(); frontier.pop_front(); @@ -70,7 +86,6 @@ WakeupTree WakeupTree::make_subtree_rooted_at(WakeupTreeNode* root) p_w.pop_front(); WakeupTreeNode* child_equivalent = subtree.make_node(p_w); - subtree_equivalent->add_child(child_equivalent); frontier.push_back(std::make_pair(child_in_other_tree, child_equivalent)); } } @@ -84,7 +99,7 @@ void WakeupTree::remove_subtree_rooted_at(WakeupTreeNode* root) "that is not contained in this wakeup tree"); } - std::list subtree_contents; + std::list subtree_contents{root}; std::list frontier{root}; while (not frontier.empty()) { auto node = frontier.front(); @@ -96,7 +111,7 @@ void WakeupTree::remove_subtree_rooted_at(WakeupTreeNode* root) } // After having found each node with BFS, now we can - // remove them. This prevents the "joys" iteration during mutation + // remove them. This prevents the "joys" of iteration during mutation for (WakeupTreeNode* node_to_remove : subtree_contents) { this->remove_node(node_to_remove); } diff --git a/src/mc/explo/odpor/WakeupTree.hpp b/src/mc/explo/odpor/WakeupTree.hpp index 553667caeb..7a6eb272bc 100644 --- a/src/mc/explo/odpor/WakeupTree.hpp +++ b/src/mc/explo/odpor/WakeupTree.hpp @@ -10,6 +10,7 @@ #include "src/mc/explo/odpor/odpor_forward.hpp" #include +#include #include namespace simgrid::mc::odpor { @@ -19,6 +20,8 @@ private: explicit WakeupTreeNode(const PartialExecution& u) : seq_(u) {} explicit WakeupTreeNode(PartialExecution&& u) : seq_(std::move(u)) {} + WakeupTreeNode* parent_ = nullptr; + /** An ordered list of children of for this node in the tree */ std::list children_; @@ -30,6 +33,7 @@ private: friend WakeupTreeIterator; public: + ~WakeupTreeNode(); WakeupTreeNode(const WakeupTreeNode&) = delete; WakeupTreeNode(WakeupTreeNode&&) = default; WakeupTreeNode& operator=(const WakeupTreeNode&) = delete; @@ -47,7 +51,7 @@ public: aid_t get_first_actor() const; /** Insert a node `node` as a new child of this node */ - void add_child(WakeupTreeNode* node) { this->children_.push_back(node); } + void add_child(WakeupTreeNode* node); }; class WakeupTree { diff --git a/src/mc/explo/odpor/WakeupTreeIterator.cpp b/src/mc/explo/odpor/WakeupTreeIterator.cpp index eb3d2190a6..6c81203193 100644 --- a/src/mc/explo/odpor/WakeupTreeIterator.cpp +++ b/src/mc/explo/odpor/WakeupTreeIterator.cpp @@ -31,7 +31,7 @@ void WakeupTreeIterator::push_until_left_most_found() for (auto iter = children.rbegin(); iter != children.rend(); ++iter) { // iter.base() points one element past where we seek; hence, // we move it over one position - post_order_iteration.push((--iter.base())); + post_order_iteration.push(std::prev(iter.base())); } cur_top_node = *post_order_iteration.top(); }