GCC Code Coverage Report

Directory: ./
File: tasks/sakharov_a_shell_sorting_with_merging_butcher/stl/src/ops_stl.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 58 93 62.4%
Functions: 10 12 83.3%
Branches: 43 102 42.2%
Line Branch Exec Source
1 #include "sakharov_a_shell_sorting_with_merging_butcher/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <functional>
6 #include <thread>
7 #include <vector>
8
9 #include "sakharov_a_shell_sorting_with_merging_butcher/common/include/common.hpp"
10 #include "util/include/util.hpp"
11
12 namespace sakharov_a_shell_sorting_with_merging_butcher {
13
14 namespace {
15
16 constexpr std::size_t kMinParallelChunkSize = 1U << 14;
17
18 32 std::vector<std::size_t> BuildChunkBounds(std::size_t size, int requested_chunks) {
19
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.
 32 if (size == 0) {
20 ✗ return {0};
21 }
22
23
1/2
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
 32 const std::size_t max_chunks_by_size = std::max<std::size_t>(1, size / kMinParallelChunkSize);
24
3/4
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 32 times.
 56 const int chunks = std::max(1, std::min<int>(requested_chunks, static_cast<int>(max_chunks_by_size)));
25
26 32 std::vector<std::size_t> bounds;
27
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 bounds.reserve(static_cast<std::size_t>(chunks) + 1);
28
29 32 const std::size_t base_chunk = size / static_cast<std::size_t>(chunks);
30 32 const std::size_t remainder = size % static_cast<std::size_t>(chunks);
31 const auto chunk_count = static_cast<std::size_t>(chunks);
32
33
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 bounds.push_back(0);
34
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 32 times.
 64 for (std::size_t chunk = 0; chunk < chunk_count; ++chunk) {
35
2/4
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 32 times.
✗ Branch 4 not taken.
 64 const std::size_t chunk_size = base_chunk + (chunk < remainder ? 1 : 0);
36
1/4
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 32 bounds.push_back(bounds.back() + chunk_size);
37 }
38
39 return bounds;
40 }
41
42
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 8 times.
 32 void ShellSort(std::vector<int>::iterator begin, std::vector<int>::iterator end) {
43 32 const auto size = static_cast<std::size_t>(end - begin);
44
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 8 times.
 32 if (size <= 1) {
45 return;
46 }
47
48
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 24 times.
 80 for (std::size_t gap = size / 2; gap > 0; gap /= 2) {
49
2/2
✓ Branch 0 taken 280 times.
✓ Branch 1 taken 56 times.
 336 for (std::size_t i = gap; i < size; ++i) {
50 280 const int temp = *(begin + static_cast<std::ptrdiff_t>(i));
51 std::size_t j = i;
52
4/4
✓ Branch 0 taken 328 times.
✓ Branch 1 taken 40 times.
✓ Branch 2 taken 88 times.
✓ Branch 3 taken 240 times.
 368 while (j >= gap && *(begin + static_cast<std::ptrdiff_t>(j - gap)) > temp) {
53 88 *(begin + static_cast<std::ptrdiff_t>(j)) = *(begin + static_cast<std::ptrdiff_t>(j - gap));
54 j -= gap;
55 }
56 280 *(begin + static_cast<std::ptrdiff_t>(j)) = temp;
57 }
58 }
59 }
60
61
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 void SortChunks(std::vector<int> &data, const std::vector<std::size_t> &bounds) {
62 32 const auto chunk_count = bounds.size() - 1;
63 32 std::vector<std::thread> threads;
64
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 threads.reserve(chunk_count);
65
66
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 32 times.
 64 for (std::size_t chunk = 0; chunk < chunk_count; ++chunk) {
67
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 threads.emplace_back([&data, &bounds, chunk]() {
68 32 auto begin = data.begin() + static_cast<std::ptrdiff_t>(bounds[chunk]);
69 32 auto end = data.begin() + static_cast<std::ptrdiff_t>(bounds[chunk + 1]);
70 32 ShellSort(begin, end);
71 32 });
72 }
73
74
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 32 times.
 64 for (auto &thread : threads) {
75
1/2
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
 32 if (thread.joinable()) {
76
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 thread.join();
77 }
78 }
79 32 }
80
81 ✗ void MergePassWorker(const std::vector<int> &source, std::vector<int> &destination,
82 const std::vector<std::size_t> &bounds, std::size_t width, std::size_t begin_merge,
83 std::size_t end_merge) {
84 ✗ const std::size_t chunk_count = bounds.size() - 1;
85
86 ✗ for (std::size_t merge_index = begin_merge; merge_index < end_merge; ++merge_index) {
87 ✗ const std::size_t left_chunk = merge_index * 2 * width;
88 ✗ const std::size_t mid = std::min(left_chunk + width, chunk_count);
89 ✗ const std::size_t right = std::min(left_chunk + (2 * width), chunk_count);
90
91 ✗ const std::size_t begin_index = bounds[left_chunk];
92 ✗ const std::size_t middle_index = bounds[mid];
93 ✗ const std::size_t end_index = bounds[right];
94
95 auto output_begin = destination.begin() + static_cast<std::ptrdiff_t>(begin_index);
96 ✗ if (mid == right) {
97 ✗ std::copy(source.begin() + static_cast<std::ptrdiff_t>(begin_index),
98 source.begin() + static_cast<std::ptrdiff_t>(end_index), output_begin);
99 } else {
100 ✗ std::merge(source.begin() + static_cast<std::ptrdiff_t>(begin_index),
101 source.begin() + static_cast<std::ptrdiff_t>(middle_index),
102 source.begin() + static_cast<std::ptrdiff_t>(middle_index),
103 source.begin() + static_cast<std::ptrdiff_t>(end_index), output_begin);
104 }
105 }
106 ✗ }
107
108 ✗ void MergePass(const std::vector<int> &source, std::vector<int> &destination, const std::vector<std::size_t> &bounds,
109 std::size_t width, int requested_threads) {
110 ✗ const std::size_t chunk_count = bounds.size() - 1;
111 ✗ const std::size_t merge_count = (chunk_count + (2 * width) - 1) / (2 * width);
112 const auto worker_count =
113 ✗ std::min<std::size_t>(merge_count, static_cast<std::size_t>(std::max(1, requested_threads)));
114
115 ✗ std::vector<std::thread> threads;
116 ✗ threads.reserve(worker_count);
117
118 ✗ const std::size_t base_chunk = merge_count / worker_count;
119 ✗ const std::size_t remainder = merge_count % worker_count;
120 ✗ std::size_t current = 0;
121
122 ✗ for (std::size_t worker = 0; worker < worker_count; ++worker) {
123 ✗ const std::size_t count = base_chunk + (worker < remainder ? 1 : 0);
124 ✗ const std::size_t next = current + count;
125 ✗ threads.emplace_back(MergePassWorker, std::cref(source), std::ref(destination), std::cref(bounds), width, current,
126 next);
127 ✗ current = next;
128 }
129
130 ✗ for (auto &thread : threads) {
131 ✗ if (thread.joinable()) {
132 ✗ thread.join();
133 }
134 }
135 ✗ }
136
137 32 std::vector<int> ParallelShellSortAndMerge(const std::vector<int> &input) {
138 32 std::vector<int> source = input;
139
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 const int thread_count = std::max(1, ppc::util::GetNumThreads());
140
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 const auto bounds = BuildChunkBounds(source.size(), thread_count);
141 32 const std::size_t chunk_count = bounds.size() - 1;
142
143
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 SortChunks(source, bounds);
144
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.
 32 if (chunk_count == 1) {
145 return source;
146 }
147
148 ✗ std::vector<int> destination(source.size());
149 ✗ for (std::size_t width = 1; width < chunk_count; width *= 2) {
150 ✗ MergePass(source, destination, bounds, width, thread_count);
151 source.swap(destination);
152 }
153
154 return source;
155 }
156
157 } // namespace
158
159
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 SakharovAShellButcherSTL::SakharovAShellButcherSTL(const InType &in) {
160 SetTypeOfTask(GetStaticTypeOfTask());
161
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 GetInput() = in;
162 40 GetOutput() = OutType();
163 40 }
164
165 40 bool SakharovAShellButcherSTL::ValidationImpl() {
166 40 return IsValidInput(GetInput());
167 }
168
169 40 bool SakharovAShellButcherSTL::PreProcessingImpl() {
170 40 GetOutput().assign(GetInput().size(), 0);
171 40 return true;
172 }
173
174
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 32 times.
 40 bool SakharovAShellButcherSTL::RunImpl() {
175 const auto &input = GetInput();
176
177
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 32 times.
 40 if (input.empty()) {
178 GetOutput().clear();
179 8 return true;
180 }
181
182 32 GetOutput() = ParallelShellSortAndMerge(input);
183 32 return true;
184 }
185
186 40 bool SakharovAShellButcherSTL::PostProcessingImpl() {
187 40 return true;
188 }
189
190 } // namespace sakharov_a_shell_sorting_with_merging_butcher
191