GCC Code Coverage Report

Directory: ./
File: tasks/khruev_a_radix_sorting_int_bather_merge/tbb/src/ops_tbb.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 57 60 95.0%
Functions: 9 10 90.0%
Branches: 43 70 61.4%
Line Branch Exec Source
1 #include "khruev_a_radix_sorting_int_bather_merge/tbb/include/ops_tbb.hpp"
2
3 #include <tbb/blocked_range.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 <limits>
11 #include <vector> //test comment
12
13 #include "khruev_a_radix_sorting_int_bather_merge/common/include/common.hpp"
14
15 namespace khruev_a_radix_sorting_int_bather_merge {
16
17 ✗ void KhruevARadixSortingIntBatherMergeTBB::CompareExchange(std::vector<int> &a, size_t i, size_t j) {
18
4/6
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 148 times.
✓ Branch 2 taken 16 times.
✓ Branch 3 taken 108 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 324 if (a[i] > a[j]) {
19 std::swap(a[i], a[j]);
20 }
21 ✗ }
22
23 56 void KhruevARadixSortingIntBatherMergeTBB::RadixSort(std::vector<int> &arr) {
24 const int bits = 8;
25 const int buckets = 1 << bits;
26 const int mask = buckets - 1;
27 const int passes = 32 / bits;
28
29 56 std::vector<int> temp(arr.size());
30 std::vector<int> *src = &arr;
31 std::vector<int> *dst = &temp;
32
33
2/2
✓ Branch 0 taken 224 times.
✓ Branch 1 taken 56 times.
 280 for (int pass = 0; pass < passes; pass++) {
34
1/4
✓ Branch 1 taken 224 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 224 std::vector<int> count(buckets, 0);
35 224 int shift = pass * bits;
36
37
2/2
✓ Branch 0 taken 992 times.
✓ Branch 1 taken 224 times.
 1216 for (int x : *src) {
38 992 uint32_t ux = static_cast<uint32_t>(x) ^ 0x80000000U;
39 992 uint32_t digit = (ux >> shift) & mask;
40 992 count[digit]++;
41 }
42
43
2/2
✓ Branch 0 taken 57120 times.
✓ Branch 1 taken 224 times.
 57344 for (int i = 1; i < buckets; i++) {
44 57120 count[i] += count[i - 1];
45 }
46
47
2/2
✓ Branch 0 taken 992 times.
✓ Branch 1 taken 224 times.
 1216 for (size_t i = src->size(); i-- > 0;) {
48 992 uint32_t ux = static_cast<uint32_t>((*src)[i]) ^ 0x80000000U;
49 992 uint32_t digit = (ux >> shift) & mask;
50 992 (*dst)[--count[digit]] = (*src)[i];
51 }
52
53 std::swap(src, dst);
54 }
55 56 }
56
57 28 void KhruevARadixSortingIntBatherMergeTBB::OddEvenMerge(std::vector<int> &a, size_t n) {
58
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 28 times.
 28 if (n < 2) {
59 ✗ return;
60 }
61
62 28 size_t po = n / 2;
63
64 // Первая итерация вынесена из цикла для снижения когнитивной сложности (избавляемся от if-else)
65 152 tbb::parallel_for(tbb::blocked_range<size_t>(0, po), [&](const tbb::blocked_range<size_t> &r) {
66
2/2
✓ Branch 0 taken 124 times.
✓ Branch 1 taken 124 times.
 248 for (size_t i = r.begin(); i != r.end(); ++i) {
67
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 108 times.
 124 CompareExchange(a, i, i + po);
68 }
69 124 });
70
71 28 po >>= 1;
72
73
2/2
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 28 times.
 80 for (; po > 0; po >>= 1) {
74 52 size_t num_blocks = ((n - (2 * po)) / (2 * po));
75
76 192 tbb::parallel_for(tbb::blocked_range<size_t>(0, num_blocks), [&](const tbb::blocked_range<size_t> &r) {
77
2/2
✓ Branch 0 taken 140 times.
✓ Branch 1 taken 140 times.
 280 for (size_t block_idx = r.begin(); block_idx != r.end(); ++block_idx) {
78 140 size_t i = po + (block_idx * 2 * po);
79
2/2
✓ Branch 0 taken 200 times.
✓ Branch 1 taken 140 times.
 340 for (size_t j = 0; j < po; ++j) {
80
2/2
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 148 times.
 200 CompareExchange(a, i + j, i + j + po);
81 }
82 }
83 140 });
84 }
85 }
86
87
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 KhruevARadixSortingIntBatherMergeTBB::KhruevARadixSortingIntBatherMergeTBB(const InType &in) {
88 SetTypeOfTask(GetStaticTypeOfTask());
89
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 GetInput() = in;
90 32 }
91
92 32 bool KhruevARadixSortingIntBatherMergeTBB::ValidationImpl() {
93 32 return !GetInput().empty();
94 }
95
96 32 bool KhruevARadixSortingIntBatherMergeTBB::PreProcessingImpl() {
97 32 GetOutput().resize(GetInput().size());
98 32 return true;
99 }
100
101 32 bool KhruevARadixSortingIntBatherMergeTBB::RunImpl() {
102 32 std::vector<int> data = GetInput();
103 size_t original_size = data.size();
104
105
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 28 times.
 32 if (original_size <= 1) {
106
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 GetOutput() = data;
107 return true;
108 }
109
110 size_t pow2 = 1;
111
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 28 times.
 108 while (pow2 < original_size) {
112 80 pow2 <<= 1;
113 }
114
115
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 data.resize(pow2, std::numeric_limits<int>::max());
116
117
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 size_t half = pow2 / 2;
118
119 auto half_dist = static_cast<std::ptrdiff_t>(half);
120
2/6
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 28 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 28 std::vector<int> left(data.begin(), data.begin() + half_dist);
121
1/4
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 28 std::vector<int> right(data.begin() + half_dist, data.end());
122
123
2/6
✓ Branch 3 taken 28 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 28 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 112 tbb::parallel_invoke([&]() { RadixSort(left); }, [&]() { RadixSort(right); });
124
125 std::ranges::copy(left, data.begin());
126 std::ranges::copy(right, data.begin() + half_dist);
127
128
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 OddEvenMerge(data, data.size());
129
130
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 data.resize(original_size);
131
132
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 GetOutput() = data;
133
134 return true;
135 }
136
137 32 bool KhruevARadixSortingIntBatherMergeTBB::PostProcessingImpl() {
138 32 return GetOutput().size() == GetInput().size();
139 }
140
141 } // namespace khruev_a_radix_sorting_int_bather_merge
142