GCC Code Coverage Report

Directory: ./
File: tasks/shemetov_d_radix_odd_even_mergesort/stl/src/ops_stl.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 79 79 100.0%
Functions: 7 7 100.0%
Branches: 65 82 79.3%
Line Branch Exec Source
1 #include "shemetov_d_radix_odd_even_mergesort/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <climits>
5 #include <cstddef>
6 #include <future>
7 #include <vector>
8
9 #include "shemetov_d_radix_odd_even_mergesort/common/include/common.hpp"
10 #include "util/include/util.hpp"
11
12 namespace shemetov_d_radix_odd_even_mergesort {
13
14
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 ShemetovDRadixOddEvenMergeSortSTL::ShemetovDRadixOddEvenMergeSortSTL(const InType &in) {
15 SetTypeOfTask(GetStaticTypeOfTask());
16 GetInput() = in;
17 96 }
18
19 176 void ShemetovDRadixOddEvenMergeSortSTL::RadixSort(std::vector<int> &array, size_t left, size_t right) {
20
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 148 times.
 176 if (left >= right) {
21 28 return;
22 }
23
24
1/2
✓ Branch 0 taken 148 times.
✗ Branch 1 not taken.
 148 int maximum = *std::max_element(array.begin() + static_cast<int>(left), array.begin() + static_cast<int>(right) + 1);
25
26 148 size_t segment = right - left + 1;
27
28 148 std::vector<int> buffer(segment);
29
1/4
✓ Branch 1 taken 148 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 148 std::vector<int> position(256, 0);
30
31
1/2
✓ Branch 0 taken 310 times.
✗ Branch 1 not taken.
 310 for (size_t merge_shift = 0; merge_shift < 32; merge_shift += 8) {
32
1/4
✓ Branch 1 taken 310 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 310 position.assign(256, 0);
33
34
2/2
✓ Branch 0 taken 2488 times.
✓ Branch 1 taken 310 times.
 2798 for (size_t i = left; i <= right; i += 1) {
35 2488 int apply_bitmask = (array[i] >> merge_shift) & 0xFF;
36
37 2488 position[apply_bitmask] += 1;
38 }
39
40
2/2
✓ Branch 0 taken 79050 times.
✓ Branch 1 taken 310 times.
 79360 for (size_t i = 1; i < 256; i += 1) {
41 79050 position[i] += position[i - 1];
42 }
43
44
2/2
✓ Branch 0 taken 2488 times.
✓ Branch 1 taken 310 times.
 2798 for (size_t i = segment; i > 0; i -= 1) {
45 2488 size_t current_index = left + i - 1;
46 2488 int apply_bitmask = (array[current_index] >> merge_shift) & 0xFF;
47
48 2488 buffer[position[apply_bitmask] -= 1] = array[current_index];
49 }
50
51
2/2
✓ Branch 0 taken 2488 times.
✓ Branch 1 taken 310 times.
 2798 for (size_t i = 0; i < segment; i += 1) {
52 2488 array[left + i] = buffer[i];
53 }
54
55
2/2
✓ Branch 0 taken 162 times.
✓ Branch 1 taken 148 times.
 310 if ((maximum >> merge_shift) < 256) {
56 break;
57 }
58 }
59 }
60
61 96 void ShemetovDRadixOddEvenMergeSortSTL::OddEvenMerge(std::vector<int> &array, size_t start_offset, size_t segment) {
62
1/2
✓ Branch 0 taken 96 times.
✗ Branch 1 not taken.
 96 if (segment <= 1) {
63 return;
64 }
65
66 96 size_t padding = segment / 2;
67
68
2/2
✓ Branch 0 taken 518 times.
✓ Branch 1 taken 96 times.
 614 for (size_t index = 0; index < padding; index += 1) {
69
2/2
✓ Branch 0 taken 100 times.
✓ Branch 1 taken 418 times.
 518 if (array[start_offset + index] > array[start_offset + padding + index]) {
70 std::swap(array[start_offset + index], array[start_offset + padding + index]);
71 }
72 }
73
74
2/2
✓ Branch 0 taken 184 times.
✓ Branch 1 taken 96 times.
 280 for (padding = segment / 4; padding > 0; padding /= 2) {
75 184 size_t step = padding * 2;
76 184 size_t num_indices = ((segment - padding) / step) * padding;
77
78
2/2
✓ Branch 0 taken 1082 times.
✓ Branch 1 taken 184 times.
 1266 for (size_t index = 0; index < num_indices; index += 1) {
79 1082 size_t i = index % padding;
80 1082 size_t start_position = padding + ((index / padding) * step);
81
82
2/2
✓ Branch 0 taken 272 times.
✓ Branch 1 taken 810 times.
 1082 if (array[start_offset + start_position + i] > array[start_offset + start_position + i + padding]) {
83 std::swap(array[start_offset + start_position + i], array[start_offset + start_position + i + padding]);
84 }
85 }
86 }
87 }
88
89 96 bool ShemetovDRadixOddEvenMergeSortSTL::ValidationImpl() {
90 const auto &[size, array] = GetInput();
91
3/4
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 88 times.
 96 return size > 0 && static_cast<size_t>(size) == array.size();
92 }
93
94
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 8 times.
 96 bool ShemetovDRadixOddEvenMergeSortSTL::PreProcessingImpl() {
95 const auto &[size, array] = GetInput();
96
97
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 8 times.
 96 if (size == 0) {
98 return true;
99 }
100
101 88 array_ = array;
102
103 88 offset_ = *std::ranges::min_element(array_.begin(), array_.end());
104 88 size_ = static_cast<size_t>(size);
105 88 power_ = 1;
106
107
2/2
✓ Branch 0 taken 256 times.
✓ Branch 1 taken 88 times.
 344 while (power_ < size_) {
108 256 power_ *= 2;
109 }
110
111
2/2
✓ Branch 0 taken 736 times.
✓ Branch 1 taken 88 times.
 824 for (size_t i = 0; i < size_; i += 1) {
112 736 array_[i] -= offset_;
113 }
114
115
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 40 times.
 88 if (power_ > size_) {
116 48 array_.resize(power_, INT_MAX);
117 }
118
119 return true;
120 }
121
122 96 bool ShemetovDRadixOddEvenMergeSortSTL::RunImpl() {
123
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 16 times.
 96 if (power_ <= 1) {
124 return true;
125 }
126
127 80 size_t threads = ppc::util::GetNumThreads();
128
129 size_t limit = 1;
130
2/2
✓ Branch 0 taken 78 times.
✓ Branch 1 taken 80 times.
 158 while (limit * 2 <= std::min(threads, power_)) {
131 limit *= 2;
132 }
133
134 80 size_t chunk_size = power_ / limit;
135
136 80 std::vector<std::future<void>> sort;
137
2/2
✓ Branch 0 taken 176 times.
✓ Branch 1 taken 80 times.
 256 for (size_t i = 0; i < limit; i += 1) {
138 176 size_t left = i * chunk_size;
139 176 size_t right = left + chunk_size - 1;
140
141
1/2
✓ Branch 1 taken 176 times.
✗ Branch 2 not taken.
 352 sort.push_back(std::async(std::launch::async, [this, left, right]() {
142
1/2
✓ Branch 1 taken 176 times.
✗ Branch 2 not taken.
 176 ShemetovDRadixOddEvenMergeSortSTL::RadixSort(this->array_, left, right);
143 }));
144 }
145
2/2
✓ Branch 0 taken 176 times.
✓ Branch 1 taken 80 times.
 256 for (auto &sorted : sort) {
146
1/2
✓ Branch 1 taken 176 times.
✗ Branch 2 not taken.
 176 sorted.get();
147 }
148
149
2/2
✓ Branch 0 taken 78 times.
✓ Branch 1 taken 80 times.
 158 for (size_t segment = chunk_size * 2; segment <= power_; segment *= 2) {
150 78 std::vector<std::future<void>> merge;
151
152
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 78 times.
 174 for (size_t i = 0; i < power_; i += segment) {
153
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 192 merge.push_back(std::async(std::launch::async, [this, i, segment]() {
154 96 ShemetovDRadixOddEvenMergeSortSTL::OddEvenMerge(this->array_, i, segment);
155 }));
156 }
157
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 78 times.
 174 for (auto &merged : merge) {
158
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 merged.get();
159 }
160 78 }
161
162 return true;
163 80 }
164
165 96 bool ShemetovDRadixOddEvenMergeSortSTL::PostProcessingImpl() {
166
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 88 times.
 96 if (size_ == 0) {
167 return true;
168 }
169
170 88 array_.resize(size_);
171
172
2/2
✓ Branch 0 taken 736 times.
✓ Branch 1 taken 88 times.
 824 for (size_t i = 0; i < size_; i += 1) {
173 736 array_[i] += offset_;
174 }
175
176
1/2
✓ Branch 0 taken 88 times.
✗ Branch 1 not taken.
 88 if (!std::ranges::is_sorted(array_.begin(), array_.end())) {
177 return false;
178 }
179
180 88 GetOutput() = array_;
181 88 return true;
182 }
183
184 } // namespace shemetov_d_radix_odd_even_mergesort
185