X-Git-Url: http://bilbo.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/e9b99cc75875aaffe31d627aceb45a3583770d55..fe4080b8dd04acb2074ca72d36e3019acddea455:/src/mc/explo/udpor/maximal_subsets_iterator.cpp diff --git a/src/mc/explo/udpor/maximal_subsets_iterator.cpp b/src/mc/explo/udpor/maximal_subsets_iterator.cpp index 1dd635a334..6c2dee3ce6 100644 --- a/src/mc/explo/udpor/maximal_subsets_iterator.cpp +++ b/src/mc/explo/udpor/maximal_subsets_iterator.cpp @@ -6,11 +6,12 @@ namespace simgrid::mc::udpor { -maximal_subsets_iterator::maximal_subsets_iterator(const Configuration& config, - std::optional filter) - : config({config}), current_maximal_set({EventSet()}) +maximal_subsets_iterator::maximal_subsets_iterator(const EventSet& events, + const std::optional& filter, + std::optional maximum_subset_size) + : maximum_subset_size(maximum_subset_size), current_maximal_set({EventSet()}) { - const auto candidate_ordering = config.get_topologically_sorted_events_of_reverse_graph(); + auto candidate_ordering = events.get_topological_ordering_of_reverse_graph(); if (filter.has_value()) { // Only store the events in the ordering that "matter" to us std::copy_if(std::move_iterator(candidate_ordering.begin()), std::move_iterator(candidate_ordering.end()), @@ -22,18 +23,19 @@ maximal_subsets_iterator::maximal_subsets_iterator(const Configuration& config, void maximal_subsets_iterator::increment() { + // Termination condition if (current_maximal_set == std::nullopt) { return; } + // Stop immediately if there's nothing to search if (topological_ordering.empty()) { - // Stop immediately if there's nothing to search current_maximal_set = std::nullopt; return; } const auto next_event_ref = [&]() { - if (!has_started_searching) { + if (not has_started_searching) { has_started_searching = true; return bookkeeper.find_next_candidate_event(topological_ordering.begin(), topological_ordering.end()); } else { @@ -41,6 +43,7 @@ void maximal_subsets_iterator::increment() } }(); + // Out of events: we've finished if (next_event_ref == topological_ordering.end()) { current_maximal_set = std::nullopt; return; @@ -60,9 +63,13 @@ maximal_subsets_iterator::continue_traversal_of_maximal_events_tree() return topological_ordering.end(); } + xbt_assert(current_maximal_set.has_value(), "Traversal continued even after the termination condition " + "was met. Please verify that the termination condition " + "of the iterator has not been modified"); + // 1. First, check if we can keep expanding from the // maximal set that we currently have - { + if (can_grow_maximal_set()) { // This is an iterator which points to the latest event `e` that // was added to what is currently the maximal set const auto latest_event_ref = backtrack_points.top(); @@ -104,7 +111,7 @@ maximal_subsets_iterator::continue_traversal_of_maximal_events_tree() return topological_ordering.end(); } -bool maximal_subsets_iterator::bookkeeper::is_candidate_event(const UnfoldingEvent* e) const +bool maximal_subsets_iterator::Bookkeeper::is_candidate_event(const UnfoldingEvent* e) const { if (const auto e_count = event_counts.find(e); e_count != event_counts.end()) { return e_count->second == 0; @@ -114,6 +121,11 @@ bool maximal_subsets_iterator::bookkeeper::is_candidate_event(const UnfoldingEve void maximal_subsets_iterator::add_element_to_current_maximal_set(const UnfoldingEvent* e) { + xbt_assert(can_grow_maximal_set(), "Attempting to add an event to the maximal set " + "when doing so would increase the size past the " + "prescribed limit. This indicates that detecting when " + "to stop growing the maximal set when continuing the " + "search is broken"); xbt_assert(current_maximal_set.has_value(), "Attempting to add an event to the maximal set " "when iteration has completed. This indicates that " "the termination condition for the iterator is broken"); @@ -130,25 +142,36 @@ void maximal_subsets_iterator::remove_element_from_current_maximal_set(const Unf bookkeeper.mark_removed_from_maximal_set(e); } +bool maximal_subsets_iterator::can_grow_maximal_set() const +{ + if (not current_maximal_set.has_value()) { + return true; + } + if (maximum_subset_size.has_value()) { + return current_maximal_set.value().size() < maximum_subset_size.value(); + } + return true; +} + maximal_subsets_iterator::topological_order_position -maximal_subsets_iterator::bookkeeper::find_next_candidate_event(topological_order_position first, +maximal_subsets_iterator::Bookkeeper::find_next_candidate_event(topological_order_position first, topological_order_position last) const { return std::find_if(first, last, [&](const UnfoldingEvent* e) { return is_candidate_event(e); }); } -void maximal_subsets_iterator::bookkeeper::mark_included_in_maximal_set(const UnfoldingEvent* e) +void maximal_subsets_iterator::Bookkeeper::mark_included_in_maximal_set(const UnfoldingEvent* e) { - const auto e_history = e->get_history(); - for (const auto e_hist : e_history) { + const auto e_local_config = e->get_local_config(); + for (const auto* e_hist : e_local_config) { event_counts[e_hist]++; } } -void maximal_subsets_iterator::bookkeeper::mark_removed_from_maximal_set(const UnfoldingEvent* e) +void maximal_subsets_iterator::Bookkeeper::mark_removed_from_maximal_set(const UnfoldingEvent* e) { - const auto e_history = e->get_history(); - for (const auto e_hist : e_history) { + const auto e_local_config = e->get_local_config(); + for (const auto* e_hist : e_local_config) { xbt_assert(event_counts.find(e_hist) != event_counts.end(), "Invariant Violation: Attempted to remove an event which was not previously added"); xbt_assert(event_counts[e_hist] > 0, "Invariant Violation: An event `e` had a count of `0` at this point " @@ -160,4 +183,4 @@ void maximal_subsets_iterator::bookkeeper::mark_removed_from_maximal_set(const U } } -} // namespace simgrid::mc::udpor \ No newline at end of file +} // namespace simgrid::mc::udpor