GCC Code Coverage Report

Directory: ./
File: tasks/tochilin_e_hoar_sort_sim_mer/stl/src/ops_stl.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 91 98 92.9%
Functions: 13 14 92.9%
Branches: 68 110 61.8%
Line Branch Exec Source
1 #include "tochilin_e_hoar_sort_sim_mer/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <iterator>
6 #include <thread>
7 #include <utility>
8 #include <vector>
9
10 #include "tochilin_e_hoar_sort_sim_mer/common/include/common.hpp"
11 #include "util/include/util.hpp"
12
13 namespace tochilin_e_hoar_sort_sim_mer {
14
15 namespace {
16
17 constexpr int kMinSequentialCutoff = 2048;
18
19 int ResolveConcurrency() {
20 80 return std::max(1, ppc::util::GetNumThreads());
21 }
22
23 } // namespace
24
25
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 TochilinEHoarSortSimMerSTL::TochilinEHoarSortSimMerSTL(const InType &in) {
26 SetTypeOfTask(GetStaticTypeOfTask());
27
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 GetInput() = in;
28 80 }
29
30 80 bool TochilinEHoarSortSimMerSTL::ValidationImpl() {
31 80 return !GetInput().empty();
32 }
33
34 80 bool TochilinEHoarSortSimMerSTL::PreProcessingImpl() {
35 80 GetOutput() = GetInput();
36 80 return true;
37 }
38
39 26432 std::pair<int, int> TochilinEHoarSortSimMerSTL::Partition(std::vector<int> &arr, int l, int r) {
40 int i = l;
41 int j = r;
42 26432 const int pivot = arr[(l + r) / 2];
43
44
2/2
✓ Branch 0 taken 81104 times.
✓ Branch 1 taken 26432 times.
 133968 while (i <= j) {
45
2/2
✓ Branch 0 taken 100968 times.
✓ Branch 1 taken 81104 times.
 182072 while (arr[i] < pivot) {
46 100968 ++i;
47 }
48
2/2
✓ Branch 0 taken 115272 times.
✓ Branch 1 taken 81104 times.
 196376 while (arr[j] > pivot) {
49 115272 --j;
50 }
51
2/2
✓ Branch 0 taken 7888 times.
✓ Branch 1 taken 73216 times.
 81104 if (i <= j) {
52 std::swap(arr[i], arr[j]);
53 73216 ++i;
54 73216 --j;
55 }
56 }
57
58 26432 return {i, j};
59 }
60
61 136 void TochilinEHoarSortSimMerSTL::QuickSortSequential(std::vector<int> &arr, int low, int high) {
62
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 128 times.
 136 if (low >= high) {
63 8 return;
64 }
65
66 128 std::vector<std::pair<int, int>> stack;
67
1/2
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
 128 stack.emplace_back(low, high);
68
69
2/2
✓ Branch 0 taken 26432 times.
✓ Branch 1 taken 128 times.
 26560 while (!stack.empty()) {
70 const auto [l, r] = stack.back();
71 stack.pop_back();
72
73
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 26432 times.
 26432 if (l >= r) {
74 ✗ continue;
75 }
76
77 26432 const auto [i, j] = Partition(arr, l, r);
78
79
2/2
✓ Branch 0 taken 12968 times.
✓ Branch 1 taken 13464 times.
 26432 if (l < j) {
80
1/2
✓ Branch 1 taken 12968 times.
✗ Branch 2 not taken.
 12968 stack.emplace_back(l, j);
81 }
82
2/2
✓ Branch 0 taken 13336 times.
✓ Branch 1 taken 13096 times.
 26432 if (i < r) {
83
1/2
✓ Branch 1 taken 13336 times.
✗ Branch 2 not taken.
 13336 stack.emplace_back(i, r);
84 }
85 }
86 }
87
88
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 96 times.
 96 bool TochilinEHoarSortSimMerSTL::ProcessRange(std::vector<int> &arr, std::pair<int, int> range, int serial_cutoff,
89 std::vector<std::pair<int, int>> &next_ranges) {
90 const auto [left, right] = range;
91
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 96 times.
 96 if (left >= right) {
92 return false;
93 }
94
95 96 const int range_size = right - left + 1;
96
1/2
✓ Branch 0 taken 96 times.
✗ Branch 1 not taken.
 96 if (range_size <= serial_cutoff) {
97 96 QuickSortSequential(arr, left, right);
98 96 return false;
99 }
100
101 ✗ const auto [i, j] = Partition(arr, left, right);
102 ✗ if (left < j) {
103 ✗ next_ranges.emplace_back(left, j);
104 }
105 ✗ if (i < right) {
106 ✗ next_ranges.emplace_back(i, right);
107 }
108
109 return true;
110 }
111
112 120 void TochilinEHoarSortSimMerSTL::QuickSortParallel(std::vector<int> &arr, int low, int high, int serial_cutoff,
113 int worker_count) {
114
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 96 times.
 120 if (low >= high) {
115 24 return;
116 }
117
118 96 std::vector<std::pair<int, int>> current_ranges;
119
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 current_ranges.emplace_back(low, high);
120
121
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 96 times.
 192 while (!current_ranges.empty()) {
122
3/4
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 96 times.
 144 const int active_workers = std::max(1, std::min(worker_count, static_cast<int>(current_ranges.size())));
123
1/4
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 96 std::vector<std::vector<std::pair<int, int>>> next_ranges_local(static_cast<std::size_t>(active_workers));
124 96 std::vector<std::thread> workers;
125
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 workers.reserve(static_cast<std::size_t>(active_workers));
126
127
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 96 times.
 192 for (int worker_idx = 0; worker_idx < active_workers; ++worker_idx) {
128
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 workers.emplace_back([&, worker_idx] {
129 96 auto &local_next = next_ranges_local[static_cast<std::size_t>(worker_idx)];
130
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 96 times.
 192 for (auto idx = static_cast<std::size_t>(worker_idx); idx < current_ranges.size();
131 96 idx += static_cast<std::size_t>(active_workers)) {
132 96 ProcessRange(arr, current_ranges[idx], serial_cutoff, local_next);
133 }
134 96 });
135 }
136
137
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 96 times.
 192 for (auto &worker : workers) {
138
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 worker.join();
139 }
140
141 96 std::vector<std::pair<int, int>> next_ranges;
142
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 96 times.
 192 for (auto &local_ranges : next_ranges_local) {
143 96 next_ranges.insert(next_ranges.end(), local_ranges.begin(), local_ranges.end());
144 }
145 current_ranges = std::move(next_ranges);
146 96 }
147 }
148
149 ✗ int TochilinEHoarSortSimMerSTL::ResolveSerialCutoff(std::size_t size) {
150 const int concurrency = ResolveConcurrency();
151 80 const std::size_t per_worker = size / static_cast<std::size_t>(concurrency * 4);
152 80 return std::max(kMinSequentialCutoff, static_cast<int>(per_worker));
153 }
154
155 80 std::vector<int> TochilinEHoarSortSimMerSTL::MergeSortedVectors(const std::vector<int> &a, const std::vector<int> &b) {
156
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 std::vector<int> result;
157
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 result.reserve(a.size() + b.size());
158
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 std::ranges::merge(a, b, std::back_inserter(result));
159 80 return result;
160 }
161
162
1/2
✓ Branch 0 taken 80 times.
✗ Branch 1 not taken.
 80 bool TochilinEHoarSortSimMerSTL::RunImpl() {
163 auto &data = GetOutput();
164
1/2
✓ Branch 0 taken 80 times.
✗ Branch 1 not taken.
 80 if (data.empty()) {
165 return false;
166 }
167
168 80 const auto mid = static_cast<std::vector<int>::difference_type>(data.size() / 2);
169 const int concurrency = ResolveConcurrency();
170 80 const int serial_cutoff = ResolveSerialCutoff(data.size());
171
172
1/2
✓ Branch 2 taken 80 times.
✗ Branch 3 not taken.
 80 std::vector<int> left(data.begin(), data.begin() + mid);
173
1/4
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 80 std::vector<int> right(data.begin() + mid, data.end());
174
175
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 60 times.
 80 if (concurrency == 1) {
176
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 QuickSortSequential(left, 0, static_cast<int>(left.size()) - 1);
177
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 QuickSortSequential(right, 0, static_cast<int>(right.size()) - 1);
178 } else {
179
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 20 times.
 60 const int left_workers = std::max(1, concurrency / 2);
180
1/2
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
 60 const int right_workers = std::max(1, concurrency - left_workers);
181
182 60 std::vector<std::thread> workers;
183
1/2
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
 60 workers.reserve(2);
184
185 60 workers.emplace_back(
186
1/2
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
 120 [&]() { QuickSortParallel(left, 0, static_cast<int>(left.size()) - 1, serial_cutoff, left_workers); });
187 60 workers.emplace_back(
188
1/2
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
 120 [&]() { QuickSortParallel(right, 0, static_cast<int>(right.size()) - 1, serial_cutoff, right_workers); });
189
190
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 60 times.
 180 for (auto &worker : workers) {
191
1/2
✓ Branch 1 taken 120 times.
✗ Branch 2 not taken.
 120 worker.join();
192 }
193 60 }
194
195
2/6
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 80 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 160 data = MergeSortedVectors(left, right);
196
197 return true;
198 }
199
200
1/2
✓ Branch 0 taken 80 times.
✗ Branch 1 not taken.
 80 bool TochilinEHoarSortSimMerSTL::PostProcessingImpl() {
201 80 return std::ranges::is_sorted(GetOutput());
202 }
203
204 } // namespace tochilin_e_hoar_sort_sim_mer
205