GCC Code Coverage Report

Directory: ./
File: tasks/levonychev_i_radix_batcher_sort/stl/src/ops_stl.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 90 94 95.7%
Functions: 12 13 92.3%
Branches: 65 102 63.7%
Line Branch Exec Source
1 #include "levonychev_i_radix_batcher_sort/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <array>
5 #include <cmath>
6 #include <cstddef>
7 #include <future>
8 #include <iterator>
9 #include <thread>
10 #include <vector>
11
12 #include "levonychev_i_radix_batcher_sort/common/include/common.hpp"
13 namespace levonychev_i_radix_batcher_sort {
14
15
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 LevonychevIRadixBatcherSortSTL::LevonychevIRadixBatcherSortSTL(const InType &in) {
16 SetTypeOfTask(GetStaticTypeOfTask());
17
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 GetInput() = in;
18 32 }
19
20
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 96 times.
 96 void LevonychevIRadixBatcherSortSTL::RadixSortSequential(std::vector<int> &arr) {
21
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 96 times.
 96 if (arr.empty()) {
22 ✗ return;
23 }
24 96 int n = static_cast<int>(arr.size());
25 96 std::vector<int> buffer(n);
26
27
2/2
✓ Branch 0 taken 384 times.
✓ Branch 1 taken 96 times.
 480 for (int byte_idx = 0; byte_idx < 4; ++byte_idx) {
28 384 std::array<int, 256> count{};
29 bool is_last_byte = (byte_idx == 3);
30
31
2/2
✓ Branch 0 taken 768 times.
✓ Branch 1 taken 384 times.
 1152 for (int x : arr) {
32 768 unsigned char b = (static_cast<unsigned int>(x) >> (byte_idx * 8)) & 0xFF;
33
2/2
✓ Branch 0 taken 192 times.
✓ Branch 1 taken 576 times.
 768 if (is_last_byte) {
34 192 b ^= 0x80;
35 }
36 768 count.at(b)++;
37 }
38
39 384 std::array<size_t, 256> offsets{};
40 offsets.at(0) = 0;
41
2/2
✓ Branch 0 taken 97920 times.
✓ Branch 1 taken 384 times.
 98304 for (int i = 1; i < 256; ++i) {
42 97920 offsets.at(i) = offsets.at(i - 1) + count.at(i - 1);
43 }
44
45
2/2
✓ Branch 0 taken 768 times.
✓ Branch 1 taken 384 times.
 1152 for (int x : arr) {
46 768 unsigned char b = (static_cast<unsigned int>(x) >> (byte_idx * 8)) & 0xFF;
47
2/2
✓ Branch 0 taken 192 times.
✓ Branch 1 taken 576 times.
 768 if (is_last_byte) {
48 192 b ^= 0x80;
49 }
50
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 768 times.
 768 buffer.at(offsets.at(b)++) = x;
51 }
52
1/2
✓ Branch 1 taken 384 times.
✗ Branch 2 not taken.
 384 arr = buffer;
53 }
54 }
55
56 120 void LevonychevIRadixBatcherSortSTL::MergeAndSplit(std::vector<int> &left_block, std::vector<int> &right_block) {
57
1/2
✓ Branch 1 taken 120 times.
✗ Branch 2 not taken.
 120 std::vector<int> merged;
58
1/2
✓ Branch 1 taken 120 times.
✗ Branch 2 not taken.
 120 merged.reserve(left_block.size() + right_block.size());
59
60
1/2
✓ Branch 1 taken 120 times.
✗ Branch 2 not taken.
 120 std::ranges::merge(left_block, right_block, std::back_inserter(merged));
61
62 auto mid = static_cast<std::ptrdiff_t>(left_block.size());
63 120 std::copy(merged.begin(), merged.begin() + mid, left_block.begin());
64
1/2
✓ Branch 0 taken 120 times.
✗ Branch 1 not taken.
 120 std::copy(merged.begin() + mid, merged.end(), right_block.begin());
65 120 }
66
67 32 bool LevonychevIRadixBatcherSortSTL::RunImpl() {
68 32 const std::vector<int> data = GetInput();
69
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 24 times.
 32 if (data.size() <= 1) {
70
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 GetOutput() = data;
71 return true;
72 }
73
74 24 const int num_blocks = GetNumBlocks(static_cast<int>(data.size()));
75
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 auto blocks = DistributeData(data, num_blocks);
76
77
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 ParallelRadixPhase(blocks);
78
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 BatcherMergePhase(blocks);
79
80 GetOutput().clear();
81
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 GetOutput().reserve(data.size());
82
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 24 times.
 120 for (const auto &b : blocks) {
83 96 GetOutput().insert(GetOutput().end(), b.begin(), b.end());
84 }
85
86 return true;
87 24 }
88
89 ✗ int LevonychevIRadixBatcherSortSTL::GetNumBlocks(int n) {
90 24 unsigned int threads_supported = std::thread::hardware_concurrency();
91
1/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
 24 int max_threads = static_cast<int>(threads_supported == 0 ? 2 : threads_supported);
92 int num_blocks = 1;
93
3/8
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 48 times.
✓ Branch 5 taken 24 times.
✓ Branch 6 taken 48 times.
✗ Branch 7 not taken.
 72 while (num_blocks * 2 <= max_threads && num_blocks * 2 <= n) {
94 num_blocks *= 2;
95 }
96 ✗ return num_blocks;
97 }
98
99 24 std::vector<std::vector<int>> LevonychevIRadixBatcherSortSTL::DistributeData(const std::vector<int> &data,
100 int num_blocks) {
101 24 std::vector<std::vector<int>> blocks(num_blocks);
102 24 const int n = static_cast<int>(data.size());
103 24 const int base_size = n / num_blocks;
104 24 const int extra = n % num_blocks;
105
106 int current_pos = 0;
107
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 24 times.
 120 for (int i = 0; i < num_blocks; ++i) {
108
1/2
✓ Branch 0 taken 96 times.
✗ Branch 1 not taken.
 96 int size = base_size + (i < extra ? 1 : 0);
109
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 96 times.
 96 blocks.at(i).assign(data.begin() + current_pos, data.begin() + current_pos + size);
110 96 current_pos += size;
111 }
112 24 return blocks;
113 ✗ }
114
115 24 void LevonychevIRadixBatcherSortSTL::ParallelRadixPhase(std::vector<std::vector<int>> &blocks) {
116
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 std::vector<std::future<void>> futures;
117
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 futures.reserve(blocks.size());
118
119
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 24 times.
 120 for (auto &block : blocks) {
120
2/4
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 96 times.
✗ Branch 5 not taken.
 288 futures.push_back(std::async(std::launch::async, [&block]() { RadixSortSequential(block); }));
121 }
122
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 24 times.
 120 for (auto &f : futures) {
123
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 f.wait();
124 }
125 24 }
126
127 24 void LevonychevIRadixBatcherSortSTL::BatcherMergePhase(std::vector<std::vector<int>> &blocks) {
128 24 const int n_blocks = static_cast<int>(blocks.size());
129
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 24 times.
 72 for (int pk = 1; pk < n_blocks; pk <<= 1) {
130
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 48 times.
 120 for (int k = pk; k > 0; k >>= 1) {
131 72 BatcherMergeStep(blocks, pk, k);
132 }
133 }
134 24 }
135
136
1/2
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
 72 void LevonychevIRadixBatcherSortSTL::BatcherMergeStep(std::vector<std::vector<int>> &blocks, int p, int k) {
137 72 const int n_blocks = static_cast<int>(blocks.size());
138 72 std::vector<std::future<void>> futures;
139
1/2
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
 72 futures.reserve(static_cast<size_t>(n_blocks));
140
141
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 72 times.
 168 for (int j = k % p; j <= n_blocks - 1 - k; j += 2 * k) {
142
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 96 times.
 216 for (int i = 0; i < std::min(k, n_blocks - j - k); ++i) {
143 120 int idx1 = j + i;
144 120 int idx2 = j + i + k;
145
146
1/2
✓ Branch 0 taken 120 times.
✗ Branch 1 not taken.
 120 if ((idx1 / (p * 2)) == (idx2 / (p * 2))) {
147
1/2
✓ Branch 1 taken 120 times.
✗ Branch 2 not taken.
 240 futures.push_back(std::async(std::launch::async, [&blocks, idx1, idx2]() {
148
2/4
✗ Branch 0 not taken.
✓ Branch 1 taken 120 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 120 times.
 120 MergeAndSplit(blocks.at(static_cast<size_t>(idx1)), blocks.at(static_cast<size_t>(idx2)));
149 120 }));
150 }
151 }
152 }
153
154
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 72 times.
 192 for (auto &f : futures) {
155
1/2
✓ Branch 1 taken 120 times.
✗ Branch 2 not taken.
 120 f.wait();
156 }
157 72 }
158
159 32 bool LevonychevIRadixBatcherSortSTL::ValidationImpl() {
160 32 return !GetInput().empty();
161 }
162 32 bool LevonychevIRadixBatcherSortSTL::PreProcessingImpl() {
163 32 return true;
164 }
165 32 bool LevonychevIRadixBatcherSortSTL::PostProcessingImpl() {
166 32 return true;
167 }
168
169 } // namespace levonychev_i_radix_batcher_sort
170