GCC Code Coverage Report

Directory: ./
File: tasks/shemetov_d_radix_odd_even_mergesort/all/src/ops_all.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 100 104 96.2%
Functions: 11 11 100.0%
Branches: 75 94 79.8%
Line Branch Exec Source
1 #include "shemetov_d_radix_odd_even_mergesort/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4 #include <omp.h>
5
6 #include <algorithm>
7 #include <climits>
8 #include <cstddef>
9 #include <utility>
10 #include <vector>
11
12 #include "shemetov_d_radix_odd_even_mergesort/common/include/common.hpp"
13
14 namespace shemetov_d_radix_odd_even_mergesort {
15
16
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 ShemetovDRadixOddEvenMergeSortALL::ShemetovDRadixOddEvenMergeSortALL(const InType &in) {
17 SetTypeOfTask(GetStaticTypeOfTask());
18 GetInput() = in;
19 24 }
20
21 20 void ShemetovDRadixOddEvenMergeSortALL::ScatterData(std::vector<int> &global_array, std::vector<int> &local_array,
22 size_t chunk, int rank, int ranks, int mpi_init) {
23
1/2
✓ Branch 0 taken 20 times.
✗ Branch 1 not taken.
 20 if (mpi_init != 0 && ranks > 1) {
24
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (rank == 0) {
25
1/2
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
 10 std::ranges::copy(global_array.begin(), global_array.begin() + static_cast<int>(chunk), local_array.begin());
26
27
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 for (int rank_index = 1; rank_index < ranks; rank_index += 1) {
28 10 MPI_Send(global_array.data() + (rank_index * chunk), static_cast<int>(chunk), MPI_INT, rank_index, 0,
29 MPI_COMM_WORLD);
30 }
31 } else {
32 10 MPI_Recv(local_array.data(), static_cast<int>(chunk), MPI_INT, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
33 }
34 ✗ } else if (rank == 0) {
35 ✗ local_array = global_array;
36 }
37 20 }
38
39 20 void ShemetovDRadixOddEvenMergeSortALL::MPISort(std::vector<int> &local_array, size_t chunk) {
40 20 size_t threads = omp_get_max_threads();
41
42 size_t limit = 1;
43
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 20 times.
 38 while (limit * 2 <= std::min(threads, chunk)) {
44 limit *= 2;
45 }
46
47 20 size_t chunk_size = chunk / limit;
48
49 20 #pragma omp parallel num_threads(limit) default(none) shared(local_array, chunk, chunk_size, limit)
50 {
51 size_t thread_num = omp_get_thread_num();
52 size_t left = thread_num * chunk_size;
53 size_t right = left + chunk_size - 1;
54
55 std::vector<int> buffer;
56 std::vector<int> position;
57
58 RadixSort(local_array, left, right, buffer, position);
59 #pragma omp barrier
60 for (size_t segment = chunk_size * 2; segment <= chunk; segment *= 2) {
61 #pragma omp for
62 for (size_t i = 0; i < chunk; i += segment) {
63 OddEvenMerge(local_array, i, segment);
64 }
65 #pragma omp barrier
66 }
67 }
68 20 }
69
70 10 void ShemetovDRadixOddEvenMergeSortALL::MPIMerge(size_t chunk) {
71 10 std::vector<int> &ref_array = array_;
72 10 size_t power = power_;
73
74
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 for (size_t segment = chunk * 2; segment <= power; segment *= 2) {
75 10 #pragma omp parallel for default(none) shared(ref_array, power, segment)
76 for (size_t i = 0; i < power; i += segment) {
77 OddEvenMerge(ref_array, i, segment);
78 }
79 }
80 10 }
81
82 20 void ShemetovDRadixOddEvenMergeSortALL::GatherData(std::vector<int> &global_array, std::vector<int> &local_array,
83 size_t chunk, int rank, int ranks, int mpi_init) {
84
1/2
✓ Branch 0 taken 20 times.
✗ Branch 1 not taken.
 20 if (mpi_init != 0 && ranks > 1) {
85
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (rank == 0) {
86 std::ranges::copy(local_array, global_array.begin());
87
88
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 for (int rank_index = 1; rank_index < ranks; rank_index += 1) {
89 10 MPI_Recv(global_array.data() + (rank_index * chunk), static_cast<int>(chunk), MPI_INT, rank_index, 0,
90 MPI_COMM_WORLD, MPI_STATUS_IGNORE);
91 }
92 } else {
93 10 MPI_Send(local_array.data(), static_cast<int>(chunk), MPI_INT, 0, 0, MPI_COMM_WORLD);
94 }
95 ✗ } else if (rank == 0) {
96 ✗ global_array = local_array;
97 }
98 20 }
99
100 38 void ShemetovDRadixOddEvenMergeSortALL::RadixSort(std::vector<int> &array, size_t left, size_t right,
101 std::vector<int> &buffer, std::vector<int> &position) {
102
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 10 times.
 38 if (left >= right) {
103 return;
104 }
105
106 int maximum =
107
1/2
✓ Branch 0 taken 28 times.
✗ Branch 1 not taken.
 28 *std::ranges::max_element(array.begin() + static_cast<int>(left), array.begin() + static_cast<int>(right) + 1);
108
109 28 size_t segment = right - left + 1;
110
111 28 buffer.resize(segment);
112
1/2
✓ Branch 0 taken 55 times.
✗ Branch 1 not taken.
 55 for (size_t merge_shift = 0; merge_shift < 32; merge_shift += 8) {
113 55 position.assign(256, 0);
114
115
2/2
✓ Branch 0 taken 258 times.
✓ Branch 1 taken 55 times.
 313 for (size_t i = left; i <= right; i += 1) {
116 258 int apply_bitmask = (array[i] >> merge_shift) & 0xFF;
117
118 258 position[apply_bitmask] += 1;
119 }
120
121
2/2
✓ Branch 0 taken 14025 times.
✓ Branch 1 taken 55 times.
 14080 for (size_t i = 1; i < 256; i += 1) {
122 14025 position[i] += position[i - 1];
123 }
124
125
2/2
✓ Branch 0 taken 258 times.
✓ Branch 1 taken 55 times.
 313 for (size_t i = segment; i > 0; i -= 1) {
126 258 size_t current_index = left + i - 1;
127 258 int apply_bitmask = (array[current_index] >> merge_shift) & 0xFF;
128
129 258 buffer[position[apply_bitmask] -= 1] = array[current_index];
130 }
131
132
2/2
✓ Branch 0 taken 258 times.
✓ Branch 1 taken 55 times.
 313 for (size_t i = 0; i < segment; i += 1) {
133 258 array[left + i] = buffer[i];
134 }
135
136
2/2
✓ Branch 0 taken 27 times.
✓ Branch 1 taken 28 times.
 55 if ((maximum >> merge_shift) < 256) {
137 break;
138 }
139 }
140 }
141
142 28 void ShemetovDRadixOddEvenMergeSortALL::OddEvenMerge(std::vector<int> &array, size_t start_offset, size_t segment) {
143
1/2
✓ Branch 0 taken 28 times.
✗ Branch 1 not taken.
 28 if (segment <= 1) {
144 return;
145 }
146
147 28 size_t padding = segment / 2;
148
2/2
✓ Branch 0 taken 129 times.
✓ Branch 1 taken 28 times.
 157 for (size_t i = 0; i < padding; i += 1) {
149
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 101 times.
 129 if (array[start_offset + i] > array[start_offset + padding + i]) {
150 std::swap(array[start_offset + i], array[start_offset + padding + i]);
151 }
152 }
153
154
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 28 times.
 76 for (padding = segment / 4; padding > 0; padding /= 2) {
155 48 size_t step = padding * 2;
156
157
2/2
✓ Branch 0 taken 154 times.
✓ Branch 1 taken 48 times.
 202 for (size_t start_position = padding; start_position < segment - padding; start_position += step) {
158
2/2
✓ Branch 0 taken 243 times.
✓ Branch 1 taken 154 times.
 397 for (size_t i = 0; i < padding; i += 1) {
159
2/2
✓ Branch 0 taken 50 times.
✓ Branch 1 taken 193 times.
 243 if (array[start_offset + start_position + i] > array[start_offset + start_position + i + padding]) {
160 std::swap(array[start_offset + start_position + i], array[start_offset + start_position + i + padding]);
161 }
162 }
163 }
164 }
165 }
166
167 24 bool ShemetovDRadixOddEvenMergeSortALL::ValidationImpl() {
168 const auto &[size, array] = GetInput();
169
3/4
✓ Branch 0 taken 22 times.
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 22 times.
 24 return size > 0 && static_cast<size_t>(size) == array.size();
170 }
171
172
2/2
✓ Branch 0 taken 22 times.
✓ Branch 1 taken 2 times.
 24 bool ShemetovDRadixOddEvenMergeSortALL::PreProcessingImpl() {
173 const auto &[size, array] = GetInput();
174
175
2/2
✓ Branch 0 taken 22 times.
✓ Branch 1 taken 2 times.
 24 if (size <= 0) {
176 return true;
177 }
178
179 22 array_ = array;
180 22 offset_ = *std::ranges::min_element(array_.begin(), array_.end());
181 22 size_ = static_cast<size_t>(size);
182 22 power_ = 1;
183
184
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 22 times.
 86 while (power_ < size_) {
185 64 power_ *= 2;
186 }
187
188
2/2
✓ Branch 0 taken 184 times.
✓ Branch 1 taken 22 times.
 206 for (size_t i = 0; i < size_; i += 1) {
189 184 array_[i] -= offset_;
190 }
191
192
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 10 times.
 22 if (power_ > size_) {
193 12 array_.resize(power_, INT_MAX);
194 }
195
196 return true;
197 }
198
199 24 bool ShemetovDRadixOddEvenMergeSortALL::RunImpl() {
200
4/4
✓ Branch 0 taken 22 times.
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 20 times.
✓ Branch 3 taken 2 times.
 24 if (size_ == 0 || power_ <= 1) {
201 return true;
202 }
203
204 20 int mpi_init = 0;
205 20 MPI_Initialized(&mpi_init);
206
207 20 int rank = 0;
208 20 int num_procs = 1;
209
210
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 20 times.
 20 if (mpi_init != 0) {
211 20 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
212 20 MPI_Comm_size(MPI_COMM_WORLD, &num_procs);
213 }
214
215 int ranks = 1;
216
3/4
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 20 times.
 40 while (ranks * 2 <= num_procs && std::cmp_less_equal(ranks * 2, power_)) {
217 ranks *= 2;
218 }
219
220
1/2
✓ Branch 0 taken 20 times.
✗ Branch 1 not taken.
 20 if (rank < ranks) {
221 20 size_t chunk = power_ / ranks;
222 20 std::vector<int> segment_array(chunk);
223
224
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 ScatterData(array_, segment_array, chunk, rank, ranks, mpi_init);
225
226 20 MPISort(segment_array, chunk);
227
228
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 GatherData(array_, segment_array, chunk, rank, ranks, mpi_init);
229
230
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (rank == 0) {
231 10 MPIMerge(chunk);
232 }
233 }
234
235
1/2
✓ Branch 0 taken 20 times.
✗ Branch 1 not taken.
 20 if (mpi_init != 0) {
236 20 MPI_Bcast(array_.data(), static_cast<int>(power_), MPI_INT, 0, MPI_COMM_WORLD);
237 }
238
239 return true;
240 }
241
242 24 bool ShemetovDRadixOddEvenMergeSortALL::PostProcessingImpl() {
243
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 22 times.
 24 if (size_ == 0) {
244 return true;
245 }
246
247 22 array_.resize(size_);
248
249
2/2
✓ Branch 0 taken 184 times.
✓ Branch 1 taken 22 times.
 206 for (size_t i = 0; i < size_; i += 1) {
250 184 array_[i] += offset_;
251 }
252
253
1/2
✓ Branch 0 taken 22 times.
✗ Branch 1 not taken.
 22 if (!std::ranges::is_sorted(array_.begin(), array_.end())) {
254 return false;
255 }
256
257 22 GetOutput() = array_;
258 22 return true;
259 }
260
261 } // namespace shemetov_d_radix_odd_even_mergesort
262