GCC Code Coverage Report

Directory: ./
File: tasks/zenin_a_radix_sort_double_batcher_merge/omp/src/ops_omp.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 61 69 88.4%
Functions: 7 10 70.0%
Branches: 45 76 59.2%
Line Branch Exec Source
1 #include "zenin_a_radix_sort_double_batcher_merge/omp/include/ops_omp.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <cstdint>
6 #include <cstring>
7 #include <limits>
8 #include <utility>
9 #include <vector>
10
11 #include "zenin_a_radix_sort_double_batcher_merge/common/include/common.hpp"
12
13 namespace zenin_a_radix_sort_double_batcher_merge {
14
15
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 ZeninARadixSortDoubleBatcherMergeOMP::ZeninARadixSortDoubleBatcherMergeOMP(const InType &in) {
16 SetTypeOfTask(GetStaticTypeOfTask());
17
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 GetInput() = in;
18 GetOutput() = {};
19 48 }
20
21 48 bool ZeninARadixSortDoubleBatcherMergeOMP::ValidationImpl() {
22 48 return true;
23 }
24
25 48 bool ZeninARadixSortDoubleBatcherMergeOMP::PreProcessingImpl() {
26 48 return true;
27 }
28
29 ✗ void ZeninARadixSortDoubleBatcherMergeOMP::BlocksComparing(std::vector<double> &arr, size_t i, size_t j) {
30 ✗ if (arr[i] > arr[j]) {
31 std::swap(arr[i], arr[j]);
32 }
33 ✗ }
34
35 40 void ZeninARadixSortDoubleBatcherMergeOMP::BatcherOddEvenMerge(std::vector<double> &arr, size_t n) {
36
2/2
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 40 times.
 144 for (size_t po = n / 2; po > 0; po >>= 1) {
37
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 64 times.
 104 if (po == n / 2) {
38 40 #pragma omp parallel for shared(arr, po) default(none)
39 for (size_t i = 0; i < po; ++i) {
40 BlocksComparing(arr, i, i + po);
41 }
42 } else {
43 64 #pragma omp parallel for shared(arr, n, po) default(none)
44 for (size_t i = po; i < n - po; i += 2 * po) {
45 for (size_t j = 0; j < po; ++j) {
46 BlocksComparing(arr, i + j, i + j + po);
47 }
48 }
49 }
50 }
51 40 }
52
53 ✗ uint64_t ZeninARadixSortDoubleBatcherMergeOMP::PackDouble(double v) noexcept {
54 uint64_t bits = 0ULL;
55 std::memcpy(&bits, &v, sizeof(bits));
56
2/4
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 216 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 256 if ((bits & (1ULL << 63)) != 0ULL) {
57 40 bits = ~bits;
58 } else {
59 216 bits ^= (1ULL << 63);
60 }
61 ✗ return bits;
62 }
63
64 ✗ double ZeninARadixSortDoubleBatcherMergeOMP::UnpackDouble(uint64_t k) noexcept {
65 ✗ if ((k & (1ULL << 63)) != 0ULL) {
66 216 k ^= (1ULL << 63);
67 } else {
68 40 k = ~k;
69 }
70 double v = 0.0;
71 std::memcpy(&v, &k, sizeof(v));
72 ✗ return v;
73 }
74
75
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 64 times.
 80 void ZeninARadixSortDoubleBatcherMergeOMP::LSDRadixSort(std::vector<double> &array) {
76 const std::size_t n = array.size();
77
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 64 times.
 80 if (n <= 1U) {
78 16 return;
79 }
80
81 constexpr int kBits = 8;
82 constexpr int kBuckets = 1 << kBits;
83 constexpr int kPasses = static_cast<int>((sizeof(uint64_t) * 8) / kBits);
84
85 64 std::vector<uint64_t> keys;
86
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 keys.resize(n);
87
2/2
✓ Branch 0 taken 256 times.
✓ Branch 1 taken 64 times.
 320 for (std::size_t i = 0; i < n; ++i) {
88
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 216 times.
 512 keys[i] = PackDouble(array[i]);
89 }
90
91 64 std::vector<uint64_t> tmp_keys;
92
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 tmp_keys.resize(n);
93 64 std::vector<double> tmp_vals;
94
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 tmp_vals.resize(n);
95
96
2/2
✓ Branch 0 taken 512 times.
✓ Branch 1 taken 64 times.
 576 for (int pass = 0; pass < kPasses; ++pass) {
97 512 int shift = pass * kBits;
98 512 std::vector<std::size_t> cnt;
99
1/4
✓ Branch 1 taken 512 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 512 cnt.assign(kBuckets + 1, 0U);
100
101
2/2
✓ Branch 0 taken 2048 times.
✓ Branch 1 taken 512 times.
 2560 for (std::size_t i = 0; i < n; ++i) {
102 2048 auto d = static_cast<std::size_t>((keys[i] >> shift) & (kBuckets - 1));
103 2048 ++cnt[d + 1];
104 }
105
2/2
✓ Branch 0 taken 131072 times.
✓ Branch 1 taken 512 times.
 131584 for (int i = 0; i < kBuckets; ++i) {
106 131072 cnt[i + 1] += cnt[i];
107 }
108
109
2/2
✓ Branch 0 taken 2048 times.
✓ Branch 1 taken 512 times.
 2560 for (std::size_t i = 0; i < n; ++i) {
110 2048 auto d = static_cast<std::size_t>((keys[i] >> shift) & (kBuckets - 1));
111 2048 std::size_t pos = cnt[d]++;
112 2048 tmp_keys[pos] = keys[i];
113 2048 tmp_vals[pos] = array[i];
114 }
115
116 keys.swap(tmp_keys);
117 array.swap(tmp_vals);
118 }
119
120
2/2
✓ Branch 0 taken 256 times.
✓ Branch 1 taken 64 times.
 320 for (std::size_t i = 0; i < n; ++i) {
121
2/2
✓ Branch 0 taken 216 times.
✓ Branch 1 taken 40 times.
 512 array[i] = UnpackDouble(keys[i]);
122 }
123 }
124
125 48 bool ZeninARadixSortDoubleBatcherMergeOMP::RunImpl() {
126 48 auto data = GetInput();
127 size_t original_size = data.size();
128
129
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 40 times.
 48 if (original_size <= 1) {
130
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 GetOutput() = data;
131 return true;
132 }
133
134 size_t pow2 = 1;
135
2/2
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 40 times.
 144 while (pow2 < original_size) {
136 104 pow2 <<= 1;
137 }
138
139
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 data.resize(pow2, std::numeric_limits<double>::max());
140
141
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 size_t half = pow2 / 2;
142 auto half_dist = static_cast<std::ptrdiff_t>(half);
143
144
2/6
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 40 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 40 std::vector<double> left(data.begin(), data.begin() + half_dist);
145
1/4
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 40 std::vector<double> right(data.begin() + half_dist, data.end());
146
147
1/2
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
 40 #pragma omp parallel sections default(none) shared(left, right)
148 {
149 #pragma omp section
150 {
151 LSDRadixSort(left);
152 }
153 #pragma omp section
154 {
155 LSDRadixSort(right);
156 }
157 }
158
159 std::ranges::copy(left, data.begin());
160 std::ranges::copy(right, data.begin() + half_dist);
161
162 40 BatcherOddEvenMerge(data, data.size());
163
164
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 data.resize(original_size);
165
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 GetOutput() = data;
166 return true;
167 }
168
169 48 bool ZeninARadixSortDoubleBatcherMergeOMP::PostProcessingImpl() {
170 48 return true;
171 }
172
173 } // namespace zenin_a_radix_sort_double_batcher_merge
174