GCC Code Coverage Report

Directory: ./
File: tasks/romanov_m_jarvis_prohod/mpi/src/ops_mpi.cpp
Date: 2026-01-27 01:59:34
Exec Total Coverage
Lines: 79 83 95.2%
Functions: 10 10 100.0%
Branches: 70 106 66.0%
Line Branch Exec Source
1 #include "romanov_m_jarvis_prohod/mpi/include/ops_mpi.hpp"
2
3 #include <mpi.h>
4
5 #include <cstddef>
6 #include <cstdint>
7 #include <utility>
8 #include <vector>
9
10 #include "romanov_m_jarvis_prohod/common/include/common.hpp"
11
12 namespace romanov_m_jarvis_prohod {
13
14
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 RomanovMJarvisProhodMPI::RomanovMJarvisProhodMPI(const InType &in) {
15 SetTypeOfTask(GetStaticTypeOfTask());
16
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 GetInput() = in;
17 GetOutput().clear();
18 8 }
19
20 8 bool RomanovMJarvisProhodMPI::ValidationImpl() {
21 8 return GetInput().size() >= 3;
22 }
23
24 8 bool RomanovMJarvisProhodMPI::PreProcessingImpl() {
25 8 return true;
26 }
27
28 namespace {
29
30 6 int LeftPoint(const std::vector<Point> &points) {
31 int idx = 0;
32
2/2
✓ Branch 0 taken 17 times.
✓ Branch 1 taken 6 times.
 23 for (std::size_t i = 1; i < points.size(); ++i) {
33
4/6
✓ Branch 0 taken 17 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 15 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 2 times.
 17 if (points[i].x < points[idx].x || (points[i].x == points[idx].x && points[i].y < points[idx].y)) {
34 ✗ idx = static_cast<int>(i);
35 }
36 }
37 6 return idx;
38 }
39
40 19 int ChooseNextBoundaryPoint(const std::vector<Point> &points, int p) {
41 19 const int n = static_cast<int>(points.size());
42 19 int q = (p + 1) % n;
43
44
2/2
✓ Branch 0 taken 75 times.
✓ Branch 1 taken 19 times.
 94 for (int i = 0; i < n; ++i) {
45
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 68 times.
 75 const int64_t cross = CrossCalculate(points[p], points[i], points[q]);
46
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 68 times.
 75 if (cross > 0) {
47 q = i;
48
2/2
✓ Branch 0 taken 38 times.
✓ Branch 1 taken 30 times.
 68 } else if (cross == 0) {
49
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 36 times.
 38 if (SqDistance(points[p], points[i]) > SqDistance(points[p], points[q])) {
50 q = i;
51 }
52 }
53 }
54 19 return q;
55 }
56
57 void BuildPointDatatype(MPI_Datatype *p_type) {
58 8 MPI_Type_contiguous(2, MPI_INT, p_type);
59 8 MPI_Type_commit(p_type);
60 }
61
62 8 void ComputeScatterLayout(int rank, int size, int n, std::vector<int> &counts, std::vector<int> &displs) {
63
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 if (rank != 0) {
64 return;
65 }
66
67 4 const int base = n / size;
68 4 const int rem = n % size;
69
70
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 4 times.
 12 for (int i = 0; i < size; ++i) {
71
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 5 times.
 8 counts[i] = (i < rem) ? (base + 1) : base;
72 }
73
74 4 displs[0] = 0;
75
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 for (int i = 1; i < size; ++i) {
76 4 displs[i] = displs[i - 1] + counts[i - 1];
77 }
78 }
79
80 } // namespace
81
82
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 std::vector<Point> RomanovMJarvisProhodMPI::JarvisMarch(std::vector<Point> points) {
83
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 if (points.size() < 3) {
84 return points;
85 }
86
87 6 std::vector<Point> hull;
88 6 const int start = LeftPoint(points);
89
90 int p = start;
91 while (true) {
92
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 17 times.
 19 hull.push_back(points[p]);
93 19 p = ChooseNextBoundaryPoint(points, p);
94
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 6 times.
 19 if (p == start) {
95 break;
96 }
97 }
98
99 return hull;
100 }
101
102 8 std::vector<Point> RomanovMJarvisProhodMPI::FinalHull(int rank, std::vector<Point> &all_hull_points) {
103
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 if (rank != 0) {
104 4 return {};
105 }
106
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 8 return JarvisMarch(std::move(all_hull_points));
107 }
108
109 8 bool RomanovMJarvisProhodMPI::RunImpl() {
110 8 int rank = 0;
111 8 int size = 0;
112 8 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
113 8 MPI_Comm_size(MPI_COMM_WORLD, &size);
114
115 8 int n = 0;
116
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 if (rank == 0) {
117 4 n = static_cast<int>(GetInput().size());
118 }
119 8 MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
120
121
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8 times.
 8 if (n < 3) {
122 ✗ if (rank == 0) {
123 ✗ GetOutput() = GetInput();
124 }
125 ✗ return true;
126 }
127
128 8 MPI_Datatype p_type = MPI_DATATYPE_NULL;
129 BuildPointDatatype(&p_type);
130
131 8 std::vector<int> counts(size);
132
1/4
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 8 std::vector<int> displs(size);
133 8 ComputeScatterLayout(rank, size, n, counts, displs);
134
135
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 5 times.
 8 const int l_size = (rank < (n % size)) ? ((n / size) + 1) : (n / size);
136
1/4
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 8 std::vector<Point> local_points(static_cast<std::size_t>(l_size));
137
138
3/4
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
✓ Branch 3 taken 8 times.
✗ Branch 4 not taken.
 12 MPI_Scatterv(rank == 0 ? GetInput().data() : nullptr, counts.data(), displs.data(), p_type, local_points.data(),
139 l_size, p_type, 0, MPI_COMM_WORLD);
140
141
3/8
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 8 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 8 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
 16 std::vector<Point> local_hull = JarvisMarch(local_points);
142 8 int local_size = static_cast<int>(local_hull.size());
143
144
1/4
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 8 std::vector<int> recv_counts(size);
145
1/4
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 8 std::vector<int> recv_displs(size);
146
147
3/4
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
✓ Branch 3 taken 8 times.
✗ Branch 4 not taken.
 12 MPI_Gather(&local_size, 1, MPI_INT, rank == 0 ? recv_counts.data() : nullptr, 1, MPI_INT, 0, MPI_COMM_WORLD);
148
149 int total = 0;
150
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 if (rank == 0) {
151
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 4 times.
 12 for (int i = 0; i < size; ++i) {
152 8 recv_displs[i] = total;
153 8 total += recv_counts[i];
154 }
155 }
156
157
1/4
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 8 std::vector<Point> all_points(static_cast<std::size_t>(total));
158
3/4
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
✓ Branch 3 taken 8 times.
✗ Branch 4 not taken.
 12 MPI_Gatherv(local_hull.data(), local_size, p_type, rank == 0 ? all_points.data() : nullptr, recv_counts.data(),
159 recv_displs.data(), p_type, 0, MPI_COMM_WORLD);
160
161
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 std::vector<Point> final_hull = FinalHull(rank, all_points);
162 8 int final_size = static_cast<int>(final_hull.size());
163
164
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 MPI_Bcast(&final_size, 1, MPI_INT, 0, MPI_COMM_WORLD);
165
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 if (rank != 0) {
166
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 final_hull.resize(static_cast<std::size_t>(final_size));
167 }
168
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 MPI_Bcast(final_hull.data(), final_size, p_type, 0, MPI_COMM_WORLD);
169
170 GetOutput() = std::move(final_hull);
171
172
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 MPI_Type_free(&p_type);
173 return true;
174 }
175
176 8 bool RomanovMJarvisProhodMPI::PostProcessingImpl() {
177 8 return true;
178 }
179
180 } // namespace romanov_m_jarvis_prohod
181