GCC Code Coverage Report

Directory: ./
File: tasks/redkina_a_graham_approach/mpi/src/ops_mpi.cpp
Date: 2026-01-27 01:59:34
Exec Total Coverage
Lines: 88 90 97.8%
Functions: 12 12 100.0%
Branches: 76 148 51.4%
Line Branch Exec Source
1 #include "redkina_a_graham_approach/mpi/include/ops_mpi.hpp"
2
3 #include <mpi.h>
4
5 #include <algorithm>
6 #include <cstddef>
7 #include <utility>
8 #include <vector>
9
10 #include "redkina_a_graham_approach/common/include/common.hpp"
11
12 namespace redkina_a_graham_approach {
13
14
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 RedkinaAGrahamApproachMPI::RedkinaAGrahamApproachMPI(const InType &in) {
15 SetTypeOfTask(GetStaticTypeOfTask());
16
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 GetInput() = in;
17 GetOutput().clear();
18 24 }
19
20 24 bool RedkinaAGrahamApproachMPI::ValidationImpl() {
21 24 return GetInput().size() >= 3;
22 }
23
24 24 bool RedkinaAGrahamApproachMPI::PreProcessingImpl() {
25 24 return true;
26 }
27
28 namespace {
29
30
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 22 times.
 30 inline bool ComparePolarAngle(const Point &pivot, const Point &a, const Point &b) noexcept {
31 const int cross = CalcCross(pivot, a, b);
32
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 22 times.
 30 if (cross == 0) {
33 8 return CalcDistSq(pivot, a) < CalcDistSq(pivot, b);
34 }
35 22 return cross > 0;
36 }
37
38 void CreateMpiPointType(MPI_Datatype *p_type) {
39 24 MPI_Type_contiguous(2, MPI_INT, p_type);
40
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 MPI_Type_commit(p_type);
41 24 }
42
43
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
 24 void ScatterPointData(int rank, const std::vector<Point> &a_points, std::vector<Point> &l_points,
44 const std::vector<int> &counts, const std::vector<int> &displs, MPI_Datatype p_type) {
45
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
 36 MPI_Scatterv(rank == 0 ? a_points.data() : nullptr, rank == 0 ? counts.data() : nullptr,
46 rank == 0 ? displs.data() : nullptr, p_type, l_points.data(), static_cast<int>(l_points.size()), p_type,
47 0, MPI_COMM_WORLD);
48 24 }
49
50 24 void GatherLocalHulls(int rank, const std::vector<Point> &l_hull, std::vector<Point> &a_hull_points,
51 const std::vector<int> &r_counts, const std::vector<int> &r_displs, MPI_Datatype p_type) {
52
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
 36 MPI_Gatherv(l_hull.data(), static_cast<int>(l_hull.size()), p_type, rank == 0 ? a_hull_points.data() : nullptr,
53 rank == 0 ? r_counts.data() : nullptr, rank == 0 ? r_displs.data() : nullptr, p_type, 0, MPI_COMM_WORLD);
54 24 }
55
56 24 void BroadcastHull(int rank, std::vector<Point> &f_hull, MPI_Datatype p_type) {
57 24 int f_size = static_cast<int>(f_hull.size());
58 24 MPI_Bcast(&f_size, 1, MPI_INT, 0, MPI_COMM_WORLD);
59
60
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
 24 if (rank != 0) {
61 12 f_hull.resize(f_size);
62 }
63
64 24 MPI_Bcast(f_hull.data(), f_size, p_type, 0, MPI_COMM_WORLD);
65 24 }
66
67 24 void InitCountsAndDispls(int rank, int size, int n, std::vector<int> &counts, std::vector<int> &displs) {
68
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
 24 if (rank == 0) {
69 12 const int base = n / size;
70 12 const int rem = n % size;
71
72
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 12 times.
 36 for (int i = 0; i < size; ++i) {
73
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 16 times.
 24 counts[i] = (i < rem) ? (base + 1) : base;
74 }
75
76 12 displs[0] = 0;
77
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
 24 for (int i = 1; i < size; ++i) {
78 12 displs[i] = displs[i - 1] + counts[i - 1];
79 }
80 }
81 24 }
82
83 } // namespace
84
85
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 std::vector<Point> RedkinaAGrahamApproachMPI::GrahamScan(std::vector<Point> points) {
86
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 if (points.size() < 3) {
87 return points;
88 }
89
90 12 const Point pivot = FindPivotPoint(points);
91
6/10
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 6 times.
✓ Branch 3 taken 2 times.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✓ Branch 8 taken 6 times.
✓ Branch 9 taken 20 times.
 52 std::erase_if(points, [&pivot](const Point &p) { return ArePointsEqual(p, pivot); });
92
93
3/24
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 14 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 2 times.
✓ Branch 23 taken 14 times.
 30 std::ranges::sort(points, [&pivot](const Point &a, const Point &b) { return ComparePolarAngle(pivot, a, b); });
94
95
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 std::vector<Point> hull;
96
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 hull.reserve(points.size() + 1);
97 hull.push_back(pivot);
98 hull.push_back(points[0]);
99 hull.push_back(points[1]);
100
101
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 12 times.
 16 for (std::size_t i = 2; i < points.size(); ++i) {
102
4/4
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 4 times.
✓ Branch 3 taken 2 times.
 8 while (hull.size() >= 2 && CalcCross(hull[hull.size() - 2], hull.back(), points[i]) <= 0) {
103 hull.pop_back();
104 }
105 hull.push_back(points[i]);
106 }
107
108 return hull;
109 }
110
111 24 std::vector<Point> RedkinaAGrahamApproachMPI::ComputeFinalHull(int rank, std::vector<Point> &all_hull_points) {
112
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
 24 if (rank != 0) {
113 12 return {};
114 }
115
116
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 if (all_hull_points.size() >= 3) {
117
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 24 return GrahamScan(std::move(all_hull_points));
118 }
119
120 return std::move(all_hull_points);
121 }
122
123 24 bool RedkinaAGrahamApproachMPI::RunImpl() {
124 24 int rank{};
125 24 int size{};
126
127 24 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
128 24 MPI_Comm_size(MPI_COMM_WORLD, &size);
129
130 24 std::vector<Point> a_points;
131 24 int n = 0;
132
133
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
 24 if (rank == 0) {
134
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 a_points = GetInput();
135 12 n = static_cast<int>(a_points.size());
136 }
137
138
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
139
140
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (n < 3) {
141 ✗ GetOutput() = (rank == 0 ? a_points : std::vector<Point>{});
142 ✗ return true;
143 }
144
145
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 MPI_Datatype p_type = MPI_DATATYPE_NULL;
146 CreateMpiPointType(&p_type);
147
148 24 const int base = n / size;
149 24 const int rem = n % size;
150
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 16 times.
 24 const int l_size = (rank < rem) ? (base + 1) : base;
151
152
1/4
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 24 std::vector<Point> l_points(l_size);
153
154
1/4
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 24 std::vector<int> counts(size);
155
1/4
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 24 std::vector<int> displs(size);
156 24 InitCountsAndDispls(rank, size, n, counts, displs);
157
158
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 ScatterPointData(rank, a_points, l_points, counts, displs, p_type);
159
160
2/8
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 6 taken 24 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
 48 std::vector<Point> l_hull = (l_size >= 3) ? GrahamScan(std::move(l_points)) : std::move(l_points);
161
162 24 int l_count = static_cast<int>(l_hull.size());
163
164
1/4
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 24 std::vector<int> r_counts(size);
165
1/4
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 24 std::vector<int> r_displs(size);
166
167
3/4
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
✓ Branch 3 taken 24 times.
✗ Branch 4 not taken.
 36 MPI_Gather(&l_count, 1, MPI_INT, rank == 0 ? r_counts.data() : nullptr, 1, MPI_INT, 0, MPI_COMM_WORLD);
168
169 int total = 0;
170
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
 24 if (rank == 0) {
171
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 12 times.
 36 for (int i = 0; i < size; ++i) {
172
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
 24 r_displs[i] = (i == 0) ? 0 : r_displs[i - 1] + r_counts[i - 1];
173 24 total += r_counts[i];
174 }
175 }
176
177
1/4
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 24 std::vector<Point> a_hull_points(total);
178
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 GatherLocalHulls(rank, l_hull, a_hull_points, r_counts, r_displs, p_type);
179
180
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 std::vector<Point> f_hull = ComputeFinalHull(rank, a_hull_points);
181
182
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 BroadcastHull(rank, f_hull, p_type);
183
184 GetOutput() = std::move(f_hull);
185
186
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 MPI_Type_free(&p_type);
187 return true;
188 }
189
190 24 bool RedkinaAGrahamApproachMPI::PostProcessingImpl() {
191 24 return true;
192 }
193
194 } // namespace redkina_a_graham_approach
195