GCC Code Coverage Report

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