GCC Code Coverage Report

Directory: ./
File: tasks/shekhirev_v_hoare_batcher_sort/stl/src/ops_stl.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 103 106 97.2%
Functions: 12 12 100.0%
Branches: 70 88 79.5%
Line Branch Exec Source
1 #include "shekhirev_v_hoare_batcher_sort/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <limits>
6 #include <thread>
7 #include <utility>
8 #include <vector>
9
10 #include "shekhirev_v_hoare_batcher_sort/common/include/common.hpp"
11
12 namespace shekhirev_v_hoare_batcher_sort {
13
14 namespace {
15
16 7744 void SplitPartition(std::vector<int> &arr, int &l, int &r, int &i, int &j) {
17 7744 int pivot = arr[l + ((r - l) / 2)];
18 7744 i = l;
19 7744 j = r;
20
21
2/2
✓ Branch 0 taken 17344 times.
✓ Branch 1 taken 7744 times.
 32832 while (i <= j) {
22
2/2
✓ Branch 0 taken 21472 times.
✓ Branch 1 taken 17344 times.
 38816 while (arr[i] < pivot) {
23 21472 i++;
24 }
25
2/2
✓ Branch 0 taken 21360 times.
✓ Branch 1 taken 17344 times.
 38704 while (arr[j] > pivot) {
26 21360 j--;
27 }
28
2/2
✓ Branch 0 taken 2416 times.
✓ Branch 1 taken 14928 times.
 17344 if (i <= j) {
29 14928 std::swap(arr[i], arr[j]);
30 14928 i++;
31 14928 j--;
32 }
33 }
34 7744 }
35
36 7744 void ProcessPartition(std::vector<int> &arr, int &l, int &r, std::vector<std::pair<int, int>> &stack) {
37 7744 int i = 0;
38 7744 int j = 0;
39 7744 SplitPartition(arr, l, r, i, j);
40
41
2/2
✓ Branch 0 taken 4144 times.
✓ Branch 1 taken 3600 times.
 7744 if (j - l < r - i) {
42
2/2
✓ Branch 0 taken 2576 times.
✓ Branch 1 taken 1568 times.
 4144 if (i < r) {
43 2576 stack.emplace_back(i, r);
44 }
45 4144 r = j;
46 } else {
47
2/2
✓ Branch 0 taken 2248 times.
✓ Branch 1 taken 1352 times.
 3600 if (l < j) {
48 2248 stack.emplace_back(l, j);
49 }
50 3600 l = i;
51 }
52 7744 }
53
54 192 void OptimizedHoareSort(std::vector<int> &arr, int left, int right) {
55
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 192 times.
 192 if (left >= right) {
56 ✗ return;
57 }
58
59 192 std::vector<std::pair<int, int>> stack;
60
1/2
✓ Branch 1 taken 192 times.
✗ Branch 2 not taken.
 192 stack.reserve(64);
61
1/2
✓ Branch 1 taken 192 times.
✗ Branch 2 not taken.
 192 stack.emplace_back(left, right);
62
63
2/2
✓ Branch 0 taken 5016 times.
✓ Branch 1 taken 192 times.
 5208 while (!stack.empty()) {
64 auto [l, r] = stack.back();
65 stack.pop_back();
66
67
2/2
✓ Branch 0 taken 7744 times.
✓ Branch 1 taken 5016 times.
 12760 while (l < r) {
68
1/2
✓ Branch 1 taken 7744 times.
✗ Branch 2 not taken.
 7744 ProcessPartition(arr, l, r, stack);
69 }
70 }
71 }
72
73 240 void MergeBlocks(std::vector<int> &arr, int start1, int start2, int chunk_size) {
74 240 std::vector<int> buffer(static_cast<std::size_t>(chunk_size) * 2);
75 int i = start1;
76 int j = start2;
77 int k = 0;
78
79 240 int end1 = start1 + chunk_size;
80 240 int end2 = start2 + chunk_size;
81
82
2/2
✓ Branch 0 taken 19544 times.
✓ Branch 1 taken 240 times.
 19784 while (i < end1 && j < end2) {
83
2/2
✓ Branch 0 taken 8752 times.
✓ Branch 1 taken 10792 times.
 19544 if (arr[i] <= arr[j]) {
84 8752 buffer[k++] = arr[i++];
85 } else {
86 10792 buffer[k++] = arr[j++];
87 }
88 }
89
90
2/2
✓ Branch 0 taken 2328 times.
✓ Branch 1 taken 240 times.
 2568 while (i < end1) {
91 2328 buffer[k++] = arr[i++];
92 }
93
2/2
✓ Branch 0 taken 288 times.
✓ Branch 1 taken 240 times.
 528 while (j < end2) {
94 288 buffer[k++] = arr[j++];
95 }
96
97
2/2
✓ Branch 0 taken 11080 times.
✓ Branch 1 taken 240 times.
 11320 for (int idx = 0; idx < chunk_size; ++idx) {
98 11080 arr[start1 + idx] = buffer[idx];
99 11080 arr[start2 + idx] = buffer[chunk_size + idx];
100 }
101 240 }
102
103 144 void DispatchMergeTasks(std::vector<int> &data, int num_threads, int chunk_size, int step_p, int step_k,
104 std::vector<std::thread> &threads) {
105
2/2
✓ Branch 0 taken 192 times.
✓ Branch 1 taken 144 times.
 336 for (int step_j = step_k % step_p; step_j + step_k < num_threads; step_j += (step_k * 2)) {
106
2/2
✓ Branch 0 taken 240 times.
✓ Branch 1 taken 192 times.
 432 for (int i = 0; i < std::min(step_k, num_threads - step_j - step_k); ++i) {
107
1/2
✓ Branch 0 taken 240 times.
✗ Branch 1 not taken.
 240 if ((step_j + i) / (step_p * 2) == (step_j + i + step_k) / (step_p * 2)) {
108 240 int start_a = (step_j + i) * chunk_size;
109 240 int start_b = (step_j + i + step_k) * chunk_size;
110
111 240 threads.emplace_back(
112 480 [&data, start_a, start_b, chunk_size]() { MergeBlocks(data, start_a, start_b, chunk_size); });
113 }
114 }
115 }
116 144 }
117
118 48 void BatcherMergePhase(std::vector<int> &data, int num_threads, int chunk_size) {
119 48 std::vector<std::thread> threads;
120
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 threads.reserve(num_threads);
121
122
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 48 times.
 144 for (int step_p = 1; step_p < num_threads; step_p *= 2) {
123
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 96 times.
 240 for (int step_k = step_p; step_k > 0; step_k /= 2) {
124
1/2
✓ Branch 1 taken 144 times.
✗ Branch 2 not taken.
 144 DispatchMergeTasks(data, num_threads, chunk_size, step_p, step_k, threads);
125
126
2/2
✓ Branch 0 taken 240 times.
✓ Branch 1 taken 144 times.
 384 for (auto &t : threads) {
127
1/2
✓ Branch 1 taken 240 times.
✗ Branch 2 not taken.
 240 t.join();
128 }
129 144 threads.clear();
130 }
131 }
132 48 }
133
134 } // namespace
135
136
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 ShekhirevHoareBatcherSortSTL::ShekhirevHoareBatcherSortSTL(const InType &in) {
137 SetTypeOfTask(GetStaticTypeOfTask());
138
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 GetInput() = in;
139 64 }
140
141 64 bool ShekhirevHoareBatcherSortSTL::ValidationImpl() {
142 64 return true;
143 }
144
145 64 bool ShekhirevHoareBatcherSortSTL::PreProcessingImpl() {
146 64 GetOutput() = GetInput();
147 64 return true;
148 }
149
150
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 16 times.
 64 bool ShekhirevHoareBatcherSortSTL::RunImpl() {
151 auto &data = GetOutput();
152 64 int orig_size = static_cast<int>(data.size());
153
154
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 16 times.
 64 if (orig_size <= 1) {
155 return true;
156 }
157
158 48 int hw_concurrency = static_cast<int>(std::thread::hardware_concurrency());
159
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 if (hw_concurrency == 0) {
160 hw_concurrency = 4;
161 }
162
163 int num_threads = 1;
164
3/4
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 48 times.
✓ Branch 2 taken 96 times.
✗ Branch 3 not taken.
 144 while (num_threads * 2 <= hw_concurrency && num_threads * 2 <= orig_size) {
165 num_threads *= 2;
166 }
167
168
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 if (num_threads == 1) {
169 ✗ OptimizedHoareSort(data, 0, orig_size - 1);
170 ✗ return true;
171 }
172
173 48 int padding = (num_threads - (orig_size % num_threads)) % num_threads;
174
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 40 times.
 48 if (padding > 0) {
175 8 data.insert(data.end(), padding, std::numeric_limits<int>::max());
176 }
177
178 48 int total_size = static_cast<int>(data.size());
179 48 int chunk_size = total_size / num_threads;
180
181 48 std::vector<std::thread> threads;
182
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 threads.reserve(num_threads);
183
184
2/2
✓ Branch 0 taken 192 times.
✓ Branch 1 taken 48 times.
 240 for (int i = 0; i < num_threads; ++i) {
185 192 threads.emplace_back(
186
1/2
✓ Branch 1 taken 192 times.
✗ Branch 2 not taken.
 384 [&data, i, chunk_size]() { OptimizedHoareSort(data, i * chunk_size, ((i + 1) * chunk_size) - 1); });
187 }
188
189
2/2
✓ Branch 0 taken 192 times.
✓ Branch 1 taken 48 times.
 240 for (auto &t : threads) {
190
1/2
✓ Branch 1 taken 192 times.
✗ Branch 2 not taken.
 192 t.join();
191 }
192 48 threads.clear();
193
194
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 BatcherMergePhase(data, num_threads, chunk_size);
195
196
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 40 times.
 48 if (padding > 0) {
197
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 data.resize(orig_size);
198 }
199
200 return true;
201 48 }
202
203 64 bool ShekhirevHoareBatcherSortSTL::PostProcessingImpl() {
204 64 return true;
205 }
206
207 } // namespace shekhirev_v_hoare_batcher_sort
208