GCC Code Coverage Report

Directory: ./
File: tasks/karpich_i_bitwise_batcher/stl/src/ops_stl.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 89 90 98.9%
Functions: 10 10 100.0%
Branches: 68 102 66.7%
Line Branch Exec Source
1 #include "karpich_i_bitwise_batcher/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <random>
5 #include <thread>
6 #include <utility>
7 #include <vector>
8
9 #include "karpich_i_bitwise_batcher/common/include/common.hpp"
10
11 namespace karpich_i_bitwise_batcher {
12
13 namespace {
14
15
2/2
✓ Branch 0 taken 240 times.
✓ Branch 1 taken 80 times.
 320 void RadixSortPositive(std::vector<int> &arr) {
16 320 int n = static_cast<int>(arr.size());
17
2/2
✓ Branch 0 taken 240 times.
✓ Branch 1 taken 80 times.
 320 if (n <= 1) {
18 80 return;
19 }
20
21 240 int max_val = *std::ranges::max_element(arr);
22
1/2
✓ Branch 0 taken 240 times.
✗ Branch 1 not taken.
 240 if (max_val == 0) {
23 return;
24 }
25
26 240 std::vector<int> buffer(n);
27
28
3/4
✓ Branch 0 taken 712 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 472 times.
✓ Branch 3 taken 240 times.
 712 for (int shift = 0; shift < 32 && (max_val >> shift) > 0; shift += 8) {
29
1/4
✓ Branch 1 taken 472 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 472 std::vector<int> count(256, 0);
30
2/2
✓ Branch 0 taken 39536 times.
✓ Branch 1 taken 472 times.
 40008 for (int i = 0; i < n; i++) {
31 39536 count[(arr[i] >> shift) & 0xFF]++;
32 }
33
2/2
✓ Branch 0 taken 120360 times.
✓ Branch 1 taken 472 times.
 120832 for (int i = 1; i < 256; i++) {
34 120360 count[i] += count[i - 1];
35 }
36
2/2
✓ Branch 0 taken 39536 times.
✓ Branch 1 taken 472 times.
 40008 for (int i = n - 1; i >= 0; i--) {
37 39536 buffer[--count[(arr[i] >> shift) & 0xFF]] = arr[i];
38 }
39
1/2
✓ Branch 1 taken 472 times.
✗ Branch 2 not taken.
 472 arr = buffer;
40 }
41 }
42
43
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 160 times.
 176 void RadixSort(std::vector<int> &arr) {
44 176 int n = static_cast<int>(arr.size());
45
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 160 times.
 176 if (n <= 1) {
46 16 return;
47 }
48
49 160 std::vector<int> negative;
50 160 std::vector<int> positive;
51
2/2
✓ Branch 0 taken 19840 times.
✓ Branch 1 taken 160 times.
 20000 for (int i = 0; i < n; i++) {
52
2/2
✓ Branch 0 taken 9680 times.
✓ Branch 1 taken 10160 times.
 19840 if (arr[i] < 0) {
53
1/4
✓ Branch 1 taken 9680 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 9680 negative.push_back(-arr[i]);
54 } else {
55 positive.push_back(arr[i]);
56 }
57 }
58
59
1/2
✓ Branch 1 taken 160 times.
✗ Branch 2 not taken.
 160 RadixSortPositive(positive);
60
1/2
✓ Branch 1 taken 160 times.
✗ Branch 2 not taken.
 160 RadixSortPositive(negative);
61
62 int idx = 0;
63
2/2
✓ Branch 0 taken 9680 times.
✓ Branch 1 taken 160 times.
 9840 for (int i = static_cast<int>(negative.size()) - 1; i >= 0; i--) {
64 9680 arr[idx++] = -negative[i];
65 }
66
2/2
✓ Branch 0 taken 10160 times.
✓ Branch 1 taken 160 times.
 10320 for (int x : positive) {
67 10160 arr[idx++] = x;
68 }
69 }
70
71 struct MergeTask {
72 int lo;
73 int hi;
74 int r;
75 };
76
77 88 std::vector<std::vector<std::pair<int, int>>> BuildMergeNetwork(int lo, int hi) {
78 88 std::vector<std::vector<std::pair<int, int>>> levels;
79
1/2
✓ Branch 1 taken 88 times.
✗ Branch 2 not taken.
 88 std::vector<MergeTask> current = {{lo, hi, 1}};
80
81
2/2
✓ Branch 0 taken 424 times.
✓ Branch 1 taken 88 times.
 512 while (!current.empty()) {
82 424 std::vector<MergeTask> next;
83 424 std::vector<std::pair<int, int>> comps;
84
85
2/2
✓ Branch 0 taken 19768 times.
✓ Branch 1 taken 424 times.
 20192 for (const auto &[tlo, thi, tr] : current) {
86 19768 int step = tr * 2;
87
2/2
✓ Branch 0 taken 9840 times.
✓ Branch 1 taken 9928 times.
 19768 if (step < thi - tlo) {
88
1/2
✓ Branch 1 taken 9840 times.
✗ Branch 2 not taken.
 9840 next.push_back({tlo, thi, step});
89
1/2
✓ Branch 1 taken 9840 times.
✗ Branch 2 not taken.
 9840 next.push_back({tlo + tr, thi, step});
90
2/2
✓ Branch 0 taken 74544 times.
✓ Branch 1 taken 9840 times.
 84384 for (int i = tlo + tr; i + tr <= thi; i += step) {
91
1/2
✓ Branch 1 taken 74544 times.
✗ Branch 2 not taken.
 74544 comps.emplace_back(i, i + tr);
92 }
93
1/2
✓ Branch 0 taken 9928 times.
✗ Branch 1 not taken.
 9928 } else if (tlo + tr <= thi) {
94
1/4
✓ Branch 1 taken 9928 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 9928 comps.emplace_back(tlo, tlo + tr);
95 }
96 }
97
98 levels.push_back(std::move(comps));
99 current = std::move(next);
100 }
101
102 88 return levels;
103 ✗ }
104
105 88 void ApplyComparatorNetwork(std::vector<int> &arr, const std::vector<std::vector<std::pair<int, int>>> &levels) {
106
2/2
✓ Branch 0 taken 424 times.
✓ Branch 1 taken 88 times.
 512 for (int lvl = static_cast<int>(levels.size()) - 1; lvl >= 0; lvl--) {
107
2/2
✓ Branch 0 taken 84472 times.
✓ Branch 1 taken 424 times.
 84896 for (const auto &[a, b] : levels[lvl]) {
108
2/2
✓ Branch 0 taken 42928 times.
✓ Branch 1 taken 41544 times.
 84472 if (arr[a] > arr[b]) {
109 std::swap(arr[a], arr[b]);
110 }
111 }
112 }
113 88 }
114
115 88 void BatcherMerge(std::vector<int> &arr, int lo, int hi) {
116 88 auto levels = BuildMergeNetwork(lo, hi);
117 88 ApplyComparatorNetwork(arr, levels);
118 88 }
119
120 } // namespace
121
122 96 KarpichIBitwiseBatcherSTL::KarpichIBitwiseBatcherSTL(const InType &in) {
123 SetTypeOfTask(GetStaticTypeOfTask());
124 96 GetInput() = in;
125 GetOutput() = 0;
126 96 }
127
128 96 bool KarpichIBitwiseBatcherSTL::ValidationImpl() {
129 96 return GetInput() > 0;
130 }
131
132 96 bool KarpichIBitwiseBatcherSTL::PreProcessingImpl() {
133 96 int n = GetInput();
134 96 data_.resize(n);
135 96 std::mt19937 gen(static_cast<unsigned int>(n));
136 std::uniform_int_distribution<int> dist(-1000, 1000);
137
2/2
✓ Branch 0 taken 19408 times.
✓ Branch 1 taken 96 times.
 19504 for (int i = 0; i < n; i++) {
138 19408 data_[i] = dist(gen);
139 }
140 96 return true;
141 }
142
143
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 8 times.
 96 bool KarpichIBitwiseBatcherSTL::RunImpl() {
144 96 int n = static_cast<int>(data_.size());
145
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 8 times.
 96 if (n <= 1) {
146 return true;
147 }
148
149 int padded = 1;
150
2/2
✓ Branch 0 taken 424 times.
✓ Branch 1 taken 88 times.
 512 while (padded < n) {
151 424 padded *= 2;
152 }
153
154 88 int max_elem = *std::ranges::max_element(data_);
155 88 data_.resize(padded, max_elem);
156
157 88 int half = padded / 2;
158
1/2
✓ Branch 2 taken 88 times.
✗ Branch 3 not taken.
 88 std::vector<int> left(data_.begin(), data_.begin() + half);
159
1/4
✓ Branch 1 taken 88 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 88 std::vector<int> right(data_.begin() + half, data_.end());
160
161
1/4
✓ Branch 2 taken 88 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 176 std::thread left_thread([&left]() { RadixSort(left); });
162
1/4
✓ Branch 2 taken 88 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 176 std::thread right_thread([&right]() { RadixSort(right); });
163
1/2
✓ Branch 1 taken 88 times.
✗ Branch 2 not taken.
 88 left_thread.join();
164
1/2
✓ Branch 1 taken 88 times.
✗ Branch 2 not taken.
 88 right_thread.join();
165
166 std::ranges::copy(left, data_.begin());
167 std::ranges::copy(right, data_.begin() + half);
168
169
1/2
✓ Branch 1 taken 88 times.
✗ Branch 2 not taken.
 88 BatcherMerge(data_, 0, padded - 1);
170
171
1/2
✓ Branch 1 taken 88 times.
✗ Branch 2 not taken.
 88 data_.resize(n);
172 return true;
173 }
174
175 96 bool KarpichIBitwiseBatcherSTL::PostProcessingImpl() {
176 19408 for (int i = 1; std::cmp_less(i, data_.size()); i++) {
177
1/2
✓ Branch 0 taken 19312 times.
✗ Branch 1 not taken.
 19312 if (data_[i] < data_[i - 1]) {
178 return false;
179 }
180 }
181 96 GetOutput() = GetInput();
182 96 return true;
183 }
184
185 } // namespace karpich_i_bitwise_batcher
186