GCC Code Coverage Report

Directory: ./
File: tasks/kutuzov_i_convex_hull_jarvis/all/src/ops_all.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 98 109 89.9%
Functions: 10 13 76.9%
Branches: 34 52 65.4%
Line Branch Exec Source
1 #include "kutuzov_i_convex_hull_jarvis/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4 #include <omp.h>
5
6 #include <array>
7 #include <cmath>
8 #include <cstddef>
9 #include <vector>
10
11 #include "kutuzov_i_convex_hull_jarvis/common/include/common.hpp"
12
13 namespace kutuzov_i_convex_hull_jarvis {
14
15 double KutuzovITestConvexHullALL::s_curr_x = 0.0;
16 double KutuzovITestConvexHullALL::s_curr_y = 0.0;
17 double KutuzovITestConvexHullALL::s_epsilon = 1e-9;
18
19 ✗ double KutuzovITestConvexHullALL::DistanceSquared(double a_x, double a_y, double b_x, double b_y) {
20 10 return ((a_x - b_x) * (a_x - b_x)) + ((a_y - b_y) * (a_y - b_y));
21 }
22
23 ✗ double KutuzovITestConvexHullALL::CrossProduct(double o_x, double o_y, double a_x, double a_y, double b_x, double b_y) {
24 18 return ((a_x - o_x) * (b_y - o_y)) - ((a_y - o_y) * (b_x - o_x));
25 }
26
27 ✗ bool KutuzovITestConvexHullALL::IsBetterPoint(double cross, double epsilon, double current_x, double current_y,
28 double i_x, double i_y, double next_x, double next_y) {
29 ✗ if (cross < -epsilon) {
30 return true;
31 }
32
2/4
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 14 if (std::abs(cross) < epsilon) {
33 ✗ return DistanceSquared(current_x, current_y, i_x, i_y) > DistanceSquared(current_x, current_y, next_x, next_y);
34 }
35 return false;
36 }
37
38 6 void KutuzovITestConvexHullALL::LeftmostReduce(void *invec, void *inoutvec, const int *len, MPI_Datatype * /*unused*/) {
39 auto *in = static_cast<double *>(invec);
40 auto *inout = static_cast<double *>(inoutvec);
41
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 for (int i = 0; i < *len; ++i) {
42 6 const auto idx = static_cast<ptrdiff_t>(3) * static_cast<ptrdiff_t>(i);
43 6 double x_in = in[idx];
44 6 double y_in = in[idx + 1];
45 6 double x_io = inout[idx];
46 6 double y_io = inout[idx + 1];
47
3/6
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 6 times.
 6 if (x_in < x_io || (x_in == x_io && y_in < y_io)) {
48 ✗ inout[idx] = x_in;
49 ✗ inout[idx + 1] = y_in;
50 ✗ inout[idx + 2] = in[idx + 2];
51 }
52 }
53 6 }
54
55 18 void KutuzovITestConvexHullALL::NextReduce(void *invec, void *inoutvec, const int *len, MPI_Datatype * /*unused*/) {
56 auto *in = static_cast<double *>(invec);
57 auto *inout = static_cast<double *>(inoutvec);
58
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 18 times.
 36 for (int i = 0; i < *len; ++i) {
59 18 const auto idx = static_cast<ptrdiff_t>(3) * static_cast<ptrdiff_t>(i);
60 18 double ax = inout[idx];
61 18 double ay = inout[idx + 1];
62 18 double bx = in[idx];
63 18 double by = in[idx + 1];
64 18 double cross = CrossProduct(s_curr_x, s_curr_y, ax, ay, bx, by);
65
3/4
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 10 times.
 28 if (IsBetterPoint(cross, s_epsilon, s_curr_x, s_curr_y, bx, by, ax, ay)) {
66 4 inout[idx] = bx;
67 4 inout[idx + 1] = by;
68 4 inout[idx + 2] = in[idx + 2];
69 }
70 }
71 18 }
72
73 6 void KutuzovITestConvexHullALL::BuildTypes() {
74 6 MPI_Type_contiguous(3, MPI_DOUBLE, &type_leftmost_);
75 6 MPI_Type_commit(&type_leftmost_);
76 6 type_next_ = type_leftmost_;
77 6 }
78
79
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 KutuzovITestConvexHullALL::KutuzovITestConvexHullALL(const InType &in) {
80 SetTypeOfTask(GetStaticTypeOfTask());
81
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 GetInput() = in;
82 GetOutput() = {};
83 6 }
84
85 6 size_t KutuzovITestConvexHullALL::FindLeftmostPoint(const InType &input, size_t start, size_t end) {
86 6 std::array<double, 3> local_lm{};
87 6 std::array<double, 3> global_lm{};
88 6 local_lm[0] = std::get<0>(input[0]);
89 6 local_lm[1] = std::get<1>(input[0]);
90 local_lm[2] = 0.0;
91
92 6 #pragma omp parallel default(none) shared(input, start, end, local_lm)
93 {
94 size_t li = 0;
95 double lx = std::get<0>(input[li]);
96 double ly = std::get<1>(input[li]);
97
98 #pragma omp for nowait
99 for (size_t i = start; i < end; ++i) {
100 double x = std::get<0>(input[i]);
101 double y = std::get<1>(input[i]);
102 if (x < lx || (x == lx && y < ly)) {
103 li = i;
104 lx = x;
105 ly = y;
106 }
107 }
108 #pragma omp critical
109 {
110 if (lx < local_lm[0] || (lx == local_lm[0] && ly < local_lm[1])) {
111 local_lm[0] = lx;
112 local_lm[1] = ly;
113 local_lm[2] = static_cast<double>(li);
114 }
115 }
116 }
117
118 6 MPI_Allreduce(local_lm.data(), global_lm.data(), 1, type_leftmost_, op_leftmost_, MPI_COMM_WORLD);
119 6 return static_cast<size_t>(global_lm[2]);
120 }
121
122 18 size_t KutuzovITestConvexHullALL::FindNextPoint(const InType &input, size_t n, size_t current, double current_x,
123 double current_y, double epsilon, size_t start, size_t end) {
124 18 size_t next = (current + 1) % n;
125 18 double next_x = std::get<0>(input[next]);
126 18 double next_y = std::get<1>(input[next]);
127
128 18 #pragma omp parallel default(none) \
129 shared(input, n, current, current_x, current_y, start, end, epsilon, next, next_x, next_y)
130 {
131 size_t local_next = (current + 1) % n;
132 double local_next_x = std::get<0>(input[local_next]);
133 double local_next_y = std::get<1>(input[local_next]);
134
135 #pragma omp for nowait
136 for (size_t i = start; i < end; ++i) {
137 if (i == current) {
138 continue;
139 }
140 double i_x = std::get<0>(input[i]);
141 double i_y = std::get<1>(input[i]);
142 double cross = CrossProduct(current_x, current_y, local_next_x, local_next_y, i_x, i_y);
143 if (IsBetterPoint(cross, epsilon, current_x, current_y, i_x, i_y, local_next_x, local_next_y)) {
144 local_next = i;
145 local_next_x = i_x;
146 local_next_y = i_y;
147 }
148 }
149
150 #pragma omp critical
151 {
152 double cross = CrossProduct(current_x, current_y, next_x, next_y, local_next_x, local_next_y);
153 if (IsBetterPoint(cross, epsilon, current_x, current_y, local_next_x, local_next_y, next_x, next_y)) {
154 next = local_next;
155 next_x = local_next_x;
156 next_y = local_next_y;
157 }
158 }
159 }
160
161 18 s_curr_x = current_x;
162 18 s_curr_y = current_y;
163 18 s_epsilon = epsilon;
164
165 18 std::array<double, 3> local_cand{next_x, next_y, static_cast<double>(next)};
166 18 std::array<double, 3> global_cand{};
167
168 18 MPI_Allreduce(local_cand.data(), global_cand.data(), 1, type_next_, op_next_, MPI_COMM_WORLD);
169
170 18 return static_cast<size_t>(global_cand[2]);
171 }
172
173 6 bool KutuzovITestConvexHullALL::ValidationImpl() {
174 6 return true;
175 }
176
177 6 bool KutuzovITestConvexHullALL::PreProcessingImpl() {
178 6 int flag = 0;
179 6 MPI_Initialized(&flag);
180
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 if (flag == 0) {
181 ✗ MPI_Init_thread(nullptr, nullptr, MPI_THREAD_FUNNELED, nullptr);
182 }
183
184 6 MPI_Comm_rank(MPI_COMM_WORLD, &rank_);
185 6 MPI_Comm_size(MPI_COMM_WORLD, &size_);
186
187 6 BuildTypes();
188
189 6 MPI_Op_create(reinterpret_cast<MPI_User_function *>(LeftmostReduce), 1, &op_leftmost_);
190 6 MPI_Op_create(reinterpret_cast<MPI_User_function *>(NextReduce), 1, &op_next_);
191
192 auto &input = GetInput();
193 6 auto n = static_cast<int>(input.size());
194
195 6 MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
196
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (rank_ != 0) {
197 3 input.resize(static_cast<size_t>(n));
198 }
199
200 6 std::vector<double> coords(static_cast<size_t>(2) * static_cast<size_t>(n));
201
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (rank_ == 0) {
202
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 3 times.
 23 for (int i = 0; i < n; ++i) {
203 20 coords[(2 * static_cast<size_t>(i))] = std::get<0>(input[static_cast<size_t>(i)]);
204 20 coords[(2 * static_cast<size_t>(i)) + 1] = std::get<1>(input[static_cast<size_t>(i)]);
205 }
206 }
207
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Bcast(coords.data(), static_cast<int>(coords.size()), MPI_DOUBLE, 0, MPI_COMM_WORLD);
208
209
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (rank_ != 0) {
210
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 3 times.
 23 for (int i = 0; i < n; ++i) {
211 20 const auto idx = static_cast<size_t>(i);
212 input[idx] = {coords[2 * idx], coords[(2 * idx) + 1]};
213 }
214 }
215
216 6 return true;
217 }
218
219
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 bool KutuzovITestConvexHullALL::RunImpl() {
220 auto &input = GetInput();
221 const auto n = static_cast<size_t>(input.size());
222
223
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 if (n < 3) {
224 ✗ GetOutput() = input;
225 ✗ return true;
226 }
227
228 6 const size_t start = (n * static_cast<size_t>(rank_)) / static_cast<size_t>(size_);
229 6 const size_t end = (n * (static_cast<size_t>(rank_) + 1)) / static_cast<size_t>(size_);
230 const double epsilon = 1e-9;
231
232 6 const size_t leftmost = FindLeftmostPoint(input, start, end);
233
234 size_t current = leftmost;
235 6 double current_x = std::get<0>(input[current]);
236
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 double current_y = std::get<1>(input[current]);
237
238 auto &output = GetOutput();
239 output.clear();
240
241 while (true) {
242 output.push_back(input[current]);
243
244 18 const size_t next = FindNextPoint(input, n, current, current_x, current_y, epsilon, start, end);
245
246
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 6 times.
 18 if (next == leftmost) {
247 break;
248 }
249
250 current = next;
251 12 current_x = std::get<0>(input[current]);
252 12 current_y = std::get<1>(input[current]);
253 12 }
254
255 return true;
256 }
257
258 6 bool KutuzovITestConvexHullALL::PostProcessingImpl() {
259
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (op_leftmost_ != MPI_OP_NULL) {
260 6 MPI_Op_free(&op_leftmost_);
261 }
262
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (op_next_ != MPI_OP_NULL) {
263 6 MPI_Op_free(&op_next_);
264 }
265
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (type_leftmost_ != MPI_DATATYPE_NULL) {
266 6 MPI_Type_free(&type_leftmost_);
267 }
268 6 return true;
269 }
270 // Comment for CI
271 } // namespace kutuzov_i_convex_hull_jarvis
272