GCC Code Coverage Report

Directory: ./
File: tasks/papulina_y_radix_sort/stl/src/ops_stl.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 74 84 88.1%
Functions: 11 15 73.3%
Branches: 53 86 61.6%
Line Branch Exec Source
1 #include "papulina_y_radix_sort/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <cmath>
5 #include <cstddef>
6 #include <cstdint>
7 #include <cstring>
8 #include <thread>
9 #include <utility>
10 #include <vector>
11
12 #include "papulina_y_radix_sort/common/include/common.hpp"
13 namespace papulina_y_radix_sort {
14
15
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 PapulinaYRadixSortSTL::PapulinaYRadixSortSTL(const InType &in) {
16 SetTypeOfTask(GetStaticTypeOfTask());
17
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 GetInput() = in;
18 56 GetOutput() = std::vector<double>();
19 56 }
20
21 56 bool PapulinaYRadixSortSTL::ValidationImpl() {
22 56 return !GetInput().empty();
23 }
24
25 56 bool PapulinaYRadixSortSTL::PreProcessingImpl() {
26 56 GetOutput().resize(GetInput().size());
27 56 return true;
28 }
29
30
1/2
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
 56 bool PapulinaYRadixSortSTL::RunImpl() {
31 size_t size = GetInput().size();
32
1/2
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
 56 if (size == 0) {
33 return true;
34 }
35
36 56 std::vector<double> data = GetInput();
37
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 RadixSortParallel(data.data(), size);
38
39 GetOutput() = std::move(data);
40 return true;
41 }
42
43 56 bool PapulinaYRadixSortSTL::PostProcessingImpl() {
44 56 return true;
45 }
46
47 ✗ uint64_t PapulinaYRadixSortSTL::InBytes(double d) {
48 uint64_t bits = 0;
49 memcpy(&bits, &d, sizeof(double));
50
2/4
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 320 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 400 if ((bits & kMask) != 0) {
51 80 bits = ~bits;
52 } else {
53 320 bits = bits ^ kMask;
54 }
55 ✗ return bits;
56 }
57
58 ✗ double PapulinaYRadixSortSTL::FromBytes(uint64_t bits) {
59 double d = 0;
60 ✗ if ((bits & kMask) != 0) {
61 320 bits = bits ^ kMask;
62 } else {
63 80 bits = ~bits;
64 }
65 memcpy(&d, &bits, sizeof(double));
66 ✗ return d;
67 }
68
69 56 void PapulinaYRadixSortSTL::RadixSortParallel(double *arr, size_t size) {
70
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 56 times.
 56 if (arr == nullptr || size == 0) {
71 ✗ return;
72 }
73
74 56 unsigned int num_threads = std::max(1U, std::thread::hardware_concurrency());
75
1/2
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
 56 if (size < 1000) {
76 num_threads = 3;
77 }
78
79 56 std::vector<uint64_t> bytes;
80
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 bytes.resize(size);
81
2/2
✓ Branch 0 taken 400 times.
✓ Branch 1 taken 56 times.
 456 for (size_t i = 0; i < size; ++i) {
82
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 320 times.
 800 bytes[i] = InBytes(arr[i]);
83 }
84
85 56 std::vector<uint64_t> temp;
86
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 temp.resize(size);
87
88 uint64_t *src_ptr = bytes.data();
89 uint64_t *dst_ptr = temp.data();
90
91
2/2
✓ Branch 0 taken 448 times.
✓ Branch 1 taken 56 times.
 504 for (int byte_idx = 0; byte_idx < 8; ++byte_idx) {
92
1/2
✓ Branch 1 taken 448 times.
✗ Branch 2 not taken.
 448 ExecuteRadixPass(src_ptr, dst_ptr, size, byte_idx, num_threads);
93 std::swap(src_ptr, dst_ptr);
94 }
95
96
2/2
✓ Branch 0 taken 400 times.
✓ Branch 1 taken 56 times.
 456 for (size_t i = 0; i < size; ++i) {
97
2/2
✓ Branch 0 taken 320 times.
✓ Branch 1 taken 80 times.
 800 arr[i] = FromBytes(src_ptr[i]);
98 }
99 }
100
101 ✗ std::pair<size_t, size_t> PapulinaYRadixSortSTL::GetThreadRange(size_t size, unsigned int num_threads,
102 unsigned int thread_idx) {
103 2688 size_t chunk = size / num_threads;
104 2688 size_t start = thread_idx * chunk;
105
0/2
✗ Branch 0 not taken.
✗ Branch 1 not taken.
 1792 size_t end = (thread_idx == num_threads - 1) ? size : (thread_idx + 1) * chunk;
106 ✗ return {start, end};
107 }
108
109 448 void PapulinaYRadixSortSTL::CountFrequencies(const uint64_t *src, size_t size, int byte_idx, unsigned int num_threads,
110 std::vector<std::vector<size_t>> &local_hists) {
111 448 std::vector<std::thread> workers;
112
1/2
✓ Branch 1 taken 448 times.
✗ Branch 2 not taken.
 448 workers.reserve(num_threads);
113
2/2
✓ Branch 0 taken 1344 times.
✓ Branch 1 taken 448 times.
 1792 for (unsigned int thread_idx = 0; thread_idx < num_threads; ++thread_idx) {
114
1/2
✓ Branch 1 taken 1344 times.
✗ Branch 2 not taken.
 1344 workers.emplace_back([&, thread_idx]() {
115
2/2
✓ Branch 0 taken 896 times.
✓ Branch 1 taken 448 times.
 1344 auto range = GetThreadRange(size, num_threads, thread_idx);
116 1344 const auto *byte_view = reinterpret_cast<const unsigned char *>(src);
117
2/2
✓ Branch 0 taken 3200 times.
✓ Branch 1 taken 1344 times.
 4544 for (size_t i = range.first; i < range.second; ++i) {
118 3200 local_hists[thread_idx][byte_view[(i * 8) + byte_idx]]++;
119 }
120 1344 });
121 }
122
2/2
✓ Branch 0 taken 1344 times.
✓ Branch 1 taken 448 times.
 1792 for (auto &worker : workers) {
123
1/2
✓ Branch 1 taken 1344 times.
✗ Branch 2 not taken.
 1344 worker.join();
124 }
125 448 }
126
127 ✗ void PapulinaYRadixSortSTL::ComputeOffsets(unsigned int num_threads,
128 const std::vector<std::vector<size_t>> &local_hists,
129 std::vector<std::vector<size_t>> &thread_pos) {
130 size_t total = 0;
131
2/4
✓ Branch 0 taken 114688 times.
✓ Branch 1 taken 448 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 115136 for (int bucket = 0; bucket < 256; ++bucket) {
132
2/4
✓ Branch 0 taken 344064 times.
✓ Branch 1 taken 114688 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 458752 for (unsigned int thread_idx = 0; thread_idx < num_threads; ++thread_idx) {
133 344064 thread_pos[thread_idx][bucket] = total;
134 344064 total += local_hists[thread_idx][bucket];
135 }
136 }
137 ✗ }
138
139 448 void PapulinaYRadixSortSTL::ReorderElements(const uint64_t *src, uint64_t *dst, size_t size, int byte_idx,
140 unsigned int num_threads, std::vector<std::vector<size_t>> &thread_pos) {
141 448 std::vector<std::thread> workers;
142
1/2
✓ Branch 1 taken 448 times.
✗ Branch 2 not taken.
 448 workers.reserve(num_threads);
143
2/2
✓ Branch 0 taken 1344 times.
✓ Branch 1 taken 448 times.
 1792 for (unsigned int thread_idx = 0; thread_idx < num_threads; ++thread_idx) {
144
1/2
✓ Branch 1 taken 1344 times.
✗ Branch 2 not taken.
 1344 workers.emplace_back([&, thread_idx]() {
145
2/2
✓ Branch 0 taken 896 times.
✓ Branch 1 taken 448 times.
 1344 auto range = GetThreadRange(size, num_threads, thread_idx);
146 1344 const auto *byte_view = reinterpret_cast<const unsigned char *>(src);
147
2/2
✓ Branch 0 taken 3200 times.
✓ Branch 1 taken 1344 times.
 4544 for (size_t i = range.first; i < range.second; ++i) {
148 3200 int bucket = byte_view[(i * 8) + byte_idx];
149 3200 dst[thread_pos[thread_idx][bucket]++] = src[i];
150 }
151 1344 });
152 }
153
2/2
✓ Branch 0 taken 1344 times.
✓ Branch 1 taken 448 times.
 1792 for (auto &worker : workers) {
154
1/2
✓ Branch 1 taken 1344 times.
✗ Branch 2 not taken.
 1344 worker.join();
155 }
156 448 }
157
158 448 void PapulinaYRadixSortSTL::ExecuteRadixPass(uint64_t *src, uint64_t *dst, size_t size, int byte_idx,
159 unsigned int num_threads) {
160
1/2
✓ Branch 2 taken 448 times.
✗ Branch 3 not taken.
 448 std::vector<std::vector<size_t>> local_hists(num_threads, std::vector<size_t>(256, 0));
161
2/4
✓ Branch 1 taken 448 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 448 times.
✗ Branch 5 not taken.
 448 std::vector<std::vector<size_t>> thread_pos(num_threads, std::vector<size_t>(256, 0));
162
163
1/2
✓ Branch 1 taken 448 times.
✗ Branch 2 not taken.
 448 CountFrequencies(src, size, byte_idx, num_threads, local_hists);
164 ComputeOffsets(num_threads, local_hists, thread_pos);
165
1/2
✓ Branch 1 taken 448 times.
✗ Branch 2 not taken.
 448 ReorderElements(src, dst, size, byte_idx, num_threads, thread_pos);
166 448 }
167
168 } // namespace papulina_y_radix_sort
169