GCC Code Coverage Report

Directory: ./
File: tasks/votincev_d_radixmerge_sort/stl/src/ops_stl.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 45 80 56.2%
Functions: 7 8 87.5%
Branches: 26 84 31.0%
Line Branch Exec Source
1 #include "votincev_d_radixmerge_sort/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <array>
5 #include <cmath>
6 #include <cstddef>
7 #include <cstdint>
8 #include <future>
9 #include <utility>
10 #include <vector>
11
12 #include "votincev_d_radixmerge_sort/common/include/common.hpp"
13
14 namespace votincev_d_radixmerge_sort {
15
16
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 VotincevDRadixMergeSortSTL::VotincevDRadixMergeSortSTL(const InType &in) {
17 SetTypeOfTask(GetStaticTypeOfTask());
18
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 GetInput() = in;
19 80 }
20
21 80 bool VotincevDRadixMergeSortSTL::ValidationImpl() {
22 80 return !GetInput().empty();
23 }
24
25 80 bool VotincevDRadixMergeSortSTL::PreProcessingImpl() {
26 80 return true;
27 }
28
29 80 void VotincevDRadixMergeSortSTL::LocalRadixSort(uint32_t *begin, uint32_t *end) {
30 80 auto n = static_cast<int32_t>(end - begin);
31
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 80 times.
 80 if (n <= 1) {
32 ✗ return;
33 }
34
35 80 uint32_t max_val = *std::max_element(begin, end);
36
37 80 std::vector<uint32_t> buffer(static_cast<size_t>(n));
38 uint32_t *src = begin;
39 uint32_t *dst = buffer.data();
40
41
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 80 times.
 224 for (int64_t exp = 1; (static_cast<int64_t>(max_val) / exp) > 0; exp *= 10) {
42 144 std::array<int32_t, 10> count{};
43
44
2/2
✓ Branch 0 taken 101600 times.
✓ Branch 1 taken 144 times.
 101744 for (int32_t i = 0; i < n; ++i) {
45
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 101600 times.
 101600 count.at(static_cast<size_t>((src[i] / exp) % 10))++;
46 }
47
2/2
✓ Branch 0 taken 1296 times.
✓ Branch 1 taken 144 times.
 1440 for (int32_t i = 1; i < 10; ++i) {
48 1296 count.at(static_cast<size_t>(i)) += count.at(static_cast<size_t>(i - 1));
49 }
50
2/2
✓ Branch 0 taken 101600 times.
✓ Branch 1 taken 144 times.
 101744 for (int32_t i = n - 1; i >= 0; --i) {
51
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 101600 times.
 101600 auto digit = static_cast<size_t>((src[i] / exp) % 10);
52 101600 size_t target_idx = static_cast<size_t>(count.at(digit)) - 1;
53 101600 dst[target_idx] = src[i];
54 101600 count.at(digit)--;
55 }
56 std::swap(src, dst);
57 }
58
59
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 48 times.
 80 if (src != begin) {
60 32 std::copy(src, src + n, begin);
61 }
62 }
63
64 ✗ void VotincevDRadixMergeSortSTL::Merge(const uint32_t *src, uint32_t *dst, int32_t left, int32_t mid, int32_t right) {
65 int32_t i = left;
66 int32_t j = mid;
67 int32_t k = left;
68 ✗ while (i < mid && j < right) {
69 ✗ dst[k++] = (src[i] <= src[j]) ? src[i++] : src[j++];
70 }
71 ✗ while (i < mid) {
72 ✗ dst[k++] = src[i++];
73 }
74 ✗ while (j < right) {
75 ✗ dst[k++] = src[j++];
76 }
77 ✗ }
78
79 80 void VotincevDRadixMergeSortSTL::ParallelRadixMergeSort(uint32_t *data, int32_t n, uint32_t *temp) {
80 const int32_t grain_size = 4096;
81
1/2
✓ Branch 0 taken 80 times.
✗ Branch 1 not taken.
 80 if (n <= grain_size) {
82 80 LocalRadixSort(data, data + n);
83 80 return;
84 }
85
86 ✗ std::vector<std::future<void>> futures;
87
88 ✗ int32_t num_blocks = (n + grain_size - 1) / grain_size;
89 ✗ futures.reserve(static_cast<size_t>(num_blocks));
90
91 ✗ for (int32_t i = 0; i < num_blocks; ++i) {
92 ✗ int32_t left = i * grain_size;
93 ✗ int32_t right = std::min(left + grain_size, n);
94
95 ✗ futures.push_back(std::async(std::launch::async, [data, left, right] {
96 ✗ VotincevDRadixMergeSortSTL::LocalRadixSort(data + left, data + right);
97 }));
98 }
99 ✗ for (auto &f : futures) {
100 ✗ f.get();
101 }
102 futures.clear();
103
104 uint32_t *src = data;
105 uint32_t *dst = temp;
106
107 ✗ for (int32_t width = grain_size; width < n; width *= 2) {
108 ✗ int32_t num_merges = (n + (2 * width) - 1) / (2 * width);
109
110 ✗ for (int32_t i = 0; i < num_merges; ++i) {
111 ✗ int32_t left = i * 2 * width;
112 ✗ int32_t mid = std::min(left + width, n);
113 ✗ int32_t right = std::min(left + (2 * width), n);
114
115 ✗ if (mid < right) {
116 ✗ futures.push_back(std::async(std::launch::async, [src, dst, left, mid, right] {
117 ✗ VotincevDRadixMergeSortSTL::Merge(src, dst, left, mid, right);
118 }));
119 ✗ } else if (left < n) {
120 ✗ std::copy(src + left, src + mid, dst + left);
121 }
122 }
123 ✗ for (auto &f : futures) {
124 ✗ f.get();
125 }
126 futures.clear();
127
128 std::swap(src, dst);
129 }
130
131 ✗ if (src != data) {
132 ✗ std::copy(src, src + n, data);
133 }
134 ✗ }
135
136
1/2
✓ Branch 0 taken 80 times.
✗ Branch 1 not taken.
 80 bool VotincevDRadixMergeSortSTL::RunImpl() {
137 const auto &input = GetInput();
138 80 auto n = static_cast<int32_t>(input.size());
139
140
1/2
✓ Branch 0 taken 80 times.
✗ Branch 1 not taken.
 80 if (n == 0) {
141 return true;
142 }
143
144 80 int32_t min_val = *std::ranges::min_element(input.begin(), input.end());
145
146 80 std::vector<uint32_t> working_array(static_cast<size_t>(n));
147
2/2
✓ Branch 0 taken 44800 times.
✓ Branch 1 taken 80 times.
 44880 for (int32_t i = 0; i < n; ++i) {
148 44800 working_array[static_cast<size_t>(i)] =
149 44800 static_cast<uint32_t>(input[static_cast<size_t>(i)]) - static_cast<uint32_t>(min_val);
150 }
151
152
2/6
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 80 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 80 std::vector<uint32_t> temp_buffer(static_cast<size_t>(n));
153
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 ParallelRadixMergeSort(working_array.data(), n, temp_buffer.data());
154
155
1/4
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 80 std::vector<int32_t> result(static_cast<size_t>(n));
156
2/2
✓ Branch 0 taken 44800 times.
✓ Branch 1 taken 80 times.
 44880 for (int32_t i = 0; i < n; ++i) {
157 44800 result[static_cast<size_t>(i)] =
158 44800 static_cast<int32_t>(working_array[static_cast<size_t>(i)] + static_cast<uint32_t>(min_val));
159 }
160
161 GetOutput() = std::move(result);
162 return true;
163 }
164
165 80 bool VotincevDRadixMergeSortSTL::PostProcessingImpl() {
166 80 return true;
167 }
168
169 } // namespace votincev_d_radixmerge_sort
170