GCC Code Coverage Report

Directory: ./
File: tasks/gaivoronskiy_m_marking_binary_components/tbb/src/ops_tbb.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 226 230 98.3%
Functions: 32 32 100.0%
Branches: 169 238 71.0%
Line Branch Exec Source
1 #include "gaivoronskiy_m_marking_binary_components/tbb/include/ops_tbb.hpp"
2
3 #include <tbb/blocked_range.h>
4 #include <tbb/parallel_for.h>
5 #include <tbb/task_arena.h>
6
7 #include <algorithm>
8 #include <array>
9 #include <cstddef>
10 #include <limits>
11 #include <numeric>
12 #include <utility>
13 #include <vector>
14
15 #include "gaivoronskiy_m_marking_binary_components/common/include/common.hpp"
16 #include "util/include/util.hpp"
17
18 namespace gaivoronskiy_m_marking_binary_components {
19
20
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 GaivoronskiyMMarkingBinaryComponentsTBB::GaivoronskiyMMarkingBinaryComponentsTBB(const InType &in) {
21 SetTypeOfTask(GetStaticTypeOfTask());
22
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 GetInput() = in;
23 GetOutput() = {};
24 24 }
25
26
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 bool GaivoronskiyMMarkingBinaryComponentsTBB::ValidationImpl() {
27 const auto &input = GetInput();
28
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 if (input.size() < 2) {
29 return false;
30 }
31 24 int rows = input[0];
32 24 int cols = input[1];
33
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 if (rows <= 0 || cols <= 0) {
34 return false;
35 }
36 24 return static_cast<int>(input.size()) == (rows * cols) + 2;
37 }
38
39 24 bool GaivoronskiyMMarkingBinaryComponentsTBB::PreProcessingImpl() {
40 const auto &input = GetInput();
41 24 int rows = input[0];
42 24 int cols = input[1];
43 24 GetOutput().assign((static_cast<std::size_t>(rows) * static_cast<std::size_t>(cols)) + 2, 0);
44 24 GetOutput()[0] = rows;
45 24 GetOutput()[1] = cols;
46 24 return true;
47 }
48
49 namespace {
50
51 constexpr std::array<int, 4> kDx = {-1, 1, 0, 0};
52 constexpr std::array<int, 4> kDy = {0, 0, -1, 1};
53
54 8 void BfsLabelFull(const InType &input, OutType &output, int rows, int cols, int start_row, int start_col, int label) {
55 8 std::vector<std::pair<int, int>> queue;
56
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 queue.reserve(64);
57 std::size_t head = 0;
58
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 queue.emplace_back(start_row, start_col);
59 8 output[(start_row * cols) + start_col + 2] = label;
60
61
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 8 times.
 28 while (head < queue.size()) {
62 20 const auto [cx, cy] = queue[head++];
63
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 20 times.
 100 for (std::size_t dir = 0; dir < 4; dir++) {
64 80 const int nx = cx + kDx.at(dir);
65 80 const int ny = cy + kDy.at(dir);
66
8/8
✓ Branch 0 taken 70 times.
✓ Branch 1 taken 10 times.
✓ Branch 2 taken 61 times.
✓ Branch 3 taken 9 times.
✓ Branch 4 taken 52 times.
✓ Branch 5 taken 9 times.
✓ Branch 6 taken 6 times.
✓ Branch 7 taken 46 times.
 80 if (nx < 0 || nx >= rows || ny < 0 || ny >= cols) {
67 34 continue;
68 }
69 46 const int nidx = (nx * cols) + ny + 2;
70
4/4
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 20 times.
✓ Branch 2 taken 12 times.
✓ Branch 3 taken 14 times.
 46 if (input[nidx] == 0 && output[nidx] == 0) {
71 12 output[nidx] = label;
72
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 queue.emplace_back(nx, ny);
73 }
74 }
75 }
76 8 }
77
78 36 void BfsLabelInStrip(const InType &input, OutType &output, int cols, int r_begin, int r_end, int start_row,
79 int start_col, int label) {
80 36 std::vector<std::pair<int, int>> queue;
81
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 36 queue.reserve(64);
82 std::size_t head = 0;
83
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 36 queue.emplace_back(start_row, start_col);
84 36 output[(start_row * cols) + start_col + 2] = label;
85
86
2/2
✓ Branch 0 taken 68 times.
✓ Branch 1 taken 36 times.
 104 while (head < queue.size()) {
87 68 const auto [cx, cy] = queue[head++];
88
2/2
✓ Branch 0 taken 272 times.
✓ Branch 1 taken 68 times.
 340 for (std::size_t dir = 0; dir < 4; dir++) {
89 272 const int nx = cx + kDx.at(dir);
90 272 const int ny = cy + kDy.at(dir);
91
8/8
✓ Branch 0 taken 211 times.
✓ Branch 1 taken 61 times.
✓ Branch 2 taken 144 times.
✓ Branch 3 taken 67 times.
✓ Branch 4 taken 113 times.
✓ Branch 5 taken 31 times.
✓ Branch 6 taken 22 times.
✓ Branch 7 taken 91 times.
 272 if (nx < r_begin || nx >= r_end || ny < 0 || ny >= cols) {
92 181 continue;
93 }
94 91 const int nidx = (nx * cols) + ny + 2;
95
4/4
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 27 times.
✓ Branch 2 taken 32 times.
✓ Branch 3 taken 32 times.
 91 if (input[nidx] == 0 && output[nidx] == 0) {
96 32 output[nidx] = label;
97
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 queue.emplace_back(nx, ny);
98 }
99 }
100 }
101 36 }
102
103 5 void RunSequentialMarking(const InType &input, OutType &output, int rows, int cols) {
104 int label = 0;
105
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 5 times.
 18 for (int row = 0; row < rows; row++) {
106
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 13 times.
 53 for (int col = 0; col < cols; col++) {
107 40 const int idx = (row * cols) + col + 2;
108
4/4
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 20 times.
✓ Branch 2 taken 12 times.
✓ Branch 3 taken 8 times.
 40 if (input[idx] != 0 || output[idx] != 0) {
109 32 continue;
110 }
111 8 label++;
112 8 BfsLabelFull(input, output, rows, cols, row, col, label);
113 }
114 }
115 5 }
116
117 int FindRoot(std::vector<int> &parent, int x) {
118 int root = x;
119
6/6
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 36 times.
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 15 times.
✓ Branch 4 taken 5 times.
✓ Branch 5 taken 15 times.
 83 while (parent[static_cast<std::size_t>(root)] != root) {
120 root = parent[static_cast<std::size_t>(root)];
121 }
122
6/6
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 36 times.
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 15 times.
✓ Branch 4 taken 5 times.
✓ Branch 5 taken 15 times.
 83 while (parent[static_cast<std::size_t>(x)] != x) {
123 const int p = parent[static_cast<std::size_t>(x)];
124 17 parent[static_cast<std::size_t>(x)] = root;
125 x = p;
126 }
127 return root;
128 }
129
130 15 void UniteLabels(std::vector<int> &parent, int a, int b) {
131 a = FindRoot(parent, a);
132 b = FindRoot(parent, b);
133
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 5 times.
 15 if (a == b) {
134 return;
135 }
136
1/2
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
 10 if (a < b) {
137 10 parent[static_cast<std::size_t>(b)] = a;
138 } else {
139 ✗ parent[static_cast<std::size_t>(a)] = b;
140 }
141 }
142
143 int NumThreadsForRows(int rows) {
144 24 const int capped = std::max(ppc::util::GetNumThreads(), 1);
145 return std::min(capped, rows);
146 }
147
148 19 std::vector<int> MakeRowStarts(int rows, int num_threads) {
149 19 std::vector<int> row_starts(static_cast<std::size_t>(num_threads) + 1);
150
2/2
✓ Branch 0 taken 63 times.
✓ Branch 1 taken 19 times.
 82 for (int thread_idx = 0; thread_idx <= num_threads; thread_idx++) {
151 63 row_starts[static_cast<std::size_t>(thread_idx)] = (thread_idx * rows) / num_threads;
152 }
153 19 return row_starts;
154 }
155
156 44 int LabelSingleStrip(const InType &input, OutType &output, int cols, int r_begin, int r_end) {
157
1/2
✓ Branch 0 taken 44 times.
✗ Branch 1 not taken.
 44 if (r_begin >= r_end) {
158 return 0;
159 }
160
161 int next_label = 0;
162
2/2
✓ Branch 0 taken 47 times.
✓ Branch 1 taken 44 times.
 91 for (int row = r_begin; row < r_end; row++) {
163
2/2
✓ Branch 0 taken 140 times.
✓ Branch 1 taken 47 times.
 187 for (int col = 0; col < cols; col++) {
164 140 const int idx = (row * cols) + col + 2;
165
4/4
✓ Branch 0 taken 68 times.
✓ Branch 1 taken 72 times.
✓ Branch 2 taken 32 times.
✓ Branch 3 taken 36 times.
 140 if (input[idx] != 0 || output[idx] != 0) {
166 104 continue;
167 }
168 36 next_label++;
169 36 BfsLabelInStrip(input, output, cols, r_begin, r_end, row, col, next_label);
170 }
171 }
172 return next_label;
173 }
174
175 44 void LabelStripsRange(const InType &input, OutType &output, int cols, const std::vector<int> &row_starts,
176 std::vector<int> &labels_used, int begin_tid, int end_tid) {
177
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 44 times.
 88 for (int tid = begin_tid; tid < end_tid; ++tid) {
178 44 const int r_begin = row_starts[static_cast<std::size_t>(tid)];
179 44 const int r_end = row_starts[static_cast<std::size_t>(tid) + 1];
180 44 labels_used[static_cast<std::size_t>(tid)] = LabelSingleStrip(input, output, cols, r_begin, r_end);
181 }
182 44 }
183
184 19 void ParallelLabelStrips(const InType &input, OutType &output, int cols, int num_threads,
185 const std::vector<int> &row_starts, std::vector<int> &labels_used) {
186
1/2
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
 19 tbb::task_arena arena(num_threads);
187
1/2
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
 19 arena.execute([&] {
188 63 tbb::parallel_for(tbb::blocked_range<int>(0, num_threads), [&](const tbb::blocked_range<int> &range) {
189 44 LabelStripsRange(input, output, cols, row_starts, labels_used, range.begin(), range.end());
190 44 });
191 19 });
192 19 }
193
194 19 std::pair<std::vector<int>, int> BuildLabelBases(const std::vector<int> &labels_used, int num_threads) {
195 19 std::vector<int> base(static_cast<std::size_t>(num_threads), 0);
196 int sum = 0;
197
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 19 times.
 63 for (int thread_idx = 0; thread_idx < num_threads; thread_idx++) {
198 44 base[static_cast<std::size_t>(thread_idx)] = sum;
199 44 sum += labels_used[static_cast<std::size_t>(thread_idx)];
200 }
201 19 return {base, sum};
202 }
203
204 34 void AddStripBaseOffset(int thread_idx, OutType &output, int cols, const std::vector<int> &row_starts,
205 const std::vector<int> &base) {
206
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 14 times.
 34 const int offset = base[static_cast<std::size_t>(thread_idx)];
207
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 14 times.
 34 if (offset == 0) {
208 return;
209 }
210 20 const int r_begin = row_starts[static_cast<std::size_t>(thread_idx)];
211 20 const int r_end = row_starts[static_cast<std::size_t>(thread_idx) + 1U];
212
2/2
✓ Branch 0 taken 23 times.
✓ Branch 1 taken 20 times.
 43 for (int row = r_begin; row < r_end; row++) {
213
2/2
✓ Branch 0 taken 70 times.
✓ Branch 1 taken 23 times.
 93 for (int col = 0; col < cols; col++) {
214 70 const int idx = (row * cols) + col + 2;
215
2/2
✓ Branch 0 taken 34 times.
✓ Branch 1 taken 36 times.
 70 const int lbl = output[idx];
216
2/2
✓ Branch 0 taken 34 times.
✓ Branch 1 taken 36 times.
 70 if (lbl > 0) {
217 34 output[idx] = offset + lbl;
218 }
219 }
220 }
221 }
222
223 void AddBaseOffsets(OutType &output, int cols, int num_threads, const std::vector<int> &row_starts,
224 const std::vector<int> &base) {
225
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 48 tbb::parallel_for(tbb::blocked_range<int>(0, num_threads), [&](const tbb::blocked_range<int> &range) {
226
2/2
✓ Branch 0 taken 34 times.
✓ Branch 1 taken 34 times.
 68 for (int thread_idx = range.begin(); thread_idx < range.end(); ++thread_idx) {
227 34 AddStripBaseOffset(thread_idx, output, cols, row_starts, base);
228 }
229 34 });
230 }
231
232 14 void MergeBoundariesUnionFind(const InType &input, const OutType &output, int rows, int cols, int num_threads,
233 const std::vector<int> &row_starts, std::vector<int> &parent) {
234
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 14 times.
 34 for (int thread_idx = 0; thread_idx + 1 < num_threads; thread_idx++) {
235
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 20 times.
 20 const int boundary_row = row_starts[static_cast<std::size_t>(thread_idx) + 1U];
236
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 20 times.
 20 if (boundary_row <= 0 || boundary_row >= rows) {
237 ✗ continue;
238 }
239 20 const int ra = boundary_row - 1;
240 const int rb = boundary_row;
241
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 20 times.
 80 for (int col = 0; col < cols; col++) {
242 60 const int ia = (ra * cols) + col + 2;
243 60 const int ib = (rb * cols) + col + 2;
244
4/4
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 21 times.
✓ Branch 3 taken 15 times.
 60 if (input[ia] != 0 || input[ib] != 0) {
245 45 continue;
246 }
247 15 const int la = output[ia];
248 15 const int lb = output[ib];
249
1/2
✓ Branch 0 taken 15 times.
✗ Branch 1 not taken.
 15 if (la > 0 && lb > 0) {
250 15 UniteLabels(parent, la, lb);
251 }
252 }
253 }
254 14 }
255
256 14 void FlattenParentForest(std::vector<int> &parent, int max_label) {
257
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 14 times.
 50 for (int label_idx = 1; label_idx <= max_label; label_idx++) {
258 36 parent[static_cast<std::size_t>(label_idx)] = FindRoot(parent, label_idx);
259 }
260 14 }
261
262 14 std::vector<int> BuildRemapFromFirstPositions(const std::vector<int> &first_pos) {
263
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 std::vector<int> roots;
264
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 roots.reserve(first_pos.size());
265
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 14 times.
 50 for (std::size_t root = 1; root < first_pos.size(); root++) {
266
2/2
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 10 times.
 36 if (first_pos[root] != std::numeric_limits<int>::max()) {
267
1/2
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
 26 roots.push_back(static_cast<int>(root));
268 }
269 }
270 std::ranges::sort(roots, [&](int a, int b) {
271
2/22
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ 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 taken 12 times.
✗ Branch 20 not taken.
✓ Branch 21 taken 12 times.
 24 return first_pos[static_cast<std::size_t>(a)] < first_pos[static_cast<std::size_t>(b)];
272 });
273
274
1/4
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 14 std::vector<int> remap(first_pos.size(), 0);
275 int next_final = 1;
276
2/2
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 14 times.
 40 for (int root : roots) {
277 26 remap[static_cast<std::size_t>(root)] = next_final++;
278 }
279 14 return remap;
280 }
281
282 34 void CollectFirstPositionsForRows(const InType &input, const OutType &output, const std::vector<int> &parent, int cols,
283 int row_begin, int row_end, std::vector<int> &local) {
284
2/2
✓ Branch 0 taken 37 times.
✓ Branch 1 taken 34 times.
 71 for (int row = row_begin; row < row_end; row++) {
285
2/2
✓ Branch 0 taken 110 times.
✓ Branch 1 taken 37 times.
 147 for (int col = 0; col < cols; col++) {
286 110 const int idx = (row * cols) + col + 2;
287
2/2
✓ Branch 0 taken 42 times.
✓ Branch 1 taken 68 times.
 110 if (input[idx] != 0) {
288 42 continue;
289 }
290 68 const int lbl = output[idx];
291
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 68 times.
 68 if (lbl <= 0) {
292 ✗ continue;
293 }
294
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 32 times.
 68 const int root = parent[static_cast<std::size_t>(lbl)];
295 68 const int pos = (row * cols) + col;
296
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 32 times.
 104 local[static_cast<std::size_t>(root)] = std::min(local[static_cast<std::size_t>(root)], pos);
297 }
298 }
299 34 }
300
301 34 void CollectFirstPositionsRange(const InType &input, const OutType &output, const std::vector<int> &parent, int rows,
302 int cols, int num_threads, std::vector<std::vector<int>> &thread_first, int begin_tid,
303 int end_tid) {
304
2/2
✓ Branch 0 taken 34 times.
✓ Branch 1 taken 34 times.
 68 for (int tid = begin_tid; tid < end_tid; ++tid) {
305 34 auto &local = thread_first[static_cast<std::size_t>(tid)];
306 34 const int row_begin = (tid * rows) / num_threads;
307 34 const int row_end = ((tid + 1) * rows) / num_threads;
308 34 CollectFirstPositionsForRows(input, output, parent, cols, row_begin, row_end, local);
309 }
310 34 }
311
312 36 void MergeRootFirstPositions(const std::vector<std::vector<int>> &thread_first, int num_threads, int root,
313 std::vector<int> &first_pos) {
314 36 int min_pos = std::numeric_limits<int>::max();
315
2/2
✓ Branch 0 taken 90 times.
✓ Branch 1 taken 36 times.
 126 for (int tid = 0; tid < num_threads; tid++) {
316
2/2
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 64 times.
 116 min_pos = std::min(min_pos, thread_first[static_cast<std::size_t>(tid)][static_cast<std::size_t>(root)]);
317 }
318 36 first_pos[static_cast<std::size_t>(root)] = min_pos;
319 36 }
320
321 14 std::vector<int> ComputeFirstPositionsParallel(const InType &input, const OutType &output,
322 const std::vector<int> &parent, int rows, int cols, int max_label,
323 int num_threads) {
324 std::vector<std::vector<int>> thread_first(
325 static_cast<std::size_t>(num_threads),
326
1/2
✓ Branch 2 taken 14 times.
✗ Branch 3 not taken.
 14 std::vector<int>(static_cast<std::size_t>(max_label) + 1U, std::numeric_limits<int>::max()));
327
328
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 tbb::task_arena arena(num_threads);
329
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 arena.execute([&] {
330 48 tbb::parallel_for(tbb::blocked_range<int>(0, num_threads), [&](const tbb::blocked_range<int> &range) {
331 34 CollectFirstPositionsRange(input, output, parent, rows, cols, num_threads, thread_first, range.begin(),
332 range.end());
333 34 });
334 14 });
335
336
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 std::vector<int> first_pos(static_cast<std::size_t>(max_label) + 1U, std::numeric_limits<int>::max());
337
1/4
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 50 tbb::parallel_for(tbb::blocked_range<int>(1, max_label + 1), [&](const tbb::blocked_range<int> &range) {
338
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 36 times.
 72 for (int root = range.begin(); root < range.end(); ++root) {
339 36 MergeRootFirstPositions(thread_first, num_threads, root, first_pos);
340 }
341 36 });
342 14 return first_pos;
343 14 }
344
345 37 void RemapRow(const InType &input, OutType &output, const std::vector<int> &parent, const std::vector<int> &remap,
346 int row, int cols) {
347
2/2
✓ Branch 0 taken 110 times.
✓ Branch 1 taken 37 times.
 147 for (int col = 0; col < cols; col++) {
348 110 const int idx = (row * cols) + col + 2;
349
2/2
✓ Branch 0 taken 42 times.
✓ Branch 1 taken 68 times.
 110 if (input[idx] != 0) {
350 42 continue;
351 }
352 68 const int lbl = output[idx];
353
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 68 times.
 68 if (lbl <= 0) {
354 ✗ continue;
355 }
356 68 const int root = parent[static_cast<std::size_t>(lbl)];
357 68 output[idx] = remap[static_cast<std::size_t>(root)];
358 }
359 37 }
360
361
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 void ApplyRemapInParallel(const InType &input, OutType &output, const std::vector<int> &parent,
362 const std::vector<int> &remap, int rows, int cols, int num_threads) {
363 tbb::task_arena arena(num_threads);
364
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 arena.execute([&] {
365 51 tbb::parallel_for(tbb::blocked_range<int>(0, rows), [&](const tbb::blocked_range<int> &range) {
366
2/2
✓ Branch 0 taken 37 times.
✓ Branch 1 taken 37 times.
 74 for (int row = range.begin(); row < range.end(); ++row) {
367 37 RemapRow(input, output, parent, remap, row, cols);
368 }
369 37 });
370 14 });
371 14 }
372
373 } // namespace
374
375
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 bool GaivoronskiyMMarkingBinaryComponentsTBB::RunImpl() {
376 const auto &input = GetInput();
377 auto &output = GetOutput();
378 24 const int rows = input[0];
379 24 const int cols = input[1];
380 24 const int cells = rows * cols;
381
382
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 if (cells == 0) {
383 return true;
384 }
385
386 const int num_threads = NumThreadsForRows(rows);
387
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 19 times.
 24 if (num_threads <= 1) {
388 5 RunSequentialMarking(input, output, rows, cols);
389 5 return true;
390 }
391
392 19 const std::vector<int> row_starts = MakeRowStarts(rows, num_threads);
393
1/4
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 19 std::vector<int> labels_used(static_cast<std::size_t>(num_threads), 0);
394
395
1/2
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
 19 ParallelLabelStrips(input, output, cols, num_threads, row_starts, labels_used);
396
397
1/2
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
 19 const auto [base, max_global_before_merge] = BuildLabelBases(labels_used, num_threads);
398
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 5 times.
 19 if (max_global_before_merge == 0) {
399 return true;
400 }
401
402 14 AddBaseOffsets(output, cols, num_threads, row_starts, base);
403
404
1/4
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 14 std::vector<int> parent(static_cast<std::size_t>(max_global_before_merge) + 1U);
405 std::iota(parent.begin() + 1, parent.end(), 1);
406
407 14 MergeBoundariesUnionFind(input, output, rows, cols, num_threads, row_starts, parent);
408 14 FlattenParentForest(parent, max_global_before_merge);
409
410 const std::vector<int> first_pos =
411
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 ComputeFirstPositionsParallel(input, output, parent, rows, cols, max_global_before_merge, num_threads);
412
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 const std::vector<int> remap = BuildRemapFromFirstPositions(first_pos);
413
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 ApplyRemapInParallel(input, output, parent, remap, rows, cols, num_threads);
414
415 return true;
416 }
417
418 24 bool GaivoronskiyMMarkingBinaryComponentsTBB::PostProcessingImpl() {
419 24 return true;
420 }
421
422 } // namespace gaivoronskiy_m_marking_binary_components
423