GCC Code Coverage Report

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