GCC Code Coverage Report

Directory: ./
File: tasks/zenin_a_radix_sort_double_batcher_merge/stl/src/ops_stl.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 83 90 92.2%
Functions: 9 12 75.0%
Branches: 73 112 65.2%
Line Branch Exec Source
1 #include "zenin_a_radix_sort_double_batcher_merge/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <cstdint>
6 #include <cstring>
7 #include <limits>
8 #include <thread>
9 #include <utility>
10 #include <vector>
11
12 #include "util/include/util.hpp"
13 #include "zenin_a_radix_sort_double_batcher_merge/common/include/common.hpp"
14
15 namespace zenin_a_radix_sort_double_batcher_merge {
16
17
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 ZeninARadixSortDoubleBatcherMergeSTL::ZeninARadixSortDoubleBatcherMergeSTL(const InType &in) {
18 SetTypeOfTask(GetStaticTypeOfTask());
19
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 GetInput() = in;
20 GetOutput() = {};
21 96 }
22
23 96 bool ZeninARadixSortDoubleBatcherMergeSTL::ValidationImpl() {
24 96 return true;
25 }
26
27 96 bool ZeninARadixSortDoubleBatcherMergeSTL::PreProcessingImpl() {
28 96 return true;
29 }
30
31 ✗ void ZeninARadixSortDoubleBatcherMergeSTL::BlocksComparing(std::vector<double> &arr, size_t i, size_t j) {
32
4/6
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 200 times.
✓ Branch 2 taken 32 times.
✓ Branch 3 taken 240 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 592 if (arr[i] > arr[j]) {
33 std::swap(arr[i], arr[j]);
34 }
35 ✗ }
36
37 ✗ uint64_t ZeninARadixSortDoubleBatcherMergeSTL::PackDouble(double v) noexcept {
38 uint64_t bits = 0ULL;
39 std::memcpy(&bits, &v, sizeof(bits));
40
2/4
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 432 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 512 if ((bits & (1ULL << 63)) != 0ULL) {
41 80 bits = ~bits;
42 } else {
43 432 bits ^= (1ULL << 63);
44 }
45 ✗ return bits;
46 }
47
48 ✗ double ZeninARadixSortDoubleBatcherMergeSTL::UnpackDouble(uint64_t k) noexcept {
49 ✗ if ((k & (1ULL << 63)) != 0ULL) {
50 432 k ^= (1ULL << 63);
51 } else {
52 80 k = ~k;
53 }
54 double v = 0.0;
55 std::memcpy(&v, &k, sizeof(v));
56 ✗ return v;
57 }
58
59
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 128 times.
 160 void ZeninARadixSortDoubleBatcherMergeSTL::LSDRadixSort(std::vector<double> &array) {
60 const std::size_t n = array.size();
61
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 128 times.
 160 if (n <= 1U) {
62 32 return;
63 }
64
65 constexpr int kBits = 8;
66 constexpr int kBuckets = 1 << kBits;
67 constexpr int kPasses = static_cast<int>((sizeof(uint64_t) * 8) / kBits);
68
69 128 std::vector<uint64_t> keys;
70
1/2
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
 128 keys.resize(n);
71
2/2
✓ Branch 0 taken 512 times.
✓ Branch 1 taken 128 times.
 640 for (std::size_t i = 0; i < n; ++i) {
72
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 432 times.
 1024 keys[i] = PackDouble(array[i]);
73 }
74
75 128 std::vector<uint64_t> tmp_keys;
76
1/2
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
 128 tmp_keys.resize(n);
77 128 std::vector<double> tmp_vals;
78
1/2
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
 128 tmp_vals.resize(n);
79
80
2/2
✓ Branch 0 taken 1024 times.
✓ Branch 1 taken 128 times.
 1152 for (int pass = 0; pass < kPasses; ++pass) {
81 1024 int shift = pass * kBits;
82 1024 std::vector<std::size_t> cnt;
83
1/4
✓ Branch 1 taken 1024 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 1024 cnt.assign(kBuckets + 1, 0U);
84
85
2/2
✓ Branch 0 taken 4096 times.
✓ Branch 1 taken 1024 times.
 5120 for (std::size_t i = 0; i < n; ++i) {
86 4096 auto d = static_cast<std::size_t>((keys[i] >> shift) & (kBuckets - 1));
87 4096 ++cnt[d + 1];
88 }
89
2/2
✓ Branch 0 taken 262144 times.
✓ Branch 1 taken 1024 times.
 263168 for (int i = 0; i < kBuckets; ++i) {
90 262144 cnt[i + 1] += cnt[i];
91 }
92
93
2/2
✓ Branch 0 taken 4096 times.
✓ Branch 1 taken 1024 times.
 5120 for (std::size_t i = 0; i < n; ++i) {
94 4096 auto d = static_cast<std::size_t>((keys[i] >> shift) & (kBuckets - 1));
95 4096 std::size_t pos = cnt[d]++;
96 4096 tmp_keys[pos] = keys[i];
97 4096 tmp_vals[pos] = array[i];
98 }
99
100 keys.swap(tmp_keys);
101 array.swap(tmp_vals);
102 }
103
104
2/2
✓ Branch 0 taken 512 times.
✓ Branch 1 taken 128 times.
 640 for (std::size_t i = 0; i < n; ++i) {
105
2/2
✓ Branch 0 taken 432 times.
✓ Branch 1 taken 80 times.
 1024 array[i] = UnpackDouble(keys[i]);
106 }
107 }
108
109 80 void ZeninARadixSortDoubleBatcherMergeSTL::MergeFirstPass(std::vector<double> &arr, size_t po, size_t num_threads) {
110 80 size_t chunk = (po + num_threads - 1) / num_threads;
111 80 std::vector<std::thread> threads;
112
2/2
✓ Branch 0 taken 188 times.
✓ Branch 1 taken 52 times.
 240 for (size_t tid = 0; tid < num_threads; ++tid) {
113 188 size_t lo = tid * chunk;
114
2/2
✓ Branch 0 taken 160 times.
✓ Branch 1 taken 28 times.
 188 size_t hi = std::min(lo + chunk, po);
115
2/2
✓ Branch 0 taken 160 times.
✓ Branch 1 taken 28 times.
 188 if (lo >= hi) {
116 break;
117 }
118
1/2
✓ Branch 1 taken 160 times.
✗ Branch 2 not taken.
 160 threads.emplace_back([&arr, lo, hi, po]() {
119
2/2
✓ Branch 0 taken 272 times.
✓ Branch 1 taken 160 times.
 432 for (size_t i = lo; i < hi; ++i) {
120
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 240 times.
 272 BlocksComparing(arr, i, i + po);
121 }
122 160 });
123 }
124
2/2
✓ Branch 0 taken 160 times.
✓ Branch 1 taken 80 times.
 240 for (auto &th : threads) {
125
1/2
✓ Branch 1 taken 160 times.
✗ Branch 2 not taken.
 160 th.join();
126 }
127 80 }
128
129 80 void ZeninARadixSortDoubleBatcherMergeSTL::BatcherOddEvenMerge(std::vector<double> &arr, size_t n, size_t num_threads) {
130
2/2
✓ Branch 0 taken 208 times.
✓ Branch 1 taken 80 times.
 288 for (size_t po = n / 2; po > 0; po >>= 1) {
131
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 80 times.
 208 if (po == n / 2) {
132 80 MergeFirstPass(arr, po, num_threads);
133 } else {
134
2/2
✓ Branch 0 taken 256 times.
✓ Branch 1 taken 128 times.
 384 for (size_t i = po; i < n - po; i += 2 * po) {
135
2/2
✓ Branch 0 taken 320 times.
✓ Branch 1 taken 256 times.
 576 for (size_t j = 0; j < po; ++j) {
136
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 200 times.
 320 BlocksComparing(arr, i + j, i + j + po);
137 }
138 }
139 }
140 }
141 80 }
142
143 96 bool ZeninARadixSortDoubleBatcherMergeSTL::RunImpl() {
144 96 auto data = GetInput();
145 size_t original_size = data.size();
146
147
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 80 times.
 96 if (original_size <= 1) {
148
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 GetOutput() = data;
149 return true;
150 }
151
152
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 int num_threads_int = ppc::util::GetNumThreads();
153 80 if (num_threads_int <= 0) {
154 num_threads_int = 1;
155 }
156 80 auto num_threads = static_cast<size_t>(num_threads_int);
157
158 size_t pow2 = 1;
159
2/2
✓ Branch 0 taken 208 times.
✓ Branch 1 taken 80 times.
 288 while (pow2 < original_size) {
160 208 pow2 <<= 1;
161 }
162
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 data.resize(pow2, std::numeric_limits<double>::max());
163
164
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 size_t half = pow2 / 2;
165 auto half_dist = static_cast<std::ptrdiff_t>(half);
166
167
2/6
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 80 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 80 std::vector<double> left(data.begin(), data.begin() + half_dist);
168
1/4
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 80 std::vector<double> right(data.begin() + half_dist, data.end());
169
170
1/4
✓ Branch 2 taken 80 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 160 std::thread t([&]() { LSDRadixSort(left); });
171
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 LSDRadixSort(right);
172
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 t.join();
173
174 std::ranges::copy(left, data.begin());
175 std::ranges::copy(right, data.begin() + half_dist);
176
177
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 BatcherOddEvenMerge(data, data.size(), num_threads);
178
179
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 data.resize(original_size);
180
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 GetOutput() = data;
181 return true;
182 }
183
184 96 bool ZeninARadixSortDoubleBatcherMergeSTL::PostProcessingImpl() {
185 96 return true;
186 }
187
188 } // namespace zenin_a_radix_sort_double_batcher_merge
189