GCC Code Coverage Report

Directory: ./
File: tasks/dergachev_a_graham_scan/all/src/ops_all.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 180 187 96.3%
Functions: 22 22 100.0%
Branches: 143 246 58.1%
Line Branch Exec Source
1 #include "dergachev_a_graham_scan/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4 #include <omp.h>
5
6 #include <algorithm>
7 #include <cmath>
8 #include <cstddef>
9 #include <utility>
10 #include <vector>
11
12 #include "dergachev_a_graham_scan/common/include/common.hpp"
13 #include "util/include/util.hpp"
14
15 namespace dergachev_a_graham_scan {
16
17 namespace {
18
19 using Pt = std::pair<double, double>;
20
21 constexpr double kPaddingMarker = 1e18;
22
23 const double kPi = std::acos(-1.0);
24
25 struct Slice {
26 const Pt *begin;
27 const Pt *end;
28 };
29
30 struct WorkBuffers {
31 std::vector<Pt> padded_input;
32 std::vector<Pt> local_data;
33 std::vector<Pt> gathered_pivots;
34 std::vector<int> counts;
35 std::vector<int> displs;
36 std::vector<int> recv_counts;
37 std::vector<int> recv_displs;
38 std::vector<Pt> gathered;
39 std::vector<Pt> sorted;
40 std::vector<Pt> merge_temp;
41 };
42
43 26 MPI_Datatype GetMpiPointType() {
44 static MPI_Datatype mpi_point = MPI_DATATYPE_NULL;
45 static bool initialized = false;
46
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 24 times.
 26 if (!initialized) {
47 2 MPI_Type_contiguous(2, MPI_DOUBLE, &mpi_point);
48 2 MPI_Type_commit(&mpi_point);
49 2 initialized = true;
50 }
51 26 return mpi_point;
52 }
53
54 bool IsLowerLeft(const Pt &a, const Pt &b) {
55
11/18
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✓ Branch 6 taken 2 times.
✓ Branch 7 taken 8 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 8 times.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✓ Branch 12 taken 10 times.
✓ Branch 13 taken 3 times.
✓ Branch 14 taken 9 times.
✓ Branch 15 taken 1 times.
✓ Branch 16 taken 1 times.
✗ Branch 17 not taken.
 34 return a.second < b.second || (a.second == b.second && a.first < b.first);
56 }
57
58 double CrossProduct(const Pt &o, const Pt &a, const Pt &b) {
59 10820 return ((a.first - o.first) * (b.second - o.second)) - ((a.second - o.second) * (b.first - o.first));
60 }
61
62 double DistSquared(const Pt &a, const Pt &b) {
63 ✗ double dx = a.first - b.first;
64 ✗ double dy = a.second - b.second;
65 ✗ return (dx * dx) + (dy * dy);
66 }
67
68 9622 bool AngleLessSeq(const Pt &a, const Pt &b, const Pt &pivot) {
69 const double cross = CrossProduct(pivot, a, b);
70
3/6
✓ Branch 0 taken 2224 times.
✓ Branch 1 taken 7398 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 2224 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 9622 return cross > 0.0 || (cross == 0.0 && DistSquared(pivot, a) < DistSquared(pivot, b));
71 }
72
73
1/2
✓ Branch 0 taken 22 times.
✗ Branch 1 not taken.
 22 int FindLocalPivotIndex(const std::vector<Pt> &pts) {
74
1/2
✓ Branch 0 taken 22 times.
✗ Branch 1 not taken.
 22 if (pts.empty()) {
75 return 0;
76 }
77
78 22 const int num_threads = ppc::util::GetNumThreads();
79 22 const int n = static_cast<int>(pts.size());
80
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 13 times.
 22 if (n < num_threads * 2) {
81 int best = 0;
82
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 9 times.
 19 for (int i = 1; i < n; i++) {
83
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 8 times.
 10 if (IsLowerLeft(pts[i], pts[best])) {
84 best = i;
85 }
86 }
87 return best;
88 }
89
90 13 std::vector<int> local_best(num_threads);
91 13 #pragma omp parallel num_threads(num_threads) default(none) shared(pts, n, local_best, num_threads)
92 {
93 const int tid = omp_get_thread_num();
94 const int lo = (tid * n) / num_threads;
95 const int hi = ((tid + 1) * n) / num_threads;
96 int best = lo;
97 for (int i = lo + 1; i < hi; i++) {
98 if (IsLowerLeft(pts[i], pts[best])) {
99 best = i;
100 }
101 }
102 local_best[tid] = best;
103 }
104
105 13 int best = local_best[0];
106
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 13 times.
 26 for (int thread_idx = 1; thread_idx < num_threads; thread_idx++) {
107
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 3 times.
 13 if (IsLowerLeft(pts[local_best[thread_idx]], pts[best])) {
108 best = local_best[thread_idx];
109 }
110 }
111 return best;
112 }
113
114 22 void ParallelSortRange(std::vector<Pt>::iterator begin, std::vector<Pt>::iterator end, const Pt &pivot) {
115 22 const int n = static_cast<int>(end - begin);
116 22 const int num_threads = ppc::util::GetNumThreads();
117
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 18 times.
 22 if (n <= 1 || num_threads <= 1) {
118 ✗ std::sort(begin, end, [&](const Pt &a, const Pt &b) { return AngleLessSeq(a, b, pivot); });
119 4 return;
120 }
121
122
14/34
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 961 times.
✓ Branch 5 taken 1149 times.
✓ Branch 6 taken 1988 times.
✓ Branch 7 taken 120 times.
✓ Branch 8 taken 3379 times.
✓ Branch 9 taken 120 times.
✓ Branch 10 taken 92 times.
✗ Branch 11 not taken.
✓ Branch 12 taken 64 times.
✓ Branch 13 taken 28 times.
✗ Branch 14 not taken.
✓ Branch 15 taken 28 times.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
✓ Branch 28 taken 297 times.
✓ Branch 29 taken 303 times.
✓ Branch 30 taken 13 times.
✓ Branch 31 taken 177 times.
✗ Branch 32 not taken.
✗ Branch 33 not taken.
 8599 auto cmp = [&](const Pt &a, const Pt &b) { return AngleLessSeq(a, b, pivot); };
123 18 const int chunk = n / num_threads;
124 18 #pragma omp parallel num_threads(num_threads) default(none) shared(begin, n, chunk, cmp, num_threads)
125 {
126 const int tid = omp_get_thread_num();
127 const int lo = tid * chunk;
128 const int hi = (tid == num_threads - 1) ? n : (tid + 1) * chunk;
129 std::sort(begin + lo, begin + hi, cmp);
130 }
131
132 int boundary = chunk;
133
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 18 times.
 36 for (int tid = 1; tid < num_threads; tid++) {
134
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 18 times.
 18 const int next = (tid == num_threads - 1) ? n : (tid + 1) * chunk;
135 18 std::inplace_merge(begin, begin + boundary, begin + next, cmp);
136 boundary = next;
137 }
138 }
139
140
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 11 times.
 11 void BuildHullFromSorted(const std::vector<Pt> &sorted, const Pt &pivot, std::vector<Pt> &hull) {
141 hull.clear();
142 hull.push_back(pivot);
143
2/2
✓ Branch 0 taken 1200 times.
✓ Branch 1 taken 11 times.
 1211 for (const auto &p : sorted) {
144
4/4
✓ Branch 0 taken 1198 times.
✓ Branch 1 taken 11 times.
✓ Branch 2 taken 9 times.
✓ Branch 3 taken 1189 times.
 1209 while (hull.size() >= 2 && CrossProduct(hull[hull.size() - 2], hull.back(), p) <= 0.0) {
145 hull.pop_back();
146 }
147 hull.push_back(p);
148 }
149 11 }
150
151
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 2 times.
 11 void MergeTwoSlices(Slice left, Slice right, const Pt &pivot, std::vector<Pt> &out) {
152 out.clear();
153 11 out.reserve(static_cast<size_t>((left.end - left.begin) + (right.end - right.begin)));
154
155 const Pt *i = left.begin;
156 const Pt *j = right.begin;
157
4/4
✓ Branch 0 taken 905 times.
✓ Branch 1 taken 9 times.
✓ Branch 2 taken 903 times.
✓ Branch 3 taken 2 times.
 914 while (i < left.end && j < right.end) {
158
2/2
✓ Branch 0 taken 604 times.
✓ Branch 1 taken 299 times.
 903 if (AngleLessSeq(*i, *j, pivot)) {
159
1/2
✓ Branch 0 taken 604 times.
✗ Branch 1 not taken.
 604 out.push_back(*i++);
160 } else {
161
1/2
✓ Branch 0 taken 299 times.
✗ Branch 1 not taken.
 299 out.push_back(*j++);
162 }
163 }
164
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 11 times.
 15 while (i < left.end) {
165
1/2
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
 4 out.push_back(*i++);
166 }
167
2/2
✓ Branch 0 taken 293 times.
✓ Branch 1 taken 11 times.
 304 while (j < right.end) {
168
1/2
✓ Branch 0 taken 293 times.
✗ Branch 1 not taken.
 293 out.push_back(*j++);
169 }
170 11 }
171
172 Slice MakeSlice(const std::vector<Pt> &data, int displ, int count) {
173
1/2
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
 11 return {.begin = data.data() + displ, .end = data.data() + displ + count};
174 }
175
176 11 std::vector<Pt> MergeAllBlocks(const std::vector<Pt> &gathered, const std::vector<int> &displs,
177 const std::vector<int> &counts, int world_size, const Pt &pivot,
178 std::vector<Pt> &merge_temp) {
179 11 const int first_displ = displs[0];
180 11 const int first_count = counts[0];
181 11 std::vector<Pt> merged(gathered.begin() + first_displ, gathered.begin() + first_displ + first_count);
182
183
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 11 times.
 22 for (int block_idx = 1; block_idx < world_size; block_idx++) {
184
1/2
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
 11 const int displ = displs[static_cast<size_t>(block_idx)];
185
1/2
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
 11 const int count = counts[static_cast<size_t>(block_idx)];
186
1/2
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
 11 MergeTwoSlices(MakeSlice(merged, 0, static_cast<int>(merged.size())), MakeSlice(gathered, displ, count), pivot,
187 merge_temp);
188 merged.swap(merge_temp);
189 }
190
191 11 return merged;
192 }
193
194 22 void RemovePaddingPoints(std::vector<Pt> &pts) {
195
2/4
✓ Branch 0 taken 1211 times.
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 1218 auto end_it = std::ranges::remove_if(pts, [](const Pt &p) { return p.first > kPaddingMarker / 10.0; });
196 pts.erase(end_it.begin(), end_it.end());
197 22 }
198
199 26 void BcastHullSize(std::vector<Pt> &hull, int rank) {
200
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 13 times.
 26 int hull_size = (rank == 0) ? static_cast<int>(hull.size()) : 0;
201 26 MPI_Bcast(&hull_size, 1, MPI_INT, 0, MPI_COMM_WORLD);
202 26 hull.resize(static_cast<size_t>(hull_size));
203 26 }
204
205 void ComputePaddedSizes(int world_size, int points_size, int &original_size, int &padded_size) {
206 13 original_size = points_size;
207 13 const int remainder = original_size % world_size;
208 8 padded_size = original_size + ((remainder == 0) ? 0 : (world_size - remainder));
209 13 }
210
211
1/2
✓ Branch 0 taken 11 times.
✗ Branch 1 not taken.
 11 bool AllPointsSame(const std::vector<Pt> &points) {
212
1/2
✓ Branch 0 taken 11 times.
✗ Branch 1 not taken.
 11 if (points.size() <= 1) {
213 return false;
214 }
215 11 return std::all_of(points.begin() + 1, points.end(),
216
3/28
✗ Branch 0 not taken.
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✓ Branch 21 taken 1 times.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
✓ Branch 25 taken 1 times.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
 11 [&](const Pt &p) { return p.first == points[0].first && p.second == points[0].second; });
217 }
218
219 26 bool HandleTrivialCases(int rank, int original_size, int all_same, std::vector<Pt> &points, std::vector<Pt> &hull) {
220
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 22 times.
 26 if (original_size <= 1) {
221
4/4
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 1 times.
✓ Branch 3 taken 1 times.
 4 if (rank == 0 && !points.empty()) {
222 hull.push_back(points[0]);
223 }
224 4 BcastHullSize(hull, rank);
225 4 return true;
226 }
227
228
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 22 times.
 22 if (all_same != 0) {
229 ✗ if (rank == 0) {
230 hull.push_back(points[0]);
231 }
232 ✗ BcastHullSize(hull, rank);
233 ✗ return true;
234 }
235
236 return false;
237 }
238
239 22 void PrepareScatterLayout(WorkBuffers &bufs, int world_size, int block_size) {
240 22 bufs.counts.assign(static_cast<size_t>(world_size), block_size);
241 22 bufs.displs.resize(static_cast<size_t>(world_size));
242
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 22 times.
 66 for (int i = 0, offset = 0; i < world_size; i++) {
243 44 bufs.displs[static_cast<size_t>(i)] = offset;
244 44 offset += block_size;
245 }
246 22 }
247
248 22 void ScatterLocalPoints(WorkBuffers &bufs, int rank, int block_size, int padded_size, int original_size,
249 MPI_Datatype mpi_point, const std::vector<Pt> &points) {
250
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 11 times.
 22 if (rank == 0) {
251 11 bufs.padded_input = points;
252
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 4 times.
 11 if (padded_size > original_size) {
253 7 bufs.padded_input.resize(static_cast<size_t>(padded_size), Pt{kPaddingMarker, kPaddingMarker});
254 }
255 }
256
257 22 bufs.local_data.resize(static_cast<size_t>(block_size));
258
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 11 times.
 33 MPI_Scatterv(rank == 0 ? bufs.padded_input.data() : nullptr, bufs.counts.data(), bufs.displs.data(), mpi_point,
259 bufs.local_data.data(), block_size, mpi_point, 0, MPI_COMM_WORLD);
260 22 RemovePaddingPoints(bufs.local_data);
261 22 }
262
263 22 Pt FindGlobalPivot(WorkBuffers &bufs, int rank, int world_size, MPI_Datatype mpi_point, const Pt &local_pivot) {
264
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 11 times.
 22 if (rank == 0) {
265 11 bufs.gathered_pivots.resize(static_cast<size_t>(world_size));
266 }
267 22 MPI_Gather(&local_pivot, 1, mpi_point, rank == 0 ? bufs.gathered_pivots.data() : nullptr, 1, mpi_point, 0,
268 MPI_COMM_WORLD);
269
270 22 Pt global_pivot{kPaddingMarker, kPaddingMarker};
271
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 11 times.
 22 if (rank == 0) {
272 global_pivot = bufs.gathered_pivots[0];
273
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 11 times.
 22 for (int i = 1; i < world_size; i++) {
274
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 10 times.
 11 if (IsLowerLeft(bufs.gathered_pivots[static_cast<size_t>(i)], global_pivot)) {
275 global_pivot = bufs.gathered_pivots[static_cast<size_t>(i)];
276 }
277 }
278 }
279 22 MPI_Bcast(&global_pivot, 1, mpi_point, 0, MPI_COMM_WORLD);
280 22 return global_pivot;
281 }
282
283 22 void RemoveGlobalPivot(WorkBuffers &bufs, int rank, int pivot_owner, const Pt &global_pivot) {
284
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 11 times.
 22 if (rank != pivot_owner) {
285 return;
286 }
287 auto it = std::ranges::find(bufs.local_data, global_pivot);
288
1/2
✓ Branch 0 taken 11 times.
✗ Branch 1 not taken.
 11 if (it != bufs.local_data.end()) {
289 bufs.local_data.erase(it);
290 }
291 }
292
293
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 11 times.
 22 void GatherSortedAndBuildHull(WorkBuffers &bufs, int rank, int world_size, MPI_Datatype mpi_point,
294 const Pt &global_pivot, std::vector<Pt> &hull) {
295 22 const int local_size = static_cast<int>(bufs.local_data.size());
296
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 11 times.
 33 MPI_Gather(&local_size, 1, MPI_INT, rank == 0 ? bufs.recv_counts.data() : nullptr, 1, MPI_INT, 0, MPI_COMM_WORLD);
297
298
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 11 times.
 22 if (rank == 0) {
299 int offset = 0;
300
2/2
✓ Branch 0 taken 22 times.
✓ Branch 1 taken 11 times.
 33 for (int i = 0; i < world_size; i++) {
301 22 bufs.recv_displs[static_cast<size_t>(i)] = offset;
302 22 offset += bufs.recv_counts[static_cast<size_t>(i)];
303 }
304 11 bufs.gathered.resize(static_cast<size_t>(offset));
305 }
306
307 22 MPI_Gatherv(bufs.local_data.data(), local_size, mpi_point, rank == 0 ? bufs.gathered.data() : nullptr,
308 rank == 0 ? bufs.recv_counts.data() : nullptr, rank == 0 ? bufs.recv_displs.data() : nullptr, mpi_point,
309 0, MPI_COMM_WORLD);
310
311
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 11 times.
 22 if (rank != 0) {
312 11 return;
313 }
314
315 bufs.sorted =
316 11 MergeAllBlocks(bufs.gathered, bufs.recv_displs, bufs.recv_counts, world_size, global_pivot, bufs.merge_temp);
317 11 BuildHullFromSorted(bufs.sorted, global_pivot, hull);
318 }
319
320 22 void RunDistributedHull(WorkBuffers &bufs, int rank, int world_size, int block_size, int padded_size, int original_size,
321 MPI_Datatype mpi_point, const std::vector<Pt> &points, std::vector<Pt> &hull) {
322 22 PrepareScatterLayout(bufs, world_size, block_size);
323 22 ScatterLocalPoints(bufs, rank, block_size, padded_size, original_size, mpi_point, points);
324
325 22 const int local_pivot_idx = FindLocalPivotIndex(bufs.local_data);
326
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 22 times.
 22 const Pt local_pivot = bufs.local_data.empty() ? Pt{kPaddingMarker, kPaddingMarker}
327 22 : bufs.local_data[static_cast<size_t>(local_pivot_idx)];
328
329 22 const Pt global_pivot = FindGlobalPivot(bufs, rank, world_size, mpi_point, local_pivot);
330
331 22 int owner_rank = (local_pivot == global_pivot) ? rank : -1;
332 22 int pivot_owner = -1;
333 22 MPI_Allreduce(&owner_rank, &pivot_owner, 1, MPI_INT, MPI_MAX, MPI_COMM_WORLD);
334 22 RemoveGlobalPivot(bufs, rank, pivot_owner, global_pivot);
335
336 22 ParallelSortRange(bufs.local_data.begin(), bufs.local_data.end(), global_pivot);
337 22 GatherSortedAndBuildHull(bufs, rank, world_size, mpi_point, global_pivot, hull);
338 22 BcastHullSize(hull, rank);
339 22 }
340
341 } // namespace
342
343 26 DergachevAGrahamScanALL::DergachevAGrahamScanALL(const InType &in) {
344 SetTypeOfTask(GetStaticTypeOfTask());
345 26 GetInput() = in;
346 GetOutput() = 0;
347 26 }
348
349 26 bool DergachevAGrahamScanALL::ValidationImpl() {
350 26 return GetInput() >= 0;
351 }
352
353
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 26 times.
 26 bool DergachevAGrahamScanALL::PreProcessingImpl() {
354 hull_.clear();
355 26 int n_input = GetInput();
356
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 24 times.
 26 if (n_input <= 0) {
357 points_.clear();
358 2 return true;
359 }
360
361 24 int rank = 0;
362 24 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
363
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
 24 if (rank != 0) {
364 points_.clear();
365 12 return true;
366 }
367
368 12 points_.resize(n_input);
369 12 double step = (2.0 * kPi) / n_input;
370 auto *pts_data = points_.data();
371 12 #pragma omp parallel for default(none) shared(pts_data, step, n_input) num_threads(ppc::util::GetNumThreads())
372 for (int i = 0; i < n_input; i++) {
373 pts_data[i] = {std::cos(step * i), std::sin(step * i)};
374 }
375
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 3 times.
 12 if (n_input > 3) {
376 9 points_.emplace_back(0.0, 0.0);
377 }
378 return true;
379 }
380
381
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 26 times.
 26 bool DergachevAGrahamScanALL::RunImpl() {
382 hull_.clear();
383
384 26 int rank = 0;
385 26 int world_size = 1;
386 26 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
387 26 MPI_Comm_size(MPI_COMM_WORLD, &world_size);
388
389 26 MPI_Datatype mpi_point = GetMpiPointType();
390
391 26 int original_size = 0;
392 26 int padded_size = 0;
393
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 13 times.
 26 if (rank == 0) {
394
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 5 times.
 13 ComputePaddedSizes(world_size, static_cast<int>(points_.size()), original_size, padded_size);
395 }
396 26 MPI_Bcast(&original_size, 1, MPI_INT, 0, MPI_COMM_WORLD);
397 26 MPI_Bcast(&padded_size, 1, MPI_INT, 0, MPI_COMM_WORLD);
398
399 26 int all_same = 0;
400
4/4
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 13 times.
✓ Branch 2 taken 11 times.
✓ Branch 3 taken 2 times.
 26 if (rank == 0 && original_size > 1) {
401
1/2
✓ Branch 0 taken 11 times.
✗ Branch 1 not taken.
 22 all_same = AllPointsSame(points_) ? 1 : 0;
402 }
403 26 MPI_Bcast(&all_same, 1, MPI_INT, 0, MPI_COMM_WORLD);
404
405
2/2
✓ Branch 1 taken 22 times.
✓ Branch 2 taken 4 times.
 26 if (HandleTrivialCases(rank, original_size, all_same, points_, hull_)) {
406 return true;
407 }
408
409
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 20 times.
 22 thread_local WorkBuffers bufs;
410 22 bufs.recv_counts.resize(static_cast<size_t>(world_size));
411 22 bufs.recv_displs.resize(static_cast<size_t>(world_size));
412
413 22 const int block_size = padded_size / world_size;
414 22 RunDistributedHull(bufs, rank, world_size, block_size, padded_size, original_size, mpi_point, points_, hull_);
415 return true;
416 }
417
418 26 bool DergachevAGrahamScanALL::PostProcessingImpl() {
419 26 GetOutput() = static_cast<int>(hull_.size());
420 26 return true;
421 }
422
423 } // namespace dergachev_a_graham_scan
424