GCC Code Coverage Report

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