GCC Code Coverage Report

Directory: ./
File: tasks/titaev_m_sortirovka_betchera/stl/src/ops_stl.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 72 114 63.2%
Functions: 13 17 76.5%
Branches: 53 120 44.2%
Line Branch Exec Source
1 #include "titaev_m_sortirovka_betchera/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <cstdint>
6 #include <cstring>
7 #include <functional>
8 #include <thread>
9 #include <vector>
10
11 #include "titaev_m_sortirovka_betchera/common/include/common.hpp"
12
13 namespace titaev_m_sortirovka_betchera {
14
15 namespace {
16
17 constexpr int kBits = 8;
18 constexpr int kBuckets = 1 << kBits;
19 constexpr int kPasses = 64 / kBits;
20 constexpr std::size_t kSequentialThreshold = 1 << 16;
21
22 uint64_t DoubleToOrderedUint(double value) {
23 uint64_t bits = 0;
24 std::memcpy(&bits, &value, sizeof(double));
25 constexpr uint64_t kSignMask = (1ULL << 63);
26
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1352 times.
 1352 if ((bits & kSignMask) != 0ULL) {
27 ✗ bits = ~bits;
28 } else {
29 1352 bits ^= kSignMask;
30 }
31 return bits;
32 }
33
34 double OrderedUintToDouble(uint64_t bits) {
35 constexpr uint64_t kSignMask = (1ULL << 63);
36
1/2
✓ Branch 0 taken 1352 times.
✗ Branch 1 not taken.
 1352 if ((bits & kSignMask) != 0ULL) {
37 1352 bits ^= kSignMask;
38 } else {
39 ✗ bits = ~bits;
40 }
41 double result = 0.0;
42 std::memcpy(&result, &bits, sizeof(double));
43 return result;
44 }
45
46 unsigned int GetThreadCount() {
47 ✗ const unsigned int hw = std::thread::hardware_concurrency();
48 ✗ return hw == 0 ? 1U : hw;
49 }
50
51 392 void RunInParallel(std::size_t total, const std::function<void(std::size_t, std::size_t)> &body) {
52
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 392 times.
 392 const unsigned int num_threads = (total < kSequentialThreshold) ? 1U : GetThreadCount();
53
54 ✗ if (num_threads <= 1) {
55 392 body(0, total);
56 392 return;
57 }
58
59 ✗ std::vector<std::thread> threads;
60 ✗ threads.reserve(num_threads);
61 ✗ const std::size_t chunk = (total + num_threads - 1) / num_threads;
62
63 ✗ for (unsigned int thr = 0; thr < num_threads; thr++) {
64 ✗ const std::size_t begin = thr * chunk;
65 ✗ const std::size_t end = std::min(begin + chunk, total);
66 ✗ if (begin >= end) {
67 break;
68 }
69 ✗ threads.emplace_back([&body, begin, end]() { body(begin, end); });
70 }
71 ✗ for (auto &th : threads) {
72 ✗ th.join();
73 }
74 ✗ }
75
76 } // namespace
77
78
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 TitaevSortirovkaBetcheraSTL::TitaevSortirovkaBetcheraSTL(const InType &in) {
79 SetTypeOfTask(GetStaticTypeOfTask());
80
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 GetInput() = in;
81 GetOutput().clear();
82 64 }
83
84 64 bool TitaevSortirovkaBetcheraSTL::ValidationImpl() {
85 64 return !GetInput().empty();
86 }
87
88 64 bool TitaevSortirovkaBetcheraSTL::PreProcessingImpl() {
89 64 GetOutput() = GetInput();
90 64 return true;
91 }
92
93
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 void TitaevSortirovkaBetcheraSTL::ConvertToKeys(const InType &input, std::vector<uint64_t> &keys) {
94
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 RunInParallel(input.size(), [&input, &keys](std::size_t begin, std::size_t end) {
95
2/2
✓ Branch 0 taken 1352 times.
✓ Branch 1 taken 56 times.
 1408 for (std::size_t i = begin; i < end; i++) {
96
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1352 times.
 2704 keys[i] = DoubleToOrderedUint(input[i]);
97 }
98 });
99 56 }
100
101 ✗ void TitaevSortirovkaBetcheraSTL::CountSequential(const std::vector<uint64_t> &keys, std::vector<std::size_t> &count,
102 int pass) {
103 const std::size_t n = keys.size();
104
2/4
✓ Branch 0 taken 10816 times.
✓ Branch 1 taken 448 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 11264 for (std::size_t i = 0; i < n; i++) {
105 10816 const std::size_t bucket = (keys[i] >> (pass * kBits)) & (kBuckets - 1);
106 10816 count[bucket]++;
107 }
108 ✗ }
109
110 ✗ void TitaevSortirovkaBetcheraSTL::CountParallel(const std::vector<uint64_t> &keys, std::vector<std::size_t> &count,
111 int pass, unsigned int num_threads) {
112 ✗ const std::size_t n = keys.size();
113 ✗ std::vector<std::vector<std::size_t>> local_count(num_threads, std::vector<std::size_t>(kBuckets, 0));
114 ✗ const std::size_t chunk = (n + num_threads - 1) / num_threads;
115
116 ✗ std::vector<std::thread> threads;
117 ✗ threads.reserve(num_threads);
118 ✗ for (unsigned int thr = 0; thr < num_threads; thr++) {
119 ✗ const std::size_t begin = thr * chunk;
120 ✗ const std::size_t end = std::min(begin + chunk, n);
121 ✗ if (begin >= end) {
122 break;
123 }
124 ✗ threads.emplace_back([&keys, &local_count, thr, begin, end, pass]() {
125 ✗ auto &lc = local_count[thr];
126 ✗ for (std::size_t i = begin; i < end; i++) {
127 ✗ const std::size_t bucket = (keys[i] >> (pass * kBits)) & (kBuckets - 1);
128 ✗ lc[bucket]++;
129 }
130 ✗ });
131 }
132 ✗ for (auto &th : threads) {
133 ✗ th.join();
134 }
135
136 ✗ for (int bucket_idx = 0; bucket_idx < kBuckets; bucket_idx++) {
137 ✗ for (unsigned int thr = 0; thr < num_threads; thr++) {
138 ✗ count[bucket_idx] += local_count[thr][bucket_idx];
139 }
140 }
141 ✗ }
142
143
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 448 times.
 448 void TitaevSortirovkaBetcheraSTL::RadixCountPass(std::vector<uint64_t> &keys, std::vector<uint64_t> &tmp, int pass) {
144 const std::size_t n = keys.size();
145
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 448 times.
 448 const unsigned int num_threads = (n < kSequentialThreshold) ? 1U : GetThreadCount();
146
147 448 std::vector<std::size_t> count(kBuckets, 0);
148
1/2
✓ Branch 0 taken 448 times.
✗ Branch 1 not taken.
 448 if (num_threads <= 1) {
149 CountSequential(keys, count, pass);
150 } else {
151 ✗ CountParallel(keys, count, pass, num_threads);
152 }
153
154
2/2
✓ Branch 0 taken 114240 times.
✓ Branch 1 taken 448 times.
 114688 for (int i = 1; i < kBuckets; i++) {
155 114240 count[i] += count[i - 1];
156 }
157
2/2
✓ Branch 0 taken 10816 times.
✓ Branch 1 taken 448 times.
 11264 for (std::size_t i = n; i-- > 0;) {
158 10816 const std::size_t bucket = (keys[i] >> (pass * kBits)) & (kBuckets - 1);
159 10816 tmp[--count[bucket]] = keys[i];
160 }
161 keys.swap(tmp);
162 448 }
163
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 56 times.
 56 void TitaevSortirovkaBetcheraSTL::RadixSort(std::vector<uint64_t> &keys) {
164 const std::size_t n = keys.size();
165
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 56 times.
 56 if (n <= 1) {
166 ✗ return;
167 }
168 56 std::vector<uint64_t> tmp(n);
169
2/2
✓ Branch 0 taken 448 times.
✓ Branch 1 taken 56 times.
 504 for (int pass = 0; pass < kPasses; pass++) {
170
1/2
✓ Branch 1 taken 448 times.
✗ Branch 2 not taken.
 448 RadixCountPass(keys, tmp, pass);
171 }
172 }
173
174 56 void TitaevSortirovkaBetcheraSTL::ConvertFromKeys(const std::vector<uint64_t> &keys, OutType &output) {
175 56 output.resize(keys.size());
176
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 RunInParallel(keys.size(), [&keys, &output](std::size_t begin, std::size_t end) {
177
2/2
✓ Branch 0 taken 1352 times.
✓ Branch 1 taken 56 times.
 1408 for (std::size_t i = begin; i < end; i++) {
178
1/2
✓ Branch 0 taken 1352 times.
✗ Branch 1 not taken.
 2704 output[i] = OrderedUintToDouble(keys[i]);
179 }
180 });
181 56 }
182
183 280 void TitaevSortirovkaBetcheraSTL::BatcherStage(OutType &result, std::size_t array_size, std::size_t block,
184 std::size_t step) {
185
1/2
✓ Branch 2 taken 280 times.
✗ Branch 3 not taken.
 280 RunInParallel(array_size, [&result, block, step](std::size_t begin, std::size_t end) {
186
2/2
✓ Branch 0 taken 5616 times.
✓ Branch 1 taken 280 times.
 5896 for (std::size_t i = begin; i < end; i++) {
187 5616 const std::size_t partner = i ^ step;
188
2/2
✓ Branch 0 taken 2808 times.
✓ Branch 1 taken 2808 times.
 5616 if (partner <= i) {
189 2808 continue;
190 }
191 2808 const bool ascending = ((i & block) == 0);
192
2/2
✓ Branch 0 taken 1920 times.
✓ Branch 1 taken 888 times.
 2808 const bool need_swap = ascending ? (result[i] > result[partner]) : (result[i] < result[partner]);
193
2/2
✓ Branch 0 taken 1280 times.
✓ Branch 1 taken 1528 times.
 2808 if (need_swap) {
194 1280 std::swap(result[i], result[partner]);
195 }
196 }
197 280 });
198 280 }
199
200
1/2
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
 40 void TitaevSortirovkaBetcheraSTL::BatcherSort() {
201 auto &result = GetOutput();
202 const std::size_t n = result.size();
203
1/2
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
 40 if (n < 2) {
204 return;
205 }
206
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 40 times.
 160 for (std::size_t block = 2; block <= n; block <<= 1) {
207
2/2
✓ Branch 0 taken 280 times.
✓ Branch 1 taken 120 times.
 400 for (std::size_t step = block >> 1; step > 0; step >>= 1) {
208 280 BatcherStage(result, n, block, step);
209 }
210 }
211 }
212
213
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 8 times.
 64 bool TitaevSortirovkaBetcheraSTL::RunImpl() {
214 auto &input = GetInput();
215 const std::size_t n = input.size();
216
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 8 times.
 64 if (n <= 1) {
217 return true;
218 }
219 56 std::vector<uint64_t> keys(n);
220
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 ConvertToKeys(input, keys);
221
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 RadixSort(keys);
222
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 ConvertFromKeys(keys, GetOutput());
223
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 16 times.
 56 if ((n & (n - 1)) == 0) {
224
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 BatcherSort();
225 }
226 return true;
227 }
228
229 64 bool TitaevSortirovkaBetcheraSTL::PostProcessingImpl() {
230 64 return true;
231 }
232
233 } // namespace titaev_m_sortirovka_betchera
234