GCC Code Coverage Report

Directory: ./
File: tasks/titaev_m_sortirovka_betchera/tbb/src/ops_tbb.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 63 68 92.6%
Functions: 10 11 90.9%
Branches: 53 74 71.6%
Line Branch Exec Source
1 #include "titaev_m_sortirovka_betchera/tbb/include/ops_tbb.hpp"
2
3 #include <oneapi/tbb/blocked_range.h>
4 #include <oneapi/tbb/parallel_for.h>
5
6 #include <algorithm>
7 #include <cstdint>
8 #include <cstring>
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 uint64_t DoubleToOrderedUint(double value) {
18 uint64_t bits = 0;
19 std::memcpy(&bits, &value, sizeof(double));
20 constexpr uint64_t kSignMask = (1ULL << 63);
21
2/4
✗ Branch 0 not taken.
✓ Branch 1 taken 292 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 384 times.
 676 if ((bits & kSignMask) != 0ULL) {
22 ✗ bits = ~bits;
23 } else {
24 676 bits ^= kSignMask;
25 }
26 return bits;
27 }
28
29 double OrderedUintToDouble(uint64_t bits) {
30 constexpr uint64_t kSignMask = (1ULL << 63);
31
2/4
✓ Branch 0 taken 292 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 384 times.
✗ Branch 3 not taken.
 676 if ((bits & kSignMask) != 0ULL) {
32 676 bits ^= kSignMask;
33 } else {
34 ✗ bits = ~bits;
35 }
36 double result = 0.0;
37 std::memcpy(&result, &bits, sizeof(double));
38 return result;
39 }
40
41 } // namespace
42
43
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 TitaevSortirovkaBetcheraTBB::TitaevSortirovkaBetcheraTBB(const InType &in) {
44 SetTypeOfTask(GetStaticTypeOfTask());
45
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 GetInput() = in;
46 GetOutput().clear();
47 32 }
48
49 32 bool TitaevSortirovkaBetcheraTBB::ValidationImpl() {
50 32 return !GetInput().empty();
51 }
52
53 32 bool TitaevSortirovkaBetcheraTBB::PreProcessingImpl() {
54 32 GetOutput() = GetInput();
55 32 return true;
56 }
57
58 28 void TitaevSortirovkaBetcheraTBB::ConvertToKeys(const InType &input, std::vector<uint64_t> &keys) {
59 const std::size_t n = input.size();
60 28 oneapi::tbb::parallel_for(oneapi::tbb::blocked_range<std::size_t>(0, n),
61 28 [&input, &keys](const oneapi::tbb::blocked_range<std::size_t> &range) {
62
4/4
✓ Branch 0 taken 292 times.
✓ Branch 1 taken 292 times.
✓ Branch 2 taken 384 times.
✓ Branch 3 taken 384 times.
 1352 for (std::size_t i = range.begin(); i < range.end(); i++) {
63
2/4
✗ Branch 0 not taken.
✓ Branch 1 taken 292 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 384 times.
 1352 keys[i] = DoubleToOrderedUint(input[i]);
64 }
65 });
66 28 }
67
68
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 28 times.
 28 void TitaevSortirovkaBetcheraTBB::RadixSort(std::vector<uint64_t> &keys) {
69 const std::size_t n = keys.size();
70
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 28 times.
 28 if (n <= 1) {
71 ✗ return;
72 }
73
74 constexpr int kBits = 8;
75 constexpr int kBuckets = 1 << kBits;
76 constexpr int kPasses = 64 / kBits;
77
78 28 std::vector<uint64_t> tmp(n);
79
80
2/2
✓ Branch 0 taken 224 times.
✓ Branch 1 taken 28 times.
 252 for (int pass = 0; pass < kPasses; pass++) {
81
1/4
✓ Branch 1 taken 224 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 224 std::vector<std::size_t> count(kBuckets, 0);
82
2/2
✓ Branch 0 taken 5408 times.
✓ Branch 1 taken 224 times.
 5632 for (std::size_t i = 0; i < n; i++) {
83 5408 const std::size_t bucket = (keys[i] >> (pass * kBits)) & (kBuckets - 1);
84 5408 count[bucket]++;
85 }
86
2/2
✓ Branch 0 taken 57120 times.
✓ Branch 1 taken 224 times.
 57344 for (int i = 1; i < kBuckets; i++) {
87 57120 count[i] += count[i - 1];
88 }
89
2/2
✓ Branch 0 taken 5408 times.
✓ Branch 1 taken 224 times.
 5632 for (std::size_t i = n; i-- > 0;) {
90 5408 const std::size_t bucket = (keys[i] >> (pass * kBits)) & (kBuckets - 1);
91 5408 tmp[--count[bucket]] = keys[i];
92 }
93 keys.swap(tmp);
94 }
95 }
96
97 28 void TitaevSortirovkaBetcheraTBB::ConvertFromKeys(const std::vector<uint64_t> &keys, OutType &output) {
98 const std::size_t n = keys.size();
99 28 output.resize(n);
100 28 oneapi::tbb::parallel_for(oneapi::tbb::blocked_range<std::size_t>(0, n),
101 28 [&keys, &output](const oneapi::tbb::blocked_range<std::size_t> &range) {
102
4/4
✓ Branch 0 taken 292 times.
✓ Branch 1 taken 292 times.
✓ Branch 2 taken 384 times.
✓ Branch 3 taken 384 times.
 1352 for (std::size_t i = range.begin(); i < range.end(); i++) {
103
2/4
✓ Branch 0 taken 292 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 384 times.
✗ Branch 3 not taken.
 1352 output[i] = OrderedUintToDouble(keys[i]);
104 }
105 });
106 28 }
107
108 ✗ void TitaevSortirovkaBetcheraTBB::BatcherStage(OutType &result, std::size_t array_size, std::size_t block,
109 std::size_t step) {
110 140 oneapi::tbb::parallel_for(oneapi::tbb::blocked_range<std::size_t>(0, array_size),
111 2948 [&result, block, step](const oneapi::tbb::blocked_range<std::size_t> &range) {
112
2/2
✓ Branch 0 taken 2808 times.
✓ Branch 1 taken 2808 times.
 5616 for (std::size_t i = range.begin(); i < range.end(); i++) {
113 2808 const std::size_t partner = i ^ step;
114
2/2
✓ Branch 0 taken 1404 times.
✓ Branch 1 taken 1404 times.
 2808 if (partner <= i) {
115 1404 continue;
116 }
117 1404 const bool ascending = ((i & block) == 0);
118
2/2
✓ Branch 0 taken 960 times.
✓ Branch 1 taken 444 times.
 1404 const bool need_swap = ascending ? (result[i] > result[partner]) : (result[i] < result[partner]);
119
2/2
✓ Branch 0 taken 640 times.
✓ Branch 1 taken 764 times.
 1404 if (need_swap) {
120 640 std::swap(result[i], result[partner]);
121 }
122 }
123 2808 });
124 ✗ }
125
126
1/2
✓ Branch 0 taken 20 times.
✗ Branch 1 not taken.
 20 void TitaevSortirovkaBetcheraTBB::BatcherSort() {
127 auto &result = GetOutput();
128 const std::size_t n = result.size();
129
1/2
✓ Branch 0 taken 20 times.
✗ Branch 1 not taken.
 20 if (n < 2) {
130 return;
131 }
132
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 20 times.
 80 for (std::size_t block = 2; block <= n; block <<= 1) {
133
2/2
✓ Branch 0 taken 140 times.
✓ Branch 1 taken 60 times.
 200 for (std::size_t step = block >> 1; step > 0; step >>= 1) {
134 BatcherStage(result, n, block, step);
135 }
136 }
137 }
138
139
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 4 times.
 32 bool TitaevSortirovkaBetcheraTBB::RunImpl() {
140 auto &input = GetInput();
141 const std::size_t n = input.size();
142
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 4 times.
 32 if (n <= 1) {
143 return true;
144 }
145 28 std::vector<uint64_t> keys(n);
146
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 ConvertToKeys(input, keys);
147
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 RadixSort(keys);
148
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 ConvertFromKeys(keys, GetOutput());
149
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 8 times.
 28 if ((n & (n - 1)) == 0) {
150
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 BatcherSort();
151 }
152 return true;
153 }
154
155 32 bool TitaevSortirovkaBetcheraTBB::PostProcessingImpl() {
156 32 return true;
157 }
158
159 } // namespace titaev_m_sortirovka_betchera
160