GCC Code Coverage Report

Directory: ./
File: tasks/krasnopevtseva_v_hoare_batcher_sort/stl/src/ops_stl.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 77 110 70.0%
Functions: 11 14 78.6%
Branches: 47 94 50.0%
Line Branch Exec Source
1 #include "krasnopevtseva_v_hoare_batcher_sort/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <future>
6 #include <stack>
7 #include <thread>
8 #include <utility>
9 #include <vector>
10
11 #include "krasnopevtseva_v_hoare_batcher_sort/common/include/common.hpp"
12
13 namespace krasnopevtseva_v_hoare_batcher_sort {
14
15
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 KrasnopevtsevaVHoareBatcherSortSTL::KrasnopevtsevaVHoareBatcherSortSTL(const InType &in) {
16 SetTypeOfTask(GetStaticTypeOfTask());
17
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 GetInput() = in;
18 48 GetOutput() = std::vector<int>();
19 48 }
20
21 48 bool KrasnopevtsevaVHoareBatcherSortSTL::ValidationImpl() {
22 48 return !GetInput().empty();
23 }
24
25 48 bool KrasnopevtsevaVHoareBatcherSortSTL::PreProcessingImpl() {
26 48 GetOutput() = std::vector<int>();
27 48 return true;
28 }
29
30 ✗ int KrasnopevtsevaVHoareBatcherSortSTL::GetNumThreads(int n) {
31 ✗ int numthreads = static_cast<int>(std::thread::hardware_concurrency());
32
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 48 if (numthreads == 0) {
33 ✗ numthreads = 1;
34 }
35 ✗ return std::min(n, numthreads);
36 }
37
38 48 void KrasnopevtsevaVHoareBatcherSortSTL::SetupChunks(std::vector<Chunk> &chunks, int n, int numthreads) {
39 48 int thread_input_size = n / numthreads;
40 48 int remainder = n % numthreads;
41
42 int current_start = 0;
43
2/2
✓ Branch 0 taken 192 times.
✓ Branch 1 taken 48 times.
 240 for (int i = 0; i < numthreads; ++i) {
44 int chunk_size = thread_input_size;
45
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 144 times.
 192 if (i == numthreads - 1) {
46 48 chunk_size += remainder;
47 }
48 192 chunks.push_back({nullptr, chunk_size, current_start, current_start + chunk_size - 1});
49 current_start += chunk_size;
50 }
51 48 }
52
53 48 void KrasnopevtsevaVHoareBatcherSortSTL::ParallelSortChunks(std::vector<int> &arr, std::vector<Chunk> &chunks) {
54
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 std::vector<std::future<void>> futures;
55
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 futures.reserve(chunks.size());
56
57
2/2
✓ Branch 0 taken 192 times.
✓ Branch 1 taken 48 times.
 240 for (auto &chunk : chunks) {
58
2/4
✓ Branch 1 taken 192 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 192 times.
✗ Branch 5 not taken.
 576 futures.push_back(std::async(std::launch::async, [&arr, &chunk]() { QuickSort(arr, chunk.left, chunk.right); }));
59 }
60
61
2/2
✓ Branch 0 taken 192 times.
✓ Branch 1 taken 48 times.
 240 for (auto &f : futures) {
62
1/2
✓ Branch 1 taken 192 times.
✗ Branch 2 not taken.
 192 f.wait();
63 }
64 48 }
65
66 ✗ void KrasnopevtsevaVHoareBatcherSortSTL::BatcherMergeBlocksStep(int *left_ptr, int &left_sz, int *right_ptr,
67 int &right_sz) {
68 192 std::inplace_merge(left_ptr, right_ptr, right_ptr + right_sz);
69
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 left_sz += right_sz;
70 ✗ }
71
72
1/2
✓ Branch 0 taken 96 times.
✗ Branch 1 not taken.
 96 void KrasnopevtsevaVHoareBatcherSortSTL::BatcherMergeLevel(int step, std::vector<Chunk> &chunks, int thread_input_size,
73 int par_if_greater) {
74 96 int pack = static_cast<int>(chunks.size());
75 96 bool do_parallel = (thread_input_size / step) > par_if_greater;
76
77 144 auto merge_pair = [&](int off) {
78 144 size_t idx1 = static_cast<size_t>(2 * step) * static_cast<size_t>(off);
79 144 size_t idx2 = idx1 + static_cast<size_t>(step);
80 144 BatcherMergeBlocksStep(chunks[idx1].ptr, chunks[idx1].size, chunks[idx2].ptr, chunks[idx2].size);
81 144 chunks[idx1].right = chunks[idx2].right;
82 240 };
83
84
1/2
✓ Branch 0 taken 96 times.
✗ Branch 1 not taken.
 96 if (do_parallel) {
85 ✗ std::vector<std::future<void>> futures;
86 ✗ futures.reserve(pack / 2);
87 ✗ for (int off = 0; off < pack / 2; ++off) {
88 ✗ futures.push_back(std::async(std::launch::async, merge_pair, off));
89 }
90 ✗ for (auto &f : futures) {
91 ✗ f.wait();
92 }
93 ✗ } else {
94
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 96 times.
 240 for (int off = 0; off < pack / 2; ++off) {
95 144 merge_pair(off);
96 }
97 }
98 96 }
99
100
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 bool KrasnopevtsevaVHoareBatcherSortSTL::RunImpl() {
101 const auto &input = GetInput();
102 std::size_t size = input.size();
103
104
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 if (size <= 1) {
105 ✗ GetOutput() = input;
106 ✗ return true;
107 }
108
109 48 std::vector<int> res = input;
110 48 int n = static_cast<int>(size);
111 int numthreads = GetNumThreads(n);
112
113 48 std::vector<Chunk> chunks;
114
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 SetupChunks(chunks, n, numthreads);
115
116
2/2
✓ Branch 0 taken 192 times.
✓ Branch 1 taken 48 times.
 240 for (auto &chunk : chunks) {
117 192 chunk.ptr = res.data() + chunk.left;
118 }
119
120
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 ParallelSortChunks(res, chunks);
121
122
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 48 times.
 144 for (int step = 1; static_cast<int>(chunks.size()) > 1; step *= 2) {
123 int pack = static_cast<int>(chunks.size());
124
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 BatcherMergeLevel(step, chunks, n / numthreads, 32);
125
126
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 48 times.
 96 if ((pack / 2) - 1 == 0) {
127 48 BatcherMergeBlocksStep(chunks[0].ptr, chunks[0].size, chunks.back().ptr, chunks.back().size);
128
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 chunks[0].right = chunks.back().right;
129
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 chunks.resize(1);
130
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 } else if ((pack / 2) % 2 != 0) {
131 ✗ size_t idx1 = static_cast<size_t>(2 * step) * static_cast<size_t>((pack / 2) - 2);
132 ✗ size_t idx2 = idx1 + static_cast<size_t>(step);
133 ✗ BatcherMergeBlocksStep(chunks[idx1].ptr, chunks[idx1].size, chunks[idx2].ptr, chunks[idx2].size);
134 chunks.erase(chunks.begin() + static_cast<ptrdiff_t>(idx2));
135 } else {
136 int new_size = pack / 2;
137
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 chunks.resize(new_size);
138 }
139 }
140
141 GetOutput() = std::move(res);
142 return true;
143 }
144
145 48 bool KrasnopevtsevaVHoareBatcherSortSTL::PostProcessingImpl() {
146 48 return true;
147 }
148
149 ✗ int KrasnopevtsevaVHoareBatcherSortSTL::Partition(std::vector<int> &arr, int first, int last) {
150 ✗ int i = first - 1;
151 ✗ int value = arr[last];
152
153 ✗ for (int j = first; j <= last - 1; ++j) {
154 ✗ if (arr[j] <= value) {
155 ✗ ++i;
156 ✗ std::swap(arr[i], arr[j]);
157 }
158 }
159 ✗ std::swap(arr[i + 1], arr[last]);
160 ✗ return i + 1;
161 }
162
163 160 void KrasnopevtsevaVHoareBatcherSortSTL::InsertionSort(std::vector<int> &arr, int first, int last) {
164
2/2
✓ Branch 0 taken 800 times.
✓ Branch 1 taken 160 times.
 960 for (int i = first + 1; i <= last; ++i) {
165 800 int key = arr[i];
166 800 int j = i - 1;
167
4/4
✓ Branch 0 taken 2328 times.
✓ Branch 1 taken 328 times.
✓ Branch 2 taken 1856 times.
✓ Branch 3 taken 472 times.
 2656 while (j >= first && arr[j] > key) {
168 1856 arr[j + 1] = arr[j];
169 1856 --j;
170 }
171 800 arr[j + 1] = key;
172 }
173 160 }
174
175 192 void KrasnopevtsevaVHoareBatcherSortSTL::QuickSort(std::vector<int> &arr, int first, int last) {
176 std::stack<std::pair<int, int>> stack;
177 stack.emplace(first, last);
178
179
2/2
✓ Branch 0 taken 192 times.
✓ Branch 1 taken 192 times.
 384 while (!stack.empty()) {
180 auto [l, r] = stack.top();
181 stack.pop();
182
183
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 160 times.
 192 if (l >= r) {
184 192 continue;
185 }
186
187
1/2
✓ Branch 0 taken 160 times.
✗ Branch 1 not taken.
 160 if (r - l < 16) {
188 160 InsertionSort(arr, l, r);
189 160 continue;
190 }
191
192 ✗ int iter = Partition(arr, l, r);
193
194 ✗ if (iter - l < r - iter) {
195 ✗ stack.emplace(iter + 1, r);
196 ✗ stack.emplace(l, iter - 1);
197 } else {
198 ✗ stack.emplace(l, iter - 1);
199 ✗ stack.emplace(iter + 1, r);
200 }
201 }
202 192 }
203
204 } // namespace krasnopevtseva_v_hoare_batcher_sort
205