GCC Code Coverage Report

Directory: ./
File: tasks/krasnopevtseva_v_bubble_sort/mpi/src/ops_mpi.cpp
Date: 2026-01-09 01:27:18
Exec Total Coverage
Lines: 94 98 95.9%
Functions: 10 11 90.9%
Branches: 75 126 59.5%
Line Branch Exec Source
1 #include "krasnopevtseva_v_bubble_sort/mpi/include/ops_mpi.hpp"
2
3 #include <mpi.h>
4
5 #include <algorithm>
6 #include <cmath>
7 #include <cstddef>
8 #include <utility>
9 #include <vector>
10
11 #include "krasnopevtseva_v_bubble_sort/common/include/common.hpp"
12
13 namespace krasnopevtseva_v_bubble_sort {
14
15
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 KrasnopevtsevaVBubbleSortMPI::KrasnopevtsevaVBubbleSortMPI(const InType &in) {
16 SetTypeOfTask(GetStaticTypeOfTask());
17
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 GetInput() = in;
18 12 GetOutput() = std::vector<int>();
19 12 }
20
21 12 bool KrasnopevtsevaVBubbleSortMPI::ValidationImpl() {
22 const auto &input = GetInput();
23 12 return (!input.empty());
24 }
25
26 12 bool KrasnopevtsevaVBubbleSortMPI::PreProcessingImpl() {
27 12 GetOutput() = std::vector<int>();
28 12 return true;
29 }
30
31 12 bool KrasnopevtsevaVBubbleSortMPI::RunImpl() {
32 12 auto input = GetInput();
33 12 int rank = 0;
34 12 int kol = 0;
35
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
36
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 MPI_Comm_size(MPI_COMM_WORLD, &kol);
37
2/4
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 12 times.
✗ Branch 3 not taken.
 12 if (input.size() <= static_cast<size_t>(kol) || (kol == 1)) {
38 ✗ SeqSort(input);
39 ✗ GetOutput() = input;
40 return true;
41 }
42
43 size_t global_size = input.size();
44
45
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 std::vector<int> local_data = DistributeData(input, rank, kol);
46
47
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 ParallelSort(local_data, rank, kol);
48
49
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 std::vector<int> result = GatherData(local_data, rank, kol, global_size);
50
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 GetOutput() = result;
51
52 return true;
53 }
54
55
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 void KrasnopevtsevaVBubbleSortMPI::ParallelSort(std::vector<int> &local_data, int rank, int kol) {
56
2/4
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 12 times.
✗ Branch 3 not taken.
 12 if (local_data.empty() || kol <= 1) {
57 return;
58 }
59
60 12 SeqSort(local_data);
61
62
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 12 times.
 36 for (int phase = 0; phase < kol; phase++) {
63 int partner = FindPartner(rank, kol, phase);
64
65
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (partner != -1) {
66 12 bool keep_smaller = (rank < partner);
67 12 MergeProc(local_data, partner, keep_smaller);
68 }
69
70 24 MPI_Barrier(MPI_COMM_WORLD);
71 }
72 }
73
74 ✗ int KrasnopevtsevaVBubbleSortMPI::FindPartner(int rank, int kol, int phase) {
75 24 const bool same_parity = ((phase % 2) == (rank % 2));
76
77
4/8
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 12 times.
✓ Branch 5 taken 12 times.
✓ Branch 6 taken 6 times.
✓ Branch 7 taken 6 times.
 24 if (same_parity && rank + 1 < kol) {
78 return rank + 1;
79 }
80
2/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 6 times.
✓ Branch 3 taken 12 times.
 18 if (!same_parity && rank > 0) {
81 6 return rank - 1;
82 }
83 return -1;
84 }
85
86 12 std::vector<int> KrasnopevtsevaVBubbleSortMPI::DistributeData(const std::vector<int> &input, int rank, int kol) {
87 12 int global_size = static_cast<int>(input.size());
88 12 MPI_Bcast(&global_size, 1, MPI_INT, 0, MPI_COMM_WORLD);
89
90 12 int base_chunk = global_size / kol;
91 12 int remainder = global_size % kol;
92
93 12 std::vector<int> send_counts(kol, base_chunk);
94
1/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 12 std::vector<int> displacements(kol, 0);
95
96
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 12 times.
 36 for (int i = 0; i < kol; i++) {
97
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 20 times.
 24 if (i < remainder) {
98 4 send_counts[i]++;
99 }
100
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
 24 if (i > 0) {
101 12 displacements[i] = displacements[i - 1] + send_counts[i - 1];
102 }
103 }
104
105
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 int local_size = send_counts[rank];
106
3/6
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 6 times.
✓ Branch 4 taken 6 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 12 std::vector<int> local_data(local_size);
107
108
3/4
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
✓ Branch 3 taken 12 times.
✗ Branch 4 not taken.
 18 MPI_Scatterv(rank == 0 ? input.data() : nullptr, send_counts.data(), displacements.data(), MPI_INT, local_data.data(),
109 local_size, MPI_INT, 0, MPI_COMM_WORLD);
110
111 12 return local_data;
112 }
113
114 12 void KrasnopevtsevaVBubbleSortMPI::MergeProc(std::vector<int> &data, int partner_rank, bool keep_smaller) {
115 12 int my_size = static_cast<int>(data.size());
116 12 int partner_size = 0;
117
118 12 MPI_Sendrecv(&my_size, 1, MPI_INT, partner_rank, 0, &partner_size, 1, MPI_INT, partner_rank, 0, MPI_COMM_WORLD,
119 MPI_STATUS_IGNORE);
120
121
2/4
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 12 times.
 12 if (partner_size == 0 || my_size == 0) {
122 ✗ return;
123 }
124
125 12 std::vector<int> partner_data(partner_size);
126
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 MPI_Sendrecv(data.data(), my_size, MPI_INT, partner_rank, 1, partner_data.data(), partner_size, MPI_INT, partner_rank,
127 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
128
129
1/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 12 std::vector<int> merged(my_size + partner_size);
130 12 std::ranges::merge(data.begin(), data.end(), partner_data.begin(), partner_data.end(), merged.begin());
131
132
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 if (keep_smaller) {
133
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 std::ranges::copy(merged.begin(), merged.begin() + my_size, data.begin());
134 } else {
135
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 std::ranges::copy(merged.end() - my_size, merged.end(), data.begin());
136 }
137 }
138
139 12 std::vector<int> KrasnopevtsevaVBubbleSortMPI::GatherData(const std::vector<int> &local_data, int rank, int kol,
140 size_t global_size) {
141 12 std::vector<int> result;
142
143
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 if (rank == 0) {
144
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 result.resize(global_size);
145 size_t offset = 0;
146
147 6 int my_size = static_cast<int>(local_data.size());
148
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (my_size > 0) {
149 std::ranges::copy(local_data.begin(), local_data.end(), result.begin() + static_cast<ptrdiff_t>(offset));
150 6 offset += my_size;
151 }
152
153
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 for (int i = 1; i < kol; i++) {
154 6 int remote_size = 0;
155
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Recv(&remote_size, 1, MPI_INT, i, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
156
157
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (remote_size > 0) {
158
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Recv(result.data() + offset, remote_size, MPI_INT, i, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
159 6 offset += remote_size;
160 }
161 }
162 } else {
163 6 int local_size = static_cast<int>(local_data.size());
164
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Send(&local_size, 1, MPI_INT, 0, 0, MPI_COMM_WORLD);
165
166
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (local_size > 0) {
167
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Send(local_data.data(), local_size, MPI_INT, 0, 1, MPI_COMM_WORLD);
168 }
169 }
170
171 12 int result_size = 0;
172
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 if (rank == 0) {
173 6 result_size = static_cast<int>(global_size);
174 }
175
176
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 MPI_Bcast(&result_size, 1, MPI_INT, 0, MPI_COMM_WORLD);
177
178
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 if (rank != 0) {
179
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 result.resize(result_size);
180 }
181
182
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 MPI_Bcast(result.data(), result_size, MPI_INT, 0, MPI_COMM_WORLD);
183
184 12 return result;
185 }
186
187
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 void KrasnopevtsevaVBubbleSortMPI::SeqSort(std::vector<int> &data) {
188
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 if (data.size() <= 1) {
189 return;
190 }
191
192 size_t n = data.size();
193 bool sorted = false;
194
195
2/2
✓ Branch 0 taken 57 times.
✓ Branch 1 taken 12 times.
 69 while (!sorted) {
196 sorted = true;
197
2/2
✓ Branch 0 taken 396 times.
✓ Branch 1 taken 57 times.
 453 for (size_t i = 1; i < n - 1; i += 2) {
198
2/2
✓ Branch 0 taken 218 times.
✓ Branch 1 taken 178 times.
 396 if (data[i] > data[i + 1]) {
199 std::swap(data[i], data[i + 1]);
200 sorted = false;
201 }
202 }
203
2/2
✓ Branch 0 taken 439 times.
✓ Branch 1 taken 57 times.
 496 for (size_t i = 0; i < n - 1; i += 2) {
204
2/2
✓ Branch 0 taken 228 times.
✓ Branch 1 taken 211 times.
 439 if (data[i] > data[i + 1]) {
205 std::swap(data[i], data[i + 1]);
206 sorted = false;
207 }
208 }
209 }
210 }
211
212 12 bool KrasnopevtsevaVBubbleSortMPI::PostProcessingImpl() {
213 12 return true;
214 }
215 } // namespace krasnopevtseva_v_bubble_sort
216