GCC Code Coverage Report

Directory: ./
File: tasks/gaivoronskiy_m_marking_binary_components/omp/src/ops_omp.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 115 119 96.6%
Functions: 13 13 100.0%
Branches: 90 116 77.6%
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 <queue>
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 24 times.
✗ Branch 2 not taken.
 24 GaivoronskiyMMarkingBinaryComponentsOMP::GaivoronskiyMMarkingBinaryComponentsOMP(const InType &in) {
18 SetTypeOfTask(GetStaticTypeOfTask());
19
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 GetInput() = in;
20 GetOutput() = {};
21 24 }
22
23
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 bool GaivoronskiyMMarkingBinaryComponentsOMP::ValidationImpl() {
24 const auto &input = GetInput();
25
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 if (input.size() < 2) {
26 return false;
27 }
28 24 int rows = input[0];
29 24 int cols = input[1];
30
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 if (rows <= 0 || cols <= 0) {
31 return false;
32 }
33 24 return static_cast<int>(input.size()) == (rows * cols) + 2;
34 }
35
36 24 bool GaivoronskiyMMarkingBinaryComponentsOMP::PreProcessingImpl() {
37 const auto &input = GetInput();
38 24 int rows = input[0];
39 24 int cols = input[1];
40 24 GetOutput().assign((static_cast<std::size_t>(rows) * static_cast<std::size_t>(cols)) + 2, 0);
41 24 GetOutput()[0] = rows;
42 24 GetOutput()[1] = cols;
43 24 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 44 void BfsLabelInStrip(const InType &input, std::vector<int> &local_plane, int cols, int r_begin, int r_end,
52 int start_row, int start_col, int label) {
53 std::queue<std::pair<int, int>> queue;
54 queue.emplace(start_row, start_col);
55 44 local_plane[(start_row * cols) + start_col] = label;
56
57
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 44 times.
 132 while (!queue.empty()) {
58 auto [cx, cy] = queue.front();
59 queue.pop();
60
61
2/2
✓ Branch 0 taken 352 times.
✓ Branch 1 taken 88 times.
 440 for (std::size_t dir = 0; dir < 4; dir++) {
62 352 int nx = cx + kDx.at(dir);
63 352 int ny = cy + kDy.at(dir);
64
8/8
✓ Branch 0 taken 281 times.
✓ Branch 1 taken 71 times.
✓ Branch 2 taken 205 times.
✓ Branch 3 taken 76 times.
✓ Branch 4 taken 165 times.
✓ Branch 5 taken 40 times.
✓ Branch 6 taken 28 times.
✓ Branch 7 taken 137 times.
 352 if (nx < r_begin || nx >= r_end || ny < 0 || ny >= cols) {
65 215 continue;
66 }
67 137 int n_flat = (nx * cols) + ny;
68 137 int nidx = n_flat + 2;
69
4/4
✓ Branch 0 taken 90 times.
✓ Branch 1 taken 47 times.
✓ Branch 2 taken 44 times.
✓ Branch 3 taken 46 times.
 137 if (input[nidx] == 0 && local_plane[n_flat] == 0) {
70
1/2
✓ Branch 1 taken 44 times.
✗ Branch 2 not taken.
 44 local_plane[n_flat] = label;
71 queue.emplace(nx, ny);
72 }
73 }
74 }
75 44 }
76
77 int FindRoot(std::vector<int> &parent, int x) {
78 int root = x;
79
6/6
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 44 times.
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 15 times.
✓ Branch 4 taken 5 times.
✓ Branch 5 taken 15 times.
 91 while (parent[static_cast<std::size_t>(root)] != root) {
80 root = parent[static_cast<std::size_t>(root)];
81 }
82
6/6
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 44 times.
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 15 times.
✓ Branch 4 taken 5 times.
✓ Branch 5 taken 15 times.
 91 while (parent[static_cast<std::size_t>(x)] != x) {
83 int p = parent[static_cast<std::size_t>(x)];
84 17 parent[static_cast<std::size_t>(x)] = root;
85 x = p;
86 }
87 return root;
88 }
89
90 15 void UniteLabels(std::vector<int> &parent, int a, int b) {
91 a = FindRoot(parent, a);
92 b = FindRoot(parent, b);
93
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 5 times.
 15 if (a == b) {
94 return;
95 }
96
1/2
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
 10 if (a < b) {
97 10 parent[static_cast<std::size_t>(b)] = a;
98 } else {
99 ✗ parent[static_cast<std::size_t>(a)] = b;
100 }
101 }
102
103 int NumThreadsForRows(int rows) {
104 24 const int capped = std::max(ppc::util::GetNumThreads(), 1);
105 return std::min(capped, rows);
106 }
107
108 24 std::vector<int> MakeRowStarts(int rows, int num_threads) {
109 24 std::vector<int> row_starts(static_cast<std::size_t>(num_threads) + 1);
110
2/2
✓ Branch 0 taken 73 times.
✓ Branch 1 taken 24 times.
 97 for (int thread_idx = 0; thread_idx <= num_threads; thread_idx++) {
111 73 row_starts[static_cast<std::size_t>(thread_idx)] = (thread_idx * rows) / num_threads;
112 }
113 24 return row_starts;
114 }
115
116 void ParallelLabelStrips(const InType &input, int cols, int num_threads, const std::vector<int> &row_starts,
117 std::vector<std::vector<int>> &local_planes, std::vector<int> &labels_used) {
118 24 #pragma omp parallel num_threads(num_threads) default(none) \
119 shared(input, local_planes, labels_used, row_starts, cols, num_threads)
120 {
121 const int tid = omp_get_thread_num();
122 const int r_begin = row_starts[static_cast<std::size_t>(tid)];
123 const int r_end = row_starts[static_cast<std::size_t>(tid) + 1];
124 int next_label = 0;
125
126 if (r_begin < r_end) {
127 auto &plane = local_planes[static_cast<std::size_t>(tid)];
128 for (int row = r_begin; row < r_end; row++) {
129 for (int col = 0; col < cols; col++) {
130 const int flat = (row * cols) + col;
131 const int idx = flat + 2;
132 if (input[idx] == 0 && plane[static_cast<std::size_t>(flat)] == 0) {
133 next_label++;
134 BfsLabelInStrip(input, plane, cols, r_begin, r_end, row, col, next_label);
135 }
136 }
137 }
138 }
139
140 labels_used[static_cast<std::size_t>(tid)] = next_label;
141 }
142 }
143
144 24 std::pair<std::vector<int>, int> BuildLabelBases(const std::vector<int> &labels_used, int num_threads) {
145 24 std::vector<int> base(static_cast<std::size_t>(num_threads), 0);
146 int sum = 0;
147
2/2
✓ Branch 0 taken 49 times.
✓ Branch 1 taken 24 times.
 73 for (int thread_idx = 0; thread_idx < num_threads; thread_idx++) {
148 49 base[static_cast<std::size_t>(thread_idx)] = sum;
149 49 sum += labels_used[static_cast<std::size_t>(thread_idx)];
150 }
151 24 return {base, sum};
152 }
153
154 18 void CopyStripsToGlobalOutput(OutType &output, int cols, int num_threads, const std::vector<int> &row_starts,
155 const std::vector<int> &base, const std::vector<std::vector<int>> &local_planes) {
156
2/2
✓ Branch 0 taken 38 times.
✓ Branch 1 taken 18 times.
 56 for (int thread_idx = 0; thread_idx < num_threads; thread_idx++) {
157
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 38 times.
 38 const int r_begin = row_starts[static_cast<std::size_t>(thread_idx)];
158 38 const int r_end = row_starts[static_cast<std::size_t>(thread_idx) + 1U];
159
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 38 times.
 38 if (r_begin >= r_end) {
160 ✗ continue;
161 }
162 const auto &plane = local_planes[static_cast<std::size_t>(thread_idx)];
163 38 const int offset = base[static_cast<std::size_t>(thread_idx)];
164
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 38 times.
 86 for (int row = r_begin; row < r_end; row++) {
165
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 48 times.
 192 for (int col = 0; col < cols; col++) {
166 144 const int flat = (row * cols) + col;
167
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 56 times.
 144 const int loc = plane[static_cast<std::size_t>(flat)];
168
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 56 times.
 144 if (loc > 0) {
169 88 output[flat + 2] = offset + loc;
170 }
171 }
172 }
173 }
174 18 }
175
176 18 void MergeBoundariesUnionFind(const InType &input, OutType &output, int rows, int cols, int num_threads,
177 const std::vector<int> &row_starts, std::vector<int> &parent) {
178
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 18 times.
 38 for (int thread_idx = 0; thread_idx + 1 < num_threads; thread_idx++) {
179 const int next_strip = thread_idx + 1;
180
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 20 times.
 20 const int boundary_row = row_starts[static_cast<std::size_t>(next_strip)];
181
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 20 times.
 20 if (boundary_row <= 0 || boundary_row >= rows) {
182 ✗ continue;
183 }
184 20 const int ra = boundary_row - 1;
185 const int rb = boundary_row;
186
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 20 times.
 80 for (int col = 0; col < cols; col++) {
187 60 const int ia = (ra * cols) + col + 2;
188 60 const int ib = (rb * cols) + col + 2;
189
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) {
190 45 continue;
191 }
192 15 const int la = output[ia];
193 15 const int lb = output[ib];
194
1/2
✓ Branch 0 taken 15 times.
✗ Branch 1 not taken.
 15 if (la > 0 && lb > 0) {
195 15 UniteLabels(parent, la, lb);
196 }
197 }
198 }
199 18 }
200
201 18 void FlattenParentForest(std::vector<int> &parent, int max_label) {
202
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 18 times.
 62 for (int label_idx = 1; label_idx <= max_label; label_idx++) {
203 44 parent[static_cast<std::size_t>(label_idx)] = FindRoot(parent, label_idx);
204 }
205 18 }
206
207 18 std::vector<int> BuildFinalRemap(const InType &input, const OutType &output, const std::vector<int> &parent, int rows,
208 int cols, int max_label) {
209 18 std::vector<int> remap(static_cast<std::size_t>(max_label) + 1, 0);
210 int next_final = 1;
211
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 18 times.
 66 for (int row = 0; row < rows; row++) {
212
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 48 times.
 192 for (int col = 0; col < cols; col++) {
213 144 const int idx = (row * cols) + col + 2;
214
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 88 times.
 144 if (input[idx] != 0) {
215 56 continue;
216 }
217 88 const int lbl = output[idx];
218
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 88 times.
 88 if (lbl <= 0) {
219 ✗ continue;
220 }
221
2/2
✓ Branch 0 taken 34 times.
✓ Branch 1 taken 54 times.
 88 const int root = parent[static_cast<std::size_t>(lbl)];
222
2/2
✓ Branch 0 taken 34 times.
✓ Branch 1 taken 54 times.
 88 if (remap[static_cast<std::size_t>(root)] == 0) {
223 34 remap[static_cast<std::size_t>(root)] = next_final++;
224 }
225 }
226 }
227 18 return remap;
228 }
229
230 void ApplyRemapInParallel(const InType &input, OutType &output, const std::vector<int> &parent,
231 const std::vector<int> &remap, int rows, int cols) {
232
1/2
✓ Branch 0 taken 18 times.
✗ Branch 1 not taken.
 18 #pragma omp parallel for default(none) shared(input, output, parent, remap, rows, cols) schedule(static)
233 for (int row = 0; row < rows; row++) {
234 for (int col = 0; col < cols; col++) {
235 const int idx = (row * cols) + col + 2;
236 if (input[idx] != 0) {
237 output[idx] = 0;
238 } else {
239 const int lbl = output[idx];
240 const int root = parent[static_cast<std::size_t>(lbl)];
241 output[idx] = remap[static_cast<std::size_t>(root)];
242 }
243 }
244 }
245 }
246
247 } // namespace
248
249
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 bool GaivoronskiyMMarkingBinaryComponentsOMP::RunImpl() {
250 const auto &input = GetInput();
251 auto &output = GetOutput();
252 24 const int rows = input[0];
253 24 const int cols = input[1];
254 24 const int cells = rows * cols;
255
256
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 if (cells == 0) {
257 return true;
258 }
259
260 const int num_threads = NumThreadsForRows(rows);
261 24 const std::vector<int> row_starts = MakeRowStarts(rows, num_threads);
262
263 std::vector<std::vector<int>> local_planes(static_cast<std::size_t>(num_threads),
264
2/6
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 24 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 24 std::vector<int>(static_cast<std::size_t>(cells), 0));
265
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 std::vector<int> labels_used(static_cast<std::size_t>(num_threads), 0);
266
267 ParallelLabelStrips(input, cols, num_threads, row_starts, local_planes, labels_used);
268
269
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 const auto [base, max_global_before_merge] = BuildLabelBases(labels_used, num_threads);
270
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 6 times.
 24 if (max_global_before_merge == 0) {
271 return true;
272 }
273
274 18 CopyStripsToGlobalOutput(output, cols, num_threads, row_starts, base, local_planes);
275
276
1/4
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 18 std::vector<int> parent(static_cast<std::size_t>(max_global_before_merge) + 1);
277
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 18 times.
 62 for (int label_idx = 1; label_idx <= max_global_before_merge; label_idx++) {
278 44 parent[static_cast<std::size_t>(label_idx)] = label_idx;
279 }
280
281 18 MergeBoundariesUnionFind(input, output, rows, cols, num_threads, row_starts, parent);
282 18 FlattenParentForest(parent, max_global_before_merge);
283
284
1/2
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
 18 const std::vector<int> remap = BuildFinalRemap(input, output, parent, rows, cols, max_global_before_merge);
285 ApplyRemapInParallel(input, output, parent, remap, rows, cols);
286
287 return true;
288 24 }
289
290 24 bool GaivoronskiyMMarkingBinaryComponentsOMP::PostProcessingImpl() {
291 24 return true;
292 }
293
294 } // namespace gaivoronskiy_m_marking_binary_components
295