GCC Code Coverage Report

Directory: ./
File: tasks/sinev_a_quicksort_with_simple_merge/mpi/src/ops_mpi.cpp
Date: 2026-01-27 01:59:34
Exec Total Coverage
Lines: 144 152 94.7%
Functions: 13 13 100.0%
Branches: 107 154 69.5%
Line Branch Exec Source
1 #include "sinev_a_quicksort_with_simple_merge/mpi/include/ops_mpi.hpp"
2
3 #include <mpi.h>
4
5 #include <algorithm>
6 #include <cstddef>
7 #include <stack>
8 #include <utility>
9 #include <vector>
10
11 #include "sinev_a_quicksort_with_simple_merge/common/include/common.hpp"
12 // #include "util/include/util.hpp"
13
14 namespace sinev_a_quicksort_with_simple_merge {
15
16
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 SinevAQuicksortWithSimpleMergeMPI::SinevAQuicksortWithSimpleMergeMPI(const InType &in) {
17 SetTypeOfTask(GetStaticTypeOfTask());
18
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 GetInput() = in;
19
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 GetOutput().resize(in.size());
20 30 }
21
22 30 bool SinevAQuicksortWithSimpleMergeMPI::ValidationImpl() {
23 30 int rank = 0;
24 30 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
25
26
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 15 times.
 30 if (rank == 0) {
27
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 15 times.
 15 if (GetInput().empty()) {
28 ✗ return false;
29 }
30 }
31
32 return true;
33 }
34
35 30 bool SinevAQuicksortWithSimpleMergeMPI::PreProcessingImpl() {
36 30 int rank = 0;
37 30 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
38
39
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 15 times.
 30 if (rank == 0) {
40 15 GetOutput() = GetInput();
41 }
42 30 return true;
43 }
44
45 47 int SinevAQuicksortWithSimpleMergeMPI::Partition(std::vector<int> &arr, int left, int right) {
46 47 int pivot_index = left + ((right - left) / 2);
47 47 int pivot_value = arr[pivot_index];
48
49 47 std::swap(arr[pivot_index], arr[left]);
50
51 47 int i = left + 1;
52 int j = right;
53
54
2/2
✓ Branch 0 taken 53 times.
✓ Branch 1 taken 4 times.
 57 while (i <= j) {
55
4/4
✓ Branch 0 taken 69 times.
✓ Branch 1 taken 19 times.
✓ Branch 2 taken 34 times.
✓ Branch 3 taken 35 times.
 88 while (i <= j && arr[i] <= pivot_value) {
56 35 i++;
57 }
58
59
4/4
✓ Branch 0 taken 43 times.
✓ Branch 1 taken 43 times.
✓ Branch 2 taken 10 times.
✓ Branch 3 taken 33 times.
 86 while (i <= j && arr[j] > pivot_value) {
60 33 j--;
61 }
62
63
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 43 times.
 53 if (i < j) {
64 10 std::swap(arr[i], arr[j]);
65 10 i++;
66 10 j--;
67 } else {
68 break;
69 }
70 }
71
72 47 std::swap(arr[left], arr[j]);
73 47 return j;
74 }
75
76 61 void SinevAQuicksortWithSimpleMergeMPI::SimpleMerge(std::vector<int> &arr, int left, int mid, int right) {
77
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 61 times.
 61 if (left >= right) {
78 ✗ return;
79 }
80
81 61 std::vector<int> temp(right - left + 1);
82
83 int i = left;
84 61 int j = mid + 1;
85 int k = 0;
86
87
2/2
✓ Branch 0 taken 118 times.
✓ Branch 1 taken 61 times.
 179 while (i <= mid && j <= right) {
88
2/2
✓ Branch 0 taken 90 times.
✓ Branch 1 taken 28 times.
 118 if (arr[i] <= arr[j]) {
89 90 temp[k++] = arr[i++];
90 } else {
91 28 temp[k++] = arr[j++];
92 }
93 }
94
95
2/2
✓ Branch 0 taken 49 times.
✓ Branch 1 taken 61 times.
 110 while (i <= mid) {
96 49 temp[k++] = arr[i++];
97 }
98
99
2/2
✓ Branch 0 taken 57 times.
✓ Branch 1 taken 61 times.
 118 while (j <= right) {
100 57 temp[k++] = arr[j++];
101 }
102
103
2/2
✓ Branch 0 taken 224 times.
✓ Branch 1 taken 61 times.
 285 for (int idx = 0; idx < k; idx++) {
104 224 arr[left + idx] = temp[idx];
105 }
106 }
107
108 29 void SinevAQuicksortWithSimpleMergeMPI::QuickSortWithSimpleMerge(std::vector<int> &arr, int left, int right) {
109 struct Range {
110 int left;
111 int right;
112 };
113
114 std::stack<Range> stack;
115
1/2
✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
 29 stack.push({left, right});
116
117
2/2
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 29 times.
 81 while (!stack.empty()) {
118
1/2
✓ Branch 0 taken 52 times.
✗ Branch 1 not taken.
 52 Range current = stack.top();
119 stack.pop();
120
121 int l = current.left;
122 int r = current.right;
123
124
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 47 times.
 52 if (l >= r) {
125 continue;
126 }
127
128 47 int pivot_index = Partition(arr, l, r);
129
130 47 int left_size = pivot_index - l;
131 47 int right_size = r - pivot_index;
132
133
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 43 times.
 47 if (left_size > 1 && right_size > 1) {
134
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
 4 if (left_size > right_size) {
135 ✗ stack.push({pivot_index + 1, r});
136 ✗ stack.push({l, pivot_index - 1});
137 } else {
138
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 stack.push({l, pivot_index - 1});
139
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 8 stack.push({pivot_index + 1, r});
140 }
141
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 37 times.
 43 } else if (left_size > 1) {
142
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 12 stack.push({l, pivot_index - 1});
143
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 28 times.
 37 } else if (right_size > 1) {
144
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 18 stack.push({pivot_index + 1, r});
145 }
146
147
1/2
✓ Branch 1 taken 47 times.
✗ Branch 2 not taken.
 47 SimpleMerge(arr, l, pivot_index, r);
148 }
149 29 }
150
151 30 SinevAQuicksortWithSimpleMergeMPI::DistributionInfo SinevAQuicksortWithSimpleMergeMPI::PrepareDistributionInfo(
152 int total_size, int world_size, int world_rank) {
153 30 DistributionInfo info;
154
155 30 int base_size = total_size / world_size;
156 30 int remainder = total_size % world_size;
157
158
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 6 times.
 30 info.local_size = base_size + (world_rank < remainder ? 1 : 0);
159
160
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 info.send_counts.assign(world_size, 0);
161
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 info.displacements.assign(world_size, 0);
162
163
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 15 times.
 30 if (world_rank == 0) {
164 int displacement = 0;
165
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 15 times.
 45 for (int i = 0; i < world_size; ++i) {
166
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 6 times.
 54 info.send_counts[i] = base_size + (i < remainder ? 1 : 0);
167 30 info.displacements[i] = displacement;
168 30 displacement += info.send_counts[i];
169 }
170 }
171
172 30 return info;
173 ✗ }
174
175 30 std::vector<int> SinevAQuicksortWithSimpleMergeMPI::DistributeData(int world_size, int world_rank) {
176 30 int total_size = 0;
177
178
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 15 times.
 30 if (world_rank == 0) {
179 15 total_size = static_cast<int>(GetOutput().size());
180 }
181
182 30 MPI_Bcast(&total_size, 1, MPI_INT, 0, MPI_COMM_WORLD);
183
184 30 DistributionInfo info = PrepareDistributionInfo(total_size, world_size, world_rank);
185
186
2/4
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 30 times.
✗ Branch 5 not taken.
 30 std::vector<int> local_buffer(info.local_size);
187
188
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 MPI_Scatterv(GetOutput().data(), info.send_counts.data(), info.displacements.data(), MPI_INT, local_buffer.data(),
189 info.local_size, MPI_INT, 0, MPI_COMM_WORLD);
190
191 30 return local_buffer;
192 30 }
193
194 15 void SinevAQuicksortWithSimpleMergeMPI::PerformMultiWayMerge(const std::vector<int> &all_sizes) {
195 15 std::vector<std::pair<int, int>> segments;
196 15 int offset = 0;
197
198
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 15 times.
 45 for (int all_size : all_sizes) {
199
2/2
✓ Branch 0 taken 29 times.
✓ Branch 1 taken 1 times.
 30 if (all_size > 0) {
200
1/4
✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 29 segments.emplace_back(offset, offset + all_size - 1);
201 29 offset += all_size;
202 }
203 }
204
205
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 15 times.
 29 while (segments.size() > 1) {
206 14 std::vector<std::pair<int, int>> next_segments;
207
208
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 14 times.
 28 for (std::size_t i = 0; i < segments.size(); i += 2) {
209
1/2
✓ Branch 0 taken 14 times.
✗ Branch 1 not taken.
 14 if (i + 1 < segments.size()) {
210 14 int left = segments[i].first;
211 14 int mid = segments[i].second;
212
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 int right = segments[i + 1].second;
213
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 SimpleMerge(GetOutput(), left, mid, right);
214
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 next_segments.emplace_back(left, right);
215 } else {
216 next_segments.push_back(segments[i]);
217 }
218 }
219
220 segments = std::move(next_segments);
221 }
222 15 }
223
224 30 void SinevAQuicksortWithSimpleMergeMPI::BroadcastFinalResult() {
225 30 int world_rank = 0;
226 30 MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);
227
228 30 int final_size = 0;
229
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 15 times.
 30 if (world_rank == 0) {
230 15 final_size = static_cast<int>(GetOutput().size());
231 }
232
233 30 MPI_Bcast(&final_size, 1, MPI_INT, 0, MPI_COMM_WORLD);
234
235
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 15 times.
 30 if (world_rank != 0) {
236 15 GetOutput().resize(final_size);
237 }
238
239 30 MPI_Bcast(GetOutput().data(), final_size, MPI_INT, 0, MPI_COMM_WORLD);
240 30 }
241
242 30 void SinevAQuicksortWithSimpleMergeMPI::ParallelQuickSort() {
243 30 int world_size = 0;
244 30 int world_rank = 0;
245 30 MPI_Comm_size(MPI_COMM_WORLD, &world_size);
246 30 MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);
247
248
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 30 times.
 30 if (world_size == 1) {
249 ✗ if (!GetOutput().empty()) {
250 ✗ QuickSortWithSimpleMerge(GetOutput(), 0, static_cast<int>(GetOutput().size()) - 1);
251 }
252 ✗ return;
253 }
254
255 // 1. Распределение данных по процессам
256 30 std::vector<int> local_buffer = DistributeData(world_size, world_rank);
257
258 // 2. Локальная сортировка на каждом процессе
259
2/2
✓ Branch 0 taken 29 times.
✓ Branch 1 taken 1 times.
 30 if (!local_buffer.empty()) {
260
1/2
✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
 29 QuickSortWithSimpleMerge(local_buffer, 0, static_cast<int>(local_buffer.size()) - 1);
261 }
262
263 // 3. Сбор размеров от всех процессов
264
2/6
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 30 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 30 std::vector<int> all_sizes(world_size);
265
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 int local_size = static_cast<int>(local_buffer.size());
266
267
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 MPI_Gather(&local_size, 1, MPI_INT, all_sizes.data(), 1, MPI_INT, 0, MPI_COMM_WORLD);
268
269 // 4. Подготовка буфера на корневом процессе
270
1/4
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 30 std::vector<int> displacements(world_size, 0);
271 int total_size = 0;
272
273
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 15 times.
 30 if (world_rank == 0) {
274
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 15 times.
 45 for (int i = 0; i < world_size; ++i) {
275 30 displacements[i] = total_size;
276 30 total_size += all_sizes[i];
277 }
278
1/2
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
 15 GetOutput().resize(total_size);
279 }
280
281 // 5. Сбор данных на корневом процессе
282
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 15 times.
 30 int *recv_data = (world_rank == 0) ? GetOutput().data() : nullptr;
283
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 15 times.
 30 int *recv_counts = (world_rank == 0) ? all_sizes.data() : nullptr;
284
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 15 times.
 30 int *recv_displs = (world_rank == 0) ? displacements.data() : nullptr;
285
286
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 MPI_Gatherv(local_buffer.data(), local_size, MPI_INT, recv_data, recv_counts, recv_displs, MPI_INT, 0,
287 MPI_COMM_WORLD);
288
289 // 6. Многостороннее слияние отсортированных частей на процессе 0
290
3/4
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 15 times.
✓ Branch 2 taken 15 times.
✗ Branch 3 not taken.
 30 if (world_rank == 0 && !GetOutput().empty()) {
291
1/2
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
 15 PerformMultiWayMerge(all_sizes);
292 }
293
294 // 7. Рассылка результата (оставляем для корректной работы тестов)
295
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 BroadcastFinalResult();
296 }
297
298 30 bool SinevAQuicksortWithSimpleMergeMPI::RunImpl() {
299 30 ParallelQuickSort();
300 30 return true;
301 }
302
303 30 bool SinevAQuicksortWithSimpleMergeMPI::PostProcessingImpl() {
304 30 return true;
305 }
306
307 } // namespace sinev_a_quicksort_with_simple_merge
308