From: Gabriel Corona <gabriel.corona@loria.fr>
Date: Wed, 23 Mar 2016 08:30:48 +0000 (+0100)
Subject: [mc] Use std::equal_range in get_search_range()
X-Git-Tag: v3_13~327^2~15
X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/commitdiff_plain/65fb3bd8de358e97a3a971de6781661456de302d

[mc] Use std::equal_range in get_search_range()

The semantic of this function chanegd slightly in order to have
simpler code in the callers.
---

diff --git a/src/mc/mc_liveness.cpp b/src/mc/mc_liveness.cpp
index c9e84cd35f..afd03345d0 100644
--- a/src/mc/mc_liveness.cpp
+++ b/src/mc/mc_liveness.cpp
@@ -142,13 +142,7 @@ static simgrid::mc::VisitedPair* is_reached_acceptance_pair(simgrid::mc::Pair* p
       }
       xbt_dynar_insert_at(acceptance_pairs, min, &new_pair);
     } else {
-      pair_test = (simgrid::mc::VisitedPair*) xbt_dynar_get_as(acceptance_pairs, index, simgrid::mc::VisitedPair*);
-      if (pair_test->nb_processes < new_pair->nb_processes)
-        xbt_dynar_insert_at(acceptance_pairs, index + 1, &new_pair);
-      else if (pair_test->heap_bytes_used < new_pair->heap_bytes_used)
-        xbt_dynar_insert_at(acceptance_pairs, index + 1, &new_pair);
-      else
-        xbt_dynar_insert_at(acceptance_pairs, index, &new_pair);
+      xbt_dynar_insert_at(acceptance_pairs, index, &new_pair);
     }
   }
   return new_pair;
@@ -378,13 +372,7 @@ int is_visited_pair(simgrid::mc::VisitedPair* visited_pair, simgrid::mc::Pair* p
       }
       xbt_dynar_insert_at(visited_pairs, min, &new_visited_pair);
     } else {
-      pair_test = (simgrid::mc::VisitedPair*) xbt_dynar_get_as(visited_pairs, index, simgrid::mc::VisitedPair*);
-      if (pair_test->nb_processes < new_visited_pair->nb_processes)
-        xbt_dynar_insert_at(visited_pairs, index + 1, &new_visited_pair);
-      else if (pair_test->heap_bytes_used < new_visited_pair->heap_bytes_used)
-        xbt_dynar_insert_at(visited_pairs, index + 1, &new_visited_pair);
-      else
-        xbt_dynar_insert_at(visited_pairs, index, &new_visited_pair);
+      xbt_dynar_insert_at(visited_pairs, index, &new_visited_pair);
     }
 
     if ((ssize_t) xbt_dynar_length(visited_pairs) > _sg_mc_visited) {
diff --git a/src/mc/mc_private.h b/src/mc/mc_private.h
index 85740e20db..cc31c85d69 100644
--- a/src/mc/mc_private.h
+++ b/src/mc/mc_private.h
@@ -16,6 +16,10 @@
 #include <sys/mman.h>
 #endif
 
+#ifdef __cpluscplus
+#include <algorithm>
+#endif
+
 #include <elfutils/libdw.h>
 
 #include <simgrid/msg.h>
@@ -67,6 +71,15 @@ SG_END_DECL()
 namespace simgrid {
 namespace mc {
 
+struct DerefAndCompareByNbProcessesAndUsedHead {
+  template<class X, class Y>
+  bool operator()(X const& a, Y const& b)
+  {
+    return std::make_pair(a->nb_processes, a->heap_bytes_used) <
+      std::make_pair(b->nb_processes, b->heap_bytes_used);
+  }
+};
+
 /**
  *  \brief Find a suitable subrange of candidate duplicates for a given state
  *  \param list dynamic array of states/pairs with candidate duplicates of the current state;
@@ -89,49 +102,19 @@ template<class U, class T>
 int get_search_interval(
   U* list, std::size_t count, T *ref, int *min, int *max)
 {
-  int nb_processes = ref->nb_processes;
-  int heap_bytes_used = ref->heap_bytes_used;
-
-  int cursor = 0;
-  int start = 0;
-  int end = count - 1;
-  while (start <= end) {
-    cursor = (start + end) / 2;
-    int nb_processes_test = list[cursor]->nb_processes;
-    int heap_bytes_used_test = list[cursor]->heap_bytes_used;
-
-    if (nb_processes_test < nb_processes)
-      start = cursor + 1;
-    else if (nb_processes_test > nb_processes)
-      end = cursor - 1;
-    else if (heap_bytes_used_test < heap_bytes_used)
-      start = cursor + 1;
-    else if (heap_bytes_used_test > heap_bytes_used)
-      end = cursor - 1;
-    else {
-        *min = *max = cursor;
-        int previous_cursor = cursor - 1;
-        while (previous_cursor >= 0) {
-          nb_processes_test = list[previous_cursor]->nb_processes;
-          heap_bytes_used_test = list[previous_cursor]->heap_bytes_used;
-          if (nb_processes_test != nb_processes || heap_bytes_used_test != heap_bytes_used)
-            break;
-          *min = previous_cursor;
-          previous_cursor--;
-        }
-        size_t next_cursor = cursor + 1;
-        while (next_cursor < count) {
-          nb_processes_test = list[next_cursor]->nb_processes;
-          heap_bytes_used_test = list[next_cursor]->heap_bytes_used;
-          if (nb_processes_test != nb_processes || heap_bytes_used_test != heap_bytes_used)
-            break;
-          *max = next_cursor;
-          next_cursor++;
-        }
-        return -1;
-    }
+  auto res = std::equal_range(
+    list, list + count, ref, DerefAndCompareByNbProcessesAndUsedHead());
+
+  // Not found, but we have the insertion point:
+  if (res.first == res.second)
+    return res.first - list;
+
+  // Found, we have the whole matching range:
+  else {
+    *min = res.first - list;
+    *max = (res.second - 1) - list;
+    return -1;
   }
-  return cursor;
 }
 
 }
diff --git a/src/mc/mc_visited.cpp b/src/mc/mc_visited.cpp
index 05422974d9..6d28bb26b5 100644
--- a/src/mc/mc_visited.cpp
+++ b/src/mc/mc_visited.cpp
@@ -210,15 +210,7 @@ std::unique_ptr<simgrid::mc::VisitedState> is_visited_state(mc_state_t graph_sta
     } else {
 
       // The state has not been visited: insert the state in the dynamic array.
-      simgrid::mc::VisitedState* state_test = &*visited_states[index];
-      std::size_t position;
-      if (state_test->nb_processes < new_state->nb_processes)
-        position = index + 1;
-      else if (state_test->heap_bytes_used < new_state->heap_bytes_used)
-        position = index + 1;
-      else
-        position = index;
-      visited_states.insert(visited_states.begin() + position, std::move(new_state));
+      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());