GCC Code Coverage Report

Directory: ./
File: tasks/nikitina_v_hoar_sort_batcher/stl/src/ops_stl.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 98 102 96.1%
Functions: 12 12 100.0%
Branches: 75 108 69.4%
Line Branch Exec Source
1 #include "nikitina_v_hoar_sort_batcher/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <limits>
5 #include <thread>
6 #include <utility>
7 #include <vector>
8
9 #include "nikitina_v_hoar_sort_batcher/common/include/common.hpp"
10
11 namespace nikitina_v_hoar_sort_batcher {
12
13 namespace {
14
15 96 void QuickSortHoare(std::vector<int> &arr, int low, int high) {
16
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 96 times.
 96 if (low >= high) {
17 ✗ return;
18 }
19 96 std::vector<std::pair<int, int>> stack;
20
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 stack.emplace_back(low, high);
21
22
2/2
✓ Branch 0 taken 480 times.
✓ Branch 1 taken 96 times.
 576 while (!stack.empty()) {
23 auto [l, h] = stack.back();
24 stack.pop_back();
25
26
2/2
✓ Branch 0 taken 288 times.
✓ Branch 1 taken 192 times.
 480 if (l >= h) {
27 288 continue;
28 }
29
30 192 int pivot = arr[l + ((h - l) / 2)];
31 192 int i = l - 1;
32 192 int j = h + 1;
33
34 while (true) {
35 312 i++;
36
2/2
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 312 times.
 416 while (arr[i] < pivot) {
37 104 i++;
38 }
39
40 312 j--;
41
2/2
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 312 times.
 416 while (arr[j] > pivot) {
42 104 j--;
43 }
44
45
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 192 times.
 312 if (i >= j) {
46 break;
47 }
48 std::swap(arr[i], arr[j]);
49 }
50
51
1/2
✓ Branch 1 taken 192 times.
✗ Branch 2 not taken.
 192 stack.emplace_back(l, j);
52
1/4
✓ Branch 1 taken 192 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 192 stack.emplace_back(j + 1, h);
53 }
54 }
55
56 120 void CompareSplit(std::vector<int> &arr, int start1, int len1, int start2, int len2) {
57
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 120 times.
 120 if (len1 == 0 || len2 == 0) {
58 ✗ return;
59 }
60
61
1/2
✓ Branch 2 taken 120 times.
✗ Branch 3 not taken.
 120 std::vector<int> left_block(arr.begin() + start1, arr.begin() + start1 + len1);
62
1/4
✓ Branch 1 taken 120 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 120 std::vector<int> right_block(arr.begin() + start2, arr.begin() + start2 + len2);
63
64 int p1 = 0;
65 int p2 = 0;
66 int write1 = start1;
67 int write2 = start2;
68
69
2/2
✓ Branch 0 taken 720 times.
✓ Branch 1 taken 120 times.
 840 for (int i = 0; i < len1 + len2; ++i) {
70 int val = 0;
71
6/6
✓ Branch 0 taken 560 times.
✓ Branch 1 taken 160 times.
✓ Branch 2 taken 496 times.
✓ Branch 3 taken 64 times.
✓ Branch 4 taken 296 times.
✓ Branch 5 taken 200 times.
 720 if (p1 < len1 && (p2 == len2 || left_block[p1] <= right_block[p2])) {
72 360 val = left_block[p1++];
73 } else {
74 360 val = right_block[p2++];
75 }
76
77
2/2
✓ Branch 0 taken 360 times.
✓ Branch 1 taken 360 times.
 720 if (i < len1) {
78 360 arr[write1++] = val;
79 } else {
80 360 arr[write2++] = val;
81 }
82 }
83 }
84
85 72 void BuildPairs(std::vector<std::pair<int, int>> &pairs, int num_threads, int step_p, int step_k) {
86
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 72 times.
 168 for (int idx_j = step_k % step_p; idx_j + step_k < num_threads; idx_j += (step_k * 2)) {
87
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 96 times.
 216 for (int idx_i = 0; idx_i < std::min(step_k, num_threads - idx_j - step_k); idx_i++) {
88
1/2
✓ Branch 0 taken 120 times.
✗ Branch 1 not taken.
 120 if ((idx_j + idx_i) / (step_p * 2) == (idx_j + idx_i + step_k) / (step_p * 2)) {
89 120 pairs.emplace_back(idx_j + idx_i, idx_j + idx_i + step_k);
90 }
91 }
92 }
93 72 }
94
95 // Вспомогательная функция для снижения когнитивной сложности
96
1/2
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
 72 void ExecuteMergeStep(std::vector<int> &output, const std::vector<int> &offsets,
97 const std::vector<std::pair<int, int>> &pairs, int actual_threads) {
98 72 int num_pairs = static_cast<int>(pairs.size());
99 72 int chunk_size = (num_pairs + actual_threads - 1) / actual_threads;
100 72 std::vector<std::thread> threads;
101
1/2
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
 72 threads.reserve(actual_threads);
102
103
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 72 times.
 192 for (int thread_idx = 0; thread_idx < actual_threads; ++thread_idx) {
104 120 int start = thread_idx * chunk_size;
105
1/2
✓ Branch 0 taken 120 times.
✗ Branch 1 not taken.
 120 int end = std::min(start + chunk_size, num_pairs);
106
107
1/2
✓ Branch 0 taken 120 times.
✗ Branch 1 not taken.
 120 if (start < end) {
108
1/2
✓ Branch 1 taken 120 times.
✗ Branch 2 not taken.
 120 threads.emplace_back([start, end, &output, &offsets, &pairs]() {
109
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 120 times.
 240 for (int idx = start; idx < end; ++idx) {
110 120 int block_a = pairs[idx].first;
111 120 int block_b = pairs[idx].second;
112 120 CompareSplit(output, offsets[block_a], offsets[block_a + 1] - offsets[block_a], offsets[block_b],
113 120 offsets[block_b + 1] - offsets[block_b]);
114 }
115 120 });
116 }
117 }
118
119
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 72 times.
 192 for (auto &th : threads) {
120
1/2
✓ Branch 1 taken 120 times.
✗ Branch 2 not taken.
 120 th.join();
121 }
122 72 }
123
124 24 void BatcherMergePhase(std::vector<int> &output, const std::vector<int> &offsets, int num_threads, int hw_threads) {
125
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 24 times.
 72 for (int step_p = 1; step_p < num_threads; step_p *= 2) {
126
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 48 times.
 120 for (int step_k = step_p; step_k > 0; step_k /= 2) {
127 72 std::vector<std::pair<int, int>> pairs;
128
1/2
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
 72 BuildPairs(pairs, num_threads, step_p, step_k);
129
130 72 int num_pairs = static_cast<int>(pairs.size());
131
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 72 if (num_pairs == 0) {
132 continue;
133 }
134
135 int actual_threads = std::min(hw_threads, num_pairs);
136
1/2
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
 72 ExecuteMergeStep(output, offsets, pairs, actual_threads);
137 }
138 }
139 24 }
140
141 } // namespace
142
143
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 HoareSortBatcherSTL::HoareSortBatcherSTL(const InType &in) {
144 SetTypeOfTask(GetStaticTypeOfTask());
145
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 GetInput() = in;
146 32 }
147
148 32 bool HoareSortBatcherSTL::ValidationImpl() {
149 32 return true;
150 }
151
152 32 bool HoareSortBatcherSTL::PreProcessingImpl() {
153 32 GetOutput() = GetInput();
154 32 return true;
155 }
156
157
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 8 times.
 32 bool HoareSortBatcherSTL::RunImpl() {
158 auto &output = GetOutput();
159
160 32 int orig_n = static_cast<int>(output.size());
161
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 8 times.
 32 if (orig_n <= 1) {
162 return true;
163 }
164
165 // Получаем количество доступных аппаратных потоков
166 24 int hw_threads = static_cast<int>(std::thread::hardware_concurrency());
167
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (hw_threads == 0) {
168 hw_threads = 4; // Fallback, если hardware_concurrency() вернул 0
169 }
170
171 int t = 1;
172
3/4
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 72 while (t * 2 <= hw_threads && t * 2 <= orig_n) {
173 t *= 2;
174 }
175
176
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (t == 1) {
177 ✗ QuickSortHoare(output, 0, orig_n - 1);
178 ✗ return true;
179 }
180
181 24 int pad = (t - (orig_n % t)) % t;
182
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 24 times.
 72 for (int i = 0; i < pad; ++i) {
183 48 output.push_back(std::numeric_limits<int>::max());
184 }
185
186 24 int n = orig_n + pad;
187 24 std::vector<int> offsets(t + 1, 0);
188 24 int chunk = n / t;
189
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 24 times.
 144 for (int i = 0; i <= t; ++i) {
190 120 offsets[i] = i * chunk;
191 }
192
193 // Параллельный запуск сортировок локальных блоков
194 24 std::vector<std::thread> sort_threads;
195
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 sort_threads.reserve(t); // Предварительное выделение памяти для векторов
196
197
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 24 times.
 120 for (int i = 0; i < t; ++i) {
198
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 192 sort_threads.emplace_back([&output, &offsets, i]() { QuickSortHoare(output, offsets[i], offsets[i + 1] - 1); });
199 }
200
201
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 24 times.
 120 for (auto &th : sort_threads) {
202
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 th.join();
203 }
204
205 // Запуск фазы слияния
206
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 BatcherMergePhase(output, offsets, t, hw_threads);
207
208
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 output.resize(orig_n);
209
210 return true;
211 24 }
212
213 32 bool HoareSortBatcherSTL::PostProcessingImpl() {
214 32 return true;
215 }
216
217 } // namespace nikitina_v_hoar_sort_batcher
218