GCC Code Coverage Report

Directory: ./
File: tasks/perepelkin_i_convex_hull_graham_scan/omp/src/ops_omp.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 61 65 93.8%
Functions: 9 11 81.8%
Branches: 47 86 54.7%
Line Branch Exec Source
1 #include "perepelkin_i_convex_hull_graham_scan/omp/include/ops_omp.hpp"
2
3 #include <omp.h>
4
5 #include <algorithm>
6 #include <cmath>
7 #include <cstddef>
8 #include <utility>
9 #include <vector>
10
11 #include "perepelkin_i_convex_hull_graham_scan/common/include/common.hpp"
12 #include "util/include/util.hpp"
13
14 namespace perepelkin_i_convex_hull_graham_scan {
15
16
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 PerepelkinIConvexHullGrahamScanOMP::PerepelkinIConvexHullGrahamScanOMP(const InType &in) {
17 SetTypeOfTask(GetStaticTypeOfTask());
18
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 GetInput() = in;
19 48 GetOutput() = std::vector<std::pair<double, double>>();
20 48 }
21
22 48 bool PerepelkinIConvexHullGrahamScanOMP::ValidationImpl() {
23 48 return GetOutput().empty();
24 }
25
26 48 bool PerepelkinIConvexHullGrahamScanOMP::PreProcessingImpl() {
27 48 return true;
28 }
29
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 40 times.
 48 bool PerepelkinIConvexHullGrahamScanOMP::RunImpl() {
30 const auto &data = GetInput();
31
32
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 40 times.
 48 if (data.size() < 2) {
33 8 GetOutput() = data;
34 8 return true;
35 }
36
37 40 std::vector<std::pair<double, double>> pts = data;
38
39 // Find pivot
40
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 size_t pivot_idx = FindPivotParallel(pts);
41
42 std::pair<double, double> pivot = pts[pivot_idx];
43 pts.erase(pts.begin() + static_cast<std::ptrdiff_t>(pivot_idx));
44
45 // Parallel sorting
46
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 ParallelSort(pts, pivot);
47
48 // Sequential hull construction
49 40 std::vector<std::pair<double, double>> hull;
50
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 HullConstruction(hull, pts, pivot);
51
52 GetOutput() = std::move(hull);
53 return true;
54 }
55
56 40 size_t PerepelkinIConvexHullGrahamScanOMP::FindPivotParallel(const std::vector<std::pair<double, double>> &pts) {
57 40 const int threads = std::min(ppc::util::GetNumThreads(), static_cast<int>(pts.size()));
58 40 std::vector<size_t> local_idx(threads, 0);
59
60 40 #pragma omp parallel default(none) shared(pts, local_idx) num_threads(threads)
61 {
62 int tid = omp_get_thread_num();
63 size_t local = 0;
64
65 #pragma omp for nowait
66 for (size_t i = 1; i < pts.size(); i++) {
67 if (pts[i].second < pts[local].second ||
68 (pts[i].second == pts[local].second && pts[i].first < pts[local].first)) {
69 local = i;
70 }
71 }
72
73 local_idx[tid] = local;
74 }
75
76 // Sequential reduction
77 size_t pivot_idx = 0;
78
79
2/2
✓ Branch 0 taken 97 times.
✓ Branch 1 taken 40 times.
 137 for (int tid = 0; tid < threads; tid++) {
80
2/2
✓ Branch 0 taken 73 times.
✓ Branch 1 taken 24 times.
 97 size_t i = local_idx[tid];
81
82
4/4
✓ Branch 0 taken 73 times.
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 58 times.
✓ Branch 3 taken 15 times.
 97 if (pts[i].second < pts[pivot_idx].second ||
83
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 48 times.
 58 (pts[i].second == pts[pivot_idx].second && pts[i].first < pts[pivot_idx].first)) {
84 pivot_idx = i;
85 }
86 }
87
88 40 return pivot_idx;
89 }
90
91 40 void PerepelkinIConvexHullGrahamScanOMP::ParallelSort(std::vector<std::pair<double, double>> &data,
92 const std::pair<double, double> &pivot) {
93 40 const int threads = std::min(ppc::util::GetNumThreads(), static_cast<int>(data.size()));
94
95 // Partitioning
96 40 std::vector<int> start(threads + 1);
97 DataPartitioning(data.size(), threads, start);
98
99 // Parallel local sorting
100 40 #pragma omp parallel default(none) shared(data, start, pivot) num_threads(threads)
101 {
102 int tid = omp_get_thread_num();
103 std::sort(data.begin() + start[tid], data.begin() + start[tid + 1],
104
4/24
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 28 times.
✓ Branch 5 taken 58 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 18 times.
✓ Branch 23 taken 58 times.
 162 [&](const auto &a, const auto &b) { return AngleCmp(a, b, pivot); });
105 }
106
107 // Merge sorted segments
108
2/2
✓ Branch 0 taken 45 times.
✓ Branch 1 taken 40 times.
 85 for (int size = 1; size < threads; size *= 2) {
109 45 #pragma omp parallel for default(none) shared(data, start, threads, size, pivot) num_threads(threads)
110 for (int i = 0; i < threads; i += 2 * size) {
111 if (i + size >= threads) {
112 continue;
113 }
114
115 int left = start[i];
116 int mid = start[i + size];
117 int right = start[std::min(i + (2 * size), threads)];
118
119 std::inplace_merge(data.begin() + left, data.begin() + mid, data.begin() + right,
120
4/10
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 20 times.
✓ Branch 5 taken 24 times.
✓ Branch 6 taken 28 times.
✓ Branch 7 taken 39 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
 111 [&](const auto &a, const auto &b) { return AngleCmp(a, b, pivot); });
121 }
122 }
123 40 }
124
125 ✗ void PerepelkinIConvexHullGrahamScanOMP::DataPartitioning(size_t total_size, const int &threads,
126 std::vector<int> &start) {
127 40 size_t base = total_size / threads;
128 40 size_t rem = total_size % threads;
129
130 size_t offset = 0;
131
132
2/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 92 times.
✓ Branch 3 taken 40 times.
 132 for (int i = 0; i < threads; i++) {
133
2/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 14 times.
✓ Branch 3 taken 78 times.
 92 start[i] = static_cast<int>(offset);
134
135 size_t extra = std::cmp_less(i, rem) ? 1 : 0;
136 92 offset += base + extra;
137 }
138
139 40 start[threads] = static_cast<int>(total_size);
140 ✗ }
141
142 40 void PerepelkinIConvexHullGrahamScanOMP::HullConstruction(std::vector<std::pair<double, double>> &hull,
143 const std::vector<std::pair<double, double>> &pts,
144 const std::pair<double, double> &pivot) {
145 40 hull.reserve(pts.size() + 1);
146
147 hull.push_back(pivot);
148 hull.push_back(pts[0]);
149
150
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 40 times.
 168 for (size_t i = 1; i < pts.size(); i++) {
151
4/4
✓ Branch 0 taken 168 times.
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 40 times.
✓ Branch 3 taken 104 times.
 336 while (hull.size() >= 2 && Orientation(hull[hull.size() - 2], hull[hull.size() - 1], pts[i]) <= 0) {
152 hull.pop_back();
153 }
154
155 hull.push_back(pts[i]);
156 }
157 40 }
158
159 ✗ double PerepelkinIConvexHullGrahamScanOMP::Orientation(const std::pair<double, double> &p,
160 const std::pair<double, double> &q,
161 const std::pair<double, double> &r) {
162
2/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 24 times.
✓ Branch 3 taken 144 times.
 168 double val = ((q.first - p.first) * (r.second - p.second)) - ((q.second - p.second) * (r.first - p.first));
163
164
2/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 24 times.
✓ Branch 3 taken 144 times.
 168 if (std::abs(val) < 1e-9) {
165 ✗ return 0.0;
166 }
167
168 return val;
169 }
170
171 273 bool PerepelkinIConvexHullGrahamScanOMP::AngleCmp(const std::pair<double, double> &a,
172 const std::pair<double, double> &b,
173 const std::pair<double, double> &pivot) {
174 273 double dx1 = a.first - pivot.first;
175 273 double dy1 = a.second - pivot.second;
176 273 double dx2 = b.first - pivot.first;
177 273 double dy2 = b.second - pivot.second;
178
179
2/2
✓ Branch 0 taken 61 times.
✓ Branch 1 taken 212 times.
 273 double cross = (dx1 * dy2) - (dy1 * dx2);
180
181
2/2
✓ Branch 0 taken 61 times.
✓ Branch 1 taken 212 times.
 273 if (std::abs(cross) < 1e-9) {
182 61 double dist1 = (dx1 * dx1) + (dy1 * dy1);
183 61 double dist2 = (dx2 * dx2) + (dy2 * dy2);
184 61 return dist1 < dist2;
185 }
186
187 212 return cross > 0;
188 }
189
190 48 bool PerepelkinIConvexHullGrahamScanOMP::PostProcessingImpl() {
191 48 return true;
192 }
193
194 } // namespace perepelkin_i_convex_hull_graham_scan
195