GCC Code Coverage Report

Directory: ./
File: tasks/ivanova_p_marking_components_on_binary_image/tbb/src/ops_tbb.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 97 130 74.6%
Functions: 11 20 55.0%
Branches: 88 136 64.7%
Line Branch Exec Source
1 #include "ivanova_p_marking_components_on_binary_image/tbb/include/ops_tbb.hpp"
2
3 #include <tbb/tbb.h>
4
5 #include <algorithm>
6 #include <string>
7 #include <vector>
8
9 #include "ivanova_p_marking_components_on_binary_image/common/include/common.hpp"
10 #include "ivanova_p_marking_components_on_binary_image/data/image_generator.hpp"
11
12 namespace ivanova_p_marking_components_on_binary_image {
13
14
2/2
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 6 times.
 58 IvanovaPMarkingComponentsOnBinaryImageTBB::IvanovaPMarkingComponentsOnBinaryImageTBB(const InType &in) {
15 SetTypeOfTask(GetStaticTypeOfTask());
16 58 GetInput() = in;
17 GetOutput().clear();
18
19 58 test_image.width = 0;
20
2/2
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 6 times.
 58 test_image.height = 0;
21 test_image.data.clear();
22 58 }
23
24 58 bool IvanovaPMarkingComponentsOnBinaryImageTBB::ValidationImpl() {
25
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 58 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 58 if (test_image.width <= 0 || test_image.height <= 0) {
26 58 int test_case = GetInput();
27
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 42 times.
 58 if (test_case >= 11 && test_case <= 14) {
28 std::string filename;
29
4/4
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 4 times.
✓ Branch 3 taken 4 times.
 16 switch (test_case) {
30 case 11:
31 filename = "tasks/ivanova_p_marking_components_on_binary_image/data/image.txt";
32 break;
33 case 12:
34 filename = "tasks/ivanova_p_marking_components_on_binary_image/data/image2.txt";
35 break;
36 case 13:
37 filename = "tasks/ivanova_p_marking_components_on_binary_image/data/image3.txt";
38 break;
39 case 14:
40 filename = "tasks/ivanova_p_marking_components_on_binary_image/data/image4.txt";
41 break;
42 default:
43 filename = "";
44 break;
45 }
46
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 32 test_image = LoadImageFromTxt(filename);
47 } else {
48 int size = ExtractImageSize(test_case);
49 84 test_image = CreateTestImage(size, size, test_case);
50 }
51 }
52
2/4
✓ Branch 0 taken 58 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 58 times.
 58 return test_image.width > 0 && !test_image.data.empty();
53 }
54
55 58 bool IvanovaPMarkingComponentsOnBinaryImageTBB::PreProcessingImpl() {
56 input_image_ = test_image;
57 58 width_ = input_image_.width;
58 58 height_ = input_image_.height;
59 58 int total_pixels = width_ * height_;
60
61 58 labels_.assign(total_pixels, 0);
62
63 // Инициализируем DSU: размер +1, так как метки теперь начинаются с 1 (idx + 1)
64 58 parent_.resize(total_pixels + 1);
65
2/2
✓ Branch 0 taken 420622 times.
✓ Branch 1 taken 58 times.
 420680 for (int i = 0; i <= total_pixels; ++i) {
66 420622 parent_[i] = i;
67 }
68
69 58 current_label_ = 0;
70 58 return true;
71 }
72
73 ✗ int IvanovaPMarkingComponentsOnBinaryImageTBB::FindRoot(int label) {
74 int root = label;
75
4/6
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 1020 times.
✓ Branch 2 taken 940 times.
✓ Branch 3 taken 1020 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 3004 while (parent_[root] != root) {
76 root = parent_[root];
77 }
78
79 // Сжатие путей (Path compression) для ускорения последующих поисков
80 int current = label;
81
2/6
✗ Branch 0 not taken.
✓ Branch 1 taken 1020 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1020 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 2040 while (parent_[current] != root) {
82 int next = parent_[current];
83 ✗ parent_[current] = root;
84 current = next;
85 }
86 ✗ return root;
87 }
88
89 1020 void IvanovaPMarkingComponentsOnBinaryImageTBB::UnionLabels(int label1, int label2) {
90 int root1 = FindRoot(label1);
91 int root2 = FindRoot(label2);
92
93
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 940 times.
 1020 if (root1 != root2) {
94
1/2
✓ Branch 0 taken 80 times.
✗ Branch 1 not taken.
 80 if (root1 < root2) {
95 80 parent_[root2] = root1;
96 } else {
97 ✗ parent_[root1] = root2;
98 }
99 }
100 1020 }
101
102 ✗ void IvanovaPMarkingComponentsOnBinaryImageTBB::ProcessPixel(int xx, int yy, int idx) {
103 ✗ int left_label = (xx > 0) ? labels_[idx - 1] : 0;
104 ✗ int top_label = (yy > 0) ? labels_[idx - width_] : 0;
105
106 ✗ bool left_exists = (left_label != 0);
107 ✗ bool top_exists = (top_label != 0);
108
109 ✗ if (!left_exists && !top_exists) {
110 ✗ current_label_++;
111 ✗ labels_[idx] = current_label_;
112 ✗ parent_[current_label_] = current_label_;
113 } else {
114 ✗ int label = left_exists ? left_label : top_label;
115 ✗ labels_[idx] = label;
116
117 ✗ if (left_exists && top_exists && left_label != top_label) {
118 ✗ UnionLabels(std::min(left_label, top_label), std::max(left_label, top_label));
119 }
120 }
121 ✗ }
122
123 ✗ int IvanovaPMarkingComponentsOnBinaryImageTBB::FindLocalRoot(int label) {
124 int root = label;
125
3/6
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
✓ Branch 2 taken 12 times.
✓ Branch 3 taken 16 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 28 while (parent_[root] != root) {
126 root = parent_[root];
127 }
128 ✗ return root;
129 }
130
131 ✗ void IvanovaPMarkingComponentsOnBinaryImageTBB::UnionLocalRoots(int root1, int root2) {
132
2/4
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 16 if (root1 != root2) {
133
1/4
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 4 if (root1 < root2) {
134 4 parent_[root2] = root1;
135 } else {
136 ✗ parent_[root1] = root2;
137 }
138 }
139 ✗ }
140
141 420564 void IvanovaPMarkingComponentsOnBinaryImageTBB::ProcessStripePixel(int xx, int yy, int idx, int start_row) {
142
2/2
✓ Branch 0 taken 29552 times.
✓ Branch 1 taken 391012 times.
 420564 if (input_image_.data[idx] == 0) {
143 return;
144 }
145
146
2/2
✓ Branch 0 taken 29508 times.
✓ Branch 1 taken 44 times.
 29552 int left_label = (xx > 0) ? labels_[idx - 1] : 0;
147
2/2
✓ Branch 0 taken 27872 times.
✓ Branch 1 taken 1680 times.
 29552 int top_label = (yy > start_row) ? labels_[idx - width_] : 0;
148
149
2/2
✓ Branch 0 taken 232 times.
✓ Branch 1 taken 29320 times.
 29552 if (left_label == 0 && top_label == 0) {
150 232 labels_[idx] = idx + 1;
151 } else {
152
2/2
✓ Branch 0 taken 1820 times.
✓ Branch 1 taken 27500 times.
 29320 int label = (left_label != 0) ? left_label : top_label;
153 29320 labels_[idx] = label;
154
155
4/4
✓ Branch 0 taken 24900 times.
✓ Branch 1 taken 4420 times.
✓ Branch 2 taken 16 times.
✓ Branch 3 taken 24884 times.
 29320 if (left_label != 0 && top_label != 0 && left_label != top_label) {
156 int root1 = FindLocalRoot(left_label);
157 int root2 = FindLocalRoot(top_label);
158 UnionLocalRoots(root1, root2);
159 }
160 }
161 }
162
163 58 void IvanovaPMarkingComponentsOnBinaryImageTBB::MergeBoundariesTbb(int num_threads, int rows_per_thread) {
164
2/2
✓ Branch 0 taken 170 times.
✓ Branch 1 taken 58 times.
 228 for (int thread_id = 0; thread_id < num_threads - 1; ++thread_id) {
165 170 int boundary_row = (thread_id + 1) * rows_per_thread;
166
2/2
✓ Branch 0 taken 162 times.
✓ Branch 1 taken 8 times.
 170 if (boundary_row >= height_) {
167 8 continue;
168 }
169
170
2/2
✓ Branch 0 taken 12432 times.
✓ Branch 1 taken 162 times.
 12594 for (int xx = 0; xx < width_; ++xx) {
171 12432 int top_idx = ((boundary_row - 1) * width_) + xx;
172 12432 int bottom_idx = (boundary_row * width_) + xx;
173
174
2/2
✓ Branch 0 taken 1020 times.
✓ Branch 1 taken 11412 times.
 12432 int top_label = labels_[top_idx];
175 12432 int bottom_label = labels_[bottom_idx];
176
177
3/4
✓ Branch 0 taken 1020 times.
✓ Branch 1 taken 11412 times.
✓ Branch 2 taken 1020 times.
✗ Branch 3 not taken.
 12432 if (top_label != 0 && bottom_label != 0 && top_label != bottom_label) {
178 1020 UnionLabels(top_label, bottom_label);
179 }
180 }
181 }
182 58 }
183
184 58 void IvanovaPMarkingComponentsOnBinaryImageTBB::FirstPass() {
185 int num_threads = std::max(1, tbb::this_task_arena::max_concurrency());
186 58 int rows_per_thread = (height_ + num_threads - 1) / num_threads;
187
188 // Фаза 1: Истинная параллельная обработка независимых полос
189 58 tbb::parallel_for(0, num_threads, [&](int thread_id) {
190 228 int start_row = thread_id * rows_per_thread;
191
2/2
✓ Branch 0 taken 220 times.
✓ Branch 1 taken 8 times.
 228 int end_row = std::min(start_row + rows_per_thread, height_);
192
2/2
✓ Branch 0 taken 220 times.
✓ Branch 1 taken 8 times.
 228 if (start_row >= height_) {
193 return;
194 }
195
196
2/2
✓ Branch 0 taken 4292 times.
✓ Branch 1 taken 220 times.
 4512 for (int yy = start_row; yy < end_row; ++yy) {
197
2/2
✓ Branch 0 taken 420564 times.
✓ Branch 1 taken 4292 times.
 424856 for (int xx = 0; xx < width_; ++xx) {
198 420564 int idx = (yy * width_) + xx;
199 420564 ProcessStripePixel(xx, yy, idx, start_row);
200 }
201 }
202 });
203
204 // Фаза 2: Быстрое последовательное объединение на стыках полос
205 58 MergeBoundariesTbb(num_threads, rows_per_thread);
206
207 58 current_label_ = 1;
208 58 }
209
210 58 void IvanovaPMarkingComponentsOnBinaryImageTBB::SecondPass() {
211 58 int total_pixels = width_ * height_;
212
213 // 1. Параллельно сжимаем пути для всех пикселей
214 58 tbb::parallel_for(0, total_pixels, [&](int i) {
215
2/2
✓ Branch 0 taken 29552 times.
✓ Branch 1 taken 391012 times.
 420564 if (labels_[i] != 0) {
216 int root = labels_[i];
217
2/2
✓ Branch 0 taken 12520 times.
✓ Branch 1 taken 29552 times.
 42072 while (parent_[root] != root) {
218 root = parent_[root];
219 }
220 29552 labels_[i] = root;
221 }
222 });
223
224 // 2. Быстрый проход для создания непрерывных ID
225 // ИСПРАВЛЕНИЕ: Вектор должен вмещать метки вплоть до total_pixels
226 58 std::vector<int> root_mapping(total_pixels + 1, 0);
227 int next_label = 1;
228
2/2
✓ Branch 0 taken 420564 times.
✓ Branch 1 taken 58 times.
 420622 for (int i = 0; i < total_pixels; ++i) {
229
2/2
✓ Branch 0 taken 29552 times.
✓ Branch 1 taken 391012 times.
 420564 if (labels_[i] != 0) {
230 int r = labels_[i];
231
2/2
✓ Branch 0 taken 148 times.
✓ Branch 1 taken 29404 times.
 29552 if (root_mapping[r] == 0) {
232 148 root_mapping[r] = next_label++;
233 }
234 }
235 }
236 58 current_label_ = next_label - 1;
237
238 // 3. Параллельно присваиваем новые нормализованные метки
239
2/6
✓ Branch 1 taken 58 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 58 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 58 tbb::parallel_for(0, total_pixels, [&](int i) {
240
2/2
✓ Branch 0 taken 29552 times.
✓ Branch 1 taken 391012 times.
 420564 if (labels_[i] != 0) {
241 29552 labels_[i] = root_mapping[labels_[i]];
242 }
243 });
244 58 }
245
246 ✗ void IvanovaPMarkingComponentsOnBinaryImageTBB::InitLabelsTbb(int /*total_pixels*/) {
247 // Не используется
248 ✗ }
249
250 ✗ void IvanovaPMarkingComponentsOnBinaryImageTBB::MergeHorizontalPairsTbb() {
251 // Не используется
252 ✗ }
253
254 ✗ void IvanovaPMarkingComponentsOnBinaryImageTBB::MergeVerticalPairsTbb() {
255 // Не используется
256 ✗ }
257
258 ✗ void IvanovaPMarkingComponentsOnBinaryImageTBB::FinalizeRootsTbb(int /*total_pixels*/) {
259 // Не используется
260 ✗ }
261
262 ✗ void IvanovaPMarkingComponentsOnBinaryImageTBB::NormalizeLabelsTbb(int /*total_pixels*/) {
263 // Не используется
264 ✗ }
265
266 58 bool IvanovaPMarkingComponentsOnBinaryImageTBB::RunImpl() {
267
2/4
✓ Branch 0 taken 58 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 58 times.
✗ Branch 3 not taken.
 58 if (width_ <= 0 || height_ <= 0) {
268 return false;
269 }
270
271 58 FirstPass();
272
273
1/2
✓ Branch 0 taken 58 times.
✗ Branch 1 not taken.
 58 if (current_label_ > 0) {
274 58 SecondPass();
275 }
276
277 return true;
278 }
279
280
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 58 times.
 58 bool IvanovaPMarkingComponentsOnBinaryImageTBB::PostProcessingImpl() {
281 OutType &output = GetOutput();
282 output.clear();
283 58 output.reserve(3 + labels_.size());
284
1/2
✓ Branch 0 taken 58 times.
✗ Branch 1 not taken.
 58 output.push_back(width_);
285
1/2
✓ Branch 0 taken 58 times.
✗ Branch 1 not taken.
 58 output.push_back(height_);
286
1/2
✓ Branch 0 taken 58 times.
✗ Branch 1 not taken.
 58 output.push_back(current_label_);
287
3/4
✓ Branch 0 taken 420564 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 420564 times.
✓ Branch 3 taken 58 times.
 420622 for (int l : labels_) {
288 output.push_back(l);
289 }
290 58 return true;
291 }
292
293 } // namespace ivanova_p_marking_components_on_binary_image
294