GCC Code Coverage Report

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