GCC Code Coverage Report

Directory: ./
File: tasks/chernov_t_radix_sort/tbb/src/ops_tbb.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 59 62 95.2%
Functions: 8 9 88.9%
Branches: 43 72 59.7%
Line Branch Exec Source
1 #include "chernov_t_radix_sort/tbb/include/ops_tbb.hpp"
2
3 #include <tbb/combinable.h>
4 #include <tbb/parallel_for.h>
5 #include <tbb/parallel_invoke.h>
6
7 #include <algorithm>
8 #include <cstddef>
9 #include <cstdint>
10 #include <vector>
11
12 #include "chernov_t_radix_sort/common/include/common.hpp"
13
14 namespace chernov_t_radix_sort {
15
16
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 ChernovTRadixSortTBB::ChernovTRadixSortTBB(const InType &in) {
17 SetTypeOfTask(GetStaticTypeOfTask());
18
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 GetInput() = in;
19 GetOutput() = {};
20 32 }
21
22 32 bool ChernovTRadixSortTBB::ValidationImpl() {
23 32 return true;
24 }
25
26 32 bool ChernovTRadixSortTBB::PreProcessingImpl() {
27 32 GetOutput() = GetInput();
28 32 return true;
29 }
30
31 constexpr int kBitsPerDigit = 8;
32 constexpr int kRadix = 1 << kBitsPerDigit;
33 constexpr uint32_t kSignMask = 0x80000000U;
34
35 ✗ void ChernovTRadixSortTBB::ComputePrefixSums(std::vector<int> &count) {
36
2/4
✓ Branch 0 taken 48960 times.
✓ Branch 1 taken 192 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 49152 for (size_t idx = 1; idx < count.size(); ++idx) {
37 48960 count[idx] += count[idx - 1];
38 }
39 ✗ }
40
41
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 void ChernovTRadixSortTBB::RadixSortLSD(std::vector<int> &data) {
42
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 if (data.empty()) {
43 ✗ return;
44 }
45
46 const size_t n = data.size();
47 48 std::vector<uint32_t> temp(n);
48
49
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 tbb::parallel_for(tbb::blocked_range<size_t>(0, n), [&temp, &data](const tbb::blocked_range<size_t> &r) {
50
2/4
✓ Branch 0 taken 164 times.
✓ Branch 1 taken 164 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 328 for (size_t i = r.begin(); i != r.end(); ++i) {
51 164 temp[i] = static_cast<uint32_t>(data[i]) ^ kSignMask;
52 }
53 });
54
55
1/4
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 48 std::vector<uint32_t> buffer(n);
56
57
2/2
✓ Branch 0 taken 192 times.
✓ Branch 1 taken 48 times.
 240 for (int byte_index = 0; byte_index < 4; ++byte_index) {
58
1/2
✓ Branch 1 taken 192 times.
✗ Branch 2 not taken.
 192 const int shift = byte_index * kBitsPerDigit;
59
60 256 tbb::combinable<std::vector<int>> local_counts([]() { return std::vector<int>(kRadix, 0); });
61
62 192 tbb::parallel_for(tbb::blocked_range<size_t>(0, n),
63
1/2
✓ Branch 1 taken 192 times.
✗ Branch 2 not taken.
 192 [&local_counts, &temp, shift](const tbb::blocked_range<size_t> &r) {
64 656 auto &my_count = local_counts.local();
65 656 for (size_t i = r.begin(); i != r.end(); ++i) {
66 656 int digit = static_cast<int>((temp[i] >> shift) & 0xFFU);
67 656 ++my_count[static_cast<size_t>(digit)];
68 }
69 656 });
70
71
1/2
✓ Branch 1 taken 192 times.
✗ Branch 2 not taken.
 192 std::vector<int> count(kRadix, 0);
72 192 local_counts.combine_each([&count](const std::vector<int> &c) {
73
2/2
✓ Branch 0 taken 65536 times.
✓ Branch 1 taken 256 times.
 65792 for (int digit_idx = 0; digit_idx < kRadix; ++digit_idx) {
74 65536 count[static_cast<size_t>(digit_idx)] += c[static_cast<size_t>(digit_idx)];
75 }
76 });
77
78 ComputePrefixSums(count);
79
80
2/2
✓ Branch 0 taken 656 times.
✓ Branch 1 taken 192 times.
 848 for (size_t i = n; i-- > 0;) {
81 656 uint32_t val = temp[i];
82 656 int digit = static_cast<int>((val >> shift) & 0xFFU);
83 656 auto pos = static_cast<size_t>(--count[static_cast<size_t>(digit)]);
84 656 buffer[pos] = val;
85 }
86
87 temp.swap(buffer);
88 }
89
90
2/6
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 48 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 48 tbb::parallel_for(tbb::blocked_range<size_t>(0, n), [&data, &temp](const tbb::blocked_range<size_t> &r) {
91
2/4
✓ Branch 0 taken 164 times.
✓ Branch 1 taken 164 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 328 for (size_t i = r.begin(); i != r.end(); ++i) {
92 164 data[i] = static_cast<int>(temp[i] ^ kSignMask);
93 }
94 });
95 }
96
97 24 void ChernovTRadixSortTBB::SimpleMerge(const std::vector<int> &left, const std::vector<int> &right,
98 std::vector<int> &result) {
99 24 result.resize(left.size() + right.size());
100
101 size_t i = 0;
102 size_t j = 0;
103 size_t k = 0;
104
105
4/4
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 16 times.
✓ Branch 2 taken 8 times.
✓ Branch 3 taken 96 times.
 120 while (i < left.size() && j < right.size()) {
106
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 52 times.
 96 if (left[i] <= right[j]) {
107 44 result[k++] = left[i++];
108 } else {
109 52 result[k++] = right[j++];
110 }
111 }
112
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 24 times.
 52 while (i < left.size()) {
113 28 result[k++] = left[i++];
114 }
115
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 24 times.
 64 while (j < right.size()) {
116 40 result[k++] = right[j++];
117 }
118 24 }
119
120
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 8 times.
 32 bool ChernovTRadixSortTBB::RunImpl() {
121 auto &data = GetOutput();
122
123
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 8 times.
 32 if (data.size() <= 1) {
124 return true;
125 }
126
127 24 const size_t mid = data.size() / 2;
128
1/2
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
 24 std::vector<int> left(data.begin(), data.begin() + static_cast<std::ptrdiff_t>(mid));
129
1/4
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 24 std::vector<int> right(data.begin() + static_cast<std::ptrdiff_t>(mid), data.end());
130
131
1/4
✓ Branch 3 taken 24 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 72 tbb::parallel_invoke([&left]() { RadixSortLSD(left); }, [&right]() { RadixSortLSD(right); });
132
133
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 SimpleMerge(left, right, data);
134
135 return true;
136 }
137
138
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 4 times.
 32 bool ChernovTRadixSortTBB::PostProcessingImpl() {
139 32 return std::is_sorted(GetOutput().begin(), GetOutput().end());
140 }
141
142 } // namespace chernov_t_radix_sort
143