GCC Code Coverage Report

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