From 33e5fe576f1e3d69beaef63076ca08f1a6671a0a Mon Sep 17 00:00:00 2001
From: Gabriel Corona <gabriel.corona@loria.fr>
Date: Wed, 23 Mar 2016 11:13:54 +0100
Subject: [PATCH] [mc] Use std::equal_range in is_visited_state()

---
 src/mc/mc_visited.cpp | 40 ++++++++++------------------------------
 1 file changed, 10 insertions(+), 30 deletions(-)

diff --git a/src/mc/mc_visited.cpp b/src/mc/mc_visited.cpp
index 6d28bb26b5..4e7ac5ee33 100644
--- a/src/mc/mc_visited.cpp
+++ b/src/mc/mc_visited.cpp
@@ -8,6 +8,7 @@
 #include <sys/wait.h>
 
 #include <memory>
+#include <algorithm>
 
 #include <xbt/automaton.h>
 #include <xbt/log.h>
@@ -154,29 +155,19 @@ std::unique_ptr<simgrid::mc::VisitedState> is_visited_state(mc_state_t graph_sta
   graph_state->in_visited_states = 1;
   XBT_DEBUG("Snapshot %p of visited state %d (exploration stack state %d)", new_state->system_state, new_state->num, graph_state->num);
 
-  if (visited_states.empty()) {
-    visited_states.push_back(std::move(new_state));
-    return nullptr;
-  }
-
-    int min = -1, max = -1, index;
-
-    index = simgrid::mc::get_search_interval(
-      visited_states.data(), visited_states.size(),
-      new_state.get(), &min, &max);
-
-    if (min != -1 && max != -1) {
+  auto range = std::equal_range(visited_states.begin(), visited_states.end(),
+    new_state.get(), simgrid::mc::DerefAndCompareByNbProcessesAndUsedHeap());
 
       if (_sg_mc_safety || (!partial_comm
         && initial_global_state->initial_communications_pattern_done)) {
 
-        int cursor = min;
-        while (cursor <= max) {
-          if (snapshot_compare(visited_states[cursor].get(), new_state.get()) == 0) {
+        for (auto i = range.first; i != range.second; ++i) {
+          auto& visited_state = *i;
+          if (snapshot_compare(visited_state.get(), new_state.get()) == 0) {
             // The state has been visited:
 
             std::unique_ptr<simgrid::mc::VisitedState> old_state =
-              std::move(visited_states[cursor]);
+              std::move(visited_state);
 
             if (old_state->other_num == -1)
               new_state->other_num = old_state->num;
@@ -197,25 +188,14 @@ std::unique_ptr<simgrid::mc::VisitedState> is_visited_state(mc_state_t graph_sta
             XBT_DEBUG("Replace visited state %d with the new visited state %d",
               old_state->num, new_state->num);
 
-            simgrid::mc::visited_states[cursor] = std::move(new_state);
+            visited_state = std::move(new_state);
             return std::move(old_state);
           }
-          cursor++;
         }
       }
-      
-      XBT_DEBUG("Insert new visited state %d (total : %lu)", new_state->num, (unsigned long) visited_states.size());
-      visited_states.insert(visited_states.begin() + min, std::move(new_state));
-
-    } else {
 
-      // The state has not been visited: insert the state in the dynamic array.
-      visited_states.insert(visited_states.begin() + index, std::move(new_state));
-      XBT_DEBUG("Insert new visited state %d (total : %lu)",
-        visited_states[index]->num,
-        (unsigned long) visited_states.size());
-
-    }
+  XBT_DEBUG("Insert new visited state %d (total : %lu)", new_state->num, (unsigned long) visited_states.size());
+  visited_states.insert(range.first, std::move(new_state));
 
   if (visited_states.size() <= (std::size_t) _sg_mc_visited)
     return nullptr;
-- 
2.20.1