GCC Code Coverage Report

Directory: ./
File: tasks/makovskiy_i_graham_hull/all/src/ops_all.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 155 156 99.4%
Functions: 18 18 100.0%
Branches: 138 186 74.2%
Line Branch Exec Source
1 #include "makovskiy_i_graham_hull/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4
5 #include <algorithm>
6 #include <cmath>
7 #include <cstddef>
8 #include <cstdint>
9 #include <future>
10 #include <utility>
11 #include <vector>
12
13 #include "makovskiy_i_graham_hull/common/include/common.hpp"
14 #include "util/include/util.hpp"
15
16 namespace makovskiy_i_graham_hull {
17
18 namespace {
19
20 double CrossProduct(const Point &o, const Point &a, const Point &b) {
21
2/2
✓ Branch 0 taken 1336 times.
✓ Branch 1 taken 1986 times.
 3322 return ((a.x - o.x) * (b.y - o.y)) - ((a.y - o.y) * (b.x - o.x));
22 }
23
24 double DistSq(const Point &a, const Point &b) {
25 4007 return ((a.x - b.x) * (a.x - b.x)) + ((a.y - b.y) * (a.y - b.y));
26 }
27
28 bool IsBetterMin(const Point &candidate, const Point &current_min) {
29
4/4
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 3320 times.
✓ Branch 3 taken 2 times.
 3337 if (candidate.y < current_min.y - 1e-9) {
30 return true;
31 }
32
7/8
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 4 times.
✓ Branch 4 taken 65 times.
✓ Branch 5 taken 3255 times.
✓ Branch 6 taken 2 times.
✓ Branch 7 taken 63 times.
 3334 return (std::abs(candidate.y - current_min.y) <= 1e-9) && (candidate.x < current_min.x);
33 }
34
35 15 size_t FindMinPointIndexSTL(const std::vector<Point> &points) {
36 15 const size_t n = points.size();
37 15 const int num_threads = std::max(1, ppc::util::GetNumThreads());
38
39 15 std::vector<std::future<size_t>> futures;
40 15 const size_t chunk = (n + static_cast<size_t>(num_threads) - 1) / static_cast<size_t>(num_threads);
41
42 30 auto worker = [&points](size_t start, size_t end) {
43 size_t local_min = start;
44
2/2
✓ Branch 0 taken 3322 times.
✓ Branch 1 taken 30 times.
 3352 for (size_t j = start + 1; j < end; ++j) {
45
2/2
✓ Branch 0 taken 3320 times.
✓ Branch 1 taken 2 times.
 3322 if (IsBetterMin(points[j], points[local_min])) {
46 local_min = j;
47 }
48 }
49 30 return local_min;
50 15 };
51
52
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 15 times.
 45 for (int i = 0; i < num_threads; ++i) {
53 30 const size_t start = static_cast<size_t>(i) * chunk;
54
1/2
✓ Branch 0 taken 30 times.
✗ Branch 1 not taken.
 30 const size_t end = std::min(start + chunk, n);
55
1/2
✓ Branch 0 taken 30 times.
✗ Branch 1 not taken.
 30 if (start >= n) {
56 break;
57 }
58
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 60 futures.push_back(std::async(std::launch::async, worker, start, end));
59 }
60
61
1/2
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
 15 size_t min_idx = futures[0].get();
62
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 15 times.
 30 for (size_t i = 1; i < futures.size(); ++i) {
63
1/2
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
 15 const size_t local_min = futures[i].get();
64 if (IsBetterMin(points[local_min], points[min_idx])) {
65 min_idx = local_min;
66 }
67 }
68
69 15 return min_idx;
70 15 }
71
72 template <typename RandomIt, typename Compare>
73
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 2 times.
 4 void StlParallelSortSub(RandomIt first, RandomIt last, Compare comp) {
74
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 2 times.
 4 if (last - first < 32) {
75 2 std::sort(first, last, comp);
76 2 return;
77 }
78 2 const auto pivot = *(first + ((last - first) / 2));
79
4/4
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 456 times.
✓ Branch 2 taken 2350 times.
✓ Branch 3 taken 454 times.
 3270 RandomIt middle1 = std::partition(first, last, [pivot, comp](const auto &a) { return comp(a, pivot); });
80
3/4
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 2800 times.
✓ Branch 3 taken 2 times.
 2806 RandomIt middle2 = std::partition(middle1, last, [pivot, comp](const auto &a) { return !comp(pivot, a); });
81
82 4 auto future1 = std::async(std::launch::async, [first, middle1, comp]() { std::sort(first, middle1, comp); });
83 2 std::sort(middle2, last, comp);
84
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 future1.wait();
85 }
86
87 template <typename RandomIt, typename Compare>
88
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 2 times.
 15 void StlParallelSort(RandomIt first, RandomIt last, Compare comp) {
89
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 2 times.
 15 if (last - first < 32) {
90 13 std::sort(first, last, comp);
91 13 return;
92 }
93 2 const auto pivot = *(first + ((last - first) / 2));
94
3/4
✗ Branch 0 not taken.
✓ Branch 1 taken 30 times.
✓ Branch 2 taken 3240 times.
✓ Branch 3 taken 28 times.
 3300 RandomIt middle1 = std::partition(first, last, [pivot, comp](const auto &a) { return comp(a, pivot); });
95
3/4
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 3264 times.
✓ Branch 3 taken 2 times.
 3270 RandomIt middle2 = std::partition(middle1, last, [pivot, comp](const auto &a) { return !comp(pivot, a); });
96
97
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 4 auto future1 = std::async(std::launch::async, [first, middle1, comp]() { StlParallelSortSub(first, middle1, comp); });
98
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 StlParallelSortSub(middle2, last, comp);
99
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 future1.wait();
100 }
101
102
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 15 times.
 15 std::vector<Point> FilterPointsSTL(const std::vector<Point> &points, const Point &p0) {
103 const size_t n = points.size();
104
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 15 times.
 15 if (n <= 2) {
105 ✗ return points;
106 }
107
108 15 std::vector<uint8_t> keep(n, 1);
109
1/2
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
 15 const int num_threads = std::max(1, ppc::util::GetNumThreads());
110
111 15 const size_t num_elements = n - 2;
112 15 const size_t chunk = (num_elements + static_cast<size_t>(num_threads) - 1) / static_cast<size_t>(num_threads);
113 15 std::vector<std::future<void>> futures;
114
115 23 auto worker = [&points, &keep, p0](size_t start, size_t end) {
116
2/2
✓ Branch 0 taken 3322 times.
✓ Branch 1 taken 23 times.
 3345 for (size_t j = start; j < end; ++j) {
117
2/2
✓ Branch 0 taken 1336 times.
✓ Branch 1 taken 1986 times.
 3322 if (std::abs(CrossProduct(p0, points[j], points[j + 1])) < 1e-9) {
118 1336 keep[j] = 0;
119 }
120 }
121 38 };
122
123
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 8 times.
 38 for (int i = 0; i < num_threads; ++i) {
124 30 const size_t start = 1 + (static_cast<size_t>(i) * chunk);
125
2/2
✓ Branch 0 taken 23 times.
✓ Branch 1 taken 7 times.
 30 const size_t end = std::min(start + chunk, n - 1);
126
127
2/2
✓ Branch 0 taken 23 times.
✓ Branch 1 taken 7 times.
 30 if (start >= n - 1) {
128 break;
129 }
130
131
1/2
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
 46 futures.push_back(std::async(std::launch::async, worker, start, end));
132 }
133
134
2/2
✓ Branch 0 taken 23 times.
✓ Branch 1 taken 15 times.
 38 for (auto &f : futures) {
135
1/2
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
 23 f.wait();
136 }
137
138 15 std::vector<Point> filtered;
139
1/2
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
 15 filtered.reserve(n);
140
2/2
✓ Branch 0 taken 3352 times.
✓ Branch 1 taken 15 times.
 3367 for (size_t i = 0; i < n; ++i) {
141
2/2
✓ Branch 0 taken 2016 times.
✓ Branch 1 taken 1336 times.
 3352 if (keep[i] != 0) {
142 filtered.push_back(points[i]);
143 }
144 }
145 return filtered;
146 15 }
147
148 10 std::vector<Point> BuildHull(const std::vector<Point> &filtered) {
149
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 std::vector<Point> hull;
150 hull.push_back(filtered[0]);
151 hull.push_back(filtered[1]);
152 hull.push_back(filtered[2]);
153
154
2/2
✓ Branch 0 taken 1976 times.
✓ Branch 1 taken 10 times.
 1986 for (size_t i = 3; i < filtered.size(); ++i) {
155
3/4
✓ Branch 0 taken 3946 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1970 times.
✓ Branch 3 taken 1976 times.
 3946 while (hull.size() > 1 && CrossProduct(hull[hull.size() - 2], hull.back(), filtered[i]) <= 1e-9) {
156 hull.pop_back();
157 }
158 hull.push_back(filtered[i]);
159 }
160 10 return hull;
161 }
162
163
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 15 times.
 27 std::vector<Point> ComputeHullSTL(const std::vector<Point> &input_points) {
164
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 15 times.
 27 if (input_points.size() < 3) {
165 12 return input_points;
166 }
167
168 15 std::vector<Point> points = input_points;
169
1/2
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
 15 const size_t min_idx = FindMinPointIndexSTL(points);
170
171 std::swap(points[0], points[min_idx]);
172 15 const Point p0 = points[0];
173
174
2/2
✓ Branch 0 taken 4007 times.
✓ Branch 1 taken 49923 times.
 53930 auto comp = [p0](const Point &a, const Point &b) {
175 const double cp = CrossProduct(p0, a, b);
176
2/2
✓ Branch 0 taken 4007 times.
✓ Branch 1 taken 49923 times.
 53930 if (std::abs(cp) < 1e-9) {
177 4007 return DistSq(p0, a) < DistSq(p0, b);
178 }
179 49923 return cp > 0;
180
1/2
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
 15 };
181
182
1/2
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
 15 StlParallelSort(points.begin() + 1, points.end(), comp);
183
184
1/2
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
 15 std::vector<Point> filtered = FilterPointsSTL(points, p0);
185
186
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 10 times.
 15 if (filtered.size() < 3) {
187 return filtered;
188 }
189
190
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 return BuildHull(filtered);
191 }
192
193 9 std::vector<Point> ReceivePointsWorker() {
194 9 std::vector<Point> local_points;
195 9 int count = 0;
196
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 MPI_Recv(&count, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
197
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 1 times.
 9 if (count > 0) {
198
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 local_points.resize(static_cast<size_t>(count));
199
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 MPI_Recv(local_points.data(), count * 2, MPI_DOUBLE, 0, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
200 }
201 9 return local_points;
202 }
203
204
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 5 times.
 9 std::vector<Point> SendPointsRoot(int size, const std::vector<Point> &input_points) {
205 9 const int num_points = static_cast<int>(input_points.size());
206
207 9 const int chunk = num_points / size;
208 9 const int rem = num_points % size;
209
210
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 5 times.
 9 int offset = chunk + (rem > 0 ? 1 : 0);
211
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 9 times.
 18 for (int i = 1; i < size; ++i) {
212
1/2
✓ Branch 0 taken 9 times.
✗ Branch 1 not taken.
 9 const int count = chunk + (i < rem ? 1 : 0);
213 9 MPI_Send(&count, 1, MPI_INT, i, 0, MPI_COMM_WORLD);
214
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 1 times.
 9 if (count > 0) {
215 8 MPI_Send(input_points.data() + offset, count * 2, MPI_DOUBLE, i, 1, MPI_COMM_WORLD);
216 }
217 9 offset += count;
218 }
219
220 const int local_count = chunk + (rem > 0 ? 1 : 0);
221
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 std::vector<Point> local_points;
222 9 local_points.assign(input_points.begin(), input_points.begin() + local_count);
223 9 return local_points;
224 }
225
226 std::vector<Point> ScatterPoints(int rank, int size, const std::vector<Point> &input_points) {
227 18 if (rank == 0) {
228
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 return SendPointsRoot(size, input_points);
229 }
230
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 return ReceivePointsWorker();
231 }
232
233 18 std::vector<Point> GatherHulls(int rank, int size, const std::vector<Point> &local_hull) {
234 18 int local_hull_size = static_cast<int>(local_hull.size());
235 18 std::vector<int> hull_sizes(static_cast<size_t>(size), 0);
236
237
3/4
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 9 times.
✓ Branch 3 taken 18 times.
✗ Branch 4 not taken.
 27 MPI_Gather(&local_hull_size, 1, MPI_INT, rank == 0 ? hull_sizes.data() : nullptr, 1, MPI_INT, 0, MPI_COMM_WORLD);
238
239 18 std::vector<int> displs;
240 18 std::vector<int> recvcounts;
241 int total_hull_points = 0;
242
243
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 9 times.
 18 if (rank == 0) {
244
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 displs.resize(static_cast<size_t>(size), 0);
245
1/4
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 9 recvcounts.resize(static_cast<size_t>(size), 0);
246
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 9 times.
 27 for (int i = 0; i < size; ++i) {
247 18 const auto idx = static_cast<size_t>(i);
248 18 recvcounts[idx] = hull_sizes[idx] * 2;
249 18 displs[idx] = total_hull_points * 2;
250 18 total_hull_points += hull_sizes[idx];
251 }
252 }
253
254 18 std::vector<Point> all_hulls;
255
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 9 times.
 18 if (rank == 0) {
256
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 all_hulls.resize(static_cast<size_t>(total_hull_points));
257 }
258
259
3/4
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 9 times.
✓ Branch 3 taken 18 times.
✗ Branch 4 not taken.
 27 MPI_Gatherv(local_hull.data(), local_hull_size * 2, MPI_DOUBLE, rank == 0 ? all_hulls.data() : nullptr,
260 recvcounts.data(), displs.data(), MPI_DOUBLE, 0, MPI_COMM_WORLD);
261
262 18 return all_hulls;
263 }
264
265 } // namespace
266
267
1/2
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
 18 ConvexHullGrahamALL::ConvexHullGrahamALL(const InType &in) {
268 SetTypeOfTask(GetStaticTypeOfTask());
269
1/2
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
 18 GetInput() = in;
270 18 }
271
272 18 bool ConvexHullGrahamALL::ValidationImpl() {
273 18 return true;
274 }
275
276 18 bool ConvexHullGrahamALL::PreProcessingImpl() {
277 18 return true;
278 }
279
280 18 bool ConvexHullGrahamALL::RunImpl() {
281 18 int rank = 0;
282 18 int size = 1;
283 18 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
284 18 MPI_Comm_size(MPI_COMM_WORLD, &size);
285
286 18 std::vector<Point> input_points;
287
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 9 times.
 18 if (rank == 0) {
288
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 input_points = GetInput();
289 }
290
291
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 9 times.
 18 std::vector<Point> local_points = ScatterPoints(rank, size, input_points);
292
1/2
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
 18 std::vector<Point> local_hull = ComputeHullSTL(local_points);
293
1/2
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
 18 std::vector<Point> all_hulls = GatherHulls(rank, size, local_hull);
294
295
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 9 times.
 18 if (rank == 0) {
296
1/4
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 18 GetOutput() = ComputeHullSTL(all_hulls);
297 }
298
299 18 return true;
300 }
301
302 18 bool ConvexHullGrahamALL::PostProcessingImpl() {
303 18 return true;
304 }
305
306 } // namespace makovskiy_i_graham_hull
307