}
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;
}
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) {
#include <sys/mman.h>
#endif
+#ifdef __cpluscplus
+#include <algorithm>
+#endif
+
#include <elfutils/libdw.h>
#include <simgrid/msg.h>
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;
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;
}
}
} 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());