GCC Code Coverage Report

Directory: ./
File: tasks/ovchinnikov_m_shell_sort_batcher_merge/all/src/ops_all.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 130 134 97.0%
Functions: 14 14 100.0%
Branches: 93 138 67.4%
Line Branch Exec Source
1 #include "ovchinnikov_m_shell_sort_batcher_merge/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4
5 #include <algorithm>
6 #include <cstddef>
7 #include <limits>
8 #include <utility>
9 #include <vector>
10
11 #include "ovchinnikov_m_shell_sort_batcher_merge/common/include/common.hpp"
12
13 namespace ovchinnikov_m_shell_sort_batcher_merge {
14
15 namespace {
16
17 std::size_t NextPowerOfTwo(std::size_t value) {
18 std::size_t power = 1;
19
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 12 times.
 42 while (power < value) {
20 30 power <<= 1;
21 }
22 return power;
23 }
24
25 29 std::vector<int> MergeSorted(const std::vector<int> &first, const std::vector<int> &second) {
26
1/2
✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
 29 std::vector<int> merged;
27
1/2
✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
 29 merged.reserve(first.size() + second.size());
28
29 std::size_t left_index = 0;
30 std::size_t right_index = 0;
31
4/4
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 21 times.
✓ Branch 2 taken 8 times.
✓ Branch 3 taken 40 times.
 69 while (left_index < first.size() && right_index < second.size()) {
32
2/2
✓ Branch 0 taken 29 times.
✓ Branch 1 taken 11 times.
 40 if (first[left_index] <= second[right_index]) {
33 merged.push_back(first[left_index]);
34 29 ++left_index;
35 } else {
36 merged.push_back(second[right_index]);
37 11 ++right_index;
38 }
39 }
40
41
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 29 times.
 37 while (left_index < first.size()) {
42 merged.push_back(first[left_index]);
43 8 ++left_index;
44 }
45
2/2
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 29 times.
 55 while (right_index < second.size()) {
46 merged.push_back(second[right_index]);
47 26 ++right_index;
48 }
49
50 29 return merged;
51 }
52
53 bool IsEvenPosition(std::size_t index) {
54 136 return (index % 2) == 0;
55 }
56
57 26 void SplitByParity(const std::vector<int> &input, std::vector<int> &even, std::vector<int> &odd) {
58 26 even.reserve((input.size() + 1) / 2);
59 26 odd.reserve(input.size() / 2);
60
2/2
✓ Branch 0 taken 68 times.
✓ Branch 1 taken 26 times.
 94 for (std::size_t i = 0; i < input.size(); ++i) {
61
2/2
✓ Branch 0 taken 34 times.
✓ Branch 1 taken 34 times.
 68 if (IsEvenPosition(i)) {
62 even.push_back(input[i]);
63 } else {
64 odd.push_back(input[i]);
65 }
66 }
67 26 }
68
69 13 std::vector<int> InterleaveByParity(const std::vector<int> &even, const std::vector<int> &odd) {
70 13 std::vector<int> merged(even.size() + odd.size());
71 std::size_t even_index = 0;
72 std::size_t odd_index = 0;
73
2/2
✓ Branch 0 taken 68 times.
✓ Branch 1 taken 13 times.
 81 for (std::size_t i = 0; i < merged.size(); ++i) {
74
2/2
✓ Branch 0 taken 34 times.
✓ Branch 1 taken 34 times.
 68 if (IsEvenPosition(i)) {
75 34 merged[i] = even[even_index];
76 34 ++even_index;
77 } else {
78 34 merged[i] = odd[odd_index];
79 34 ++odd_index;
80 }
81 }
82 13 return merged;
83 }
84
85 13 void CompareExchangeOddPairs(std::vector<int> &data) {
86
2/2
✓ Branch 0 taken 21 times.
✓ Branch 1 taken 13 times.
 34 for (std::size_t i = 1; i + 1 < data.size(); i += 2) {
87
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 15 times.
 21 if (data[i] > data[i + 1]) {
88 std::swap(data[i], data[i + 1]);
89 }
90 }
91 13 }
92
93 int LargestPowerOfTwoNotGreaterThan(int value) {
94 int power = 1;
95
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
 24 while ((power * 2) <= value) {
96 power *= 2;
97 }
98 return power;
99 }
100
101 } // namespace
102
103
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 OvchinnikovMShellSortBatcherMergeALL::OvchinnikovMShellSortBatcherMergeALL(const InType &in) {
104 SetTypeOfTask(GetStaticTypeOfTask());
105
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 GetInput() = in;
106 16 }
107
108 20 void OvchinnikovMShellSortBatcherMergeALL::ShellSort(std::vector<int> &data) {
109 const std::size_t n = data.size();
110
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 20 times.
 36 for (std::size_t gap = n / 2; gap > 0; gap /= 2) {
111
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 16 times.
 32 for (std::size_t i = gap; i < n; ++i) {
112 16 const int temp = data[i];
113 std::size_t j = i;
114
4/4
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 8 times.
✓ Branch 2 taken 8 times.
✓ Branch 3 taken 8 times.
 24 while (j >= gap && data[j - gap] > temp) {
115 8 data[j] = data[j - gap];
116 j -= gap;
117 }
118 16 data[j] = temp;
119 }
120 }
121 20 }
122
123
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
 16 std::vector<int> OvchinnikovMShellSortBatcherMergeALL::BatcherOddEvenMerge(const std::vector<int> &left,
124 const std::vector<int> &right) {
125
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
 16 if (left.empty()) {
126 ✗ return right;
127 }
128
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
 16 if (right.empty()) {
129 ✗ return left;
130 }
131
132
3/4
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 3 times.
✓ Branch 3 taken 13 times.
 16 if (left.size() != right.size() || left.size() <= 1) {
133 3 return MergeSorted(left, right);
134 }
135
136 13 std::vector<int> left_even;
137 13 std::vector<int> left_odd;
138 13 std::vector<int> right_even;
139 13 std::vector<int> right_odd;
140
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 SplitByParity(left, left_even, left_odd);
141
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 SplitByParity(right, right_even, right_odd);
142
143
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 std::vector<int> merged_even = MergeSorted(left_even, right_even);
144
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 std::vector<int> merged_odd = MergeSorted(left_odd, right_odd);
145
146
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 std::vector<int> merged = InterleaveByParity(merged_even, merged_odd);
147 13 CompareExchangeOddPairs(merged);
148 return merged;
149 }
150
151
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 10 times.
 12 void OvchinnikovMShellSortBatcherMergeALL::LocalSort(std::vector<int> &local_data) {
152 constexpr std::size_t kMinSizeToSort = 2;
153
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 10 times.
 12 if (local_data.size() < kMinSizeToSort) {
154 2 return;
155 }
156
157 10 const std::size_t half_size = local_data.size() / 2;
158 const auto middle = local_data.begin() + static_cast<std::ptrdiff_t>(half_size);
159
1/2
✓ Branch 2 taken 10 times.
✗ Branch 3 not taken.
 10 std::vector<int> left(local_data.begin(), middle);
160
1/4
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 10 std::vector<int> right(middle, local_data.end());
161
162 10 #pragma omp parallel sections default(none) shared(left, right)
163 {
164 #pragma omp section
165 {
166 ShellSort(left);
167 }
168 #pragma omp section
169 {
170 ShellSort(right);
171 }
172 }
173
174
2/6
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 10 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 20 local_data = BatcherOddEvenMerge(left, right);
175 }
176
177 12 void OvchinnikovMShellSortBatcherMergeALL::TreeMerge(int rank, int active_processes, int chunk_size,
178 std::vector<int> &local_data) {
179
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 6 times.
 18 for (int step = 1; step < active_processes; step *= 2) {
180
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 if ((rank % (2 * step)) == 0) {
181 6 const int sender = rank + step;
182
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 if (sender >= active_processes) {
183 ✗ continue;
184 }
185
186
1/2
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
 6 std::vector<int> received_data(static_cast<std::size_t>(chunk_size) * static_cast<std::size_t>(step));
187
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Recv(received_data.data(), static_cast<int>(received_data.size()), MPI_INT, sender, 0, MPI_COMM_WORLD,
188 MPI_STATUS_IGNORE);
189
2/6
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 6 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 12 local_data = BatcherOddEvenMerge(local_data, received_data);
190 } else {
191 6 const int receiver = rank - step;
192 6 MPI_Send(local_data.data(), static_cast<int>(local_data.size()), MPI_INT, receiver, 0, MPI_COMM_WORLD);
193 6 break;
194 }
195 }
196 12 }
197
198 12 void OvchinnikovMShellSortBatcherMergeALL::ScatterData(int rank, int active_processes, int chunk_size,
199 std::size_t padded_size, std::vector<int> &local_data) {
200
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 if (rank == 0) {
201 6 std::vector<int> padded_data = GetInput();
202
1/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 6 padded_data.resize(padded_size, std::numeric_limits<int>::max());
203
204 const auto chunk_size_diff = static_cast<std::ptrdiff_t>(chunk_size);
205 6 std::copy(padded_data.begin(), padded_data.begin() + chunk_size_diff, local_data.begin());
206
207
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 for (int process = 1; process < active_processes; ++process) {
208 6 const auto offset = static_cast<std::ptrdiff_t>(process) * static_cast<std::ptrdiff_t>(chunk_size);
209
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Send(padded_data.data() + offset, chunk_size, MPI_INT, process, 0, MPI_COMM_WORLD);
210 }
211 } else {
212 6 MPI_Recv(local_data.data(), chunk_size, MPI_INT, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
213 }
214 12 }
215
216 16 bool OvchinnikovMShellSortBatcherMergeALL::ValidationImpl() {
217 16 int is_valid = 1;
218 16 MPI_Bcast(&is_valid, 1, MPI_INT, 0, MPI_COMM_WORLD);
219 16 return is_valid == 1;
220 }
221
222
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
 16 bool OvchinnikovMShellSortBatcherMergeALL::PreProcessingImpl() {
223 GetOutput().clear();
224 16 return true;
225 }
226
227 16 bool OvchinnikovMShellSortBatcherMergeALL::RunImpl() {
228 16 int rank = 0;
229 16 int process_count = 0;
230 16 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
231 16 MPI_Comm_size(MPI_COMM_WORLD, &process_count);
232
233 16 int original_size_int = 0;
234
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 8 times.
 16 if (rank == 0) {
235 8 original_size_int = static_cast<int>(GetInput().size());
236 }
237 16 MPI_Bcast(&original_size_int, 1, MPI_INT, 0, MPI_COMM_WORLD);
238
239 16 const auto original_size = static_cast<std::size_t>(original_size_int);
240
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 14 times.
 16 if (original_size == 0) {
241 GetOutput().clear();
242 2 return true;
243 }
244
245
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 12 times.
 14 if (original_size == 1) {
246
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
 2 if (rank == 0) {
247 1 GetOutput() = GetInput();
248 } else {
249 1 GetOutput().assign(1, 0);
250 }
251 2 MPI_Bcast(GetOutput().data(), 1, MPI_INT, 0, MPI_COMM_WORLD);
252 2 return true;
253 }
254
255 12 const int active_processes = LargestPowerOfTwoNotGreaterThan(process_count);
256 std::size_t padded_size = NextPowerOfTwo(original_size);
257 while (std::cmp_less(padded_size, active_processes)) {
258 ✗ padded_size <<= 1;
259 }
260
261 12 const int chunk_size = static_cast<int>(padded_size / static_cast<std::size_t>(active_processes));
262 12 std::vector<int> local_data;
263
264
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 if (rank < active_processes) {
265
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 local_data.resize(chunk_size);
266
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 ScatterData(rank, active_processes, chunk_size, padded_size, local_data);
267
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 LocalSort(local_data);
268
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 TreeMerge(rank, active_processes, chunk_size, local_data);
269 }
270
271
1/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 12 std::vector<int> result(original_size);
272
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 if (rank == 0) {
273 6 std::copy(local_data.begin(), local_data.begin() + static_cast<std::ptrdiff_t>(original_size), result.begin());
274 }
275
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 MPI_Bcast(result.data(), original_size_int, MPI_INT, 0, MPI_COMM_WORLD);
276
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 GetOutput() = result;
277
278 return true;
279 }
280
281
1/2
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
 16 bool OvchinnikovMShellSortBatcherMergeALL::PostProcessingImpl() {
282
1/2
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
 16 return GetOutput().size() == GetInput().size() && std::ranges::is_sorted(GetOutput().begin(), GetOutput().end());
283 }
284
285 } // namespace ovchinnikov_m_shell_sort_batcher_merge
286