GCC Code Coverage Report

Directory: ./
File: tasks/gonozov_l_bitwise_sorting_double_Batcher_merge/tbb/src/ops_tbb.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 64 66 97.0%
Functions: 9 9 100.0%
Branches: 45 72 62.5%
Line Branch Exec Source
1 #include "gonozov_l_bitwise_sorting_double_Batcher_merge/tbb/include/ops_tbb.hpp"
2
3 #include <oneapi/tbb/parallel_for.h>
4 #include <oneapi/tbb/parallel_invoke.h>
5 #include <tbb/tbb.h>
6
7 #include <algorithm>
8 #include <cstddef>
9 #include <cstdint>
10 #include <cstring>
11 #include <limits>
12 #include <utility>
13 #include <vector>
14
15 #include "gonozov_l_bitwise_sorting_double_Batcher_merge/common/include/common.hpp"
16
17 namespace gonozov_l_bitwise_sorting_double_batcher_merge {
18
19
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 GonozovLBitSortBatcherMergeTBB::GonozovLBitSortBatcherMergeTBB(const InType &in) {
20 SetTypeOfTask(GetStaticTypeOfTask());
21
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 GetInput() = in;
22 16 }
23
24 16 bool GonozovLBitSortBatcherMergeTBB::ValidationImpl() {
25 16 return !GetInput().empty();
26 }
27
28 16 bool GonozovLBitSortBatcherMergeTBB::PreProcessingImpl() {
29 16 return true;
30 }
31
32 namespace {
33
34 /// double -> uint64_t
35 uint64_t DoubleToSortableInt(double d) {
36 uint64_t bits = 0;
37 std::memcpy(&bits, &d, sizeof(double));
38
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 104 times.
 128 if ((bits >> 63) != 0) {
39 24 return ~bits;
40 }
41 104 return bits | 0x8000000000000000ULL;
42 }
43
44 /// uint64_t -> double
45 double SortableIntToDouble(uint64_t bits) {
46 128 if ((bits >> 63) != 0) {
47 104 bits &= ~0x8000000000000000ULL;
48 } else {
49 24 bits = ~bits;
50 }
51 double result = 0.0;
52 std::memcpy(&result, &bits, sizeof(double));
53 return result;
54 }
55
56 size_t NextPowerOfTwo(size_t n) {
57 size_t power = 1;
58
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 16 times.
 64 while (power < n) {
59 48 power <<= 1;
60 }
61 return power;
62 }
63
64 constexpr size_t kRadix = 256;
65
66 /// Поразрядная сортировка для vector<double> (работает с копией)
67
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.
 32 void RadixSortDouble(std::vector<double> &data) {
68
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.
 32 if (data.empty()) {
69 ✗ return;
70 }
71
72 32 std::vector<uint64_t> keys(data.size());
73
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 32 times.
 160 for (size_t i = 0; i < data.size(); ++i) {
74
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 104 times.
 256 keys[i] = DoubleToSortableInt(data[i]);
75 }
76
77
1/4
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 32 std::vector<uint64_t> temp_keys(data.size());
78
79
2/2
✓ Branch 0 taken 256 times.
✓ Branch 1 taken 32 times.
 288 for (int pass = 0; pass < 8; ++pass) {
80
1/4
✓ Branch 1 taken 256 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 256 std::vector<size_t> count(kRadix, 0);
81 256 int shift = pass * 8;
82
83
2/2
✓ Branch 0 taken 1024 times.
✓ Branch 1 taken 256 times.
 1280 for (uint64_t key : keys) {
84 1024 uint8_t byte = (key >> shift) & 0xFF;
85 1024 count[byte]++;
86 }
87
88 65280 for (int i = 1; std::cmp_less(i, kRadix); ++i) {
89 65280 count[i] += count[i - 1];
90 }
91
92
2/2
✓ Branch 0 taken 1024 times.
✓ Branch 1 taken 256 times.
 1280 for (int i = static_cast<int>(keys.size()) - 1; i >= 0; --i) {
93 1024 uint8_t byte = (keys[i] >> shift) & 0xFF;
94 1024 temp_keys[--count[byte]] = keys[i];
95 }
96 keys.swap(temp_keys);
97 }
98
99
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 32 times.
 160 for (size_t i = 0; i < data.size(); ++i) {
100
2/2
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 24 times.
 256 data[i] = SortableIntToDouble(keys[i]);
101 }
102 }
103
104 /// Слияние половинок для сети Бэтчера
105 112 void MergingHalves(std::vector<double> &arr, size_t i, size_t len) {
106 112 size_t half = len / 2;
107 112 size_t end = std::min(i + len, arr.size());
108
109
2/2
✓ Branch 0 taken 176 times.
✓ Branch 1 taken 112 times.
 288 for (size_t step = half; step > 0; step /= 2) {
110
2/2
✓ Branch 0 taken 496 times.
✓ Branch 1 taken 176 times.
 672 for (size_t j = i; j + step < end; ++j) {
111
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 440 times.
 496 if (arr[j] > arr[j + step]) {
112 std::swap(arr[j], arr[j + step]);
113 }
114 }
115 }
116 112 }
117
118 /// Итеративная сеть Бэтчера (параллельная)
119 16 void BatcherOddEvenMergeIterative(std::vector<double> &arr, size_t n) {
120
1/2
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
 16 if (n <= 1) {
121 return;
122 }
123 16 n = std::min(n, arr.size());
124
125
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 16 times.
 64 for (size_t len = 2; len <= n; len *= 2) {
126 48 tbb::parallel_for(tbb::blocked_range<size_t>(0, n, len), [&](const tbb::blocked_range<size_t> &r) {
127
2/4
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 112 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 224 for (size_t i = r.begin(); i < r.end(); i += len) {
128 112 MergingHalves(arr, i, len);
129 }
130 });
131 }
132 }
133
134 /// Гибридная сортировка (с копированием половин, как в OMP)
135
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
 16 void HybridSortDouble(std::vector<double> &data) {
136
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
 16 if (data.size() <= 1) {
137 ✗ return;
138 }
139
140 size_t original_size = data.size();
141 size_t new_size = NextPowerOfTwo(original_size);
142 16 data.resize(new_size, std::numeric_limits<double>::max());
143
144 16 size_t mid = new_size / 2;
145
146 // Копируем половины
147
1/2
✓ Branch 2 taken 16 times.
✗ Branch 3 not taken.
 16 std::vector<double> left(data.begin(), data.begin() + static_cast<ptrdiff_t>(mid));
148
1/4
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 16 std::vector<double> right(data.begin() + static_cast<ptrdiff_t>(mid), data.end());
149
150 // Параллельно сортируем две половины
151
2/6
✓ Branch 3 taken 16 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 16 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 64 tbb::parallel_invoke([&]() { RadixSortDouble(left); }, [&]() { RadixSortDouble(right); });
152
153 // Собираем обратно
154 std::ranges::copy(left.begin(), left.end(), data.begin());
155 std::ranges::copy(right.begin(), right.end(), data.begin() + static_cast<ptrdiff_t>(mid));
156
157 // Слияние Бэтчера
158
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 BatcherOddEvenMergeIterative(data, new_size);
159
160 // Обрезаем до исходного размера
161
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 data.resize(original_size);
162 }
163
164 } // namespace
165
166 16 bool GonozovLBitSortBatcherMergeTBB::RunImpl() {
167 16 std::vector<double> array = GetInput();
168
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 HybridSortDouble(array);
169
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 GetOutput() = array;
170 16 return true;
171 }
172
173 16 bool GonozovLBitSortBatcherMergeTBB::PostProcessingImpl() {
174 16 return true;
175 }
176
177 } // namespace gonozov_l_bitwise_sorting_double_batcher_merge
178