GCC Code Coverage Report

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