GCC Code Coverage Report

Directory: ./
File: tasks/melnik_i_radix_sort_int/stl/src/ops_stl.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 124 125 99.2%
Functions: 14 14 100.0%
Branches: 84 116 72.4%
Line Branch Exec Source
1 #include "melnik_i_radix_sort_int/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <array>
5 #include <cstddef>
6 #include <cstdint>
7 #include <thread>
8 #include <utility>
9 #include <vector>
10
11 #include "melnik_i_radix_sort_int/common/include/common.hpp"
12 #include "util/include/util.hpp"
13
14 namespace melnik_i_radix_sort_int {
15
16 namespace {
17
18 42 std::vector<MelnikIRadixSortIntSTL::Range> BuildInitialRanges(std::size_t data_size, int num_ranges,
19 std::vector<int> *initial_buffer) {
20 42 std::vector<MelnikIRadixSortIntSTL::Range> ranges;
21
1/2
✓ Branch 1 taken 42 times.
✗ Branch 2 not taken.
 42 ranges.reserve(static_cast<std::size_t>(num_ranges));
22 42 const std::size_t chunk_size =
23 42 (data_size + static_cast<std::size_t>(num_ranges) - 1U) / static_cast<std::size_t>(num_ranges);
24
25
2/2
✓ Branch 0 taken 122 times.
✓ Branch 1 taken 36 times.
 158 for (int range_index = 0; range_index < num_ranges; ++range_index) {
26 122 const std::size_t begin = static_cast<std::size_t>(range_index) * chunk_size;
27
2/2
✓ Branch 0 taken 116 times.
✓ Branch 1 taken 6 times.
 122 if (begin >= data_size) {
28 break;
29 }
30
1/2
✓ Branch 1 taken 116 times.
✗ Branch 2 not taken.
 116 const std::size_t end = std::min(begin + chunk_size, data_size);
31
1/4
✓ Branch 1 taken 116 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 116 ranges.push_back(MelnikIRadixSortIntSTL::Range{.begin = begin, .end = end, .buffer = initial_buffer});
32 }
33
34 42 return ranges;
35 }
36
37 } // namespace
38
39
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 MelnikIRadixSortIntSTL::MelnikIRadixSortIntSTL(const InType &in) {
40 SetTypeOfTask(GetStaticTypeOfTask());
41
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 GetInput() = in;
42 GetOutput() = {};
43 56 }
44
45 56 bool MelnikIRadixSortIntSTL::ValidationImpl() {
46 56 return !GetInput().empty();
47 }
48
49 56 bool MelnikIRadixSortIntSTL::PreProcessingImpl() {
50 56 GetOutput() = GetInput();
51 56 return !GetOutput().empty();
52 }
53
54
1/2
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
 56 bool MelnikIRadixSortIntSTL::RunImpl() {
55
1/2
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
 56 if (GetOutput().empty()) {
56 return false;
57 }
58
59 const std::size_t data_size = GetOutput().size();
60 56 const int requested_threads = std::max(1, ppc::util::GetNumThreads());
61 56 const int num_threads = std::min<int>(requested_threads, static_cast<int>(data_size));
62
63
2/2
✓ Branch 1 taken 14 times.
✓ Branch 2 taken 42 times.
 56 std::vector<int> buffer(data_size);
64 auto &output = GetOutput();
65
66
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 42 times.
 56 if (num_threads <= 1) {
67
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 auto *final_buffer = RadixSortRange(output, buffer, 0, data_size);
68
1/2
✓ Branch 0 taken 14 times.
✗ Branch 1 not taken.
 14 if (final_buffer != &output) {
69 output.swap(*final_buffer);
70 }
71 14 return !output.empty();
72 }
73
74
1/2
✓ Branch 1 taken 42 times.
✗ Branch 2 not taken.
 42 std::vector<Range> ranges = BuildInitialRanges(data_size, num_threads, &output);
75 42 const int active_ranges = static_cast<int>(ranges.size());
76
77 42 std::vector<std::thread> workers;
78
1/2
✓ Branch 1 taken 42 times.
✗ Branch 2 not taken.
 42 workers.reserve(static_cast<std::size_t>(active_ranges));
79
80
2/2
✓ Branch 0 taken 116 times.
✓ Branch 1 taken 42 times.
 158 for (int i = 0; i < active_ranges; ++i) {
81
1/2
✓ Branch 1 taken 116 times.
✗ Branch 2 not taken.
 116 workers.emplace_back([&, i]() {
82
1/2
✓ Branch 0 taken 116 times.
✗ Branch 1 not taken.
 116 Range &range = ranges[static_cast<std::size_t>(i)];
83
1/2
✓ Branch 0 taken 116 times.
✗ Branch 1 not taken.
 116 if (range.begin < range.end) {
84 116 range.buffer = RadixSortRange(output, buffer, range.begin, range.end);
85 }
86 116 });
87 }
88
89
2/2
✓ Branch 0 taken 116 times.
✓ Branch 1 taken 42 times.
 158 for (auto &worker : workers) {
90
1/2
✓ Branch 1 taken 116 times.
✗ Branch 2 not taken.
 116 worker.join();
91 }
92
93
1/2
✓ Branch 1 taken 42 times.
✗ Branch 2 not taken.
 42 MergeSortedRanges(output, buffer, ranges);
94 42 return !GetOutput().empty();
95 42 }
96
97
1/2
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
 56 bool MelnikIRadixSortIntSTL::PostProcessingImpl() {
98 56 return std::ranges::is_sorted(GetOutput());
99 }
100
101 86 void MelnikIRadixSortIntSTL::CountingSortByByte(const std::vector<int> &source, std::vector<int> &destination,
102 std::size_t begin, std::size_t end, std::int64_t exp,
103 std::int64_t offset, const std::array<std::size_t, kBuckets> &count) {
104 86 std::array<std::size_t, kBuckets> positions{};
105 86 positions.at(0) = begin;
106
2/2
✓ Branch 0 taken 21930 times.
✓ Branch 1 taken 86 times.
 22016 for (std::size_t bucket = 1; bucket < kBuckets; ++bucket) {
107 21930 positions.at(bucket) = positions.at(bucket - 1U) + count.at(bucket - 1U);
108 }
109
110
2/2
✓ Branch 0 taken 244 times.
✓ Branch 1 taken 86 times.
 330 for (std::size_t index = begin; index < end; ++index) {
111 244 const std::int64_t shifted_value = static_cast<std::int64_t>(source[index]) + offset;
112
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 244 times.
 244 const auto bucket = static_cast<std::size_t>((shifted_value / exp) % static_cast<std::int64_t>(kBuckets));
113 244 destination[positions.at(bucket)] = source[index];
114 244 ++positions.at(bucket);
115 }
116 86 }
117
118 130 std::vector<int> *MelnikIRadixSortIntSTL::RadixSortRange(std::vector<int> &data, std::vector<int> &buffer,
119 std::size_t begin, std::size_t end) {
120
2/2
✓ Branch 0 taken 86 times.
✓ Branch 1 taken 44 times.
 130 if (end - begin <= 1) {
121 return &data;
122 }
123
124 const auto range_begin = data.begin() + static_cast<ptrdiff_t>(begin);
125 const auto range_end = data.begin() + static_cast<ptrdiff_t>(end);
126
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 72 times.
 86 const auto [min_it, max_it] = std::ranges::minmax_element(range_begin, range_end);
127 86 const auto min_value = static_cast<std::int64_t>(*min_it);
128 86 const auto max_value = static_cast<std::int64_t>(*max_it);
129
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 72 times.
 86 const std::int64_t offset = (min_value < 0) ? -min_value : 0;
130 86 const std::int64_t max_shifted_value = max_value + offset;
131
132 86 std::vector<std::array<std::size_t, kBuckets>> all_counts;
133
2/2
✓ Branch 0 taken 86 times.
✓ Branch 1 taken 86 times.
 172 for (std::int64_t exp = 1; max_shifted_value / exp > 0; exp <<= kBitsPerPass) {
134
1/2
✓ Branch 1 taken 86 times.
✗ Branch 2 not taken.
 86 all_counts.emplace_back();
135 all_counts.back().fill(0);
136 }
137
138
2/2
✓ Branch 0 taken 244 times.
✓ Branch 1 taken 86 times.
 330 for (std::size_t index = begin; index < end; ++index) {
139 244 std::int64_t val = static_cast<std::int64_t>(data[index]) + offset;
140
2/2
✓ Branch 0 taken 244 times.
✓ Branch 1 taken 244 times.
 488 for (auto &count_table : all_counts) {
141
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 244 times.
 244 count_table.at(static_cast<std::size_t>(val % static_cast<std::int64_t>(kBuckets)))++;
142 244 val /= static_cast<std::int64_t>(kBuckets);
143 }
144 }
145
146 std::vector<int> *source = &data;
147 std::vector<int> *destination = &buffer;
148 std::int64_t exp = 1;
149
150
2/2
✓ Branch 0 taken 86 times.
✓ Branch 1 taken 86 times.
 172 for (const auto &count_table : all_counts) {
151
1/2
✓ Branch 1 taken 86 times.
✗ Branch 2 not taken.
 86 CountingSortByByte(*source, *destination, begin, end, exp, offset, count_table);
152 std::swap(source, destination);
153 86 exp <<= kBitsPerPass;
154 }
155
156 return source;
157 }
158
159 74 void MelnikIRadixSortIntSTL::MergeRanges(const std::vector<int> &left_source, const std::vector<int> &right_source,
160 std::vector<int> &destination, Range left, Range right,
161 std::size_t write_begin) {
162 74 std::size_t left_index = left.begin;
163 74 std::size_t right_index = right.begin;
164 std::size_t write_index = write_begin;
165
166
4/4
✓ Branch 0 taken 226 times.
✓ Branch 1 taken 40 times.
✓ Branch 2 taken 192 times.
✓ Branch 3 taken 34 times.
 266 while (left_index < left.end && right_index < right.end) {
167
2/2
✓ Branch 0 taken 134 times.
✓ Branch 1 taken 58 times.
 192 if (left_source[left_index] <= right_source[right_index]) {
168 134 destination[write_index] = left_source[left_index];
169 134 ++left_index;
170 } else {
171 58 destination[write_index] = right_source[right_index];
172 58 ++right_index;
173 }
174 192 ++write_index;
175 }
176
177
2/2
✓ Branch 0 taken 34 times.
✓ Branch 1 taken 40 times.
 74 if (left_index < left.end) {
178 34 std::copy(left_source.begin() + static_cast<ptrdiff_t>(left_index),
179 left_source.begin() + static_cast<ptrdiff_t>(left.end),
180 destination.begin() + static_cast<ptrdiff_t>(write_index));
181
1/2
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
 40 } else if (right_index < right.end) {
182 40 std::copy(right_source.begin() + static_cast<ptrdiff_t>(right_index),
183 right_source.begin() + static_cast<ptrdiff_t>(right.end),
184 destination.begin() + static_cast<ptrdiff_t>(write_index));
185 }
186 74 }
187
188 172 void MelnikIRadixSortIntSTL::EnsureRangeInBuffer(Range &range, std::vector<int> *target_buffer) {
189
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 128 times.
 172 if (range.buffer == target_buffer) {
190 return;
191 }
192 44 std::copy(range.buffer->begin() + static_cast<ptrdiff_t>(range.begin),
193 44 range.buffer->begin() + static_cast<ptrdiff_t>(range.end),
194 44 target_buffer->begin() + static_cast<ptrdiff_t>(range.begin));
195 44 range.buffer = target_buffer;
196 }
197
198 98 MelnikIRadixSortIntSTL::Range MelnikIRadixSortIntSTL::ProcessMergePair(std::size_t pair_index,
199 const std::vector<Range> &current_ranges,
200 std::vector<int> *majority_source,
201 std::vector<int> *level_dest) {
202
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 74 times.
 98 const std::size_t left_pos = pair_index * 2U;
203 98 Range left = current_ranges[left_pos];
204
205
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 74 times.
 98 if (left_pos + 1U >= current_ranges.size()) {
206 24 EnsureRangeInBuffer(left, majority_source);
207 24 return left;
208 }
209
210 74 Range right = current_ranges[left_pos + 1U];
211 74 EnsureRangeInBuffer(left, majority_source);
212 74 EnsureRangeInBuffer(right, majority_source);
213 74 MergeRanges(*majority_source, *majority_source, *level_dest, left, right, left.begin);
214 74 return Range{.begin = left.begin, .end = right.end, .buffer = level_dest};
215 }
216
217
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 42 times.
 42 void MelnikIRadixSortIntSTL::MergeSortedRanges(std::vector<int> &data, std::vector<int> &buffer,
218 std::vector<Range> &ranges) {
219
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 42 times.
 42 if (ranges.empty()) {
220 ✗ return;
221 }
222
223 42 std::vector<Range> current_ranges = ranges;
224
225
2/2
✓ Branch 0 taken 70 times.
✓ Branch 1 taken 42 times.
 112 while (current_ranges.size() > 1U) {
226 70 const std::size_t merged_count = (current_ranges.size() + 1U) / 2U;
227
3/6
✓ Branch 1 taken 70 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 42 times.
✓ Branch 4 taken 28 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 70 std::vector<Range> next_ranges(merged_count);
228 70 std::vector<int> *majority_source = current_ranges[0].buffer;
229
2/2
✓ Branch 0 taken 42 times.
✓ Branch 1 taken 28 times.
 70 std::vector<int> *level_dest = (majority_source == &data) ? &buffer : &data;
230
231 70 std::vector<std::thread> workers;
232
1/2
✓ Branch 1 taken 70 times.
✗ Branch 2 not taken.
 70 workers.reserve(merged_count);
233
234
2/2
✓ Branch 0 taken 98 times.
✓ Branch 1 taken 70 times.
 168 for (std::size_t pair_index = 0; pair_index < merged_count; ++pair_index) {
235
1/2
✓ Branch 1 taken 98 times.
✗ Branch 2 not taken.
 98 workers.emplace_back([&, pair_index, majority_source, level_dest]() {
236 98 next_ranges[pair_index] = ProcessMergePair(pair_index, current_ranges, majority_source, level_dest);
237 98 });
238 }
239
240
2/2
✓ Branch 0 taken 98 times.
✓ Branch 1 taken 70 times.
 168 for (auto &worker : workers) {
241
1/2
✓ Branch 1 taken 98 times.
✗ Branch 2 not taken.
 98 worker.join();
242 }
243
244 current_ranges = std::move(next_ranges);
245 70 }
246
247
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 22 times.
 42 if (current_ranges[0].buffer != &data) {
248 data.swap(*current_ranges[0].buffer);
249 }
250 }
251
252 } // namespace melnik_i_radix_sort_int
253