GCC Code Coverage Report

Directory: ./
File: tasks/popova_e_radix_sort_for_double_with_simple_merge/stl/src/ops_stl.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 94 96 97.9%
Functions: 9 9 100.0%
Branches: 76 98 77.6%
Line Branch Exec Source
1 #include "popova_e_radix_sort_for_double_with_simple_merge/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <array>
5 #include <cstdint>
6 #include <cstring>
7 #include <functional>
8 #include <random>
9 #include <thread>
10 #include <utility>
11 #include <vector>
12
13 #include "popova_e_radix_sort_for_double_with_simple_merge/common/include/common.hpp"
14 #include "util/include/util.hpp"
15
16 namespace popova_e_radix_sort_for_double_with_simple_merge_threads {
17
18 namespace {
19
20 uint64_t DoubleToSortable(double value) {
21 uint64_t bits = 0;
22 std::memcpy(&bits, &value, sizeof(double));
23 49688 bool is_negative = (bits >> 63) == 1;
24
2/2
✓ Branch 0 taken 24814 times.
✓ Branch 1 taken 24874 times.
 49688 if (is_negative) {
25 24814 bits = ~bits;
26 } else {
27 24874 bits ^= (1ULL << 63);
28 }
29 return bits;
30 }
31
32 double SortableToDouble(uint64_t bits) {
33 49688 bool is_negative = (bits >> 63) == 1;
34
2/2
✓ Branch 0 taken 24874 times.
✓ Branch 1 taken 24814 times.
 49688 if (is_negative) {
35 24874 bits ^= (1ULL << 63);
36 } else {
37 24814 bits = ~bits;
38 }
39 double value = 0;
40 memcpy(&value, &bits, sizeof(double));
41 return value;
42 }
43
44
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 232 times.
 232 void RadixSortUInt(std::vector<uint64_t> &arr) {
45
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 232 times.
 232 if (arr.empty()) {
46 ✗ return;
47 }
48
49 const int bytes_count = 8;
50 const int base = 256;
51 232 std::vector<uint64_t> buffer(arr.size());
52
53
2/2
✓ Branch 0 taken 1856 times.
✓ Branch 1 taken 232 times.
 2088 for (int byte_index = 0; byte_index < bytes_count; byte_index++) {
54 1856 int sdvig = byte_index * 8;
55 1856 std::array<size_t, base> count = {0};
56
57
2/2
✓ Branch 0 taken 397504 times.
✓ Branch 1 taken 1856 times.
 399360 for (const auto &val : arr) {
58 397504 count.at((val >> sdvig) & 0xFF)++;
59 }
60
61 size_t offset = 0;
62
2/2
✓ Branch 0 taken 475136 times.
✓ Branch 1 taken 1856 times.
 476992 for (auto &c : count) {
63 475136 size_t tmp = c;
64 475136 c = offset;
65 475136 offset += tmp;
66 }
67
68
2/2
✓ Branch 0 taken 397504 times.
✓ Branch 1 taken 1856 times.
 399360 for (const auto &val : arr) {
69 397504 size_t pos = (val >> sdvig) & 0xFF;
70
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 397504 times.
 397504 buffer.at(count.at(pos)) = val;
71 397504 count.at(pos)++;
72 }
73
1/2
✓ Branch 1 taken 1856 times.
✗ Branch 2 not taken.
 1856 arr = buffer;
74 }
75 }
76
77 136 std::vector<double> MergeSorted(const std::vector<double> &left, const std::vector<double> &right) {
78
1/2
✓ Branch 1 taken 136 times.
✗ Branch 2 not taken.
 136 std::vector<double> res;
79
1/2
✓ Branch 1 taken 136 times.
✗ Branch 2 not taken.
 136 res.reserve(left.size() + right.size());
80 size_t i = 0;
81 size_t j = 0;
82
4/4
✓ Branch 0 taken 66 times.
✓ Branch 1 taken 60855 times.
✓ Branch 2 taken 70 times.
✓ Branch 3 taken 60785 times.
 60921 while (i < left.size() && j < right.size()) {
83
2/2
✓ Branch 0 taken 37064 times.
✓ Branch 1 taken 23721 times.
 60785 if (left[i] <= right[j]) {
84
1/2
✓ Branch 0 taken 37064 times.
✗ Branch 1 not taken.
 37064 res.push_back(left[i++]);
85 } else {
86
1/2
✓ Branch 0 taken 23721 times.
✗ Branch 1 not taken.
 23721 res.push_back(right[j++]);
87 }
88 }
89
2/2
✓ Branch 0 taken 156 times.
✓ Branch 1 taken 136 times.
 292 while (i < left.size()) {
90
1/2
✓ Branch 0 taken 156 times.
✗ Branch 1 not taken.
 156 res.push_back(left[i++]);
91 }
92
2/2
✓ Branch 0 taken 103 times.
✓ Branch 1 taken 136 times.
 239 while (j < right.size()) {
93
1/2
✓ Branch 0 taken 103 times.
✗ Branch 1 not taken.
 103 res.push_back(right[j++]);
94 }
95 136 return res;
96 }
97
98 49688 double RandomDouble(double min_val, double max_val) {
99
4/6
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 49680 times.
✓ Branch 3 taken 8 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 8 times.
✗ Branch 7 not taken.
 49688 static std::random_device rd;
100
3/4
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 49680 times.
✓ Branch 3 taken 8 times.
✗ Branch 4 not taken.
 49704 static std::mt19937 gen(rd());
101 std::uniform_real_distribution<> dis(min_val, max_val);
102 49688 return dis(gen);
103 }
104
105 bool IsSorted(const std::vector<double> &arr) {
106
2/2
✓ Branch 0 taken 49592 times.
✓ Branch 1 taken 96 times.
 49688 for (size_t i = 1; i < arr.size(); i++) {
107
1/2
✓ Branch 0 taken 49592 times.
✗ Branch 1 not taken.
 49592 if (arr[i - 1] > arr[i]) {
108 return false;
109 }
110 }
111 return true;
112 }
113
114 bool SameData(const std::vector<double> &original, const std::vector<double> &result) {
115 uint64_t hash_original = 0;
116 uint64_t hash_result = 0;
117
118
2/2
✓ Branch 0 taken 49688 times.
✓ Branch 1 taken 96 times.
 49784 for (const double &value : original) {
119 uint64_t bits = 0;
120 std::memcpy(&bits, &value, sizeof(double));
121 49688 hash_original ^= bits;
122 }
123
124
2/2
✓ Branch 0 taken 49688 times.
✓ Branch 1 taken 96 times.
 49784 for (const double &value : result) {
125 uint64_t bits = 0;
126 std::memcpy(&bits, &value, sizeof(double));
127 49688 hash_result ^= bits;
128 }
129
130 96 return hash_original == hash_result;
131 }
132
133 240 void PartSort(int thread_id, int n, int n_threads, const std::vector<double> &src, std::vector<double> &res) {
134 240 int left_idx = (thread_id * n) / n_threads;
135 240 int right_idx = ((thread_id + 1) * n) / n_threads;
136
137
2/2
✓ Branch 0 taken 232 times.
✓ Branch 1 taken 8 times.
 240 if (left_idx < right_idx) {
138 232 int local_size = right_idx - left_idx;
139 232 std::vector<uint64_t> local_bits(local_size);
140
141
2/2
✓ Branch 0 taken 49688 times.
✓ Branch 1 taken 232 times.
 49920 for (int i = 0; i < local_size; i++) {
142
2/2
✓ Branch 0 taken 24814 times.
✓ Branch 1 taken 24874 times.
 99376 local_bits[i] = DoubleToSortable(src[left_idx + i]);
143 }
144
145
1/2
✓ Branch 1 taken 232 times.
✗ Branch 2 not taken.
 232 RadixSortUInt(local_bits);
146
147
1/2
✓ Branch 1 taken 232 times.
✗ Branch 2 not taken.
 232 res.resize(local_size);
148
2/2
✓ Branch 0 taken 49688 times.
✓ Branch 1 taken 232 times.
 49920 for (int i = 0; i < local_size; i++) {
149
2/2
✓ Branch 0 taken 24874 times.
✓ Branch 1 taken 24814 times.
 99376 res[i] = SortableToDouble(local_bits[i]);
150 }
151 }
152 240 }
153
154 } // namespace
155
156 96 PopovaERadixSorForDoubleWithSimpleMergeSTL::PopovaERadixSorForDoubleWithSimpleMergeSTL(const InType &in) {
157 SetTypeOfTask(GetStaticTypeOfTask());
158 96 GetInput() = in;
159 GetOutput() = 0;
160 96 }
161
162 96 bool PopovaERadixSorForDoubleWithSimpleMergeSTL::ValidationImpl() {
163 96 return GetInput() > 0;
164 }
165
166 96 bool PopovaERadixSorForDoubleWithSimpleMergeSTL::PreProcessingImpl() {
167 96 int size = GetInput();
168 96 array_.resize(size);
169
2/2
✓ Branch 0 taken 49688 times.
✓ Branch 1 taken 96 times.
 49784 for (int i = 0; i < size; i++) {
170 49688 array_[i] = RandomDouble(-100.0, 100.0);
171 }
172 96 return true;
173 }
174
175 96 bool PopovaERadixSorForDoubleWithSimpleMergeSTL::RunImpl() {
176 96 int n = static_cast<int>(array_.size());
177 96 int n_threads = std::max(1, ppc::util::GetNumThreads());
178 96 std::vector<std::vector<double>> local_results(n_threads);
179 96 std::vector<std::thread> threads;
180
181
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 threads.reserve(n_threads);
182
183
2/2
✓ Branch 0 taken 240 times.
✓ Branch 1 taken 96 times.
 336 for (int i = 0; i < n_threads; ++i) {
184
1/2
✓ Branch 1 taken 240 times.
✗ Branch 2 not taken.
 240 threads.emplace_back(PartSort, i, n, n_threads, std::ref(array_), std::ref(local_results[i]));
185 }
186
187
2/2
✓ Branch 0 taken 240 times.
✓ Branch 1 taken 96 times.
 336 for (std::thread &t : threads) {
188
1/2
✓ Branch 0 taken 240 times.
✗ Branch 1 not taken.
 240 if (t.joinable()) {
189
1/2
✓ Branch 1 taken 240 times.
✗ Branch 2 not taken.
 240 t.join();
190 }
191 }
192
193 result_.clear();
194
2/2
✓ Branch 0 taken 240 times.
✓ Branch 1 taken 96 times.
 336 for (int i = 0; i < n_threads; i++) {
195
2/2
✓ Branch 0 taken 232 times.
✓ Branch 1 taken 8 times.
 240 if (!local_results[i].empty()) {
196
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 136 times.
 232 if (result_.empty()) {
197 96 result_ = std::move(local_results[i]);
198 } else {
199
1/2
✓ Branch 1 taken 136 times.
✗ Branch 2 not taken.
 272 result_ = MergeSorted(result_, local_results[i]);
200 }
201 }
202 }
203
204 96 return true;
205 96 }
206
207 96 bool PopovaERadixSorForDoubleWithSimpleMergeSTL::PostProcessingImpl() {
208 bool sorted = IsSorted(result_);
209 bool same = SameData(array_, result_);
210
211
1/2
✓ Branch 0 taken 96 times.
✗ Branch 1 not taken.
 96 if (sorted && same) {
212 96 GetOutput() = 1;
213 } else {
214 ✗ GetOutput() = 0;
215 }
216 96 return true;
217 }
218
219 } // namespace popova_e_radix_sort_for_double_with_simple_merge_threads
220