[mc] Use std::set for the list-of-heap-location-pairs

[simgrid.git] / src / mc / compare.cpp

diff --git a/src/mc/compare.cpp b/src/mc/compare.cpp
index 5d60d76..72e930b 100644 (file)
--- a/src/mc/compare.cpp
+++ b/src/mc/compare.cpp
@@ -10,6 +10,7 @@
 
 #include <array>
 #include <memory>
+#include <set>
 #include <utility>
 #include <unordered_set>
 
@@ -48,6 +49,10 @@ XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_compare, xbt,
 namespace simgrid {
 namespace mc {
 
+struct HeapLocation;
+typedef std::array<HeapLocation, 2> HeapLocationPair;
+typedef std::set<HeapLocationPair> HeapLocationPairs;
+struct HeapArea;
 struct ProcessComparisonState;
 struct StateComparator;
 
@@ -55,7 +60,7 @@ static int compare_heap_area(
   StateComparator& state,
   int process_index, const void *area1, const void* area2,
   Snapshot* snapshot1, Snapshot* snapshot2,
-  xbt_dynar_t previous, Type* type, int pointer_level);
+  HeapLocationPairs* previous, Type* type, int pointer_level);
 
 }
 }
@@ -71,11 +76,29 @@ namespace mc {
 struct HeapLocation {
   int block = 0;
   int fragment = 0;
+
   HeapLocation() {}
   HeapLocation(int block, int fragment = 0) : block(block), fragment(fragment) {}
+
+  bool operator==(HeapLocation const& that) const
+  {
+    return block == that.block && fragment == that.fragment;
+  }
+  bool operator<(HeapLocation const& that) const
+  {
+    return std::make_pair(block, fragment)
+      < std::make_pair(that.block, that.fragment);
+  }
 };
 
-typedef std::array<HeapLocation, 2> HeapLocationPair;
+static inline
+HeapLocationPair makeHeapLocationPair(int block1, int fragment1, int block2, int fragment2)
+{
+  return simgrid::mc::HeapLocationPair({
+    simgrid::mc::HeapLocation(block1, fragment1),
+    simgrid::mc::HeapLocation(block2, fragment2)
+  });
+}
 
 struct HeapArea : public HeapLocation {
   bool valid = false;
@@ -200,7 +223,7 @@ struct StateComparator {
         && this->equals_to2_(b2, f2).fragment == f1;
   }
 
-  void match_equals(xbt_dynar_t list);
+  void match_equals(HeapLocationPairs* list);
 };
 
 }
