GCC Code Coverage Report

Directory: ./
File: tasks/egorova_l_binary_convex_hull/tbb/src/ops_tbb.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 85 86 98.8%
Functions: 11 11 100.0%
Branches: 81 116 69.8%
Line Branch Exec Source
1 #include "egorova_l_binary_convex_hull/tbb/include/ops_tbb.hpp"
2
3 #include <tbb/tbb.h>
4
5 #include <algorithm>
6 #include <array>
7 #include <cstddef>
8 #include <cstdint>
9 #include <cstdlib>
10 #include <mutex>
11 #include <tuple>
12 #include <utility>
13 #include <vector>
14
15 #include "egorova_l_binary_convex_hull/common/include/common.hpp"
16 #include "oneapi/tbb/blocked_range2d.h"
17 #include "oneapi/tbb/parallel_for.h"
18
19 namespace egorova_l_binary_convex_hull {
20
21 namespace {
22
23 336 void ProcessNeighbours(const std::vector<uint8_t> &data, std::vector<int> &labels, std::vector<int> &queue, int cx,
24 int cy, int width, int height, int label) {
25 336 const std::array<int, 4> dx = {1, -1, 0, 0};
26 336 const std::array<int, 4> dy = {0, 0, 1, -1};
27
2/2
✓ Branch 0 taken 1344 times.
✓ Branch 1 taken 336 times.
 1680 for (int di = 0; di < 4; ++di) {
28 1344 const int nx = cx + dx.at(static_cast<std::size_t>(di));
29 1344 const int ny = cy + dy.at(static_cast<std::size_t>(di));
30
2/4
✓ Branch 0 taken 1344 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 1344 times.
 1344 if (nx < 0 || nx >= width || ny < 0 || ny >= height) {
31 ✗ continue;
32 }
33 1344 const int nidx = (ny * width) + nx;
34
4/4
✓ Branch 0 taken 848 times.
✓ Branch 1 taken 496 times.
✓ Branch 2 taken 296 times.
✓ Branch 3 taken 552 times.
 1344 if (data[static_cast<std::size_t>(nidx)] != 0 && labels[nidx] == -1) {
35
1/2
✓ Branch 0 taken 296 times.
✗ Branch 1 not taken.
 296 labels[nidx] = label;
36 queue.push_back(nidx);
37 }
38 }
39 336 }
40
41 32 std::vector<int> LabelComponents(const std::vector<uint8_t> &data, int width, int height, int &num_components) {
42 32 const int n = width * height;
43 32 std::vector<int> labels(n, -1);
44 32 num_components = 0;
45
46 32 std::vector<int> queue;
47
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 queue.reserve(static_cast<std::size_t>(n));
48
49
2/2
✓ Branch 0 taken 8100 times.
✓ Branch 1 taken 32 times.
 8132 for (int start = 0; start < n; ++start) {
50
4/4
✓ Branch 0 taken 336 times.
✓ Branch 1 taken 7764 times.
✓ Branch 2 taken 296 times.
✓ Branch 3 taken 40 times.
 8100 if (data[static_cast<std::size_t>(start)] == 0 || labels[start] != -1) {
51 8060 continue;
52 }
53 40 const int label = num_components++;
54
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 28 times.
 40 labels[start] = label;
55 queue.clear();
56 queue.push_back(start);
57
58
2/2
✓ Branch 0 taken 336 times.
✓ Branch 1 taken 40 times.
 376 for (std::size_t qi = 0; qi < queue.size(); ++qi) {
59 336 const int cur = queue[qi];
60 336 const int cx = cur % width;
61 336 const int cy = cur / width;
62
1/2
✓ Branch 1 taken 336 times.
✗ Branch 2 not taken.
 336 ProcessNeighbours(data, labels, queue, cx, cy, width, height, label);
63 }
64 }
65 32 return labels;
66 }
67
68 int64_t Cross(const Point &o, const Point &a, const Point &b) {
69
2/2
✓ Branch 0 taken 140 times.
✓ Branch 1 taken 224 times.
 364 return (static_cast<int64_t>(a.x - o.x) * (b.y - o.y)) - (static_cast<int64_t>(a.y - o.y) * (b.x - o.x));
70 }
71
72 40 std::vector<Point> ConvexHull(std::vector<Point> pts) {
73 std::ranges::sort(pts,
74 [](const Point &lhs, const Point &rhs) { return std::tie(lhs.x, lhs.y) < std::tie(rhs.x, rhs.y); });
75 pts.erase(std::ranges::unique(pts,
76 [](const Point &lhs, const Point &rhs) {
77
3/8
✓ Branch 0 taken 208 times.
✓ Branch 1 taken 88 times.
✓ Branch 2 taken 208 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 296 return lhs.x == rhs.x && lhs.y == rhs.y;
78 }).begin(),
79 pts.end());
80
81
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 40 times.
 40 if (pts.size() < 3) {
82 return pts;
83 }
84
85
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 std::vector<Point> hull;
86
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 hull.reserve(2 * pts.size());
87
88
2/2
✓ Branch 0 taken 336 times.
✓ Branch 1 taken 40 times.
 376 for (const auto &p : pts) {
89
4/4
✓ Branch 0 taken 356 times.
✓ Branch 1 taken 208 times.
✓ Branch 2 taken 228 times.
✓ Branch 3 taken 128 times.
 564 while (hull.size() >= 2 && Cross(hull[hull.size() - 2], hull.back(), p) <= 0) {
90 hull.pop_back();
91 }
92 hull.push_back(p);
93 }
94
95 40 const std::size_t lower_size = hull.size() + 1;
96
2/2
✓ Branch 0 taken 296 times.
✓ Branch 1 taken 40 times.
 336 for (int i = static_cast<int>(pts.size()) - 2; i >= 0; --i) {
97
4/4
✓ Branch 0 taken 364 times.
✓ Branch 1 taken 156 times.
✓ Branch 2 taken 140 times.
✓ Branch 3 taken 224 times.
 520 while (hull.size() >= lower_size && Cross(hull[hull.size() - 2], hull.back(), pts[i]) <= 0) {
98 hull.pop_back();
99 }
100
1/2
✓ Branch 0 taken 296 times.
✗ Branch 1 not taken.
 296 hull.push_back(pts[i]);
101 }
102
103 hull.pop_back();
104 return hull;
105 }
106
107 4787 void CollectPoints(const std::vector<int> &labels, int num_components, int width,
108 std::vector<std::vector<Point>> &component_points, std::vector<std::mutex> &mutexes,
109 const tbb::blocked_range2d<int> &r) {
110 4787 std::vector<std::vector<Point>> local(static_cast<std::size_t>(num_components));
111
2/2
✓ Branch 0 taken 5701 times.
✓ Branch 1 taken 4787 times.
 10488 for (int row = r.rows().begin(); row < r.rows().end(); ++row) {
112
2/2
✓ Branch 0 taken 7700 times.
✓ Branch 1 taken 5701 times.
 13401 for (int col = r.cols().begin(); col < r.cols().end(); ++col) {
113 7700 const int idx = (row * width) + col;
114
2/2
✓ Branch 0 taken 336 times.
✓ Branch 1 taken 7364 times.
 7700 const int lbl = labels[static_cast<std::size_t>(idx)];
115
2/2
✓ Branch 0 taken 336 times.
✓ Branch 1 taken 7364 times.
 7700 if (lbl >= 0) {
116
1/2
✓ Branch 1 taken 336 times.
✗ Branch 2 not taken.
 336 local[static_cast<std::size_t>(lbl)].push_back({col, row});
117 }
118 }
119 }
120
2/2
✓ Branch 0 taken 8264 times.
✓ Branch 1 taken 4787 times.
 13051 for (int ci = 0; ci < num_components; ++ci) {
121
2/2
✓ Branch 0 taken 256 times.
✓ Branch 1 taken 8008 times.
 8264 auto &bucket = local[static_cast<std::size_t>(ci)];
122
2/2
✓ Branch 0 taken 256 times.
✓ Branch 1 taken 8008 times.
 8264 if (!bucket.empty()) {
123 std::scoped_lock lock(mutexes[static_cast<std::size_t>(ci)]);
124 auto &dst = component_points[static_cast<std::size_t>(ci)];
125 256 dst.insert(dst.end(), bucket.begin(), bucket.end());
126 }
127 }
128 4787 }
129
130 } // namespace
131
132
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 BinaryConvexHullTBB::BinaryConvexHullTBB(const InType &in) {
133 SetTypeOfTask(GetStaticTypeOfTask());
134 GetInput() = in;
135 32 }
136
137 32 bool BinaryConvexHullTBB::ValidationImpl() {
138 const auto &img = GetInput();
139
2/4
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 32 times.
✗ Branch 3 not taken.
 32 if (img.width <= 0 || img.height <= 0) {
140 return false;
141 }
142 32 const std::size_t expected = static_cast<std::size_t>(img.width) * static_cast<std::size_t>(img.height);
143 32 return img.data.size() == expected;
144 }
145
146
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.
 32 bool BinaryConvexHullTBB::PreProcessingImpl() {
147 GetOutput().clear();
148 32 return true;
149 }
150
151 32 bool BinaryConvexHullTBB::RunImpl() {
152 const auto &img = GetInput();
153 32 const int width = img.width;
154 32 const int height = img.height;
155
156 32 int num_components = 0;
157 32 const std::vector<int> labels = LabelComponents(img.data, width, height, num_components);
158
159
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 28 times.
 32 if (num_components == 0) {
160 GetOutput().clear();
161 4 return true;
162 }
163
164
1/4
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 28 std::vector<std::vector<Point>> component_points(static_cast<std::size_t>(num_components));
165
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 std::vector<std::mutex> mutexes(static_cast<std::size_t>(num_components));
166
167
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 tbb::parallel_for(tbb::blocked_range2d<int>(0, height, 0, width), [&](const tbb::blocked_range2d<int> &r) {
168 4787 CollectPoints(labels, num_components, width, component_points, mutexes, r);
169 4787 });
170
171
1/4
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 28 std::vector<std::vector<Point>> hulls(static_cast<std::size_t>(num_components));
172
173
2/4
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 28 times.
 28 tbb::parallel_for(0, num_components, [&](int ci) {
174
1/2
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
 40 auto &pts = component_points[static_cast<std::size_t>(ci)];
175
1/2
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
 40 if (!pts.empty()) {
176
1/2
✓ Branch 2 taken 40 times.
✗ Branch 3 not taken.
 80 hulls[static_cast<std::size_t>(ci)] = ConvexHull(pts);
177 }
178 40 });
179
180 GetOutput().clear();
181
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 28 times.
 68 for (auto &h : hulls) {
182
1/2
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
 40 if (!h.empty()) {
183 GetOutput().push_back(std::move(h));
184 }
185 }
186
187 return true;
188 56 }
189
190
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 28 times.
 32 bool BinaryConvexHullTBB::PostProcessingImpl() {
191
4/6
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 4 times.
✓ Branch 4 taken 4 times.
✗ Branch 5 not taken.
 32 return !GetOutput().empty() || GetInput().data.empty() ||
192 32 std::all_of(GetInput().data.begin(), GetInput().data.end(), [](uint8_t v) { return v == 0; });
193 }
194
195 } // namespace egorova_l_binary_convex_hull
196