GCC Code Coverage Report

Directory: ./
File: tasks/vasiliev_m_shell_sort_batcher_merge/stl/src/ops_stl.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 126 126 100.0%
Functions: 15 15 100.0%
Branches: 103 154 66.9%
Line Branch Exec Source
1 #include "vasiliev_m_shell_sort_batcher_merge/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <cmath>
5 #include <cstddef>
6 #include <thread>
7 #include <vector>
8
9 #include "util/include/util.hpp"
10 #include "vasiliev_m_shell_sort_batcher_merge/common/include/common.hpp"
11
12 namespace vasiliev_m_shell_sort_batcher_merge {
13
14
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 VasilievMShellSortBatcherMergeSTL::VasilievMShellSortBatcherMergeSTL(const InType &in) {
15 SetTypeOfTask(GetStaticTypeOfTask());
16
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 GetInput() = in;
17 48 GetOutput() = OutType{};
18 48 }
19
20 48 bool VasilievMShellSortBatcherMergeSTL::ValidationImpl() {
21 48 return !GetInput().empty();
22 }
23
24
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 bool VasilievMShellSortBatcherMergeSTL::PreProcessingImpl() {
25 GetOutput().clear();
26 48 return true;
27 }
28
29
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 bool VasilievMShellSortBatcherMergeSTL::RunImpl() {
30 auto &vec = GetInput();
31 const size_t n = vec.size();
32
33
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 if (vec.empty()) {
34 return false;
35 }
36
37 48 int threads = std::max(1, ppc::util::GetNumThreads());
38
39 48 std::vector<size_t> bounds = ChunkBoundaries(n, threads);
40 48 size_t chunk_count = bounds.size() - 1;
41
42
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 ShellSort(vec, bounds, threads);
43
44
1/4
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 48 std::vector<ValType> buffer(n);
45
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 48 times.
 108 for (size_t size = 1; size < chunk_count; size *= 2) {
46
1/2
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
 60 CycleMerge(vec, buffer, bounds, size, threads);
47 vec.swap(buffer);
48 }
49
50
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 GetOutput() = vec;
51 return true;
52 }
53
54 48 bool VasilievMShellSortBatcherMergeSTL::PostProcessingImpl() {
55 48 return true;
56 }
57
58 48 std::vector<size_t> VasilievMShellSortBatcherMergeSTL::ChunkBoundaries(size_t vec_size, int threads) {
59
4/4
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 46 times.
✓ Branch 2 taken 36 times.
✓ Branch 3 taken 12 times.
 50 size_t chunks = std::max(1, std::min(threads, static_cast<int>(vec_size)));
60
61 48 std::vector<size_t> bounds;
62
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 bounds.reserve(chunks + 1);
63
64 48 size_t chunk_size = vec_size / chunks;
65 48 size_t remainder = vec_size % chunks;
66
67
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 bounds.push_back(0);
68
69
2/2
✓ Branch 0 taken 118 times.
✓ Branch 1 taken 48 times.
 166 for (size_t i = 0; i < chunks; i++) {
70
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 88 times.
 118 if (i < remainder) {
71
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 bounds.push_back(bounds.back() + chunk_size + 1);
72 } else {
73
1/4
✓ Branch 1 taken 88 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 88 bounds.push_back(bounds.back() + chunk_size);
74 }
75 }
76 48 return bounds;
77 }
78
79
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 void VasilievMShellSortBatcherMergeSTL::ShellSort(std::vector<ValType> &vec, std::vector<size_t> &bounds,
80 size_t num_threads) {
81
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 const size_t chunk_count = bounds.size() - 1;
82 const size_t worker_count = std::min(chunk_count, num_threads);
83 48 std::vector<std::thread> threads;
84
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 threads.reserve(worker_count);
85
86 48 const size_t base = chunk_count / worker_count;
87 48 const size_t rem = chunk_count % worker_count;
88 size_t current = 0;
89
2/2
✓ Branch 0 taken 118 times.
✓ Branch 1 taken 48 times.
 166 for (size_t thread_id = 0; thread_id < worker_count; thread_id++) {
90
1/2
✓ Branch 0 taken 118 times.
✗ Branch 1 not taken.
 118 const size_t count = base + (thread_id < rem ? 1 : 0);
91 const size_t begin = current;
92 118 const size_t end = current + count;
93 current = end;
94
95
1/2
✓ Branch 1 taken 118 times.
✗ Branch 2 not taken.
 118 threads.emplace_back([&, begin, end]() {
96
2/2
✓ Branch 0 taken 118 times.
✓ Branch 1 taken 118 times.
 236 for (size_t chunk = begin; chunk < end; chunk++) {
97 118 ShellSortChunk(vec, bounds[chunk], bounds[chunk + 1]);
98 }
99 118 });
100 }
101
102
2/2
✓ Branch 0 taken 118 times.
✓ Branch 1 taken 48 times.
 166 for (auto &th : threads) {
103
1/2
✓ Branch 0 taken 118 times.
✗ Branch 1 not taken.
 118 if (th.joinable()) {
104
1/2
✓ Branch 1 taken 118 times.
✗ Branch 2 not taken.
 118 th.join();
105 }
106 }
107 48 }
108
109
1/2
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
 60 void VasilievMShellSortBatcherMergeSTL::CycleMerge(std::vector<ValType> &vec, std::vector<ValType> &buffer,
110 std::vector<size_t> &bounds, size_t size, size_t num_threads) {
111 60 const size_t chunk_count = bounds.size() - 1;
112
1/2
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
 60 const size_t merge_count = (chunk_count + (2 * size) - 1) / (2 * size);
113 const size_t worker_count = std::min(merge_count, num_threads);
114 60 std::vector<std::thread> threads;
115
1/2
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
 60 threads.reserve(worker_count);
116
117 60 const size_t base = merge_count / worker_count;
118 60 const size_t rem = merge_count % worker_count;
119 size_t current = 0;
120
2/2
✓ Branch 0 taken 84 times.
✓ Branch 1 taken 60 times.
 144 for (size_t thread_id = 0; thread_id < worker_count; thread_id++) {
121
1/2
✓ Branch 0 taken 84 times.
✗ Branch 1 not taken.
 84 const size_t count = base + (thread_id < rem ? 1 : 0);
122 const size_t begin = current;
123 84 const size_t end = current + count;
124 current = end;
125
126
1/2
✓ Branch 1 taken 84 times.
✗ Branch 2 not taken.
 84 threads.emplace_back([&, begin, end]() {
127
2/2
✓ Branch 0 taken 84 times.
✓ Branch 1 taken 84 times.
 168 for (size_t idx = begin; idx < end; idx++) {
128 84 const size_t l = idx * 2 * size;
129
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 84 times.
 84 const size_t mid = std::min(l + size, chunk_count);
130
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 56 times.
 84 const size_t r = std::min(l + (2 * size), chunk_count);
131
132 84 const size_t start = bounds[l];
133 84 const size_t middle = bounds[mid];
134 84 const size_t end_pos = bounds[r];
135 84 MergeChunks(vec, buffer, start, middle, end_pos);
136 }
137 84 });
138 }
139
140
2/2
✓ Branch 0 taken 84 times.
✓ Branch 1 taken 60 times.
 144 for (auto &th : threads) {
141
1/2
✓ Branch 0 taken 84 times.
✗ Branch 1 not taken.
 84 if (th.joinable()) {
142
1/2
✓ Branch 1 taken 84 times.
✗ Branch 2 not taken.
 84 th.join();
143 }
144 }
145 60 }
146
147 70 std::vector<ValType> VasilievMShellSortBatcherMergeSTL::BatcherMerge(std::vector<ValType> &l, std::vector<ValType> &r) {
148 70 std::vector<ValType> even_l;
149 70 std::vector<ValType> odd_l;
150 70 std::vector<ValType> even_r;
151 70 std::vector<ValType> odd_r;
152
153
1/2
✓ Branch 1 taken 70 times.
✗ Branch 2 not taken.
 70 SplitEvenOdd(l, even_l, odd_l);
154
1/2
✓ Branch 1 taken 70 times.
✗ Branch 2 not taken.
 70 SplitEvenOdd(r, even_r, odd_r);
155
156
1/2
✓ Branch 1 taken 70 times.
✗ Branch 2 not taken.
 70 std::vector<ValType> even = Merge(even_l, even_r);
157
1/2
✓ Branch 1 taken 70 times.
✗ Branch 2 not taken.
 70 std::vector<ValType> odd = Merge(odd_l, odd_r);
158
159
1/2
✓ Branch 1 taken 70 times.
✗ Branch 2 not taken.
 70 std::vector<ValType> res;
160
1/2
✓ Branch 1 taken 70 times.
✗ Branch 2 not taken.
 70 res.reserve(l.size() + r.size());
161
162
3/4
✓ Branch 0 taken 70 times.
✓ Branch 1 taken 230 times.
✓ Branch 2 taken 70 times.
✗ Branch 3 not taken.
 300 for (size_t i = 0; i < even.size() || i < odd.size(); i++) {
163
1/2
✓ Branch 0 taken 230 times.
✗ Branch 1 not taken.
 230 if (i < even.size()) {
164 res.push_back(even[i]);
165 }
166
2/2
✓ Branch 0 taken 164 times.
✓ Branch 1 taken 66 times.
 230 if (i < odd.size()) {
167 res.push_back(odd[i]);
168 }
169 }
170
171
2/2
✓ Branch 0 taken 136 times.
✓ Branch 1 taken 70 times.
 206 for (size_t i = 1; i + 1 < res.size(); i += 2) {
172
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 72 times.
 136 if (res[i] > res[i + 1]) {
173 std::swap(res[i], res[i + 1]);
174 }
175 }
176
177 70 return res;
178 }
179
180 140 void VasilievMShellSortBatcherMergeSTL::SplitEvenOdd(std::vector<ValType> &vec, std::vector<ValType> &even,
181 std::vector<ValType> &odd) {
182 140 even.reserve(even.size() + (vec.size() / 2) + 1);
183 140 odd.reserve(odd.size() + (vec.size() / 2));
184
185
2/2
✓ Branch 0 taken 230 times.
✓ Branch 1 taken 140 times.
 370 for (size_t i = 0; i < vec.size(); i += 2) {
186 even.push_back(vec[i]);
187
2/2
✓ Branch 0 taken 164 times.
✓ Branch 1 taken 66 times.
 230 if (i + 1 < vec.size()) {
188 odd.push_back(vec[i + 1]);
189 }
190 }
191 140 }
192
193 140 std::vector<ValType> VasilievMShellSortBatcherMergeSTL::Merge(std::vector<ValType> &a, std::vector<ValType> &b) {
194
1/2
✓ Branch 1 taken 140 times.
✗ Branch 2 not taken.
 140 std::vector<ValType> merged;
195
1/2
✓ Branch 1 taken 140 times.
✗ Branch 2 not taken.
 140 merged.reserve(a.size() + b.size());
196 size_t i = 0;
197 size_t j = 0;
198
4/4
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 300 times.
✓ Branch 2 taken 68 times.
✓ Branch 3 taken 232 times.
 372 while (i < a.size() && j < b.size()) {
199
2/2
✓ Branch 0 taken 146 times.
✓ Branch 1 taken 86 times.
 232 if (a[i] <= b[j]) {
200
1/2
✓ Branch 0 taken 146 times.
✗ Branch 1 not taken.
 146 merged.push_back(a[i++]);
201 } else {
202
1/2
✓ Branch 0 taken 86 times.
✗ Branch 1 not taken.
 86 merged.push_back(b[j++]);
203 }
204 }
205
206
2/2
✓ Branch 0 taken 82 times.
✓ Branch 1 taken 140 times.
 222 while (i < a.size()) {
207
1/2
✓ Branch 0 taken 82 times.
✗ Branch 1 not taken.
 82 merged.push_back(a[i++]);
208 }
209
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 140 times.
 220 while (j < b.size()) {
210
1/2
✓ Branch 0 taken 80 times.
✗ Branch 1 not taken.
 80 merged.push_back(b[j++]);
211 }
212
213 140 return merged;
214 }
215
216 118 void VasilievMShellSortBatcherMergeSTL::ShellSortChunk(std::vector<ValType> &vec, size_t first, size_t last) {
217 118 size_t n = last - first;
218
219
2/2
✓ Branch 0 taken 124 times.
✓ Branch 1 taken 118 times.
 242 for (size_t gap = n / 2; gap > 0; gap /= 2) {
220
2/2
✓ Branch 0 taken 342 times.
✓ Branch 1 taken 124 times.
 466 for (size_t i = first + gap; i < last; i++) {
221 342 ValType tmp = vec[i];
222 size_t j = i;
223
4/4
✓ Branch 0 taken 426 times.
✓ Branch 1 taken 72 times.
✓ Branch 2 taken 156 times.
✓ Branch 3 taken 270 times.
 498 while (j >= first + gap && vec[j - gap] > tmp) {
224 156 vec[j] = vec[j - gap];
225 j -= gap;
226 }
227 342 vec[j] = tmp;
228 }
229 }
230 118 }
231
232 84 void VasilievMShellSortBatcherMergeSTL::MergeChunks(std::vector<ValType> &vec, std::vector<ValType> &buffer,
233 size_t start, size_t middle, size_t end_pos) {
234
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 70 times.
 84 if (middle == end_pos) {
235 14 std::copy(vec.begin() + static_cast<std::ptrdiff_t>(start), vec.begin() + static_cast<std::ptrdiff_t>(end_pos),
236 buffer.begin() + static_cast<std::ptrdiff_t>(start));
237 14 return;
238 }
239 std::vector<ValType> l_vect(vec.begin() + static_cast<std::ptrdiff_t>(start),
240
1/2
✓ Branch 2 taken 70 times.
✗ Branch 3 not taken.
 70 vec.begin() + static_cast<std::ptrdiff_t>(middle));
241 std::vector<ValType> r_vect(vec.begin() + static_cast<std::ptrdiff_t>(middle),
242
1/4
✓ Branch 1 taken 70 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 70 vec.begin() + static_cast<std::ptrdiff_t>(end_pos));
243
244
1/2
✓ Branch 1 taken 70 times.
✗ Branch 2 not taken.
 70 std::vector<ValType> merged = BatcherMerge(l_vect, r_vect);
245
2/2
✓ Branch 0 taken 394 times.
✓ Branch 1 taken 70 times.
 464 for (size_t i = 0; i < merged.size(); i++) {
246 394 buffer[start + i] = merged[i];
247 }
248 }
249
250 } // namespace vasiliev_m_shell_sort_batcher_merge
251