GCC Code Coverage Report

Directory: ./
File: tasks/dorofeev_i_bitwise_sort_double_eo_batcher_merge/omp/src/ops_omp.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 60 61 98.4%
Functions: 7 7 100.0%
Branches: 51 66 77.3%
Line Branch Exec Source
1 #include "dorofeev_i_bitwise_sort_double_eo_batcher_merge/omp/include/ops_omp.hpp"
2
3 #include <omp.h>
4
5 #include <algorithm>
6 #include <cstdint>
7 #include <cstring>
8 #include <limits>
9 #include <vector>
10
11 #include "dorofeev_i_bitwise_sort_double_eo_batcher_merge/common/include/common.hpp"
12 #include "util/include/util.hpp"
13
14 namespace dorofeev_i_bitwise_sort_double_eo_batcher_merge {
15
16 namespace {
17
18 uint64_t DoubleToUint(double d) {
19 uint64_t u = 0;
20 std::memcpy(&u, &d, sizeof(double));
21
2/2
✓ Branch 0 taken 2492 times.
✓ Branch 1 taken 3204 times.
 5696 if ((u & 0x8000000000000000ULL) != 0) {
22 2492 u = ~u;
23 } else {
24 3204 u |= 0x8000000000000000ULL;
25 }
26 return u;
27 }
28
29 double UintToDouble(uint64_t u) {
30 5696 if ((u & 0x8000000000000000ULL) != 0) {
31 3204 u &= ~0x8000000000000000ULL;
32 } else {
33 2492 u = ~u;
34 }
35 double d = 0.0;
36 std::memcpy(&d, &u, sizeof(double));
37 return d;
38 }
39
40
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 36 times.
 36 void RadixSortDouble(std::vector<double> &arr) {
41
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 36 times.
 36 if (arr.empty()) {
42 ✗ return;
43 }
44
45 36 std::vector<uint64_t> uarr(arr.size());
46
2/2
✓ Branch 0 taken 5696 times.
✓ Branch 1 taken 36 times.
 5732 for (size_t i = 0; i < arr.size(); ++i) {
47
2/2
✓ Branch 0 taken 2492 times.
✓ Branch 1 taken 3204 times.
 11392 uarr[i] = DoubleToUint(arr[i]);
48 }
49
50
1/4
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 36 std::vector<uint64_t> temp(uarr.size());
51
2/2
✓ Branch 0 taken 288 times.
✓ Branch 1 taken 36 times.
 324 for (size_t byte = 0; byte < 8; ++byte) {
52
1/4
✓ Branch 1 taken 288 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 288 std::vector<int> count(256, 0);
53
2/2
✓ Branch 0 taken 45568 times.
✓ Branch 1 taken 288 times.
 45856 for (uint64_t val : uarr) {
54 45568 count[(val >> (byte * 8)) & 0xFF]++;
55 }
56
2/2
✓ Branch 0 taken 73440 times.
✓ Branch 1 taken 288 times.
 73728 for (size_t i = 1; i < 256; ++i) {
57 73440 count[i] += count[i - 1];
58 }
59
2/2
✓ Branch 0 taken 45568 times.
✓ Branch 1 taken 288 times.
 45856 for (int i = static_cast<int>(uarr.size()) - 1; i >= 0; --i) {
60 45568 temp[--count[(uarr[i] >> (byte * 8)) & 0xFF]] = uarr[i];
61 }
62
1/2
✓ Branch 1 taken 288 times.
✗ Branch 2 not taken.
 288 uarr = temp;
63 }
64
65
2/2
✓ Branch 0 taken 5696 times.
✓ Branch 1 taken 36 times.
 5732 for (size_t i = 0; i < arr.size(); ++i) {
66
2/2
✓ Branch 0 taken 3204 times.
✓ Branch 1 taken 2492 times.
 11392 arr[i] = UintToDouble(uarr[i]);
67 }
68 }
69
70 void CompareExchangeBlocks(double *arr, size_t i, size_t step) {
71
4/4
✓ Branch 0 taken 2848 times.
✓ Branch 1 taken 20 times.
✓ Branch 2 taken 20108 times.
✓ Branch 3 taken 5539 times.
 28515 for (size_t k = 0; k < step; ++k) {
72
4/4
✓ Branch 0 taken 371 times.
✓ Branch 1 taken 2477 times.
✓ Branch 2 taken 10172 times.
✓ Branch 3 taken 9936 times.
 22956 if (arr[i + k] > arr[i + k + step]) {
73 std::swap(arr[i + k], arr[i + k + step]);
74 }
75 }
76 }
77
78 20 void OddEvenMergeIterative(double *arr, size_t start, size_t n) {
79
1/2
✓ Branch 0 taken 20 times.
✗ Branch 1 not taken.
 20 if (n <= 1) {
80 return;
81 }
82
83 20 size_t step = n / 2;
84 CompareExchangeBlocks(arr, start, step);
85
86 20 step /= 2;
87
2/2
✓ Branch 0 taken 117 times.
✓ Branch 1 taken 20 times.
 137 for (; step > 0; step /= 2) {
88
2/2
✓ Branch 0 taken 5539 times.
✓ Branch 1 taken 117 times.
 5656 for (size_t i = step; i < n - step; i += step * 2) {
89 5539 CompareExchangeBlocks(arr, start + i, step);
90 }
91 }
92 }
93
94 } // namespace
95
96
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 DorofeevIBitwiseSortDoubleEOBatcherMergeOMP::DorofeevIBitwiseSortDoubleEOBatcherMergeOMP(const InType &in) {
97 SetTypeOfTask(GetStaticTypeOfTask());
98
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 GetInput() = in;
99 16 }
100
101 16 bool DorofeevIBitwiseSortDoubleEOBatcherMergeOMP::ValidationImpl() {
102 16 return true;
103 }
104
105 16 bool DorofeevIBitwiseSortDoubleEOBatcherMergeOMP::PreProcessingImpl() {
106 16 local_data_ = GetInput();
107 16 return true;
108 }
109
110
1/2
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
 16 bool DorofeevIBitwiseSortDoubleEOBatcherMergeOMP::RunImpl() {
111
1/2
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
 16 if (local_data_.empty()) {
112 return true;
113 }
114
115 size_t original_size = local_data_.size();
116 size_t pow2 = 1;
117
2/2
✓ Branch 0 taken 116 times.
✓ Branch 1 taken 16 times.
 132 while (pow2 < original_size) {
118 116 pow2 *= 2;
119 }
120
121
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 4 times.
 16 if (pow2 > original_size) {
122 12 local_data_.resize(pow2, std::numeric_limits<double>::max());
123 }
124
125 16 int num_threads = ppc::util::GetNumThreads();
126 16 if (num_threads <= 0) {
127 num_threads = 1;
128 }
129
130 size_t num_chunks = 1;
131
3/4
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 16 times.
✓ Branch 2 taken 16 times.
✗ Branch 3 not taken.
 32 while (num_chunks * 2 <= static_cast<size_t>(num_threads) && num_chunks * 2 <= pow2) {
132 num_chunks *= 2;
133 }
134
135 16 size_t chunk_size = pow2 / num_chunks;
136 double *raw_data = local_data_.data();
137
138 // Выносим количество чанков в int, чтобы угодить линтеру со сравнениями типов
139 16 int num_chunks_int = static_cast<int>(num_chunks);
140
141 // 2. Параллельно сортируем каждый блок (явно указываем shared переменные)
142 16 #pragma omp parallel for num_threads(num_threads) default(none) shared(chunk_size, raw_data, num_chunks_int)
143 for (int i = 0; i < num_chunks_int; ++i) {
144 size_t start_idx = static_cast<size_t>(i) * chunk_size;
145
146 std::vector<double> local_arr(chunk_size);
147 double *local_raw = local_arr.data();
148
149 for (size_t j = 0; j < chunk_size; ++j) {
150 local_raw[j] = raw_data[start_idx + j];
151 }
152
153 RadixSortDouble(local_arr);
154
155 for (size_t j = 0; j < chunk_size; ++j) {
156 raw_data[start_idx + j] = local_raw[j];
157 }
158 }
159
160 // 3. Собираем отсортированные блоки вместе
161
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 16 times.
 32 for (size_t size = chunk_size; size < pow2; size *= 2) {
162 16 int merges_count = static_cast<int>(pow2 / (size * 2));
163
164 16 #pragma omp parallel for num_threads(num_threads) default(none) shared(size, raw_data, merges_count)
165 for (int i = 0; i < merges_count; ++i) {
166 OddEvenMergeIterative(raw_data, static_cast<size_t>(i) * 2 * size, 2 * size);
167 }
168 }
169
170
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 4 times.
 16 if (pow2 > original_size) {
171 12 local_data_.resize(original_size);
172 }
173
174 return true;
175 }
176
177 16 bool DorofeevIBitwiseSortDoubleEOBatcherMergeOMP::PostProcessingImpl() {
178 16 GetOutput() = local_data_;
179 16 return true;
180 }
181
182 } // namespace dorofeev_i_bitwise_sort_double_eo_batcher_merge
183