GCC Code Coverage Report

Directory: ./
File: tasks/iskhakov_d_graham_convex_hull/mpi/src/ops_mpi.cpp
Date: 2026-01-27 01:59:34
Exec Total Coverage
Lines: 159 166 95.8%
Functions: 14 15 93.3%
Branches: 145 242 59.9%
Line Branch Exec Source
1 #include "iskhakov_d_graham_convex_hull/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 "iskhakov_d_graham_convex_hull/common/include/common.hpp"
12
13 namespace iskhakov_d_graham_convex_hull {
14
15 namespace {
16
17 constexpr double kEpsilon = 1e-9;
18 constexpr int kMinPointsPerProcess = 10;
19
20 constexpr int kTagSize = 0;
21 constexpr int kTagX = 1;
22 constexpr int kTagY = 2;
23
24 int CalculateLocalOrSendcount(int index, int active_procs, int base_count, int remainder) {
25
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (index < active_procs) {
26
4/4
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 5 times.
✓ Branch 3 taken 1 times.
 22 return base_count + (index < remainder ? 1 : 0);
27 }
28 return 0;
29 }
30
31 int ComputeOrientation(const Point &p, const Point &q, const Point &r) {
32
4/4
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 160 times.
✓ Branch 2 taken 35 times.
✓ Branch 3 taken 147 times.
 352 const double value = ((q.y - p.y) * (r.x - q.x)) - ((q.x - p.x) * (r.y - q.y));
33
34
6/6
✓ Branch 0 taken 53 times.
✓ Branch 1 taken 643 times.
✓ Branch 2 taken 10 times.
✓ Branch 3 taken 160 times.
✓ Branch 4 taken 35 times.
✓ Branch 5 taken 147 times.
 1048 if (std::abs(value) < kEpsilon) {
35 return 0;
36 }
37
4/4
✓ Branch 0 taken 313 times.
✓ Branch 1 taken 330 times.
✓ Branch 2 taken 34 times.
✓ Branch 3 taken 126 times.
 803 return (value > 0) ? 1 : 2;
38 }
39
40 double ComputeDistanceSquared(const Point &a, const Point &b) {
41 53 return ((a.x - b.x) * (a.x - b.x)) + ((a.y - b.y) * (a.y - b.y));
42 }
43
44 25 std::size_t FindMinPointIndex(const std::vector<Point> &points) {
45 std::size_t min_index = 0;
46
2/2
✓ Branch 0 taken 207 times.
✓ Branch 1 taken 25 times.
 232 for (std::size_t i = 1; i < points.size(); ++i) {
47
4/4
✓ Branch 0 taken 192 times.
✓ Branch 1 taken 15 times.
✓ Branch 2 taken 26 times.
✓ Branch 3 taken 166 times.
 207 if (points[i].y < points[min_index].y ||
48
4/4
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 166 times.
✓ Branch 2 taken 3 times.
✓ Branch 3 taken 23 times.
 192 (std::abs(points[i].y - points[min_index].y) < kEpsilon && points[i].x < points[min_index].x)) {
49 min_index = i;
50 }
51 }
52 25 return min_index;
53 }
54
55 25 void FilterCollinearPoints(std::vector<Point> &points, const Point &pivot) {
56 std::size_t unique_count = 1;
57
2/2
✓ Branch 0 taken 172 times.
✓ Branch 1 taken 25 times.
 197 for (std::size_t i = 1; i < points.size(); ++i) {
58
2/2
✓ Branch 0 taken 182 times.
✓ Branch 1 taken 25 times.
 207 while (i + 1 < points.size() && ComputeOrientation(pivot, points[i], points[i + 1]) == 0) {
59 ++i;
60 }
61 172 points[unique_count++] = points[i];
62 }
63 25 points.resize(unique_count);
64 25 }
65
66
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 25 times.
 25 void BuildConvexHull(const std::vector<Point> &points, std::vector<Point> &hull) {
67 hull.clear();
68
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 21 times.
 25 if (points.size() < 3) {
69 4 hull = points;
70 4 return;
71 }
72
73 21 hull.reserve(points.size());
74 hull.push_back(points[0]);
75 hull.push_back(points[1]);
76 hull.push_back(points[2]);
77
78
2/2
✓ Branch 0 taken 126 times.
✓ Branch 1 taken 21 times.
 147 for (std::size_t i = 3; i < points.size(); ++i) {
79
1/2
✓ Branch 0 taken 170 times.
✗ Branch 1 not taken.
 170 while (hull.size() >= 2 && ComputeOrientation(hull[hull.size() - 2], hull[hull.size() - 1], points[i]) != 2) {
80 hull.pop_back();
81 }
82 hull.push_back(points[i]);
83 }
84 }
85
86 } // namespace
87
88
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 IskhakovDGrahamConvexHullMPI::IskhakovDGrahamConvexHullMPI(const InType &in) {
89 SetTypeOfTask(GetStaticTypeOfTask());
90
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 GetInput() = in;
91 32 GetOutput() = OutType{};
92 32 }
93
94 32 bool IskhakovDGrahamConvexHullMPI::ValidationImpl() {
95 32 return GetInput().size() >= 3;
96 }
97
98 32 bool IskhakovDGrahamConvexHullMPI::PreProcessingImpl() {
99 32 return true;
100 }
101
102
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 25 times.
 25 std::vector<Point> IskhakovDGrahamConvexHullMPI::GrahamScan(const std::vector<Point> &input_points) {
103
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 25 times.
 25 if (input_points.size() < 3) {
104 ✗ return input_points;
105 }
106
107 25 std::vector<Point> points{input_points};
108
109 25 const std::size_t min_index = FindMinPointIndex(points);
110 std::swap(points[0], points[min_index]);
111 25 const Point pivot = points[0];
112
113 721 std::sort(points.begin() + 1, points.end(), [&pivot](const Point &a, const Point &b) {
114
2/2
✓ Branch 0 taken 53 times.
✓ Branch 1 taken 643 times.
 696 const int orient = ComputeOrientation(pivot, a, b);
115 if (orient == 0) {
116 const double dist_a = ComputeDistanceSquared(a, pivot);
117 const double dist_b = ComputeDistanceSquared(b, pivot);
118 53 return dist_a < dist_b;
119 }
120 643 return orient == 2;
121 });
122
123
1/2
✓ Branch 1 taken 25 times.
✗ Branch 2 not taken.
 25 FilterCollinearPoints(points, pivot);
124
125 25 std::vector<Point> hull;
126
1/2
✓ Branch 1 taken 25 times.
✗ Branch 2 not taken.
 25 BuildConvexHull(points, hull);
127
128 return hull;
129 }
130
131
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 std::vector<Point> IskhakovDGrahamConvexHullMPI::MergeHulls(const std::vector<Point> &hull_left,
132 const std::vector<Point> &hull_right) {
133
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 if (hull_left.empty()) {
134 ✗ return hull_right;
135 }
136
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 if (hull_right.empty()) {
137 ✗ return hull_left;
138 }
139
140
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 std::vector<Point> merged;
141
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 merged.reserve(hull_left.size() + hull_right.size());
142
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 merged.insert(merged.end(), hull_left.begin(), hull_left.end());
143 6 merged.insert(merged.end(), hull_right.begin(), hull_right.end());
144
145
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 return GrahamScan(merged);
146 }
147
148 ✗ int IskhakovDGrahamConvexHullMPI::CalculateOptimalActiveProcs(int points_count, int world_size) {
149 ✗ int active_procs = world_size;
150
151
6/12
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 26 times.
✓ Branch 2 taken 26 times.
✓ Branch 3 taken 6 times.
✓ Branch 4 taken 6 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 6 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
 64 while (active_procs > 1 && points_count / active_procs < kMinPointsPerProcess) {
152 26 --active_procs;
153 }
154
155
5/12
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 6 times.
✓ Branch 4 taken 6 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 6 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
 38 while (active_procs > 1 && points_count / active_procs < 3) {
156 ✗ --active_procs;
157 }
158
159 ✗ return std::max(active_procs, 1);
160 }
161
162 6 std::vector<Point> IskhakovDGrahamConvexHullMPI::PrepareAndDistributeData(int world_rank, int world_size,
163 int &active_procs_out) {
164 6 int total_points = 0;
165
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (world_rank == 0) {
166 3 total_points = static_cast<int>(GetInput().size());
167 }
168
169 6 MPI_Bcast(&total_points, 1, MPI_INT, 0, MPI_COMM_WORLD);
170
171 6 const int active_procs = CalculateOptimalActiveProcs(total_points, world_size);
172 6 active_procs_out = active_procs;
173
174 const bool is_active = world_rank < active_procs;
175
176 6 const int base_count = total_points / active_procs;
177 6 const int remainder = total_points % active_procs;
178
179
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 const int local_count = is_active ? CalculateLocalOrSendcount(world_rank, active_procs, base_count, remainder) : 0;
180
181 6 std::vector<int> sendcounts(world_size, 0);
182
1/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 6 std::vector<int> displs(world_size, 0);
183
184
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (world_rank == 0) {
185 int offset = 0;
186
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 3 times.
 9 for (int i = 0; i < world_size; ++i) {
187 6 sendcounts[i] = CalculateLocalOrSendcount(i, active_procs, base_count, remainder);
188 6 displs[i] = offset;
189 6 offset += sendcounts[i];
190 }
191 }
192
193
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Bcast(sendcounts.data(), world_size, MPI_INT, 0, MPI_COMM_WORLD);
194
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Bcast(displs.data(), world_size, MPI_INT, 0, MPI_COMM_WORLD);
195
196 6 std::vector<double> all_x;
197 6 std::vector<double> all_y;
198
199
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (world_rank == 0) {
200
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 all_x.resize(total_points);
201
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 all_y.resize(total_points);
202
2/2
✓ Branch 0 taken 75 times.
✓ Branch 1 taken 3 times.
 78 for (int i = 0; i < total_points; ++i) {
203 75 all_x[i] = GetInput()[static_cast<std::size_t>(i)].x;
204 75 all_y[i] = GetInput()[static_cast<std::size_t>(i)].y;
205 }
206 }
207
208
1/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 6 std::vector<double> local_x(static_cast<std::size_t>(local_count));
209
1/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 6 std::vector<double> local_y(static_cast<std::size_t>(local_count));
210
211
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (local_count > 0) {
212
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Scatterv(all_x.data(), sendcounts.data(), displs.data(), MPI_DOUBLE, local_x.data(), local_count, MPI_DOUBLE, 0,
213 MPI_COMM_WORLD);
214
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Scatterv(all_y.data(), sendcounts.data(), displs.data(), MPI_DOUBLE, local_y.data(), local_count, MPI_DOUBLE, 0,
215 MPI_COMM_WORLD);
216 }
217
218 6 std::vector<Point> local_points;
219
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 local_points.reserve(static_cast<std::size_t>(local_count));
220
2/2
✓ Branch 0 taken 75 times.
✓ Branch 1 taken 6 times.
 81 for (int i = 0; i < local_count; ++i) {
221
1/2
✓ Branch 1 taken 75 times.
✗ Branch 2 not taken.
 75 local_points.emplace_back(local_x[i], local_y[i]);
222 }
223
224 6 return local_points;
225 }
226
227 6 std::vector<Point> IskhakovDGrahamConvexHullMPI::MergeHullsBinaryTree(int world_rank,
228 const std::vector<Point> &local_hull,
229 int active_procs) {
230 6 std::vector<Point> current_hull = local_hull;
231
232
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 for (int step = 1; step < active_procs; step <<= 1) {
233 6 const int partner = world_rank ^ step;
234
235
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (world_rank < active_procs && partner < active_procs) {
236 6 int my_size = static_cast<int>(current_hull.size());
237 6 int partner_size = 0;
238
239
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Sendrecv(&my_size, 1, MPI_INT, partner, kTagSize, &partner_size, 1, MPI_INT, partner, kTagSize,
240 MPI_COMM_WORLD, MPI_STATUS_IGNORE);
241
242
1/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 6 std::vector<double> my_x(my_size);
243
1/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 6 std::vector<double> my_y(my_size);
244
245
2/2
✓ Branch 0 taken 45 times.
✓ Branch 1 taken 6 times.
 51 for (int i = 0; i < my_size; ++i) {
246 45 my_x[i] = current_hull[static_cast<std::size_t>(i)].x;
247 45 my_y[i] = current_hull[static_cast<std::size_t>(i)].y;
248 }
249
250
1/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 6 std::vector<double> remote_x(partner_size);
251
1/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 6 std::vector<double> remote_y(partner_size);
252
253
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Sendrecv(my_x.data(), my_size, MPI_DOUBLE, partner, kTagX, remote_x.data(), partner_size, MPI_DOUBLE, partner,
254 kTagX, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
255
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Sendrecv(my_y.data(), my_size, MPI_DOUBLE, partner, kTagY, remote_y.data(), partner_size, MPI_DOUBLE, partner,
256 kTagY, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
257
258 6 std::vector<Point> remote_hull;
259
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 remote_hull.reserve(static_cast<std::size_t>(partner_size));
260
2/2
✓ Branch 0 taken 45 times.
✓ Branch 1 taken 6 times.
 51 for (int i = 0; i < partner_size; ++i) {
261
1/2
✓ Branch 1 taken 45 times.
✗ Branch 2 not taken.
 45 remote_hull.emplace_back(remote_x[i], remote_y[i]);
262 }
263
264
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 current_hull = MergeHulls(current_hull, remote_hull);
265 }
266
267
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Barrier(MPI_COMM_WORLD);
268 }
269
270
2/4
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 6 times.
✗ Branch 4 not taken.
 12 return (world_rank < active_procs) ? current_hull : std::vector<Point>{};
271 }
272
273 32 std::vector<Point> IskhakovDGrahamConvexHullMPI::BroadcastFinalResult(int world_rank,
274 const std::vector<Point> &root_hull) {
275 32 int hull_size = 0;
276
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 16 times.
 32 if (world_rank == 0) {
277 16 hull_size = static_cast<int>(root_hull.size());
278 }
279
280 32 MPI_Bcast(&hull_size, 1, MPI_INT, 0, MPI_COMM_WORLD);
281
282 32 std::vector<Point> result;
283
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 result.reserve(static_cast<std::size_t>(hull_size));
284
285
1/4
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 32 std::vector<double> x(static_cast<std::size_t>(hull_size));
286
1/4
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 32 std::vector<double> y(static_cast<std::size_t>(hull_size));
287
288
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 16 times.
 32 if (world_rank == 0) {
289
2/2
✓ Branch 0 taken 76 times.
✓ Branch 1 taken 16 times.
 92 for (int i = 0; i < hull_size; ++i) {
290 76 x[i] = root_hull[static_cast<std::size_t>(i)].x;
291 76 y[i] = root_hull[static_cast<std::size_t>(i)].y;
292 }
293 }
294
295
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 MPI_Bcast(x.data(), hull_size, MPI_DOUBLE, 0, MPI_COMM_WORLD);
296
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 MPI_Bcast(y.data(), hull_size, MPI_DOUBLE, 0, MPI_COMM_WORLD);
297
298
2/2
✓ Branch 0 taken 152 times.
✓ Branch 1 taken 32 times.
 184 for (int i = 0; i < hull_size; ++i) {
299
1/2
✓ Branch 1 taken 152 times.
✗ Branch 2 not taken.
 152 result.emplace_back(x[i], y[i]);
300 }
301
302 32 return result;
303 }
304
305 32 bool IskhakovDGrahamConvexHullMPI::RunImpl() {
306 32 int world_size = 0;
307 32 int world_rank = 0;
308
309 32 MPI_Comm_size(MPI_COMM_WORLD, &world_size);
310 32 MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);
311
312 32 int points_count = 0;
313
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 16 times.
 32 if (world_rank == 0) {
314 16 points_count = static_cast<int>(GetInput().size());
315 }
316
317 32 MPI_Bcast(&points_count, 1, MPI_INT, 0, MPI_COMM_WORLD);
318
319 32 const int active_procs = CalculateOptimalActiveProcs(points_count, world_size);
320
321
2/2
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 6 times.
 32 if (active_procs == 1) {
322 26 std::vector<Point> result;
323
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 13 times.
 26 if (world_rank == 0) {
324
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 26 result = GrahamScan(GetInput());
325 }
326
3/6
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 13 times.
✓ Branch 4 taken 13 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 52 GetOutput() = BroadcastFinalResult(world_rank, result);
327 return true;
328 }
329
330 6 int actual_active_procs = 0;
331 6 const std::vector<Point> local_points = PrepareAndDistributeData(world_rank, world_size, actual_active_procs);
332
333
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 std::vector<Point> local_hull;
334
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (!local_points.empty()) {
335
1/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 12 local_hull = GrahamScan(local_points);
336 }
337
338
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 const std::vector<Point> merged = MergeHullsBinaryTree(world_rank, local_hull, actual_active_procs);
339
340
3/4
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
✓ Branch 3 taken 3 times.
✗ Branch 4 not taken.
 6 const std::vector<Point> root_hull = (world_rank == 0) ? merged : std::vector<Point>{};
341
342
3/6
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 3 times.
✓ Branch 4 taken 3 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 12 GetOutput() = BroadcastFinalResult(world_rank, root_hull);
343 return true;
344 }
345
346 32 bool IskhakovDGrahamConvexHullMPI::PostProcessingImpl() {
347 32 return true;
348 }
349
350 } // namespace iskhakov_d_graham_convex_hull
351