GCC Code Coverage Report

Directory: ./
File: tasks/olesnitskiy_v_hoare_sort_simple_merge/stl/src/ops_stl.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 77 81 95.1%
Functions: 12 12 100.0%
Branches: 54 74 73.0%
Line Branch Exec Source
1 #include "olesnitskiy_v_hoare_sort_simple_merge/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <stack>
6 #include <thread>
7 #include <utility>
8 #include <vector>
9
10 #include "olesnitskiy_v_hoare_sort_simple_merge/common/include/common.hpp"
11
12 namespace olesnitskiy_v_hoare_sort_simple_merge {
13
14 namespace {
15
16 constexpr size_t kBlockSize = 64;
17
18 size_t GetThreadCount(size_t task_count) {
19 120 if (task_count == 0) {
20 return 0;
21 }
22
23 120 const unsigned int hardware_threads = std::thread::hardware_concurrency();
24
2/4
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 112 times.
✗ Branch 3 not taken.
 120 const size_t available_threads = hardware_threads == 0 ? 2 : static_cast<size_t>(hardware_threads);
25 return std::min(task_count, available_threads);
26 }
27
28 template <class Function>
29
1/2
✓ Branch 0 taken 120 times.
✗ Branch 1 not taken.
 240 void RunInThreads(size_t task_count, Function function) {
30 const size_t thread_count = GetThreadCount(task_count);
31
2/2
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 8 times.
 240 if (thread_count <= 1) {
32
2/2
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 112 times.
 448 for (size_t task_index = 0; task_index < task_count; ++task_index) {
33 224 function(task_index);
34 }
35 224 return;
36 }
37
38 16 std::vector<std::thread> threads;
39
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 16 threads.reserve(thread_count);
40
41
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 8 times.
 48 for (size_t thread_index = 0; thread_index < thread_count; ++thread_index) {
42
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 32 threads.emplace_back([thread_index, thread_count, task_count, &function]() {
43
2/4
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 32 for (size_t task_index = thread_index; task_index < task_count; task_index += thread_count) {
44 16 function(task_index);
45 }
46 });
47 }
48
49
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 8 times.
 48 for (auto &thread : threads) {
50
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 32 thread.join();
51 }
52 16 }
53
54 } // namespace
55
56
1/2
✓ Branch 1 taken 120 times.
✗ Branch 2 not taken.
 120 OlesnitskiyVHoareSortSimpleMergeSTL::OlesnitskiyVHoareSortSimpleMergeSTL(const InType &in) {
57 SetTypeOfTask(GetStaticTypeOfTask());
58
1/2
✓ Branch 1 taken 120 times.
✗ Branch 2 not taken.
 120 GetInput() = in;
59 GetOutput() = {};
60 120 }
61
62 1640 int OlesnitskiyVHoareSortSimpleMergeSTL::HoarePartition(std::vector<int> &array, int left, int right) {
63 1640 const int pivot = array[left + ((right - left) / 2)];
64 1640 int i = left - 1;
65 1640 int j = right + 1;
66
67 while (true) {
68 4032 ++i;
69
2/2
✓ Branch 0 taken 1152 times.
✓ Branch 1 taken 4032 times.
 5184 while (array[i] < pivot) {
70 1152 ++i;
71 }
72
73 4032 --j;
74
2/2
✓ Branch 0 taken 1968 times.
✓ Branch 1 taken 4032 times.
 6000 while (array[j] > pivot) {
75 1968 --j;
76 }
77
78
2/2
✓ Branch 0 taken 1640 times.
✓ Branch 1 taken 2392 times.
 4032 if (i >= j) {
79 1640 return j;
80 }
81
82 std::swap(array[i], array[j]);
83 }
84 }
85
86 112 void OlesnitskiyVHoareSortSimpleMergeSTL::HoareQuickSort(std::vector<int> &array, int left, int right) {
87 std::stack<std::pair<int, int>> stack;
88 stack.emplace(left, right);
89
90
2/2
✓ Branch 0 taken 3392 times.
✓ Branch 1 taken 112 times.
 3504 while (!stack.empty()) {
91 auto [current_left, current_right] = stack.top();
92 stack.pop();
93
94
2/2
✓ Branch 0 taken 1752 times.
✓ Branch 1 taken 1640 times.
 3392 if (current_left >= current_right) {
95 1752 continue;
96 }
97
98 1640 const int middle = HoarePartition(array, current_left, current_right);
99
100
2/2
✓ Branch 0 taken 152 times.
✓ Branch 1 taken 1488 times.
 1640 if ((middle - current_left) > (current_right - (middle + 1))) {
101 stack.emplace(current_left, middle);
102
1/2
✓ Branch 1 taken 152 times.
✗ Branch 2 not taken.
 152 stack.emplace(middle + 1, current_right);
103 } else {
104
2/4
✓ Branch 1 taken 1488 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1488 times.
✗ Branch 5 not taken.
 1488 stack.emplace(middle + 1, current_right);
105 stack.emplace(current_left, middle);
106 }
107 }
108 112 }
109
110 8 void OlesnitskiyVHoareSortSimpleMergeSTL::SimpleMerge(const std::vector<int> &source, std::vector<int> &destination,
111 size_t left, size_t middle, size_t right) {
112 size_t left_index = left;
113 size_t right_index = middle;
114 size_t destination_index = left;
115
116
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 8 times.
 16 while (left_index < middle && right_index < right) {
117
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8 times.
 8 if (source[left_index] <= source[right_index]) {
118 ✗ destination[destination_index++] = source[left_index++];
119 } else {
120 8 destination[destination_index++] = source[right_index++];
121 }
122 }
123
124
2/2
✓ Branch 0 taken 512 times.
✓ Branch 1 taken 8 times.
 520 while (left_index < middle) {
125 512 destination[destination_index++] = source[left_index++];
126 }
127
128
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8 times.
 8 while (right_index < right) {
129 ✗ destination[destination_index++] = source[right_index++];
130 }
131 8 }
132
133 120 bool OlesnitskiyVHoareSortSimpleMergeSTL::ValidationImpl() {
134 120 return !GetInput().empty();
135 }
136
137 120 bool OlesnitskiyVHoareSortSimpleMergeSTL::PreProcessingImpl() {
138 120 data_ = GetInput();
139 GetOutput().clear();
140 120 return true;
141 }
142
143
2/2
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 8 times.
 120 bool OlesnitskiyVHoareSortSimpleMergeSTL::RunImpl() {
144
2/2
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 8 times.
 120 if (data_.size() <= 1) {
145 return true;
146 }
147
148 const size_t size = data_.size();
149 112 const size_t block_count = (size + kBlockSize - 1) / kBlockSize;
150
151 112 RunInThreads(block_count, [this, size](size_t block_index) {
152 120 size_t block_start = block_index * kBlockSize;
153
2/2
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 8 times.
 120 size_t block_end = std::min(block_start + kBlockSize, size);
154
2/2
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 8 times.
 120 if ((block_end - block_start) > 1) {
155 112 HoareQuickSort(data_, static_cast<int>(block_start), static_cast<int>(block_end - 1));
156 }
157 120 });
158
159
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 112 times.
 120 for (size_t merge_width = kBlockSize; merge_width < size; merge_width *= 2) {
160 8 std::vector<int> merged_data(size);
161 8 const size_t merge_count = (size + (2 * merge_width) - 1) / (2 * merge_width);
162
163
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 RunInThreads(merge_count, [this, size, merge_width, &merged_data](size_t merge_index) {
164 8 size_t left = merge_index * 2 * merge_width;
165
1/2
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
 8 size_t middle = std::min(left + merge_width, size);
166 8 size_t right = std::min(left + (2 * merge_width), size);
167
168
1/2
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
 8 if (middle < right) {
169 8 SimpleMerge(data_, merged_data, left, middle, right);
170 } else {
171 ✗ std::copy(data_.begin() + static_cast<std::ptrdiff_t>(left), data_.begin() + static_cast<std::ptrdiff_t>(right),
172 ✗ merged_data.begin() + static_cast<std::ptrdiff_t>(left));
173 }
174 8 });
175
176 data_.swap(merged_data);
177 }
178
179 return true;
180 }
181
182
1/2
✓ Branch 0 taken 120 times.
✗ Branch 1 not taken.
 120 bool OlesnitskiyVHoareSortSimpleMergeSTL::PostProcessingImpl() {
183 const bool is_sorted = std::ranges::is_sorted(data_);
184
1/2
✓ Branch 0 taken 120 times.
✗ Branch 1 not taken.
 120 if (is_sorted) {
185 120 GetOutput() = data_;
186 }
187 120 return is_sorted;
188 }
189
190 } // namespace olesnitskiy_v_hoare_sort_simple_merge
191