@@ -208,35 +231,6 @@ struct StateComparator {
 
 /************************************************************************************/
 
-static int is_new_heap_area_pair(xbt_dynar_t list, int block1, int fragment1,
-                                 int block2, int fragment2)
-{
-
-  unsigned int cursor = 0;
-  simgrid::mc::HeapLocationPair* current_pair;
-  xbt_dynar_foreach(list, cursor, current_pair)
-    if ((*current_pair)[0].block == block1
-        && (*current_pair)[1].block == block2
-        && (*current_pair)[0].fragment == fragment1
-        && (*current_pair)[1].fragment == fragment2)
-      return 0;
-  return 1;
-}
-
-static int add_heap_area_pair(xbt_dynar_t list, int block1, int fragment1,
-                              int block2, int fragment2)
-{
-  if (!is_new_heap_area_pair(list, block1, fragment1, block2, fragment2))
-    return 0;
-  simgrid::mc::HeapLocationPair* pair = xbt_new0(simgrid::mc::HeapLocationPair, 1);
-  (*pair)[0].block = block1;
-  (*pair)[0].fragment = fragment1;
-  (*pair)[1].block = block2;
-  (*pair)[1].fragment = fragment2;
-  xbt_dynar_push(list, &pair);
-  return 1;
-}
-
 static ssize_t heap_comparison_ignore_size(
   std::vector<simgrid::mc::IgnoredHeapRegion>* ignore_list,
   const void *address)
@@ -278,22 +272,19 @@ static bool is_block_stack(int block)
 namespace simgrid {
 namespace mc {
 
-void StateComparator::match_equals(xbt_dynar_t list)
+void StateComparator::match_equals(HeapLocationPairs* list)
 {
-  unsigned int cursor = 0;
-  simgrid::mc::HeapLocationPair* current_pair;
-
-  xbt_dynar_foreach(list, cursor, current_pair) {
-    if ((*current_pair)[0].fragment != -1) {
-      this->equals_to1_((*current_pair)[0].block, (*current_pair)[0].fragment) =
-          simgrid::mc::HeapArea((*current_pair)[1].block, (*current_pair)[1].fragment);
-      this->equals_to2_((*current_pair)[1].block, (*current_pair)[1].fragment) =
-          simgrid::mc::HeapArea((*current_pair)[0].block, (*current_pair)[0].fragment);
+  for (auto const& pair : *list) {
+    if (pair[0].fragment != -1) {
+      this->equals_to1_(pair[0].block, pair[0].fragment) =
+          simgrid::mc::HeapArea(pair[1].block, pair[1].fragment);
+      this->equals_to2_(pair[1].block, pair[1].fragment) =
+          simgrid::mc::HeapArea(pair[0].block, pair[0].fragment);
     } else {
-      this->equals_to1_((*current_pair)[0].block, 0) =
-          simgrid::mc::HeapArea((*current_pair)[1].block, (*current_pair)[1].fragment);
-      this->equals_to2_((*current_pair)[1].block, 0) =
-          simgrid::mc::HeapArea((*current_pair)[0].block, (*current_pair)[0].fragment);
+      this->equals_to1_(pair[0].block, 0) =
+          simgrid::mc::HeapArea(pair[1].block, pair[1].fragment);
+      this->equals_to2_(pair[1].block, 0) =
+          simgrid::mc::HeapArea(pair[0].block, pair[0].fragment);
     }
   }
 }
@@ -654,7 +645,7 @@ static int compare_heap_area_without_type(
   const void *real_area1, const void *real_area2,
   simgrid::mc::Snapshot* snapshot1,
   simgrid::mc::Snapshot* snapshot2,
-  xbt_dynar_t previous, int size,
+  HeapLocationPairs* previous, int size,
   int check_ignore)
 {
   simgrid::mc::Process* process = &mc_model_checker->process();
@@ -738,7 +729,7 @@ static int compare_heap_area_with_type(
   const void *real_area1, const void *real_area2,
   simgrid::mc::Snapshot* snapshot1,
   simgrid::mc::Snapshot* snapshot2,
-  xbt_dynar_t previous, simgrid::mc::Type* type,
+  HeapLocationPairs* previous, simgrid::mc::Type* type,
   int area_size, int check_ignore,
   int pointer_level)
 {
@@ -1009,7 +1000,7 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index,
                       const void *area1, const void *area2,
                       simgrid::mc::Snapshot* snapshot1,
                       simgrid::mc::Snapshot* snapshot2,
-                      xbt_dynar_t previous,
+                      HeapLocationPairs* previous,
                       simgrid::mc::Type* type, int pointer_level)
 {
   simgrid::mc::Process* process = &mc_model_checker->process();
@@ -1038,8 +1029,7 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index,
   malloc_info heapinfo_temp1, heapinfo_temp2;
 
   if (previous == nullptr) {
-    previous = xbt_dynar_new(sizeof(simgrid::mc::HeapLocationPair*), [](void *d) {
-      xbt_free((simgrid::mc::HeapLocationPair*) * (void **) d); });
+    previous = new HeapLocationPairs();
     match_pairs = 1;
   }
 
@@ -1053,10 +1043,11 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index,
 
   // If either block is a stack block:
   if (is_block_stack((int) block1) && is_block_stack((int) block2)) {
-    add_heap_area_pair(previous, block1, -1, block2, -1);
+    previous->insert(simgrid::mc::makeHeapLocationPair(
+      block1, -1, block2, -1));
     if (match_pairs) {
       state.match_equals(previous);
-      xbt_dynar_free(&previous);
+      delete previous;
     }
     return 0;
   }
@@ -1067,7 +1058,7 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index,
       || ((char *) area2 < (char *) state.std_heap_copy.heapbase)
       || (block2 > (ssize_t) state.processStates[1].heapsize) || (block2 < 1)) {
     if (match_pairs)
-      xbt_dynar_free(&previous);
+      delete previous;
     return 1;
   }
 
@@ -1109,7 +1100,7 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index,
     /* Free block */
     if (match_pairs) {
       state.match_equals(previous);
-      xbt_dynar_free(&previous);
+      delete previous;
     }
     return 0;
   }
@@ -1128,7 +1119,7 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index,
         && state.blocksEqual(block1, block2)) {
       if (match_pairs) {
         state.match_equals(previous);
-        xbt_dynar_free(&previous);
+        delete previous;
       }
       return 0;
     }
@@ -1139,7 +1130,7 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index,
           && (type->name.empty() || type->name == "struct s_smx_context")) {
         if (match_pairs) {
           state.match_equals(previous);
-          xbt_dynar_free(&previous);
+          delete previous;
         }
         return -1;
       }
@@ -1147,20 +1138,21 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index,
 
     if (heapinfo1->busy_block.size != heapinfo2->busy_block.size) {
       if (match_pairs)
-        xbt_dynar_free(&previous);
+        delete previous;
       return 1;
     }
 
     if (heapinfo1->busy_block.busy_size != heapinfo2->busy_block.busy_size) {
       if (match_pairs)
-        xbt_dynar_free(&previous);
+        delete previous;
       return 1;
     }
 
-    if (!add_heap_area_pair(previous, block1, -1, block2, -1)) {
+    if (!previous->insert(simgrid::mc::makeHeapLocationPair(
+        block1, -1, block2, -1)).second) {
       if (match_pairs) {
         state.match_equals(previous);
-        xbt_dynar_free(&previous);
+        delete previous;
       }
       return 0;
     }
@@ -1177,7 +1169,7 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index,
     if (size <= 0) {
       if (match_pairs) {
         state.match_equals(previous);
-        xbt_dynar_free(&previous);
+        delete previous;
       }
       return 0;
     }
@@ -1211,7 +1203,7 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index,
           || heapinfo2->busy_frag.frag_size[frag2] == -1) {
         if (match_pairs) {
           state.match_equals(previous);
-          xbt_dynar_free(&previous);
+          delete previous;
         }
         return -1;
       }
@@ -1220,7 +1212,7 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index,
           || type_size != heapinfo2->busy_frag.frag_size[frag2]) {
         if (match_pairs) {
           state.match_equals(previous);
-          xbt_dynar_free(&previous);
+          delete previous;
         }
         return -1;
       }
@@ -1232,7 +1224,7 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index,
       if (offset1==offset2 && state.fragmentsEqual(block1, frag1, block2, frag2)) {
         if (match_pairs) {
           state.match_equals(previous);
-          xbt_dynar_free(&previous);
+          delete previous;
         }
         return 0;
       }
@@ -1243,12 +1235,12 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index,
       if (type_size == -1) {
         if (match_pairs) {
           state.match_equals(previous);
-          xbt_dynar_free(&previous);
+          delete previous;
         }
         return -1;
       } else {
         if (match_pairs)
-          xbt_dynar_free(&previous);
+          delete previous;
         return 1;
       }
     }
@@ -1300,7 +1292,7 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index,
       } else {
         if (match_pairs) {
           state.match_equals(previous);
-          xbt_dynar_free(&previous);
+          delete previous;
         }
         return -1;
       }
