GCC Code Coverage Report

Directory: ./
File: tasks/chernov_t_radix_sort/stl/src/ops_stl.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 32 119 26.9%
Functions: 6 15 40.0%
Branches: 27 134 20.1%
Line Branch Exec Source
1 #include "chernov_t_radix_sort/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <cstdint>
6 #include <thread>
7 #include <vector>
8
9 #include "chernov_t_radix_sort/common/include/common.hpp"
10 #include "util/include/util.hpp"
11
12 namespace chernov_t_radix_sort {
13
14
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 ChernovTRadixSortSTL::ChernovTRadixSortSTL(const InType &in) {
15 SetTypeOfTask(GetStaticTypeOfTask());
16
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 GetInput() = in;
17 GetOutput() = {};
18 64 }
19
20 64 bool ChernovTRadixSortSTL::ValidationImpl() {
21 64 return true;
22 }
23
24 64 bool ChernovTRadixSortSTL::PreProcessingImpl() {
25 64 GetOutput() = GetInput();
26 64 return true;
27 }
28
29 constexpr int kBitsPerDigit = 8;
30 constexpr int kRadix = 1 << kBitsPerDigit;
31 constexpr uint32_t kSignMask = 0x80000000U;
32
33
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 void ChernovTRadixSortSTL::RadixSortLSDSequential(std::vector<int> &data) {
34
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 if (data.size() <= 1) {
35 ✗ return;
36 }
37
38 const size_t n = data.size();
39 48 std::vector<uint32_t> temp(n);
40
2/2
✓ Branch 0 taken 328 times.
✓ Branch 1 taken 48 times.
 376 for (size_t i = 0; i < n; ++i) {
41 328 temp[i] = static_cast<uint32_t>(data[i]) ^ kSignMask;
42 }
43
44
1/4
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 48 std::vector<uint32_t> buffer(n);
45
46
2/2
✓ Branch 0 taken 192 times.
✓ Branch 1 taken 48 times.
 240 for (int byte = 0; byte < 4; ++byte) {
47 192 const int shift = byte * kBitsPerDigit;
48
1/4
✓ Branch 1 taken 192 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 192 std::vector<int> count(kRadix, 0);
49
50
2/2
✓ Branch 0 taken 1312 times.
✓ Branch 1 taken 192 times.
 1504 for (size_t i = 0; i < n; ++i) {
51 1312 ++count[static_cast<int>((temp[i] >> shift) & 0xFFU)];
52 }
53
2/2
✓ Branch 0 taken 48960 times.
✓ Branch 1 taken 192 times.
 49152 for (int i = 1; i < kRadix; ++i) {
54 48960 count[i] += count[i - 1];
55 }
56
2/2
✓ Branch 0 taken 1312 times.
✓ Branch 1 taken 192 times.
 1504 for (size_t i = n; i-- > 0;) {
57 1312 buffer[static_cast<size_t>(--count[static_cast<int>((temp[i] >> shift) & 0xFFU)])] = temp[i];
58 }
59 temp.swap(buffer);
60 }
61
62
2/2
✓ Branch 0 taken 328 times.
✓ Branch 1 taken 48 times.
 376 for (size_t i = 0; i < n; ++i) {
63 328 data[i] = static_cast<int>(temp[i] ^ kSignMask);
64 }
65 }
66
67 ✗ void ChernovTRadixSortSTL::ConvertToIntegers(const std::vector<int> &input, std::vector<uint32_t> &output, size_t start,
68 size_t end, uint32_t sign_mask) {
69 ✗ for (size_t i = start; i < end; ++i) {
70 ✗ output[i] = static_cast<uint32_t>(input[i]) ^ sign_mask;
71 }
72 ✗ }
73
74 ✗ void ChernovTRadixSortSTL::ComputeLocalHistograms(const std::vector<uint32_t> &data,
75 std::vector<std::vector<int>> &local_counts, size_t start, size_t end,
76 int shift, int thread_idx) {
77 ✗ auto &cnt = local_counts[static_cast<size_t>(thread_idx)];
78 ✗ for (size_t i = start; i < end; ++i) {
79 ✗ int digit = static_cast<int>((data[i] >> shift) & 0xFFU);
80 ✗ ++cnt[digit];
81 }
82 ✗ }
83
84 ✗ void ChernovTRadixSortSTL::ComputeGlobalStarts(const std::vector<std::vector<int>> &local_counts,
85 std::vector<int> &global_start, int k_radix, int num_threads) {
86 int current_pos = 0;
87 ✗ for (int digit_idx = 0; digit_idx < k_radix; ++digit_idx) {
88 int total = 0;
89 ✗ for (int thread_idx = 0; thread_idx < num_threads; ++thread_idx) {
90 ✗ total += local_counts[static_cast<size_t>(thread_idx)][digit_idx];
91 }
92 ✗ global_start[digit_idx] = current_pos;
93 ✗ current_pos += total;
94 }
95 ✗ }
96
97 ✗ void ChernovTRadixSortSTL::ComputeThreadOffsets(const std::vector<std::vector<int>> &local_counts,
98 std::vector<std::vector<int>> &thread_offset, int k_radix,
99 int num_threads) {
100 ✗ for (int digit_idx = 0; digit_idx < k_radix; ++digit_idx) {
101 int offset = 0;
102 ✗ for (int thread_idx = 0; thread_idx < num_threads; ++thread_idx) {
103 ✗ thread_offset[static_cast<size_t>(thread_idx)][digit_idx] = offset;
104 ✗ offset += local_counts[static_cast<size_t>(thread_idx)][digit_idx];
105 }
106 }
107 ✗ }
108
109 ✗ void ChernovTRadixSortSTL::ScatterElements(const std::vector<uint32_t> &input, std::vector<uint32_t> &output,
110 const std::vector<int> &global_start,
111 const std::vector<std::vector<int>> &thread_offset,
112 std::vector<std::vector<int>> &local_counter, size_t start, size_t end,
113 int shift, int thread_idx) {
114 ✗ auto &my_counter = local_counter[static_cast<size_t>(thread_idx)];
115 ✗ for (size_t i = start; i < end; ++i) {
116 ✗ int digit = static_cast<int>((input[i] >> shift) & 0xFFU);
117 ✗ int pos = global_start[digit] + thread_offset[static_cast<size_t>(thread_idx)][digit] + my_counter[digit];
118 ✗ output[static_cast<size_t>(pos)] = input[i];
119 ✗ ++my_counter[digit];
120 }
121 ✗ }
122
123 ✗ void ChernovTRadixSortSTL::ConvertFromIntegers(const std::vector<uint32_t> &input, std::vector<int> &output,
124 size_t start, size_t end, uint32_t sign_mask) {
125 ✗ for (size_t i = start; i < end; ++i) {
126 ✗ output[i] = static_cast<int>(input[i] ^ sign_mask);
127 }
128 ✗ }
129
130 ✗ void ChernovTRadixSortSTL::RadixSortLSDParallel(std::vector<int> &data, int num_threads) {
131 ✗ const size_t n = data.size();
132 ✗ if (n <= 1) {
133 ✗ return;
134 }
135
136 ✗ std::vector<uint32_t> temp(n);
137 ✗ std::vector<std::thread> threads;
138 ✗ const size_t chunk_size = (n + static_cast<size_t>(num_threads) - 1) / static_cast<size_t>(num_threads);
139
140 ✗ for (int thread_idx = 0; thread_idx < num_threads; ++thread_idx) {
141 ✗ const size_t start = static_cast<size_t>(thread_idx) * chunk_size;
142 ✗ const size_t end = std::min(start + chunk_size, n);
143 ✗ threads.emplace_back([&data, &temp, start, end]() { ConvertToIntegers(data, temp, start, end, kSignMask); });
144 }
145 ✗ for (auto &th : threads) {
146 ✗ th.join();
147 }
148 ✗ threads.clear();
149
150 ✗ std::vector<uint32_t> buffer(n);
151
152 ✗ for (int byte_index = 0; byte_index < 4; ++byte_index) {
153 ✗ const int shift = byte_index * kBitsPerDigit;
154
155 // Гистограммы
156 ✗ std::vector<std::vector<int>> local_counts(static_cast<size_t>(num_threads), std::vector<int>(kRadix, 0));
157 ✗ for (int thread_idx = 0; thread_idx < num_threads; ++thread_idx) {
158 ✗ const size_t start = static_cast<size_t>(thread_idx) * chunk_size;
159 ✗ const size_t end = std::min(start + chunk_size, n);
160 ✗ threads.emplace_back([&temp, &local_counts, start, end, shift, thread_idx]() {
161 ✗ ComputeLocalHistograms(temp, local_counts, start, end, shift, thread_idx);
162 ✗ });
163 }
164 ✗ for (auto &th : threads) {
165 ✗ th.join();
166 }
167 ✗ threads.clear();
168
169 ✗ std::vector<int> global_start(kRadix, 0);
170 ComputeGlobalStarts(local_counts, global_start, kRadix, num_threads);
171
172 ✗ std::vector<std::vector<int>> thread_offset(static_cast<size_t>(num_threads), std::vector<int>(kRadix, 0));
173 ComputeThreadOffsets(local_counts, thread_offset, kRadix, num_threads);
174
175 ✗ std::vector<std::vector<int>> local_counter(static_cast<size_t>(num_threads), std::vector<int>(kRadix, 0));
176
177 ✗ for (int thread_idx = 0; thread_idx < num_threads; ++thread_idx) {
178 ✗ const size_t start = static_cast<size_t>(thread_idx) * chunk_size;
179 ✗ const size_t end = std::min(start + chunk_size, n);
180 ✗ threads.emplace_back(
181 ✗ [&temp, &buffer, &global_start, &thread_offset, &local_counter, start, end, shift, thread_idx]() {
182 ✗ ScatterElements(temp, buffer, global_start, thread_offset, local_counter, start, end, shift, thread_idx);
183 ✗ });
184 }
185 ✗ for (auto &th : threads) {
186 ✗ th.join();
187 }
188 ✗ threads.clear();
189
190 temp.swap(buffer);
191 ✗ }
192
193 ✗ for (int thread_idx = 0; thread_idx < num_threads; ++thread_idx) {
194 ✗ const size_t start = static_cast<size_t>(thread_idx) * chunk_size;
195 ✗ const size_t end = std::min(start + chunk_size, n);
196 ✗ threads.emplace_back([&temp, &data, start, end]() { ConvertFromIntegers(temp, data, start, end, kSignMask); });
197 }
198 ✗ for (auto &th : threads) {
199 ✗ th.join();
200 }
201 ✗ }
202
203
4/4
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 16 times.
✓ Branch 2 taken 48 times.
✓ Branch 3 taken 16 times.
 128 bool ChernovTRadixSortSTL::RunImpl() {
204 auto &data = GetOutput();
205
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 16 times.
 64 if (data.size() <= 1) {
206 return true;
207 }
208
209
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 if (data.size() < 1000) {
210 48 RadixSortLSDSequential(data);
211 48 return true;
212 }
213
214 ✗ const int num_threads = ppc::util::GetNumThreads();
215 ✗ RadixSortLSDParallel(data, num_threads);
216 ✗ return true;
217 }
218
219
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 8 times.
 64 bool ChernovTRadixSortSTL::PostProcessingImpl() {
220 64 return std::is_sorted(GetOutput().begin(), GetOutput().end());
221 }
222
223 } // namespace chernov_t_radix_sort
224