GCC Code Coverage Report

Directory: ./
File: tasks/timofeev_n_radix_merge_sort/mpi/src/ops_mpi.cpp
Date: 2026-01-27 01:59:34
Exec Total Coverage
Lines: 95 152 62.5%
Functions: 11 14 78.6%
Branches: 56 144 38.9%
Line Branch Exec Source
1 #include "timofeev_n_radix_merge_sort/mpi/include/ops_mpi.hpp"
2
3 #include <mpi.h>
4
5 #include <algorithm>
6 #include <climits>
7 #include <cmath>
8 #include <cstddef>
9 #include <ranges>
10 #include <vector>
11
12 #include "timofeev_n_radix_merge_sort/common/include/common.hpp"
13
14 namespace timofeev_n_radix_merge_sort {
15
16
1/2
✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
 22 TimofeevNRadixMergeMPI::TimofeevNRadixMergeMPI(const InType &in) {
17 SetTypeOfTask(GetStaticTypeOfTask());
18
1/2
✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
 22 GetInput() = in;
19 22 GetOutput() = std::vector<int>(0);
20 22 }
21
22 22 bool TimofeevNRadixMergeMPI::ValidationImpl() {
23 22 return !GetInput().empty();
24 }
25
26 22 bool TimofeevNRadixMergeMPI::PreProcessingImpl() {
27 22 return true;
28 }
29
30 ✗ int TimofeevNRadixMergeMPI::GetDigit(int num, int digit) {
31 38 int abs_num = std::abs(num);
32
33 // потому что без использования возведения в степень (как функции)
34
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 38 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 38 for (int i = 0; i < digit; i++) {
35 ✗ abs_num /= 10;
36 }
37
38 38 return abs_num % 10;
39 }
40
41
1/2
✓ Branch 0 taken 11 times.
✗ Branch 1 not taken.
 11 int TimofeevNRadixMergeMPI::GetMaxDigits(const std::vector<int> &arr) {
42
1/2
✓ Branch 0 taken 11 times.
✗ Branch 1 not taken.
 11 if (arr.empty()) {
43 return 0;
44 }
45
46 // Находим максимальное по модулю число
47 11 int max_abs = 0;
48
2/2
✓ Branch 0 taken 38 times.
✓ Branch 1 taken 11 times.
 49 for (int num : arr) {
49 38 int abs_num = std::abs(num);
50 38 max_abs = std::max(abs_num, max_abs);
51 }
52
53 int digits = 0;
54
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 11 times.
 21 while (max_abs > 0) {
55 10 digits++;
56 10 max_abs /= 10;
57 }
58 11 return digits == 0 ? 1 : digits; // минимум 1 разряд
59 }
60
61 9 void TimofeevNRadixMergeMPI::SplitPosNeg(const std::vector<int> &arr, std::vector<int> &negative,
62 std::vector<int> &positive) {
63
2/2
✓ Branch 0 taken 38 times.
✓ Branch 1 taken 9 times.
 47 for (int num : arr) {
64
2/2
✓ Branch 0 taken 17 times.
✓ Branch 1 taken 21 times.
 38 if (num < 0) {
65 17 negative.push_back(-num);
66 } else {
67 positive.push_back(num);
68 }
69 }
70 9 }
71
72 11 void TimofeevNRadixMergeMPI::RadixMergeBucketHelpingFunction(std::vector<int> &part, int digit) {
73 11 std::vector<std::vector<int>> buckets(10);
74
2/2
✓ Branch 0 taken 38 times.
✓ Branch 1 taken 11 times.
 49 for (int num : part) {
75 int d = GetDigit(num, digit);
76
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 38 times.
 38 buckets[d].push_back(num);
77 }
78
79 // Собираем числа обратно в вектор
80 part.clear();
81
2/2
✓ Branch 0 taken 110 times.
✓ Branch 1 taken 11 times.
 121 for (int i = 0; i < 10; i++) {
82
3/4
✓ Branch 0 taken 38 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 38 times.
✓ Branch 3 taken 110 times.
 148 for (int num : buckets[i]) {
83 part.push_back(num);
84 }
85 }
86 11 }
87
88
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 9 times.
 11 void TimofeevNRadixMergeMPI::RadixMergeSort(std::vector<int> &part) {
89
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 9 times.
 11 if (part.size() <= 1) {
90 2 return;
91 }
92
93 // Разделяем на отрицательные и положительные числа
94 9 std::vector<int> negative;
95 9 std::vector<int> positive;
96
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 SplitPosNeg(part, negative, positive);
97
98 // Сортируем отрицательные числа (по модулю)
99
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 4 times.
 9 if (!negative.empty()) {
100 5 int max_digits_neg = GetMaxDigits(negative);
101
102
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 for (int digit = 0; digit < max_digits_neg; digit++) {
103
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 RadixMergeBucketHelpingFunction(negative, digit);
104 }
105 }
106
107 // Сортируем положительные числа
108
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 3 times.
 9 if (!positive.empty()) {
109 6 int max_digits_pos = GetMaxDigits(positive);
110
111
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 for (int digit = 0; digit < max_digits_pos; digit++) {
112
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 RadixMergeBucketHelpingFunction(positive, digit);
113 }
114 }
115 // А теперь сливаем всё в один вектор, причём негативные - задом наперёд,
116 // позитивные - как было.
117 // Вот так.
118
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 4 times.
 9 if (!negative.empty()) {
119 int j = 0;
120
2/2
✓ Branch 0 taken 17 times.
✓ Branch 1 taken 5 times.
 22 for (int &i : std::ranges::reverse_view(negative)) {
121 17 part[j] = -i;
122 17 j++;
123 }
124 }
125
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 3 times.
 9 if (!positive.empty()) {
126
2/2
✓ Branch 0 taken 21 times.
✓ Branch 1 taken 6 times.
 27 for (size_t i = 0; i < positive.size(); i++) {
127 21 part[i + negative.size()] = positive[i];
128 }
129 }
130 }
131
132 ✗ void TimofeevNRadixMergeMPI::SliyanieHelp(std::vector<std::vector<int>> &received, std::vector<int> &indexes,
133 std::vector<int> &out, int &i) {
134 int smales = INT_MAX;
135 int index_smales = 0;
136 ✗ for (size_t j = 0; j < received.size(); j++) {
137 ✗ if (static_cast<size_t>(indexes[j]) < received[j].size() && received[j][indexes[j]] <= smales) {
138 ✗ index_smales = static_cast<int>(j);
139 smales = received[j][indexes[j]];
140 }
141 }
142 ✗ out[i] = received[index_smales][indexes[index_smales]];
143 ✗ indexes[index_smales]++;
144 ✗ }
145
146 ✗ void TimofeevNRadixMergeMPI::Sliyanie(std::vector<std::vector<int>> &received, std::vector<int> &out) {
147 ✗ std::vector<int> indexes(received.size(), 0);
148 ✗ for (int i = 0; static_cast<size_t>(i) < out.size(); i++) {
149 ✗ SliyanieHelp(received, indexes, out, i);
150 }
151 ✗ }
152
153 11 void TimofeevNRadixMergeMPI::HandleTwoProcesses(std::vector<int> &in, std::vector<int> &out) {
154 11 int yes = 1;
155 11 MPI_Send(&yes, 1, MPI_INT, 1, 0, MPI_COMM_WORLD);
156 11 size_t size_size = in.size();
157 11 MPI_Send(&size_size, 1, MPI_UNSIGNED_LONG, 1, 0, MPI_COMM_WORLD);
158 11 MPI_Send(in.data(), static_cast<int>(size_size), MPI_INT, 1, 0, MPI_COMM_WORLD);
159 11 out.resize(in.size());
160 11 MPI_Recv(out.data(), static_cast<int>(size_size), MPI_INT, 1, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
161 11 size_t concdlusion_size = out.size();
162 11 MPI_Bcast(&concdlusion_size, 1, MPI_UNSIGNED_LONG, 0, MPI_COMM_WORLD);
163 11 MPI_Bcast(out.data(), static_cast<int>(concdlusion_size), MPI_INT, 0, MPI_COMM_WORLD);
164 11 MPI_Barrier(MPI_COMM_WORLD);
165 11 }
166
167 11 bool TimofeevNRadixMergeMPI::HandleZeroRank(std::vector<int> &in, std::vector<int> &out, int &size) {
168
1/2
✓ Branch 0 taken 11 times.
✗ Branch 1 not taken.
 11 if (size == 2) {
169 11 HandleTwoProcesses(in, out);
170 11 return true;
171 }
172 ✗ int served_size = size - 1;
173 size_t k =
174 ✗ (in.size() / static_cast<size_t>(served_size)) + (in.size() % static_cast<size_t>(served_size) > 0 ? 1 : 0);
175 ✗ std::vector<int> sizes_for_processes(served_size, 0);
176 size_t to_sort_size = in.size();
177 ✗ for (size_t i = 0; i < sizes_for_processes.size() - 1; i += k) {
178 ✗ sizes_for_processes[i] = static_cast<int>((to_sort_size - k > 0 ? k : 0));
179 ✗ to_sort_size -= static_cast<int>((to_sort_size > k ? k : 0));
180 }
181 ✗ sizes_for_processes[served_size - 1] = static_cast<int>(to_sort_size);
182 ✗ for (int i = 0; i < served_size; i++) {
183 ✗ int yes = 1;
184 ✗ MPI_Send(&yes, 1, MPI_INT, i + 1, 0, MPI_COMM_WORLD);
185 }
186 ✗ for (int i = served_size; i < size - 1; i++) {
187 ✗ int no = 0;
188 ✗ MPI_Send(&no, 1, MPI_INT, i + 1, 0, MPI_COMM_WORLD);
189 }
190 int accumulated_size = 0;
191 ✗ for (size_t i = 0; i < sizes_for_processes.size(); i++) {
192 ✗ std::vector<int> buf_vec(in.begin() + accumulated_size, in.begin() + accumulated_size + sizes_for_processes[i]);
193 ✗ size_t cur_size = buf_vec.size();
194 ✗ MPI_Send(&cur_size, 1, MPI_UNSIGNED_LONG, static_cast<int>(i + 1), 0, MPI_COMM_WORLD);
195 ✗ MPI_Send(buf_vec.data(), static_cast<int>(cur_size), MPI_INT, static_cast<int>(i + 1), 0, MPI_COMM_WORLD);
196 ✗ accumulated_size += sizes_for_processes[i];
197 }
198 ✗ std::vector<std::vector<int>> received(sizes_for_processes.size(), std::vector<int>(1, 0));
199 ✗ for (size_t i = 0; i < sizes_for_processes.size(); i++) {
200 ✗ received[i].resize(sizes_for_processes[i]);
201 ✗ MPI_Recv(received[i].data(), sizes_for_processes[i], MPI_INT, static_cast<int>(i + 1), 0, MPI_COMM_WORLD,
202 MPI_STATUS_IGNORE);
203 }
204 ✗ if (out.size() != in.size()) {
205 ✗ out.resize(in.size());
206 }
207 ✗ for (size_t i = 0; i < in.size(); i++) {
208 ✗ out[i] = in[i];
209 }
210 ✗ Sliyanie(received, out);
211 ✗ size_t concdlusion_size = out.size();
212 ✗ MPI_Bcast(&concdlusion_size, 1, MPI_UNSIGNED_LONG, 0, MPI_COMM_WORLD);
213 ✗ MPI_Bcast(out.data(), static_cast<int>(concdlusion_size), MPI_INT, 0, MPI_COMM_WORLD);
214 ✗ MPI_Barrier(MPI_COMM_WORLD);
215 return true;
216 ✗ }
217
218 22 bool TimofeevNRadixMergeMPI::RunImpl() {
219 22 int rank = 0;
220 22 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
221 22 int size = 0;
222 22 MPI_Comm_size(MPI_COMM_WORLD, &size);
223
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 22 times.
 22 if (size == 1) {
224 ✗ GetOutput().resize(GetInput().size());
225 ✗ for (size_t i = 0; i < GetInput().size(); i++) {
226 ✗ GetOutput()[i] = GetInput()[i];
227 }
228 ✗ RadixMergeSort(GetOutput());
229 ✗ return true;
230 }
231
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 11 times.
 22 if (rank == 0) {
232 11 return HandleZeroRank(GetInput(), GetOutput(), size);
233 }
234 11 int should_i_work = 0;
235 11 MPI_Recv(&should_i_work, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
236
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 11 times.
 11 if (should_i_work == 0) {
237 ✗ size_t concdlusion_size = 0;
238 ✗ MPI_Bcast(&concdlusion_size, 1, MPI_UNSIGNED_LONG, 0, MPI_COMM_WORLD);
239 ✗ GetOutput().resize(concdlusion_size);
240 ✗ MPI_Bcast(GetOutput().data(), static_cast<int>(concdlusion_size), MPI_INT, 0, MPI_COMM_WORLD);
241 ✗ MPI_Barrier(MPI_COMM_WORLD);
242 return true;
243 }
244 11 size_t cur_size = 0;
245 11 MPI_Recv(&cur_size, 1, MPI_UNSIGNED_LONG, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
246 11 std::vector<int> buf_vec(cur_size);
247
1/2
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
 11 MPI_Recv(buf_vec.data(), static_cast<int>(cur_size), MPI_INT, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
248
1/2
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
 11 RadixMergeSort(buf_vec);
249
1/2
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
 11 MPI_Send(buf_vec.data(), static_cast<int>(cur_size), MPI_INT, 0, 0, MPI_COMM_WORLD);
250 11 size_t concdlusion_size = 0;
251
1/2
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
 11 MPI_Bcast(&concdlusion_size, 1, MPI_UNSIGNED_LONG, 0, MPI_COMM_WORLD);
252
1/2
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
 11 GetOutput().resize(concdlusion_size);
253
1/2
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
 11 MPI_Bcast(GetOutput().data(), static_cast<int>(concdlusion_size), MPI_INT, 0, MPI_COMM_WORLD);
254
1/2
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
 11 MPI_Barrier(MPI_COMM_WORLD);
255 return true;
256 }
257
258 22 bool TimofeevNRadixMergeMPI::PostProcessingImpl() {
259 22 return true;
260 }
261
262 } // namespace timofeev_n_radix_merge_sort
263