GCC Code Coverage Report

Directory: ./
File: tasks/ivanova_p_marking_components_on_binary_image/omp/src/ops_omp.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 59 69 85.5%
Functions: 8 13 61.5%
Branches: 39 54 72.2%
Line Branch Exec Source
1 #include "ivanova_p_marking_components_on_binary_image/omp/include/ops_omp.hpp"
2
3 #include <omp.h>
4
5 #include <atomic>
6 #include <cstdint>
7 #include <string>
8 #include <vector>
9
10 #include "ivanova_p_marking_components_on_binary_image/common/include/common.hpp"
11 #include "ivanova_p_marking_components_on_binary_image/data/image_generator.hpp"
12 #include "util/include/util.hpp"
13
14 namespace ivanova_p_marking_components_on_binary_image {
15
16 58 IvanovaPMarkingComponentsOnBinaryImageOMP::IvanovaPMarkingComponentsOnBinaryImageOMP(const InType &in) {
17 SetTypeOfTask(GetStaticTypeOfTask());
18 58 GetInput() = in;
19 GetOutput().clear();
20 58 }
21
22 58 bool IvanovaPMarkingComponentsOnBinaryImageOMP::ValidationImpl() {
23 58 return GetInput() > 0;
24 }
25
26 58 bool IvanovaPMarkingComponentsOnBinaryImageOMP::PreProcessingImpl() {
27 58 const int test_case = GetInput();
28
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 42 times.
 58 if (test_case >= 11 && test_case <= 14) {
29 std::string filename;
30
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) {
31 case 11:
32 filename = "tasks/ivanova_p_marking_components_on_binary_image/data/image.txt";
33 break;
34 case 12:
35 filename = "tasks/ivanova_p_marking_components_on_binary_image/data/image2.txt";
36 break;
37 case 13:
38 filename = "tasks/ivanova_p_marking_components_on_binary_image/data/image3.txt";
39 break;
40 case 14:
41 filename = "tasks/ivanova_p_marking_components_on_binary_image/data/image4.txt";
42 break;
43 default:
44 filename = "";
45 }
46
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 32 input_image_ = LoadImageFromTxt(filename);
47 } else {
48 // Функциональные тесты создают изображения размера 100x100.
49 const int width = 100;
50 const int height = 100;
51 84 input_image_ = CreateTestImage(width, height, test_case);
52 }
53
54
3/6
✓ Branch 0 taken 58 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 58 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 58 times.
✗ Branch 5 not taken.
 58 if (input_image_.width <= 0 || input_image_.height <= 0 || input_image_.data.empty()) {
55 return false;
56 }
57
58 58 width_ = input_image_.width;
59 58 height_ = input_image_.height;
60
61 58 int total_pixels = width_ * height_;
62 58 labels_.assign(total_pixels, 0);
63 58 current_label_ = 0;
64
65 // Инициализация DSU
66 58 parent_.resize(total_pixels + 1);
67
2/2
✓ Branch 0 taken 420622 times.
✓ Branch 1 taken 58 times.
 420680 for (int i = 0; i <= total_pixels; ++i) {
68 420622 parent_[i] = i;
69 }
70
71 return true;
72 }
73
74 ✗ int IvanovaPMarkingComponentsOnBinaryImageOMP::FindRoot(int i) {
75
8/10
✓ Branch 0 taken 53519 times.
✓ Branch 1 taken 55240 times.
✓ Branch 2 taken 25862 times.
✓ Branch 3 taken 55240 times.
✓ Branch 4 taken 27682 times.
✓ Branch 5 taken 29404 times.
✓ Branch 6 taken 5 times.
✓ Branch 7 taken 29404 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
 191712 while (parent_[i] != i) {
76 107068 parent_[i] = parent_[parent_[i]];
77 i = parent_[i];
78 }
79 ✗ return i;
80 }
81
82 55240 void IvanovaPMarkingComponentsOnBinaryImageOMP::UnionLabels(int i, int j) {
83 int r_i = FindRoot(i);
84 int r_j = FindRoot(j);
85
2/2
✓ Branch 0 taken 29404 times.
✓ Branch 1 taken 25836 times.
 55240 if (r_i == r_j) {
86 return; // Быстрый выход без блокировки
87 }
88
89 58808 #pragma omp critical(dsu_union)
90 {
91 // Повторная проверка внутри блокировки (на случай, если за это время корень изменился)
92 r_i = FindRoot(i);
93 r_j = FindRoot(j);
94
1/2
✓ Branch 0 taken 29404 times.
✗ Branch 1 not taken.
 29404 if (r_i != r_j) {
95
2/2
✓ Branch 0 taken 29399 times.
✓ Branch 1 taken 5 times.
 29404 if (r_i < r_j) {
96 29399 parent_[r_j] = r_i;
97 } else {
98 5 parent_[r_i] = r_j;
99 }
100 }
101 }
102 }
103
104 ✗ void IvanovaPMarkingComponentsOnBinaryImageOMP::InitLabelsOmp(int total_pixels, int n_threads) {
105 58 #pragma omp parallel for default(none) shared(total_pixels) num_threads(n_threads)
106 for (int i = 0; i < total_pixels; ++i) {
107 if (input_image_.data[i] != 0) {
108 labels_[i] = i + 1;
109 }
110 }
111 ✗ }
112
113 ✗ void IvanovaPMarkingComponentsOnBinaryImageOMP::MergeHorizontalPairsOmp(int n_threads) {
114 58 #pragma omp parallel for default(none) shared(n_threads) num_threads(n_threads)
115 for (int yy = 0; yy < height_; ++yy) {
116 for (int xx = 0; xx < width_ - 1; ++xx) {
117 const int idx = (yy * width_) + xx;
118 const int cur_label = labels_[idx];
119 if (cur_label == 0) {
120 continue;
121 }
122
123 const int right_label = labels_[idx + 1];
124 if (right_label != 0) {
125 UnionLabels(cur_label, right_label);
126 }
127 }
128 }
129 ✗ }
130
131 ✗ void IvanovaPMarkingComponentsOnBinaryImageOMP::MergeVerticalPairsOmp(int n_threads) {
132 58 #pragma omp parallel for default(none) shared(n_threads) num_threads(n_threads)
133 for (int yy = 0; yy < height_ - 1; ++yy) {
134 for (int xx = 0; xx < width_; ++xx) {
135 const int idx = (yy * width_) + xx;
136 const int cur_label = labels_[idx];
137 if (cur_label == 0) {
138 continue;
139 }
140
141 const int bottom_label = labels_[idx + width_];
142 if (bottom_label != 0) {
143 UnionLabels(cur_label, bottom_label);
144 }
145 }
146 }
147 ✗ }
148
149 ✗ void IvanovaPMarkingComponentsOnBinaryImageOMP::FinalizeRootsOmp(int total_pixels, int n_threads) {
150 58 #pragma omp parallel for default(none) shared(total_pixels) num_threads(n_threads)
151 for (int i = 0; i < total_pixels; ++i) {
152 if (labels_[i] != 0) {
153 labels_[i] = FindRoot(labels_[i]);
154 }
155 }
156 ✗ }
157
158 58 void IvanovaPMarkingComponentsOnBinaryImageOMP::NormalizeLabelsOmp(int total_pixels, int n_threads) {
159 // Создаем временный массив для пометки используемых корней
160 58 std::vector<uint8_t> is_root_used(total_pixels + 1, 0);
161
162 58 #pragma omp parallel for default(none) shared(total_pixels, is_root_used) num_threads(n_threads)
163 for (int i = 0; i < total_pixels; ++i) {
164 if (labels_[i] != 0) {
165 is_root_used[labels_[i]] = 1; // Помечаем, что этот корень реально существует
166 }
167 }
168
169 // Последовательно собираем только УНИКАЛЬНЫЕ корни и создаем маппинг
170
1/4
✓ Branch 1 taken 58 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 58 std::vector<int> mapping(total_pixels + 1, 0);
171 int next_id = 1;
172
2/2
✓ Branch 0 taken 420564 times.
✓ Branch 1 taken 58 times.
 420622 for (int i = 1; i <= total_pixels; ++i) {
173
2/2
✓ Branch 0 taken 148 times.
✓ Branch 1 taken 420416 times.
 420564 if (is_root_used[i] != 0) {
174 148 mapping[i] = next_id++;
175 }
176 }
177 58 current_label_ = next_id - 1;
178
179 // В параллели обновляем метки через маппинг (O(1) доступ вместо lower_bound)
180
1/2
✓ Branch 0 taken 58 times.
✗ Branch 1 not taken.
 58 #pragma omp parallel for default(none) shared(total_pixels, mapping) num_threads(n_threads)
181 for (int i = 0; i < total_pixels; ++i) {
182 if (labels_[i] != 0) {
183 labels_[i] = mapping[labels_[i]];
184 }
185 }
186 58 }
187
188 58 void IvanovaPMarkingComponentsOnBinaryImageOMP::TouchFrameworkOmp() {
189 58 std::atomic<int> counter(0);
190 58 #pragma omp parallel default(none) shared(counter) num_threads(ppc::util::GetNumThreads())
191 {
192 counter++;
193 }
194 58 }
195
196 58 bool IvanovaPMarkingComponentsOnBinaryImageOMP::RunImpl() {
197 58 const int n_threads = ppc::util::GetNumThreads();
198 (void)n_threads;
199 58 const int total_pixels = width_ * height_;
200
201 InitLabelsOmp(total_pixels, n_threads);
202 MergeHorizontalPairsOmp(n_threads);
203 MergeVerticalPairsOmp(n_threads);
204 FinalizeRootsOmp(total_pixels, n_threads);
205 58 NormalizeLabelsOmp(total_pixels, n_threads);
206 58 TouchFrameworkOmp();
207 58 return true;
208 }
209
210
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 58 times.
 58 bool IvanovaPMarkingComponentsOnBinaryImageOMP::PostProcessingImpl() {
211 OutType &output = GetOutput();
212 output.clear();
213
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 58 times.
 58 output.push_back(width_);
214
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 58 times.
 58 output.push_back(height_);
215
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 58 times.
 58 output.push_back(current_label_);
216
4/4
✓ Branch 0 taken 420000 times.
✓ Branch 1 taken 564 times.
✓ Branch 2 taken 420564 times.
✓ Branch 3 taken 58 times.
 420622 for (int l : labels_) {
217 output.push_back(l);
218 }
219
220 58 return true;
221 }
222
223 } // namespace ivanova_p_marking_components_on_binary_image
224