GCC Code Coverage Report

Directory: ./
File: tasks/ovchinnikov_m_shell_sort_batcher_merge/tbb/src/ops_tbb.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 84 86 97.7%
Functions: 14 14 100.0%
Branches: 63 92 68.5%
Line Branch Exec Source
1 #include "ovchinnikov_m_shell_sort_batcher_merge/tbb/include/ops_tbb.hpp"
2
3 #include <tbb/global_control.h>
4 #include <tbb/parallel_invoke.h>
5
6 #include <algorithm>
7 #include <cstddef>
8 #include <limits>
9 #include <utility>
10 #include <vector>
11
12 #include "ovchinnikov_m_shell_sort_batcher_merge/common/include/common.hpp"
13 #include "util/include/util.hpp"
14 // try 4
15 namespace ovchinnikov_m_shell_sort_batcher_merge {
16
17 namespace {
18
19 std::size_t NextPowerOfTwo(std::size_t value) {
20 std::size_t power = 1;
21
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 24 times.
 84 while (power < value) {
22 60 power <<= 1;
23 }
24 return power;
25 }
26
27 44 std::vector<int> MergeSorted(const std::vector<int> &first, const std::vector<int> &second) {
28
1/2
✓ Branch 1 taken 44 times.
✗ Branch 2 not taken.
 44 std::vector<int> merged;
29
1/2
✓ Branch 1 taken 44 times.
✗ Branch 2 not taken.
 44 merged.reserve(first.size() + second.size());
30
31 std::size_t left_index = 0;
32 std::size_t right_index = 0;
33
4/4
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 100 times.
✓ Branch 2 taken 12 times.
✓ Branch 3 taken 88 times.
 132 while (left_index < first.size() && right_index < second.size()) {
34
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 24 times.
 88 if (first[left_index] <= second[right_index]) {
35
1/2
✓ Branch 0 taken 64 times.
✗ Branch 1 not taken.
 64 merged.push_back(first[left_index++]);
36 } else {
37
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 merged.push_back(second[right_index++]);
38 }
39 }
40
41
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 44 times.
 56 while (left_index < first.size()) {
42
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 merged.push_back(first[left_index++]);
43 }
44
2/2
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 44 times.
 96 while (right_index < second.size()) {
45
1/2
✓ Branch 0 taken 52 times.
✗ Branch 1 not taken.
 52 merged.push_back(second[right_index++]);
46 }
47
48 44 return merged;
49 }
50
51 bool IsEvenPosition(std::size_t index) {
52 288 return (index % 2) == 0;
53 }
54
55 40 void SplitByParity(const std::vector<int> &input, std::vector<int> &even, std::vector<int> &odd) {
56 40 even.reserve((input.size() + 1) / 2);
57 40 odd.reserve(input.size() / 2);
58
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 40 times.
 184 for (std::size_t i = 0; i < input.size(); ++i) {
59
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 72 times.
 144 if (IsEvenPosition(i)) {
60 even.push_back(input[i]);
61 } else {
62 odd.push_back(input[i]);
63 }
64 }
65 40 }
66
67 20 std::vector<int> InterleaveByParity(const std::vector<int> &even, const std::vector<int> &odd) {
68 20 std::vector<int> merged(even.size() + odd.size());
69 std::size_t even_index = 0;
70 std::size_t odd_index = 0;
71
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 20 times.
 164 for (std::size_t i = 0; i < merged.size(); ++i) {
72
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 72 times.
 144 if (IsEvenPosition(i)) {
73 72 merged[i] = even[even_index++];
74 } else {
75 72 merged[i] = odd[odd_index++];
76 }
77 }
78 20 return merged;
79 }
80
81 24 std::pair<std::vector<int>, std::vector<int>> SplitInHalf(const std::vector<int> &data) {
82 24 const auto middle = data.begin() + static_cast<std::ptrdiff_t>(data.size() / 2);
83
1/2
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
 24 std::vector<int> left(data.begin(), middle);
84
1/4
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 24 std::vector<int> right(middle, data.end());
85 24 return {std::move(left), std::move(right)};
86 }
87
88 20 void CompareExchangeOddPairs(std::vector<int> &data) {
89
2/2
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 20 times.
 72 for (std::size_t i = 1; i + 1 < data.size(); i += 2) {
90
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 40 times.
 52 if (data[i] > data[i + 1]) {
91 std::swap(data[i], data[i + 1]);
92 }
93 }
94 20 }
95
96 } // namespace
97
98
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 OvchinnikovMShellSortBatcherMergeTBB::OvchinnikovMShellSortBatcherMergeTBB(const InType &in) {
99 SetTypeOfTask(GetStaticTypeOfTask());
100
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 GetInput() = in;
101 32 }
102
103 48 void OvchinnikovMShellSortBatcherMergeTBB::ShellSort(std::vector<int> &data) {
104 const std::size_t n = data.size();
105
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 48 times.
 120 for (std::size_t gap = n / 2; gap > 0; gap /= 2) {
106
2/2
✓ Branch 0 taken 168 times.
✓ Branch 1 taken 72 times.
 240 for (std::size_t i = gap; i < n; ++i) {
107 168 const int temp = data[i];
108 std::size_t j = i;
109
4/4
✓ Branch 0 taken 196 times.
✓ Branch 1 taken 36 times.
✓ Branch 2 taken 64 times.
✓ Branch 3 taken 132 times.
 232 while (j >= gap && data[j - gap] > temp) {
110 64 data[j] = data[j - gap];
111 j -= gap;
112 }
113 168 data[j] = temp;
114 }
115 }
116 48 }
117
118
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 std::vector<int> OvchinnikovMShellSortBatcherMergeTBB::BatcherOddEvenMerge(const std::vector<int> &left,
119 const std::vector<int> &right) {
120
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (left.empty()) {
121 ✗ return right;
122 }
123
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (right.empty()) {
124 ✗ return left;
125 }
126
127
3/4
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 4 times.
✓ Branch 3 taken 20 times.
 24 if (left.size() != right.size() || left.size() <= 1) {
128 4 return MergeSorted(left, right);
129 }
130
131 20 std::vector<int> left_even;
132 20 std::vector<int> left_odd;
133 20 std::vector<int> right_even;
134 20 std::vector<int> right_odd;
135 20 tbb::parallel_invoke([&]() { SplitByParity(left, left_even, left_odd); },
136
1/4
✓ Branch 2 taken 20 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 40 [&]() { SplitByParity(right, right_even, right_odd); });
137
138 20 std::vector<int> merged_even;
139 20 std::vector<int> merged_odd;
140 20 tbb::parallel_invoke([&]() { merged_even = MergeSorted(left_even, right_even); },
141
1/4
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 40 [&]() { merged_odd = MergeSorted(left_odd, right_odd); });
142
143
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 std::vector<int> merged = InterleaveByParity(merged_even, merged_odd);
144 20 CompareExchangeOddPairs(merged);
145 return merged;
146 }
147
148 32 bool OvchinnikovMShellSortBatcherMergeTBB::ValidationImpl() {
149 32 return true;
150 }
151
152 32 bool OvchinnikovMShellSortBatcherMergeTBB::PreProcessingImpl() {
153 32 data_ = GetInput();
154 32 return true;
155 }
156
157
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 8 times.
 32 bool OvchinnikovMShellSortBatcherMergeTBB::RunImpl() {
158 constexpr std::size_t kMinSizeToSort = 2;
159
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 8 times.
 32 if (data_.size() < kMinSizeToSort) {
160 return true;
161 }
162
163 const std::size_t original_size = data_.size();
164 const std::size_t padded_size = NextPowerOfTwo(original_size);
165 24 data_.resize(padded_size, std::numeric_limits<int>::max());
166
167 24 auto halves = SplitInHalf(data_);
168 auto &left = halves.first;
169 auto &right = halves.second;
170
171
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 const auto parallelism = static_cast<std::size_t>(std::max(1, ppc::util::GetNumThreads()));
172
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 const tbb::global_control control(tbb::global_control::max_allowed_parallelism, parallelism);
173
1/2
✓ Branch 3 taken 24 times.
✗ Branch 4 not taken.
 72 tbb::parallel_invoke([&]() { ShellSort(left); }, [&]() { ShellSort(right); });
174
175
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 data_ = BatcherOddEvenMerge(left, right);
176
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 data_.resize(original_size);
177 return true;
178 24 }
179
180
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 4 times.
 32 bool OvchinnikovMShellSortBatcherMergeTBB::PostProcessingImpl() {
181
1/2
✓ Branch 0 taken 28 times.
✗ Branch 1 not taken.
 28 if (!std::ranges::is_sorted(data_.begin(), data_.end())) {
182 return false;
183 }
184 32 GetOutput() = data_;
185 32 return true;
186 }
187
188 } // namespace ovchinnikov_m_shell_sort_batcher_merge
189