GCC Code Coverage Report

Directory: ./
File: tasks/zenin_a_radix_sort_double_batcher_merge/tbb/src/ops_tbb.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 67 74 90.5%
Functions: 8 11 72.7%
Branches: 61 96 63.5%
Line Branch Exec Source
1 #include "zenin_a_radix_sort_double_batcher_merge/tbb/include/ops_tbb.hpp"
2
3 #include <tbb/tbb.h>
4
5 #include <algorithm>
6 #include <cstddef>
7 #include <cstdint>
8 #include <cstring>
9 #include <limits>
10 #include <utility>
11 #include <vector>
12
13 #include "oneapi/tbb/parallel_for.h"
14 #include "zenin_a_radix_sort_double_batcher_merge/common/include/common.hpp"
15
16 namespace zenin_a_radix_sort_double_batcher_merge {
17
18
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 ZeninARadixSortDoubleBatcherMergeTBB::ZeninARadixSortDoubleBatcherMergeTBB(const InType &in) {
19 SetTypeOfTask(GetStaticTypeOfTask());
20
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 GetInput() = in;
21 GetOutput() = {};
22 48 }
23
24 48 bool ZeninARadixSortDoubleBatcherMergeTBB::ValidationImpl() {
25 48 return true;
26 }
27
28 48 bool ZeninARadixSortDoubleBatcherMergeTBB::PreProcessingImpl() {
29 48 return true;
30 }
31
32 ✗ void ZeninARadixSortDoubleBatcherMergeTBB::BlocksComparing(std::vector<double> &arr, size_t i, size_t j) {
33
4/6
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 100 times.
✓ Branch 2 taken 16 times.
✓ Branch 3 taken 120 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 296 if (arr[i] > arr[j]) {
34 std::swap(arr[i], arr[j]);
35 }
36 ✗ }
37
38 ✗ uint64_t ZeninARadixSortDoubleBatcherMergeTBB::PackDouble(double v) noexcept {
39 uint64_t bits = 0ULL;
40 std::memcpy(&bits, &v, sizeof(bits));
41
2/4
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 216 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 256 if ((bits & (1ULL << 63)) != 0ULL) {
42 40 bits = ~bits;
43 } else {
44 216 bits ^= (1ULL << 63);
45 }
46 ✗ return bits;
47 }
48
49 ✗ double ZeninARadixSortDoubleBatcherMergeTBB::UnpackDouble(uint64_t k) noexcept {
50 ✗ if ((k & (1ULL << 63)) != 0ULL) {
51 216 k ^= (1ULL << 63);
52 } else {
53 40 k = ~k;
54 }
55 double v = 0.0;
56 std::memcpy(&v, &k, sizeof(v));
57 ✗ return v;
58 }
59
60
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 64 times.
 80 void ZeninARadixSortDoubleBatcherMergeTBB::LSDRadixSort(std::vector<double> &array) {
61 const std::size_t n = array.size();
62
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 64 times.
 80 if (n <= 1U) {
63 16 return;
64 }
65
66 constexpr int kBits = 8;
67 constexpr int kBuckets = 1 << kBits;
68 constexpr int kPasses = static_cast<int>((sizeof(uint64_t) * 8) / kBits);
69
70 64 std::vector<uint64_t> keys;
71
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 keys.resize(n);
72
2/2
✓ Branch 0 taken 256 times.
✓ Branch 1 taken 64 times.
 320 for (std::size_t i = 0; i < n; ++i) {
73
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 216 times.
 512 keys[i] = PackDouble(array[i]);
74 }
75
76 64 std::vector<uint64_t> tmp_keys;
77
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 tmp_keys.resize(n);
78 64 std::vector<double> tmp_vals;
79
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 tmp_vals.resize(n);
80
81
2/2
✓ Branch 0 taken 512 times.
✓ Branch 1 taken 64 times.
 576 for (int pass = 0; pass < kPasses; ++pass) {
82 512 int shift = pass * kBits;
83 512 std::vector<std::size_t> cnt;
84
1/4
✓ Branch 1 taken 512 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 512 cnt.assign(kBuckets + 1, 0U);
85
86
2/2
✓ Branch 0 taken 2048 times.
✓ Branch 1 taken 512 times.
 2560 for (std::size_t i = 0; i < n; ++i) {
87 2048 auto d = static_cast<std::size_t>((keys[i] >> shift) & (kBuckets - 1));
88 2048 ++cnt[d + 1];
89 }
90
2/2
✓ Branch 0 taken 131072 times.
✓ Branch 1 taken 512 times.
 131584 for (int i = 0; i < kBuckets; ++i) {
91 131072 cnt[i + 1] += cnt[i];
92 }
93
94
2/2
✓ Branch 0 taken 2048 times.
✓ Branch 1 taken 512 times.
 2560 for (std::size_t i = 0; i < n; ++i) {
95 2048 auto d = static_cast<std::size_t>((keys[i] >> shift) & (kBuckets - 1));
96 2048 std::size_t pos = cnt[d]++;
97 2048 tmp_keys[pos] = keys[i];
98 2048 tmp_vals[pos] = array[i];
99 }
100
101 keys.swap(tmp_keys);
102 array.swap(tmp_vals);
103 }
104
105
2/2
✓ Branch 0 taken 256 times.
✓ Branch 1 taken 64 times.
 320 for (std::size_t i = 0; i < n; ++i) {
106
2/2
✓ Branch 0 taken 216 times.
✓ Branch 1 taken 40 times.
 512 array[i] = UnpackDouble(keys[i]);
107 }
108 }
109
110 40 void ZeninARadixSortDoubleBatcherMergeTBB::BatcherOddEvenMerge(std::vector<double> &arr, size_t n) {
111
2/2
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 40 times.
 144 for (size_t po = n / 2; po > 0; po >>= 1) {
112
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 40 times.
 104 if (po == n / 2) {
113 176 tbb::parallel_for(tbb::blocked_range<size_t>(0, po), [&](const tbb::blocked_range<size_t> &r) {
114
2/2
✓ Branch 0 taken 136 times.
✓ Branch 1 taken 136 times.
 272 for (size_t i = r.begin(); i < r.end(); ++i) {
115
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 120 times.
 136 BlocksComparing(arr, i, i + po);
116 }
117 136 });
118 } else {
119
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 64 times.
 192 for (size_t i = po; i < n - po; i += 2 * po) {
120
2/2
✓ Branch 0 taken 160 times.
✓ Branch 1 taken 128 times.
 288 for (size_t j = 0; j < po; ++j) {
121
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 100 times.
 160 BlocksComparing(arr, i + j, i + j + po);
122 }
123 }
124 }
125 }
126 40 }
127
128 48 bool ZeninARadixSortDoubleBatcherMergeTBB::RunImpl() {
129 48 auto data = GetInput();
130 size_t original_size = data.size();
131
132
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 40 times.
 48 if (original_size <= 1) {
133
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 GetOutput() = data;
134 return true;
135 }
136
137 size_t pow2 = 1;
138
2/2
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 40 times.
 144 while (pow2 < original_size) {
139 104 pow2 <<= 1;
140 }
141
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 data.resize(pow2, std::numeric_limits<double>::max());
142
143
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 size_t half = pow2 / 2;
144 auto half_dist = static_cast<std::ptrdiff_t>(half);
145
146
2/6
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 40 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 40 std::vector<double> left(data.begin(), data.begin() + half_dist);
147
1/4
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 40 std::vector<double> right(data.begin() + half_dist, data.end());
148
149
2/6
✓ Branch 3 taken 40 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 40 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 160 tbb::parallel_invoke([&]() { LSDRadixSort(left); }, [&]() { LSDRadixSort(right); });
150
151 std::ranges::copy(left, data.begin());
152 std::ranges::copy(right, data.begin() + half_dist);
153
154
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 BatcherOddEvenMerge(data, data.size());
155
156
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 data.resize(original_size);
157
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 GetOutput() = data;
158 return true;
159 }
160
161 48 bool ZeninARadixSortDoubleBatcherMergeTBB::PostProcessingImpl() {
162 48 return true;
163 }
164
165 } // namespace zenin_a_radix_sort_double_batcher_merge
166