GCC Code Coverage Report

Directory: ./
File: tasks/safronov_m_quicksort_with_batcher_even_odd_merge/mpi/src/ops_mpi.cpp
Date: 2026-01-27 01:59:34
Exec Total Coverage
Lines: 139 145 95.9%
Functions: 15 16 93.8%
Branches: 97 140 69.3%
Line Branch Exec Source
1 #include "safronov_m_quicksort_with_batcher_even_odd_merge/mpi/include/ops_mpi.hpp"
2
3 #include <mpi.h>
4
5 #include <algorithm>
6 #include <cstddef>
7 #include <utility>
8 #include <vector>
9
10 #include "safronov_m_quicksort_with_batcher_even_odd_merge/common/include/common.hpp"
11
12 namespace safronov_m_quicksort_with_batcher_even_odd_merge {
13
14
1/2
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
 26 SafronovMQuicksortWithBatcherEvenOddMergeMPI::SafronovMQuicksortWithBatcherEvenOddMergeMPI(const InType &in) {
15 SetTypeOfTask(GetStaticTypeOfTask());
16
1/2
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
 26 GetInput() = in;
17 26 }
18
19 26 bool SafronovMQuicksortWithBatcherEvenOddMergeMPI::ValidationImpl() {
20 26 return GetOutput().empty();
21 }
22
23
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 26 times.
 26 bool SafronovMQuicksortWithBatcherEvenOddMergeMPI::PreProcessingImpl() {
24 GetOutput().clear();
25 26 return true;
26 }
27
28 26 void SafronovMQuicksortWithBatcherEvenOddMergeMPI::SendingVector(int rank) {
29 26 int size_vec = 0;
30
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 13 times.
 26 if (rank == 0) {
31 13 size_vec = static_cast<int>(GetInput().size());
32 }
33 26 MPI_Bcast(&size_vec, 1, MPI_INT, 0, MPI_COMM_WORLD);
34
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 13 times.
 26 if (rank != 0) {
35 13 GetInput().resize(size_vec);
36 }
37 26 MPI_Bcast(GetInput().data(), size_vec, MPI_INT, 0, MPI_COMM_WORLD);
38 26 }
39
40 ✗ int SafronovMQuicksortWithBatcherEvenOddMergeMPI::LengthsLocalArrays(int size_arr, int rank, int size) {
41 32 int local_size = size_arr / (size);
42 ✗ if ((rank) < (size_arr % size)) {
43 10 local_size += 1;
44 }
45 ✗ return local_size;
46 }
47
48 26 std::vector<int> SafronovMQuicksortWithBatcherEvenOddMergeMPI::CalculatingInterval(int size_prcs, int rank,
49 int size_arr) {
50 26 std::vector<int> vec(2);
51 26 int whole_part = size_arr / size_prcs;
52 26 int real_part = size_arr % size_prcs;
53 26 int start = rank * whole_part;
54
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 20 times.
 26 if ((rank - 1 < real_part) && (rank - 1 != -1)) {
55 6 start += rank;
56
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 13 times.
 20 } else if (rank != 0) {
57 7 start += real_part;
58 }
59 26 int end = start + whole_part - 1;
60
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 20 times.
 26 if (rank < real_part) {
61 end += 1;
62 }
63 26 vec[0] = start;
64 26 vec[1] = end;
65 26 return vec;
66 }
67
68 161 std::pair<int, int> SafronovMQuicksortWithBatcherEvenOddMergeMPI::SplitRange(std::vector<int> &array, int left,
69 int right) {
70 int i = left;
71 int j = right;
72 161 int mid = left + ((right - left) / 2);
73 161 int pivot = array[mid];
74
75
2/2
✓ Branch 0 taken 274 times.
✓ Branch 1 taken 161 times.
 596 while (i <= j) {
76
2/2
✓ Branch 0 taken 204 times.
✓ Branch 1 taken 274 times.
 478 while (array[i] < pivot) {
77 204 i++;
78 }
79
2/2
✓ Branch 0 taken 284 times.
✓ Branch 1 taken 274 times.
 558 while (array[j] > pivot) {
80 284 j--;
81 }
82
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 234 times.
 274 if (i <= j) {
83 int tmp = array[i];
84 234 array[i] = array[j];
85 234 array[j] = tmp;
86 234 i++;
87 234 j--;
88 }
89 }
90
91 161 return {i, j};
92 }
93
94
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 23 times.
 23 void SafronovMQuicksortWithBatcherEvenOddMergeMPI::QuickSort(std::vector<int> &array) {
95
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 23 times.
 23 if (array.empty()) {
96 ✗ return;
97 }
98
1/2
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
 23 std::vector<std::pair<int, int>> stack;
99
1/4
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 23 stack.emplace_back(0, static_cast<int>(array.size()) - 1);
100
101
2/2
✓ Branch 0 taken 164 times.
✓ Branch 1 taken 23 times.
 187 while (!stack.empty()) {
102 auto range = stack.back();
103 stack.pop_back();
104 164 int left = range.first;
105 164 int right = range.second;
106
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 161 times.
 164 if (left >= right) {
107 3 continue;
108 }
109 161 auto borders = SplitRange(array, left, right);
110
2/2
✓ Branch 0 taken 66 times.
✓ Branch 1 taken 95 times.
 161 if (left < borders.second) {
111
1/2
✓ Branch 1 taken 66 times.
✗ Branch 2 not taken.
 66 stack.emplace_back(left, borders.second);
112 }
113
2/2
✓ Branch 0 taken 75 times.
✓ Branch 1 taken 86 times.
 161 if (borders.first < right) {
114
1/2
✓ Branch 1 taken 75 times.
✗ Branch 2 not taken.
 75 stack.emplace_back(borders.first, right);
115 }
116 }
117 }
118
119 32 void SafronovMQuicksortWithBatcherEvenOddMergeMPI::MergeAndSplit(std::vector<int> &own_data,
120 std::vector<int> &neighbor_data, bool flag) {
121 32 std::vector<int> data(own_data.size() + neighbor_data.size());
122 // std::merge(own_data.begin(), own_data.end(), neighbor_data.begin(), neighbor_data.end(), data.begin());
123 32 std::ranges::merge(own_data, neighbor_data, data.begin());
124
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 16 times.
 32 if (!flag) {
125 auto mid = data.begin() + static_cast<std::ptrdiff_t>(own_data.size());
126 16 std::copy(data.begin(), mid, own_data.begin());
127 } else {
128 auto start = data.begin() + static_cast<std::ptrdiff_t>(neighbor_data.size());
129 16 std::copy(start, data.end(), own_data.begin());
130 }
131 32 }
132
133 32 void SafronovMQuicksortWithBatcherEvenOddMergeMPI::DataExchange(std::vector<int> &own_data, int size_arr, int rank,
134 int size, int neighbor) {
135 MPI_Status status;
136
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 22 times.
 32 int neighbor_size = LengthsLocalArrays(size_arr, rank + neighbor, size);
137
1/2
✓ Branch 2 taken 32 times.
✗ Branch 3 not taken.
 32 std::vector<int> neighbor_data(neighbor_size);
138
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 MPI_Sendrecv(own_data.data(), static_cast<int>(own_data.size()), MPI_INT, rank + neighbor, 0, neighbor_data.data(),
139 neighbor_size, MPI_INT, rank + neighbor, 0, MPI_COMM_WORLD, &status);
140 32 bool flag = (neighbor != 1);
141
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 MergeAndSplit(own_data, neighbor_data, flag);
142 32 }
143
144 34 void SafronovMQuicksortWithBatcherEvenOddMergeMPI::EvenPhase(std::vector<int> &own_data, std::vector<int> &interval,
145 int size_arr, int rank, int size) {
146
6/8
✓ Branch 0 taken 17 times.
✓ Branch 1 taken 17 times.
✓ Branch 2 taken 17 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 16 times.
✓ Branch 5 taken 1 times.
✓ Branch 6 taken 16 times.
✗ Branch 7 not taken.
 34 if ((rank % 2 == 0) && (rank + 1 < size) && (interval[1] != size_arr - 1) && (interval[0] <= interval[1])) {
147 16 DataExchange(own_data, size_arr, rank, size, 1);
148
4/4
✓ Branch 0 taken 17 times.
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 16 times.
✓ Branch 3 taken 1 times.
 18 } else if ((interval[0] <= interval[1]) && (rank % 2 == 1)) {
149 16 DataExchange(own_data, size_arr, rank, size, -1);
150 }
151 34 }
152
153 22 void SafronovMQuicksortWithBatcherEvenOddMergeMPI::OddPhase(std::vector<int> &own_data, std::vector<int> &interval,
154 int size_arr, int rank, int size) {
155
3/8
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 11 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 22 if ((rank % 2 == 1) && (rank + 1 < size) && (interval[1] != size_arr - 1) && (interval[0] <= interval[1])) {
156 ✗ DataExchange(own_data, size_arr, rank, size, 1);
157
4/6
✓ Branch 0 taken 22 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 11 times.
✓ Branch 3 taken 11 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 11 times.
 22 } else if ((interval[0] <= interval[1]) && (rank != 0) && (rank % 2 == 0)) {
158 ✗ DataExchange(own_data, size_arr, rank, size, -1);
159 }
160 22 }
161
162 26 void SafronovMQuicksortWithBatcherEvenOddMergeMPI::BatcherOddEvenPhases(std::vector<int> &own_data,
163 std::vector<int> &interval, int size_arr,
164 int rank, int size) {
165 26 int min_local_block_size = size_arr / size;
166
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 22 times.
 26 if (min_local_block_size == 0) {
167 min_local_block_size = 1;
168 }
169 26 int phases = (size_arr + min_local_block_size - 1) / min_local_block_size;
170
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 26 times.
 82 for (int i = 0; i < phases; i++) {
171
2/2
✓ Branch 0 taken 34 times.
✓ Branch 1 taken 22 times.
 56 if (i % 2 == 0) {
172 34 EvenPhase(own_data, interval, size_arr, rank, size);
173 } else {
174 22 OddPhase(own_data, interval, size_arr, rank, size);
175 }
176 }
177 26 }
178
179 26 void SafronovMQuicksortWithBatcherEvenOddMergeMPI::SendingResult(int rank) {
180 26 int total_size = 0;
181
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 13 times.
 26 if (rank == 0) {
182 13 total_size = static_cast<int>(GetOutput().size());
183 }
184
185 26 MPI_Bcast(&total_size, 1, MPI_INT, 0, MPI_COMM_WORLD);
186
187
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 13 times.
 26 if (rank != 0) {
188 13 GetOutput().resize(total_size);
189 }
190
191 26 MPI_Bcast(GetOutput().data(), total_size, MPI_INT, 0, MPI_COMM_WORLD);
192 26 }
193
194 26 bool SafronovMQuicksortWithBatcherEvenOddMergeMPI::RunImpl() {
195 26 int size = 0;
196 26 int rank = 0;
197 26 MPI_Comm_size(MPI_COMM_WORLD, &size);
198 26 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
199
200 26 SendingVector(rank);
201
202
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 13 times.
 26 if (rank == 0) {
203 13 int size_arr = static_cast<int>(GetInput().size());
204 13 std::vector<int> sizes_local_arrays(size);
205
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 13 times.
 26 for (int i = 1; i < size; i++) {
206
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 std::vector<int> interval = CalculatingInterval(size, i, size_arr);
207 13 sizes_local_arrays[i] = (interval[1] + 1) - interval[0];
208
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 MPI_Send(interval.data(), 2, MPI_INT, i, 0, MPI_COMM_WORLD);
209 }
210
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 std::vector<int> interval = CalculatingInterval(size, 0, size_arr);
211
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 1 times.
 13 std::vector<int> own_data = {};
212
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 1 times.
 13 if (interval[0] <= interval[1]) {
213
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 own_data = std::vector<int>(GetInput().begin() + interval[0], GetInput().begin() + interval[1] + 1);
214
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 QuickSort(own_data);
215 }
216
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 BatcherOddEvenPhases(own_data, interval, size_arr, rank, size);
217 13 GetOutput().insert(GetOutput().end(), own_data.begin(), own_data.end());
218 MPI_Status status;
219
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 13 times.
 26 for (int i = 1; i < size; i++) {
220
1/4
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 13 std::vector<int> buf(sizes_local_arrays[i]);
221
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 MPI_Recv(buf.data(), sizes_local_arrays[i], MPI_INT, i, 2, MPI_COMM_WORLD, &status);
222
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 2 times.
 13 GetOutput().insert(GetOutput().end(), buf.begin(), buf.end());
223 }
224 } else {
225 MPI_Status status;
226
1/2
✓ Branch 2 taken 13 times.
✗ Branch 3 not taken.
 13 std::vector<int> buf(2);
227
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 MPI_Recv(buf.data(), 2, MPI_INT, 0, 0, MPI_COMM_WORLD, &status);
228 13 std::vector<int> own_data = {};
229
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 2 times.
 13 if (buf[0] <= buf[1]) {
230
1/4
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 11 own_data = std::vector<int>(GetInput().begin() + buf[0], GetInput().begin() + buf[1] + 1);
231
1/2
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
 11 QuickSort(own_data);
232 }
233 13 int size_arr = static_cast<int>(GetInput().size());
234
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 BatcherOddEvenPhases(own_data, buf, size_arr, rank, size);
235
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 MPI_Send(own_data.data(), static_cast<int>(own_data.size()), MPI_INT, 0, 2, MPI_COMM_WORLD);
236 }
237 26 SendingResult(rank);
238 26 return true;
239 }
240
241 26 bool SafronovMQuicksortWithBatcherEvenOddMergeMPI::PostProcessingImpl() {
242 26 return true;
243 }
244
245 } // namespace safronov_m_quicksort_with_batcher_even_odd_merge
246