GCC Code Coverage Report

Directory: ./
File: tasks/popova_e_radix_sort_for_double_with_simple_merge/omp/src/ops_omp.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 68 70 97.1%
Functions: 8 8 100.0%
Branches: 54 74 73.0%
Line Branch Exec Source
1 #include "popova_e_radix_sort_for_double_with_simple_merge/omp/include/ops_omp.hpp"
2
3 #include <omp.h>
4
5 #include <array>
6 #include <cmath>
7 #include <cstdint>
8 #include <cstring>
9 #include <random>
10 #include <vector>
11
12 #include "popova_e_radix_sort_for_double_with_simple_merge/common/include/common.hpp"
13
14 namespace popova_e_radix_sort_for_double_with_simple_merge_threads {
15
16 namespace {
17
18 uint64_t DoubleToSortable(double value) {
19 uint64_t bits = 0;
20 std::memcpy(&bits, &value, sizeof(double));
21 bool is_negative = (bits >> 63) == 1;
22 if (is_negative) {
23 bits = ~bits;
24 } else {
25 bits ^= (1ULL << 63);
26 }
27 return bits;
28 }
29
30 double SortableToDouble(uint64_t bits) {
31 bool is_negative = (bits >> 63) == 1;
32 if (is_negative) {
33 bits ^= (1ULL << 63);
34 } else {
35 bits = ~bits;
36 }
37 double value = 0;
38 memcpy(&value, &bits, sizeof(double));
39 return value;
40 }
41
42
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 116 times.
 116 void RadixSortUInt(std::vector<uint64_t> &arr) {
43
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 116 times.
 116 if (arr.empty()) {
44 ✗ return;
45 }
46
47 const int bytes_count = 8;
48 const int base = 256;
49 116 std::vector<uint64_t> buffer(arr.size());
50
51
2/2
✓ Branch 0 taken 928 times.
✓ Branch 1 taken 116 times.
 1044 for (int byte_index = 0; byte_index < bytes_count; byte_index++) {
52 928 int sdvig = byte_index * 8;
53 928 std::array<size_t, base> count = {0};
54
55
2/2
✓ Branch 0 taken 198752 times.
✓ Branch 1 taken 928 times.
 199680 for (const auto &val : arr) {
56 198752 count.at((val >> sdvig) & 0xFF)++;
57 }
58
59 size_t offset = 0;
60
2/2
✓ Branch 0 taken 237568 times.
✓ Branch 1 taken 928 times.
 238496 for (auto &c : count) {
61 237568 size_t tmp = c;
62 237568 c = offset;
63 237568 offset += tmp;
64 }
65
66
2/2
✓ Branch 0 taken 198752 times.
✓ Branch 1 taken 928 times.
 199680 for (const auto &val : arr) {
67 198752 size_t pos = (val >> sdvig) & 0xFF;
68
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 198752 times.
 198752 buffer.at(count.at(pos)) = val;
69 198752 count.at(pos)++;
70 }
71
1/2
✓ Branch 1 taken 928 times.
✗ Branch 2 not taken.
 928 arr = buffer;
72 }
73 }
74
75 71 std::vector<double> MergeSorted(const std::vector<double> &left, const std::vector<double> &right) {
76
1/2
✓ Branch 1 taken 71 times.
✗ Branch 2 not taken.
 71 std::vector<double> res;
77
1/2
✓ Branch 1 taken 71 times.
✗ Branch 2 not taken.
 71 res.reserve(left.size() + right.size());
78 size_t i = 0;
79 size_t j = 0;
80
4/4
✓ Branch 0 taken 29 times.
✓ Branch 1 taken 30455 times.
✓ Branch 2 taken 42 times.
✓ Branch 3 taken 30413 times.
 30484 while (i < left.size() && j < right.size()) {
81
2/2
✓ Branch 0 taken 18537 times.
✓ Branch 1 taken 11876 times.
 30413 if (left[i] <= right[j]) {
82
1/2
✓ Branch 0 taken 18537 times.
✗ Branch 1 not taken.
 18537 res.push_back(left[i++]);
83 } else {
84
1/2
✓ Branch 0 taken 11876 times.
✗ Branch 1 not taken.
 11876 res.push_back(right[j++]);
85 }
86 }
87
2/2
✓ Branch 0 taken 73 times.
✓ Branch 1 taken 71 times.
 144 while (i < left.size()) {
88
1/2
✓ Branch 0 taken 73 times.
✗ Branch 1 not taken.
 73 res.push_back(left[i++]);
89 }
90
2/2
✓ Branch 0 taken 39 times.
✓ Branch 1 taken 71 times.
 110 while (j < right.size()) {
91
1/2
✓ Branch 0 taken 39 times.
✗ Branch 1 not taken.
 39 res.push_back(right[j++]);
92 }
93 71 return res;
94 }
95
96 24844 double RandomDouble(double min_val, double max_val) {
97
4/6
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 24840 times.
✓ Branch 3 taken 4 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 4 times.
✗ Branch 7 not taken.
 24844 static std::random_device rd;
98
3/4
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 24840 times.
✓ Branch 3 taken 4 times.
✗ Branch 4 not taken.
 24852 static std::mt19937 gen(rd());
99 std::uniform_real_distribution<> dis(min_val, max_val);
100 24844 return dis(gen);
101 }
102
103 bool IsSorted(const std::vector<double> &arr) {
104
2/2
✓ Branch 0 taken 24796 times.
✓ Branch 1 taken 48 times.
 24844 for (size_t i = 1; i < arr.size(); i++) {
105
1/2
✓ Branch 0 taken 24796 times.
✗ Branch 1 not taken.
 24796 if (arr[i - 1] > arr[i]) {
106 return false;
107 }
108 }
109 return true;
110 }
111
112 bool SameData(const std::vector<double> &original, const std::vector<double> &result) {
113 uint64_t hash_original = 0;
114 uint64_t hash_result = 0;
115
116
2/2
✓ Branch 0 taken 24844 times.
✓ Branch 1 taken 48 times.
 24892 for (const double &value : original) {
117 uint64_t bits = 0;
118 std::memcpy(&bits, &value, sizeof(double));
119 24844 hash_original ^= bits;
120 }
121
122
2/2
✓ Branch 0 taken 24844 times.
✓ Branch 1 taken 48 times.
 24892 for (const double &value : result) {
123 uint64_t bits = 0;
124 std::memcpy(&bits, &value, sizeof(double));
125 24844 hash_result ^= bits;
126 }
127
128 48 return hash_original == hash_result;
129 }
130
131 } // namespace
132
133 48 PopovaERadixSorForDoubleWithSimpleMergeOMP::PopovaERadixSorForDoubleWithSimpleMergeOMP(const InType &in) {
134 SetTypeOfTask(GetStaticTypeOfTask());
135 48 GetInput() = in;
136 GetOutput() = 0;
137 48 }
138
139 48 bool PopovaERadixSorForDoubleWithSimpleMergeOMP::ValidationImpl() {
140 48 return GetInput() > 0;
141 }
142
143 48 bool PopovaERadixSorForDoubleWithSimpleMergeOMP::PreProcessingImpl() {
144 48 int size = GetInput();
145 48 array_.resize(size);
146
2/2
✓ Branch 0 taken 24844 times.
✓ Branch 1 taken 48 times.
 24892 for (int i = 0; i < size; i++) {
147 24844 array_[i] = RandomDouble(-100.0, 100.0);
148 }
149 48 return true;
150 }
151
152 48 bool PopovaERadixSorForDoubleWithSimpleMergeOMP::RunImpl() {
153 48 int n_threads = omp_get_max_threads();
154 48 int n = static_cast<int>(array_.size());
155 48 std::vector<std::vector<double>> local_results(n_threads);
156
157 48 auto &ref_array = array_;
158 auto &ref_local_results = local_results;
159
160
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 #pragma omp parallel num_threads(n_threads) default(none) shared(n, n_threads, ref_array, ref_local_results)
161 {
162 int thread_id = omp_get_thread_num();
163 int left_idx = (thread_id * n) / n_threads;
164 int right_idx = ((thread_id + 1) * n) / n_threads;
165
166 if (left_idx < right_idx) {
167 int local_size = right_idx - left_idx;
168 std::vector<uint64_t> local_bits(local_size);
169
170 for (int i = 0; i < local_size; i++) {
171 local_bits.at(i) = DoubleToSortable(ref_array.at(left_idx + i));
172 }
173
174 RadixSortUInt(local_bits);
175
176 ref_local_results.at(thread_id).resize(local_size);
177 for (int i = 0; i < local_size; i++) {
178 ref_local_results.at(thread_id).at(i) = SortableToDouble(local_bits.at(i));
179 }
180 }
181 }
182
183 result_.clear();
184
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 if (!local_results.empty()) {
185
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 result_ = local_results.at(0);
186
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 48 times.
 120 for (int i = 1; i < n_threads; i++) {
187
3/4
✗ Branch 0 not taken.
✓ Branch 1 taken 72 times.
✓ Branch 2 taken 71 times.
✓ Branch 3 taken 1 times.
 72 if (!local_results.at(i).empty()) {
188
1/2
✓ Branch 1 taken 71 times.
✗ Branch 2 not taken.
 142 result_ = MergeSorted(result_, local_results.at(i));
189 }
190 }
191 }
192
193 48 return true;
194 48 }
195
196 48 bool PopovaERadixSorForDoubleWithSimpleMergeOMP::PostProcessingImpl() {
197 bool sorted = IsSorted(result_);
198 bool same = SameData(array_, result_);
199
200
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 if (sorted && same) {
201 48 GetOutput() = 1;
202 } else {
203 ✗ GetOutput() = 0;
204 }
205 48 return true;
206 }
207
208 } // namespace popova_e_radix_sort_for_double_with_simple_merge_threads
209