GCC Code Coverage Report

Directory: ./
File: tasks/konstantinov_s_graham/all/src/ops_all.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 215 221 97.3%
Functions: 22 24 91.7%
Branches: 204 338 60.4%
Line Branch Exec Source
1 #include "konstantinov_s_graham/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4 #include <tbb/blocked_range.h>
5 #include <tbb/global_control.h>
6 #include <tbb/parallel_for.h>
7 #include <tbb/parallel_reduce.h>
8 #include <tbb/parallel_sort.h>
9
10 #include <algorithm>
11 #include <cmath>
12 #include <cstddef>
13 #include <cstdint>
14 #include <ranges>
15 #include <utility>
16 #include <vector>
17
18 #include "konstantinov_s_graham/common/include/common.hpp"
19 #include "util/include/util.hpp"
20
21 namespace konstantinov_s_graham {
22
23
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 KonstantinovAGrahamALL::KonstantinovAGrahamALL(const InType &in) {
24
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 MPI_Comm_rank(MPI_COMM_WORLD, &proc_rank_);
25
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 MPI_Comm_size(MPI_COMM_WORLD, &proc_num_);
26
27 SetTypeOfTask(GetStaticTypeOfTask());
28
29
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (proc_rank_ == 0) {
30 GetInput() = in;
31 }
32
33 20 GetOutput() = OutType();
34 20 }
35
36 20 bool KonstantinovAGrahamALL::ValidationImpl() {
37 20 return GetInput().first.size() == GetInput().second.size();
38 }
39
40 20 bool KonstantinovAGrahamALL::PreProcessingImpl() {
41 20 return true;
42 }
43
44 23 void KonstantinovAGrahamALL::RemoveDuplicates(std::vector<double> &xs, std::vector<double> &ys) {
45
1/2
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
 23 std::vector<std::pair<double, double>> pts;
46
1/2
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
 23 pts.reserve(xs.size());
47
48
2/2
✓ Branch 0 taken 83 times.
✓ Branch 1 taken 23 times.
 106 for (size_t i = 0; i < xs.size(); ++i) {
49
1/2
✓ Branch 1 taken 83 times.
✗ Branch 2 not taken.
 83 pts.emplace_back(xs[i], ys[i]);
50 }
51
52 std::ranges::sort(pts, [](const auto &lhs, const auto &rhs) {
53
4/24
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 74 times.
✓ Branch 5 taken 12 times.
✗ 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 not taken.
✓ Branch 22 taken 54 times.
✓ Branch 23 taken 6 times.
 146 if (std::abs(lhs.first - rhs.first) > kKEps) {
54 128 return lhs.first < rhs.first;
55 }
56 18 return lhs.second < rhs.second;
57 });
58
59 const auto unique_end = std::ranges::unique(pts, [](const auto &lhs, const auto &rhs) {
60
5/8
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 45 times.
✓ Branch 2 taken 10 times.
✓ Branch 3 taken 3 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 2 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 60 return std::abs(lhs.first - rhs.first) < kKEps && std::abs(lhs.second - rhs.second) < kKEps;
61 });
62
63 pts.erase(unique_end.begin(), pts.end());
64
65
1/2
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
 23 xs.resize(pts.size());
66
1/2
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
 23 ys.resize(pts.size());
67
68
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 23 times.
 103 for (size_t i = 0; i < pts.size(); ++i) {
69 80 xs[i] = pts[i].first;
70 80 ys[i] = pts[i].second;
71 }
72 23 }
73
74
2/2
✓ Branch 0 taken 41 times.
✓ Branch 1 taken 9 times.
 50 bool KonstantinovAGrahamALL::IsLowerAnchor(const std::vector<double> &xs, const std::vector<double> &ys, size_t lhs,
75 size_t rhs) {
76
2/2
✓ Branch 0 taken 41 times.
✓ Branch 1 taken 9 times.
 50 if (ys[lhs] < ys[rhs] - kKEps) {
77 return true;
78 }
79
80
3/4
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 35 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 6 times.
 41 if (std::abs(ys[lhs] - ys[rhs]) < kKEps && xs[lhs] < xs[rhs] - kKEps) {
81 ✗ return true;
82 }
83
84 return false;
85 }
86
87
1/2
✓ Branch 0 taken 15 times.
✗ Branch 1 not taken.
 15 size_t KonstantinovAGrahamALL::FindAnchorIndex(const std::vector<double> &xs, const std::vector<double> &ys) {
88
1/2
✓ Branch 0 taken 15 times.
✗ Branch 1 not taken.
 15 if (xs.empty()) {
89 return 0;
90 }
91
92 30 return tbb::parallel_reduce(tbb::blocked_range<size_t>(1, xs.size()), size_t{0},
93 50 [&xs, &ys](const tbb::blocked_range<size_t> &range, size_t local_idx) {
94
2/2
✓ Branch 0 taken 50 times.
✓ Branch 1 taken 50 times.
 100 for (size_t i = range.begin(); i < range.end(); ++i) {
95
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 41 times.
 50 if (IsLowerAnchor(xs, ys, i, local_idx)) {
96 local_idx = i;
97 }
98 }
99 50 return local_idx;
100
0/2
✗ Branch 0 not taken.
✗ Branch 1 not taken.
 15 }, [&xs, &ys](size_t left, size_t right) { return IsLowerAnchor(xs, ys, left, right) ? left : right; });
101 }
102
103 ✗ double KonstantinovAGrahamALL::Dist2(const std::vector<double> &xs, const std::vector<double> &ys, size_t i, size_t j) {
104 6 const double dx = xs[j] - xs[i];
105 6 const double dy = ys[j] - ys[i];
106 6 return (dx * dx) + (dy * dy);
107 }
108
109 119 double KonstantinovAGrahamALL::CrossVal(const std::vector<double> &xs, const std::vector<double> &ys, size_t i,
110 size_t j, size_t k) {
111 119 const double ax = xs[j] - xs[i];
112 119 const double ay = ys[j] - ys[i];
113 119 const double bx = xs[k] - xs[i];
114 119 const double by = ys[k] - ys[i];
115 119 return (ax * by) - (ay * bx);
116 }
117
118 ✗ void KonstantinovAGrahamALL::FillIndexRange(std::vector<size_t> &idxs, size_t begin, size_t end, size_t anchor_idx) {
119
4/6
✓ Branch 0 taken 21 times.
✓ Branch 1 taken 7 times.
✓ Branch 2 taken 44 times.
✓ Branch 3 taken 16 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 88 for (size_t i = begin; i < end; ++i) {
120
4/6
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 14 times.
✓ Branch 2 taken 5 times.
✓ Branch 3 taken 39 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 65 if (i < anchor_idx) {
121 12 idxs[i] = i;
122
4/6
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
✓ Branch 2 taken 31 times.
✓ Branch 3 taken 8 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 53 } else if (i > anchor_idx) {
123 38 idxs[i - 1] = i;
124 }
125 }
126 ✗ }
127
128 15 void KonstantinovAGrahamALL::FillIndicesParallel(std::vector<size_t> &idxs, size_t point_count, size_t anchor_idx) {
129 15 const auto thread_count = static_cast<size_t>(ppc::util::GetNumThreads());
130
131
3/4
✓ Branch 0 taken 15 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 7 times.
✓ Branch 3 taken 8 times.
 15 if (thread_count <= 1 || point_count < (thread_count * 2)) {
132 7 FillIndexRange(idxs, 0, point_count, anchor_idx);
133 7 return;
134 }
135
136 8 std::vector<tbb::blocked_range<size_t>> ranges;
137
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 ranges.reserve(thread_count);
138
139 8 const size_t block_size = (point_count + thread_count - 1) / thread_count;
140
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 8 times.
 24 for (size_t thread_idx = 0; thread_idx < thread_count; ++thread_idx) {
141 16 const size_t begin = thread_idx * block_size;
142
1/2
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
 16 const size_t end = std::min(point_count, begin + block_size);
143
1/2
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
 16 if (begin < end) {
144
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 ranges.emplace_back(begin, end);
145 }
146 }
147
148
2/6
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 8 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 24 tbb::parallel_for(tbb::blocked_range<size_t>(0, ranges.size()), [&](const tbb::blocked_range<size_t> &outer_range) {
149
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 16 times.
 32 for (size_t i = outer_range.begin(); i < outer_range.end(); ++i) {
150 16 FillIndexRange(idxs, ranges[i].begin(), ranges[i].end(), anchor_idx);
151 }
152 16 });
153 }
154
155 15 std::vector<size_t> KonstantinovAGrahamALL::CollectAndSortIndices(const std::vector<double> &xs,
156 const std::vector<double> &ys, size_t anchor_idx) {
157
1/2
✓ Branch 2 taken 15 times.
✗ Branch 3 not taken.
 15 std::vector<size_t> idxs(xs.size() - 1);
158
159
1/2
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
 15 FillIndicesParallel(idxs, xs.size(), anchor_idx);
160
161
1/4
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 15 tbb::parallel_sort(idxs.begin(), idxs.end(), [&xs, &ys, anchor_idx](size_t lhs, size_t rhs) {
162
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 54 times.
 60 const double cross = CrossVal(xs, ys, anchor_idx, lhs, rhs);
163
164
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 54 times.
 60 if (std::abs(cross) < kKEps) {
165 6 return Dist2(xs, ys, anchor_idx, lhs) < Dist2(xs, ys, anchor_idx, rhs);
166 }
167
168 54 return cross > 0;
169 });
170
171 15 return idxs;
172 }
173
174 15 bool KonstantinovAGrahamALL::CheckCollinearRange(const std::vector<double> &xs, const std::vector<double> &ys,
175 size_t anchor_idx, const std::vector<size_t> &sorted_idxs,
176 size_t begin, size_t end) {
177
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 1 times.
 16 for (size_t i = begin; i < end; ++i) {
178
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 14 times.
 15 if (std::abs(CrossVal(xs, ys, anchor_idx, sorted_idxs[0], sorted_idxs[i])) > kKEps) {
179 return false;
180 }
181 }
182
183 return true;
184 }
185
186
1/2
✓ Branch 0 taken 15 times.
✗ Branch 1 not taken.
 15 bool KonstantinovAGrahamALL::AllCollinearWithAnchor(const std::vector<double> &xs, const std::vector<double> &ys,
187 size_t anchor_idx, const std::vector<size_t> &sorted_idxs) {
188
1/2
✓ Branch 0 taken 15 times.
✗ Branch 1 not taken.
 15 if (sorted_idxs.size() < 2) {
189 return true;
190 }
191
192 15 const auto thread_count = static_cast<size_t>(ppc::util::GetNumThreads());
193
194
3/4
✓ Branch 0 taken 15 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 9 times.
✓ Branch 3 taken 6 times.
 15 if (thread_count <= 1 || sorted_idxs.size() < (thread_count * 2)) {
195 9 return CheckCollinearRange(xs, ys, anchor_idx, sorted_idxs, 1, sorted_idxs.size());
196 }
197
198 6 std::vector<tbb::blocked_range<size_t>> ranges;
199
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 ranges.reserve(thread_count);
200
201 6 const size_t block_size = (sorted_idxs.size() + thread_count - 1) / thread_count;
202
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 6 times.
 18 for (size_t thread_idx = 0; thread_idx < thread_count; ++thread_idx) {
203
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 const size_t begin = std::max<size_t>(1, thread_idx * block_size);
204
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 const size_t end = std::min(sorted_idxs.size(), begin + block_size);
205
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 if (begin < end) {
206
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 ranges.emplace_back(begin, end);
207 }
208 }
209
210 12 return tbb::parallel_reduce(tbb::blocked_range<size_t>(0, ranges.size()), true,
211
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 18 [&](const tbb::blocked_range<size_t> &outer_range, bool local_ok) {
212
4/4
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 6 times.
✓ Branch 3 taken 6 times.
 18 for (size_t i = outer_range.begin(); i < outer_range.end() && local_ok; ++i) {
213 6 if (!CheckCollinearRange(xs, ys, anchor_idx, sorted_idxs, ranges[i].begin(), ranges[i].end())) {
214 local_ok = false;
215 }
216 }
217 12 return local_ok;
218
1/4
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 6 }, [](bool lhs, bool rhs) { return lhs && rhs; });
219 }
220
221 14 std::vector<std::pair<double, double>> KonstantinovAGrahamALL::BuildHullFromSorted(
222 const std::vector<double> &xs, const std::vector<double> &ys, size_t anchor_idx,
223 const std::vector<size_t> &sorted_idxs) {
224
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 std::vector<size_t> stack;
225
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 stack.reserve(sorted_idxs.size() + 1);
226 stack.push_back(anchor_idx);
227
228
1/2
✓ Branch 0 taken 14 times.
✗ Branch 1 not taken.
 14 if (!sorted_idxs.empty()) {
229 stack.push_back(sorted_idxs[0]);
230 }
231
232
2/2
✓ Branch 0 taken 34 times.
✓ Branch 1 taken 14 times.
 48 for (size_t i = 1; i < sorted_idxs.size(); ++i) {
233 34 const size_t cur = sorted_idxs[i];
234
235
1/2
✓ Branch 0 taken 44 times.
✗ Branch 1 not taken.
 44 while (stack.size() >= 2) {
236
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 34 times.
 44 const size_t q = stack.back();
237 44 const size_t p = stack[stack.size() - 2];
238 44 const double cross = CrossVal(xs, ys, p, q, cur);
239
240
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 34 times.
 44 if (cross <= kKEps) {
241 stack.pop_back();
242 } else {
243 break;
244 }
245 }
246
247 stack.push_back(cur);
248 }
249
250
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 std::vector<std::pair<double, double>> hull;
251
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 hull.reserve(stack.size());
252
253
3/4
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 52 times.
✓ Branch 4 taken 14 times.
 66 for (size_t id : stack) {
254
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 hull.emplace_back(xs[id], ys[id]);
255 }
256
257 14 return hull;
258 }
259
260 23 std::vector<std::pair<double, double>> KonstantinovAGrahamALL::BuildHullFromCoords(const std::vector<double> &xs,
261 const std::vector<double> &ys) {
262 23 std::vector<double> local_xs = xs;
263
1/2
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
 23 std::vector<double> local_ys = ys;
264
265
1/2
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
 23 RemoveDuplicates(local_xs, local_ys);
266
267
2/4
✓ Branch 0 taken 23 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 23 times.
 23 if (local_xs.size() != local_ys.size() || local_xs.empty()) {
268 ✗ return {};
269 }
270
271
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 15 times.
 23 if (local_xs.size() < 3) {
272
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 std::vector<std::pair<double, double>> out;
273
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 out.reserve(local_xs.size());
274
275
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 8 times.
 23 for (size_t i = 0; i < local_xs.size(); ++i) {
276
1/2
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
 15 out.emplace_back(local_xs[i], local_ys[i]);
277 }
278
279 return out;
280 }
281
282
1/2
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
 15 const size_t anchor_idx = FindAnchorIndex(local_xs, local_ys);
283
1/2
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
 15 const std::vector<size_t> sorted_idxs = CollectAndSortIndices(local_xs, local_ys, anchor_idx);
284
285
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 15 times.
 15 if (sorted_idxs.empty()) {
286 ✗ return {{local_xs[anchor_idx], local_ys[anchor_idx]}};
287 }
288
289
3/4
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1 times.
✓ Branch 4 taken 14 times.
 15 if (AllCollinearWithAnchor(local_xs, local_ys, anchor_idx, sorted_idxs)) {
290
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 const size_t far_idx = sorted_idxs.back();
291
1/4
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 1 return {{local_xs[anchor_idx], local_ys[anchor_idx]}, {local_xs[far_idx], local_ys[far_idx]}};
292 }
293
294
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 return BuildHullFromSorted(local_xs, local_ys, anchor_idx, sorted_idxs);
295 }
296
297 14 void KonstantinovAGrahamALL::ScatterInput(size_t total_size, std::vector<double> &local_xs,
298 std::vector<double> &local_ys) {
299 14 std::vector<int> counts(proc_num_, 0);
300
1/4
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 14 std::vector<int> displs(proc_num_, 0);
301
302 14 const size_t base = total_size / static_cast<size_t>(proc_num_);
303 14 const size_t remainder = total_size % static_cast<size_t>(proc_num_);
304
305 size_t offset = 0;
306
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 14 times.
 42 for (int rank = 0; rank < proc_num_; ++rank) {
307 28 const size_t amount = base + (std::cmp_less(rank, remainder) ? 1U : 0U);
308 28 counts[rank] = static_cast<int>(amount);
309 28 displs[rank] = static_cast<int>(offset);
310 28 offset += amount;
311 }
312
313
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 const int local_size = counts[proc_rank_];
314
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 local_xs.resize(static_cast<size_t>(local_size));
315
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 local_ys.resize(static_cast<size_t>(local_size));
316
317
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 const double *send_xs = proc_rank_ == 0 ? GetInput().first.data() : nullptr;
318
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 const double *send_ys = proc_rank_ == 0 ? GetInput().second.data() : nullptr;
319
320
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 MPI_Scatterv(send_xs, counts.data(), displs.data(), MPI_DOUBLE, local_xs.data(), local_size, MPI_DOUBLE, 0,
321 MPI_COMM_WORLD);
322
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 MPI_Scatterv(send_ys, counts.data(), displs.data(), MPI_DOUBLE, local_ys.data(), local_size, MPI_DOUBLE, 0,
323 MPI_COMM_WORLD);
324 14 }
325
326 14 void KonstantinovAGrahamALL::GatherLocalHull(const std::vector<std::pair<double, double>> &local_hull,
327 std::vector<double> &gathered_xs, std::vector<double> &gathered_ys) const {
328 14 const auto local_size = static_cast<int>(local_hull.size());
329
330 14 std::vector<int> counts(proc_num_, 0);
331
3/4
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
✓ Branch 3 taken 14 times.
✗ Branch 4 not taken.
 21 MPI_Gather(&local_size, 1, MPI_INT, proc_rank_ == 0 ? counts.data() : nullptr, 1, MPI_INT, 0, MPI_COMM_WORLD);
332
333
1/4
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 14 std::vector<int> displs(proc_num_, 0);
334 int total_size = 0;
335
336
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 if (proc_rank_ == 0) {
337
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 7 times.
 21 for (int rank = 0; rank < proc_num_; ++rank) {
338 14 displs[rank] = total_size;
339 14 total_size += counts[rank];
340 }
341
342
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 7 gathered_xs.resize(static_cast<size_t>(total_size));
343
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 7 gathered_ys.resize(static_cast<size_t>(total_size));
344 }
345
346
1/4
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 14 std::vector<double> local_xs(static_cast<size_t>(local_size));
347
1/4
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 14 std::vector<double> local_ys(static_cast<size_t>(local_size));
348
349
2/2
✓ Branch 0 taken 39 times.
✓ Branch 1 taken 14 times.
 53 for (int i = 0; i < local_size; ++i) {
350 39 local_xs[static_cast<size_t>(i)] = local_hull[static_cast<size_t>(i)].first;
351 39 local_ys[static_cast<size_t>(i)] = local_hull[static_cast<size_t>(i)].second;
352 }
353
354
5/6
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
✓ Branch 2 taken 7 times.
✓ Branch 3 taken 7 times.
✓ Branch 5 taken 14 times.
✗ Branch 6 not taken.
 28 MPI_Gatherv(local_xs.data(), local_size, MPI_DOUBLE, proc_rank_ == 0 ? gathered_xs.data() : nullptr,
355
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 proc_rank_ == 0 ? counts.data() : nullptr, proc_rank_ == 0 ? displs.data() : nullptr, MPI_DOUBLE, 0,
356 MPI_COMM_WORLD);
357
358
5/6
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
✓ Branch 2 taken 7 times.
✓ Branch 3 taken 7 times.
✓ Branch 5 taken 14 times.
✗ Branch 6 not taken.
 28 MPI_Gatherv(local_ys.data(), local_size, MPI_DOUBLE, proc_rank_ == 0 ? gathered_ys.data() : nullptr,
359
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 proc_rank_ == 0 ? counts.data() : nullptr, proc_rank_ == 0 ? displs.data() : nullptr, MPI_DOUBLE, 0,
360 MPI_COMM_WORLD);
361 14 }
362
363 20 void KonstantinovAGrahamALL::BroadcastOutput() {
364 20 std::uint64_t size_u64 = 0;
365
366
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (proc_rank_ == 0) {
367 10 size_u64 = static_cast<std::uint64_t>(GetOutput().size());
368 }
369
370 20 MPI_Bcast(&size_u64, 1, MPI_UINT64_T, 0, MPI_COMM_WORLD);
371
372 20 const auto size = static_cast<size_t>(size_u64);
373
374 20 std::vector<double> xs(size);
375
1/4
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 20 std::vector<double> ys(size);
376
377
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (proc_rank_ == 0) {
378
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 10 times.
 40 for (size_t i = 0; i < size; ++i) {
379 30 xs[i] = GetOutput()[i].first;
380 30 ys[i] = GetOutput()[i].second;
381 }
382 }
383
384
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 2 times.
 20 if (size > 0) {
385
1/2
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
 18 MPI_Bcast(xs.data(), static_cast<int>(size), MPI_DOUBLE, 0, MPI_COMM_WORLD);
386
1/2
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
 18 MPI_Bcast(ys.data(), static_cast<int>(size), MPI_DOUBLE, 0, MPI_COMM_WORLD);
387 }
388
389
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (proc_rank_ != 0) {
390
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 GetOutput().resize(size);
391
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 10 times.
 40 for (size_t i = 0; i < size; ++i) {
392 GetOutput()[i] = {xs[i], ys[i]};
393 }
394 }
395 20 }
396
397 20 bool KonstantinovAGrahamALL::RunImpl() {
398 20 const tbb::global_control gc(tbb::global_control::max_allowed_parallelism, ppc::util::GetNumThreads());
399
400 20 std::uint64_t total_size_u64 = 0;
401
402
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (proc_rank_ == 0) {
403 10 total_size_u64 = static_cast<std::uint64_t>(GetInput().first.size());
404 }
405
406
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 MPI_Bcast(&total_size_u64, 1, MPI_UINT64_T, 0, MPI_COMM_WORLD);
407
408 20 const auto total_size = static_cast<size_t>(total_size_u64);
409
410
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 18 times.
 20 if (total_size == 0) {
411
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
 2 if (proc_rank_ == 0) {
412 GetOutput() = {};
413 }
414
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 BroadcastOutput();
415 return true;
416 }
417
418
3/4
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 14 times.
 18 if (total_size < 3 || proc_num_ == 1) {
419
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 2 times.
 4 if (proc_rank_ == 0) {
420
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 4 GetOutput() = BuildHullFromCoords(GetInput().first, GetInput().second);
421 }
422
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 BroadcastOutput();
423 return true;
424 }
425
426 14 std::vector<double> local_xs;
427 14 std::vector<double> local_ys;
428
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 ScatterInput(total_size, local_xs, local_ys);
429
430
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 const std::vector<std::pair<double, double>> local_hull = BuildHullFromCoords(local_xs, local_ys);
431
432 14 std::vector<double> gathered_xs;
433 14 std::vector<double> gathered_ys;
434
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 GatherLocalHull(local_hull, gathered_xs, gathered_ys);
435
436
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 if (proc_rank_ == 0) {
437
1/4
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 14 GetOutput() = BuildHullFromCoords(gathered_xs, gathered_ys);
438 }
439
440
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 BroadcastOutput();
441 return true;
442 }
443
444 20 bool KonstantinovAGrahamALL::PostProcessingImpl() {
445 20 return true;
446 }
447
448 } // namespace konstantinov_s_graham
449