GCC Code Coverage Report

Directory: ./
File: tasks/ivanova_p_marking_components_on_binary_image/all/src/ops_all.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 132 157 84.1%
Functions: 13 23 56.5%
Branches: 101 158 63.9%
Line Branch Exec Source
1 #include "ivanova_p_marking_components_on_binary_image/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4 #include <tbb/tbb.h>
5
6 #include <algorithm>
7 #include <cstddef>
8 #include <string>
9 #include <vector>
10
11 #include "ivanova_p_marking_components_on_binary_image/common/include/common.hpp"
12 #include "ivanova_p_marking_components_on_binary_image/data/image_generator.hpp"
13
14 namespace ivanova_p_marking_components_on_binary_image {
15
16 28 IvanovaPMarkingComponentsOnBinaryImageALL::IvanovaPMarkingComponentsOnBinaryImageALL(const InType &in) {
17 SetTypeOfTask(GetStaticTypeOfTask());
18 28 GetInput() = in;
19 28 GetOutput() = OutType();
20
21 28 test_image.width = 0;
22
2/2
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 2 times.
 28 test_image.height = 0;
23 test_image.data.clear();
24 28 }
25
26 28 bool IvanovaPMarkingComponentsOnBinaryImageALL::ValidationImpl() {
27
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 28 if (test_image.width <= 0 || test_image.height <= 0) {
28 28 int test_case = GetInput();
29
30
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 20 times.
 28 if (test_case >= 11 && test_case <= 14) {
31 std::string filename;
32
4/4
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 2 times.
 8 switch (test_case) {
33 case 11:
34 filename = "tasks/ivanova_p_marking_components_on_binary_image/data/image.txt";
35 break;
36 case 12:
37 filename = "tasks/ivanova_p_marking_components_on_binary_image/data/image2.txt";
38 break;
39 case 13:
40 filename = "tasks/ivanova_p_marking_components_on_binary_image/data/image3.txt";
41 break;
42 case 14:
43 filename = "tasks/ivanova_p_marking_components_on_binary_image/data/image4.txt";
44 break;
45 default:
46 filename = "";
47 break;
48 }
49
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 16 test_image = LoadImageFromTxt(filename);
50 } else {
51 int size = ExtractImageSize(test_case);
52 40 test_image = CreateTestImage(size, size, test_case);
53 }
54 }
55
56
3/6
✓ Branch 0 taken 28 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 28 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 28 times.
✗ Branch 5 not taken.
 28 if (test_image.width <= 0 || test_image.height <= 0 || test_image.data.empty()) {
57 return false;
58 }
59
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 28 times.
 28 if (test_image.data.size() != static_cast<size_t>(test_image.width) * static_cast<size_t>(test_image.height)) {
60 ✗ return false;
61 }
62 return true;
63 }
64
65 28 bool IvanovaPMarkingComponentsOnBinaryImageALL::PreProcessingImpl() {
66
2/4
✓ Branch 0 taken 28 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 28 times.
 28 if (test_image.width <= 0 || test_image.height <= 0) {
67 // Дублирующий блок из оригинального кода оставлен для сохранения логики
68 ✗ int test_case = GetInput();
69 ✗ if (test_case >= 11 && test_case <= 14) {
70 std::string filename;
71 ✗ switch (test_case) {
72 case 11:
73 filename = "tasks/ivanova_p_marking_components_on_binary_image/data/image.txt";
74 break;
75 case 12:
76 filename = "tasks/ivanova_p_marking_components_on_binary_image/data/image2.txt";
77 break;
78 case 13:
79 filename = "tasks/ivanova_p_marking_components_on_binary_image/data/image3.txt";
80 break;
81 case 14:
82 filename = "tasks/ivanova_p_marking_components_on_binary_image/data/image4.txt";
83 break;
84 default:
85 filename = "";
86 break;
87 }
88 ✗ test_image = LoadImageFromTxt(filename);
89 } else {
90 int size = ExtractImageSize(test_case);
91 ✗ test_image = CreateTestImage(size, size, test_case);
92 }
93 }
94
95 input_image_ = test_image;
96 28 width_ = input_image_.width;
97 28 height_ = input_image_.height;
98
99 28 int total_pixels = width_ * height_;
100 28 labels_.assign(total_pixels, 0);
101
102 // Выделяем память под глобальный DSU с запасом на все потоки
103 int num_threads = tbb::this_task_arena::max_concurrency();
104 28 parent_.resize((static_cast<size_t>(num_threads) * static_cast<size_t>(total_pixels)) + 1);
105
2/2
✓ Branch 0 taken 400592 times.
✓ Branch 1 taken 28 times.
 400620 for (size_t i = 0; i < parent_.size(); ++i) {
106 400592 parent_[i] = static_cast<int>(i);
107 }
108
109 28 current_label_ = 0;
110 28 return true;
111 }
112
113 ✗ int IvanovaPMarkingComponentsOnBinaryImageALL::FindRoot(int label) {
114 int root = label;
115
5/8
✓ Branch 0 taken 4280 times.
✓ Branch 1 taken 14776 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 314 times.
✓ Branch 4 taken 294 times.
✓ Branch 5 taken 314 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 19978 while (parent_[root] != root) {
116 root = parent_[root];
117 }
118
119 // Сжатие путей (Path compression)
120 int current = label;
121
3/8
✗ Branch 0 not taken.
✓ Branch 1 taken 14776 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 314 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 314 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 15404 while (parent_[current] != root) {
122 int next = parent_[current];
123 ✗ parent_[current] = root;
124 current = next;
125 }
126 ✗ return root;
127 }
128
129 314 void IvanovaPMarkingComponentsOnBinaryImageALL::UnionLabels(int label1, int label2) {
130 int root1 = FindRoot(label1);
131 int root2 = FindRoot(label2);
132
133
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 294 times.
 314 if (root1 != root2) {
134
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 2 times.
 20 if (root1 < root2) {
135 18 parent_[root2] = root1;
136 } else {
137 2 parent_[root1] = root2;
138 }
139 }
140 314 }
141
142 ✗ void IvanovaPMarkingComponentsOnBinaryImageALL::ProcessPixel(int /*xx*/, int /*yy*/, int /*idx*/) {
143 // Не используется в основном параллельном проходе, оставлено для интерфейса класса
144 ✗ }
145
146 ✗ int IvanovaPMarkingComponentsOnBinaryImageALL::FindLocalRootAll(int label, const std::vector<int> &local_parent) {
147 int root = label;
148
3/10
✗ Branch 0 not taken.
✓ Branch 1 taken 8 times.
✓ Branch 2 taken 6 times.
✓ Branch 3 taken 8 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
 14 while (local_parent[static_cast<size_t>(root)] != root) {
149 root = local_parent[static_cast<size_t>(root)];
150 }
151 ✗ return root;
152 }
153
154 ✗ void IvanovaPMarkingComponentsOnBinaryImageALL::UnionLocalLabelsAll(int label1, int label2,
155 std::vector<int> &local_parent) {
156 int root1 = FindLocalRootAll(label1, local_parent);
157 int root2 = FindLocalRootAll(label2, local_parent);
158
2/4
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 8 if (root1 != root2) {
159
1/4
✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 2 if (root1 < root2) {
160 2 local_parent[static_cast<size_t>(root2)] = root1;
161 } else {
162 ✗ local_parent[static_cast<size_t>(root1)] = root2;
163 }
164 }
165 ✗ }
166
167 200282 void IvanovaPMarkingComponentsOnBinaryImageALL::ProcessStripePixelAll(int xx, int yy, int idx, int start_row,
168 std::vector<int> &local_parent,
169 int &local_label) {
170
2/2
✓ Branch 0 taken 14776 times.
✓ Branch 1 taken 185506 times.
 200282 if (input_image_.data[static_cast<size_t>(idx)] == 0) {
171 return;
172 }
173
174
2/2
✓ Branch 0 taken 14754 times.
✓ Branch 1 taken 22 times.
 14776 int left_label = (xx > 0) ? labels_[static_cast<size_t>(idx - 1)] : 0;
175
2/2
✓ Branch 0 taken 14240 times.
✓ Branch 1 taken 536 times.
 14776 int top_label = (yy > start_row) ? labels_[static_cast<size_t>(idx - width_)] : 0;
176
177 14776 bool left_exists = (left_label != 0);
178 14776 bool top_exists = (top_label != 0);
179
180
2/2
✓ Branch 0 taken 94 times.
✓ Branch 1 taken 14682 times.
 14776 if (!left_exists && !top_exists) {
181 94 local_label++;
182 94 labels_[static_cast<size_t>(idx)] = local_label;
183 } else {
184
2/2
✓ Branch 0 taken 932 times.
✓ Branch 1 taken 13750 times.
 14682 int label = left_exists ? left_label : top_label;
185 14682 labels_[static_cast<size_t>(idx)] = label;
186
187
4/4
✓ Branch 0 taken 12626 times.
✓ Branch 1 taken 2056 times.
✓ Branch 2 taken 8 times.
✓ Branch 3 taken 12618 times.
 14682 if (left_exists && top_exists && left_label != top_label) {
188 UnionLocalLabelsAll(left_label, top_label, local_parent);
189 }
190 }
191 }
192
193 ✗ void IvanovaPMarkingComponentsOnBinaryImageALL::InitializeLocalParent(std::vector<int> &local_parent, int max_labels) {
194 56 local_parent.resize(static_cast<size_t>(max_labels));
195
2/4
✓ Branch 0 taken 801184 times.
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 801240 for (int i = 0; i < max_labels; ++i) {
196 801184 local_parent[static_cast<size_t>(i)] = i;
197 }
198 ✗ }
199
200 56 void IvanovaPMarkingComponentsOnBinaryImageALL::ProcessStripe(int start_row, int end_row,
201 std::vector<int> &local_parent, int &local_label) {
202
2/2
✓ Branch 0 taken 2046 times.
✓ Branch 1 taken 56 times.
 2102 for (int yy = start_row; yy < end_row; ++yy) {
203
2/2
✓ Branch 0 taken 200282 times.
✓ Branch 1 taken 2046 times.
 202328 for (int xx = 0; xx < width_; ++xx) {
204 200282 int idx = (yy * width_) + xx;
205 200282 ProcessStripePixelAll(xx, yy, idx, start_row, local_parent, local_label);
206 }
207 }
208 56 }
209
210 28 void IvanovaPMarkingComponentsOnBinaryImageALL::MergeBoundaries(int num_threads, int rows_per_thread) {
211
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 28 times.
 56 for (int thread_id = 0; thread_id < num_threads - 1; ++thread_id) {
212 28 int boundary_row = (thread_id + 1) * rows_per_thread;
213
1/2
✓ Branch 0 taken 28 times.
✗ Branch 1 not taken.
 28 if (boundary_row >= height_) {
214 ✗ continue;
215 }
216
217
2/2
✓ Branch 0 taken 2046 times.
✓ Branch 1 taken 28 times.
 2074 for (int xx = 0; xx < width_; ++xx) {
218 2046 int top_idx = ((boundary_row - 1) * width_) + xx;
219 2046 int bottom_idx = (boundary_row * width_) + xx;
220
221
2/2
✓ Branch 0 taken 312 times.
✓ Branch 1 taken 1734 times.
 2046 int top_label = labels_[static_cast<size_t>(top_idx)];
222 2046 int bottom_label = labels_[static_cast<size_t>(bottom_idx)];
223
224
3/4
✓ Branch 0 taken 312 times.
✓ Branch 1 taken 1734 times.
✓ Branch 2 taken 312 times.
✗ Branch 3 not taken.
 2046 if (top_label != 0 && bottom_label != 0 && top_label != bottom_label) {
225 312 UnionLabels(top_label, bottom_label);
226 }
227 }
228 }
229 28 }
230
231 28 void IvanovaPMarkingComponentsOnBinaryImageALL::MergeLocalParents(const std::vector<std::vector<int>> &local_parents,
232 const std::vector<int> &local_labels, int num_threads,
233 int total_pixels) {
234
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 28 times.
 84 for (int thread_id = 0; thread_id < num_threads; ++thread_id) {
235
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 56 times.
 56 if (local_parents[static_cast<size_t>(thread_id)].empty()) {
236 ✗ continue;
237 }
238
239 56 int start_lbl = (thread_id * total_pixels) + 1;
240 56 int end_lbl = local_labels[static_cast<size_t>(thread_id)];
241
242
2/2
✓ Branch 0 taken 94 times.
✓ Branch 1 taken 56 times.
 150 for (int label = start_lbl; label <= end_lbl; ++label) {
243
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 92 times.
 94 int p = local_parents[static_cast<size_t>(thread_id)][static_cast<size_t>(label)];
244
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 92 times.
 94 if (p != label) {
245 2 UnionLabels(label, p);
246 }
247 }
248 }
249 28 }
250
251 28 void IvanovaPMarkingComponentsOnBinaryImageALL::FirstPass() {
252 28 int num_threads = tbb::this_task_arena::max_concurrency();
253 28 int rows_per_thread = (height_ + num_threads - 1) / num_threads;
254 28 int total_pixels = width_ * height_;
255
256 28 std::vector<std::vector<int>> local_parents(static_cast<size_t>(num_threads));
257
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 std::vector<int> local_labels(static_cast<size_t>(num_threads), 0);
258
259 // Фаза 1: Параллельная обработка полос с TBB
260
1/4
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 28 tbb::parallel_for(0, num_threads, [&](int thread_id) {
261 56 int start_row = thread_id * rows_per_thread;
262
1/2
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
 56 int end_row = std::min(start_row + rows_per_thread, height_);
263
1/2
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
 56 if (start_row >= height_) {
264 return;
265 }
266
267 56 int max_possible_labels = (num_threads * total_pixels) + 1;
268 56 InitializeLocalParent(local_parents[static_cast<size_t>(thread_id)], max_possible_labels);
269
270 56 int &local_label = local_labels[static_cast<size_t>(thread_id)];
271 56 local_label = thread_id * total_pixels;
272
273 56 ProcessStripe(start_row, end_row, local_parents[static_cast<size_t>(thread_id)], local_label);
274 });
275
276 // Фаза 2: Последовательное объединение границ между полосами
277 28 MergeBoundaries(num_threads, rows_per_thread);
278
279 // Фаза 3: Перенос локальных связей потоков в глобальный вектор DSU
280 28 MergeLocalParents(local_parents, local_labels, num_threads, total_pixels);
281
282 28 current_label_ = 0;
283
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 28 times.
 84 for (int thread_id = 0; thread_id < num_threads; ++thread_id) {
284
2/2
✓ Branch 0 taken 50 times.
✓ Branch 1 taken 6 times.
 106 current_label_ = std::max(current_label_, local_labels[static_cast<size_t>(thread_id)]);
285 }
286 28 }
287
288 28 void IvanovaPMarkingComponentsOnBinaryImageALL::SecondPass() {
289 int num_threads = tbb::this_task_arena::max_concurrency();
290 28 int total_pixels = width_ * height_;
291
292 // Вектор вместо unordered_map для нормализации меток
293 28 std::vector<int> new_labels((static_cast<size_t>(num_threads) * static_cast<size_t>(total_pixels)) + 1, 0);
294 int next_label = 1;
295
296
2/2
✓ Branch 0 taken 200282 times.
✓ Branch 1 taken 28 times.
 200310 for (int &label : labels_) {
297
2/2
✓ Branch 0 taken 14776 times.
✓ Branch 1 taken 185506 times.
 200282 if (label != 0) {
298 int root = FindRoot(label);
299
300
2/2
✓ Branch 0 taken 74 times.
✓ Branch 1 taken 14702 times.
 14776 if (new_labels[static_cast<size_t>(root)] == 0) {
301 74 new_labels[static_cast<size_t>(root)] = next_label++;
302 }
303
304 14776 label = new_labels[static_cast<size_t>(root)];
305 }
306 }
307
308
1/2
✓ Branch 0 taken 28 times.
✗ Branch 1 not taken.
 28 current_label_ = next_label - 1;
309 28 }
310
311 ✗ void IvanovaPMarkingComponentsOnBinaryImageALL::InitLabelsAll(int /*unused*/) {}
312 ✗ void IvanovaPMarkingComponentsOnBinaryImageALL::MergeHorizontalPairsAll() {}
313 ✗ void IvanovaPMarkingComponentsOnBinaryImageALL::MergeVerticalPairsAll() {}
314 ✗ void IvanovaPMarkingComponentsOnBinaryImageALL::FinalizeRootsAll(int /*unused*/) {}
315 ✗ void IvanovaPMarkingComponentsOnBinaryImageALL::NormalizeLabelsAll(int /*unused*/) {}
316
317 28 bool IvanovaPMarkingComponentsOnBinaryImageALL::RunImpl() {
318 28 int total_pixels = width_ * height_;
319
1/2
✓ Branch 0 taken 28 times.
✗ Branch 1 not taken.
 28 if (total_pixels <= 0) {
320 return false;
321 }
322
323 28 int rank = 0;
324 28 int world_size = 1;
325 28 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
326 28 MPI_Comm_size(MPI_COMM_WORLD, &world_size);
327
328 28 FirstPass();
329
330
1/2
✓ Branch 0 taken 28 times.
✗ Branch 1 not taken.
 28 if (current_label_ > 0) {
331 28 SecondPass();
332 }
333
334
1/2
✓ Branch 0 taken 28 times.
✗ Branch 1 not taken.
 28 if (world_size > 1) {
335 28 MPI_Barrier(MPI_COMM_WORLD);
336 28 MPI_Bcast(&current_label_, 1, MPI_INT, 0, MPI_COMM_WORLD);
337 28 MPI_Bcast(labels_.data(), static_cast<int>(labels_.size()), MPI_INT, 0, MPI_COMM_WORLD);
338 }
339
340 return true;
341 }
342
343
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 28 times.
 28 bool IvanovaPMarkingComponentsOnBinaryImageALL::PostProcessingImpl() {
344 OutType &output = GetOutput();
345 output.clear();
346
347
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 28 times.
 28 output.push_back(width_);
348
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 28 times.
 28 output.push_back(height_);
349
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 28 times.
 28 output.push_back(current_label_);
350
351
4/4
✓ Branch 0 taken 200012 times.
✓ Branch 1 taken 270 times.
✓ Branch 2 taken 200282 times.
✓ Branch 3 taken 28 times.
 200310 for (int label : labels_) {
352 output.push_back(label);
353 }
354
355 28 return true;
356 }
357
358 } // namespace ivanova_p_marking_components_on_binary_image
359