@@ -1320,7 +1312,7 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index,
       } else {
         if (match_pairs) {
           state.match_equals(previous);
-          xbt_dynar_free(&previous);
+          delete previous;
         }
         return -1;
       }
@@ -1332,10 +1324,11 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index,
     }
 
     if (offset1 == 0 && offset2 == 0
-      && !add_heap_area_pair(previous, block1, frag1, block2, frag2)) {
+      && !previous->insert(simgrid::mc::makeHeapLocationPair(
+        block1, frag1, block2, frag2)).second) {
         if (match_pairs) {
           state.match_equals(previous);
-          xbt_dynar_free(&previous);
+          delete previous;
         }
         return 0;
       }
@@ -1343,7 +1336,7 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index,
     if (size <= 0) {
       if (match_pairs) {
         state.match_equals(previous);
-        xbt_dynar_free(&previous);
+        delete previous;
       }
       return 0;
     }
@@ -1355,7 +1348,7 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index,
 
   } else {
     if (match_pairs)
-      xbt_dynar_free(&previous);
+      delete previous;
     return 1;
   }
 
@@ -1373,13 +1366,13 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index,
 
   if (res_compare == 1) {
     if (match_pairs)
-      xbt_dynar_free(&previous);
+      delete previous;
     return res_compare;
   }
 
   if (match_pairs) {
     state.match_equals(previous);
-    xbt_dynar_free(&previous);
+    delete previous;
   }
 
   return 0;