GCC Code Coverage Report

Directory: ./
File: tasks/ovchinnikov_m_shell_sort_batcher_merge/omp/src/ops_omp.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 82 84 97.6%
Functions: 12 12 100.0%
Branches: 58 78 74.4%
Line Branch Exec Source
1 #include "ovchinnikov_m_shell_sort_batcher_merge/omp/include/ops_omp.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <limits>
6 #include <utility>
7 #include <vector>
8
9 #include "ovchinnikov_m_shell_sort_batcher_merge/common/include/common.hpp"
10
11 namespace ovchinnikov_m_shell_sort_batcher_merge {
12
13 namespace {
14 // nothing
15 std::size_t NextPowerOfTwo(std::size_t value) {
16 std::size_t power = 1;
17
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 24 times.
 84 while (power < value) {
18 60 power <<= 1;
19 }
20 return power;
21 }
22
23 44 std::vector<int> MergeSorted(const std::vector<int> &first, const std::vector<int> &second) {
24
1/2
✓ Branch 1 taken 44 times.
✗ Branch 2 not taken.
 44 std::vector<int> merged;
25
1/2
✓ Branch 1 taken 44 times.
✗ Branch 2 not taken.
 44 merged.reserve(first.size() + second.size());
26
27 std::size_t left_index = 0;
28 std::size_t right_index = 0;
29
4/4
✓ Branch 0 taken 100 times.
✓ Branch 1 taken 32 times.
✓ Branch 2 taken 12 times.
✓ Branch 3 taken 88 times.
 132 while (left_index < first.size() && right_index < second.size()) {
30
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 24 times.
 88 if (first[left_index] <= second[right_index]) {
31 merged.push_back(first[left_index]);
32 64 ++left_index;
33 } else {
34 merged.push_back(second[right_index]);
35 24 ++right_index;
36 }
37 }
38
39
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 44 times.
 56 while (left_index < first.size()) {
40 merged.push_back(first[left_index]);
41 12 ++left_index;
42 }
43
2/2
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 44 times.
 96 while (right_index < second.size()) {
44 merged.push_back(second[right_index]);
45 52 ++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 72 ++even_index;
75 } else {
76 72 merged[i] = odd[odd_index];
77 72 ++odd_index;
78 }
79 }
80 20 return merged;
81 }
82
83 24 std::pair<std::vector<int>, std::vector<int>> SplitInHalf(const std::vector<int> &data) {
84 24 const auto middle = data.begin() + static_cast<std::ptrdiff_t>(data.size() / 2);
85
1/2
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
 24 std::vector<int> left(data.begin(), middle);
86
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());
87 24 return {std::move(left), std::move(right)};
88 }
89
90 20 void CompareExchangeOddPairs(std::vector<int> &data) {
91
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) {
92
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 40 times.
 52 if (data[i] > data[i + 1]) {
93 std::swap(data[i], data[i + 1]);
94 }
95 }
96 20 }
97
98 } // namespace
99
100
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 OvchinnikovMShellSortBatcherMergeOMP::OvchinnikovMShellSortBatcherMergeOMP(const InType &in) {
101 SetTypeOfTask(GetStaticTypeOfTask());
102
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 GetInput() = in;
103 32 }
104
105 48 void OvchinnikovMShellSortBatcherMergeOMP::ShellSort(std::vector<int> &data) {
106 const std::size_t n = data.size();
107
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 48 times.
 120 for (std::size_t gap = n / 2; gap > 0; gap /= 2) {
108
2/2
✓ Branch 0 taken 168 times.
✓ Branch 1 taken 72 times.
 240 for (std::size_t i = gap; i < n; ++i) {
109 168 int temp = data[i];
110 std::size_t j = i;
111
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) {
112 64 data[j] = data[j - gap];
113 j -= gap;
114 }
115 168 data[j] = temp;
116 }
117 }
118 48 }
119
120
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 std::vector<int> OvchinnikovMShellSortBatcherMergeOMP::BatcherOddEvenMerge(const std::vector<int> &left,
121 const std::vector<int> &right) {
122
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (left.empty()) {
123 ✗ return right;
124 }
125
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (right.empty()) {
126 ✗ return left;
127 }
128
129
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) {
130 4 return MergeSorted(left, right);
131 }
132
133 20 std::vector<int> left_even;
134 20 std::vector<int> left_odd;
135 20 std::vector<int> right_even;
136 20 std::vector<int> right_odd;
137
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 SplitByParity(left, left_even, left_odd);
138
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 SplitByParity(right, right_even, right_odd);
139
140
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 std::vector<int> merged_even = MergeSorted(left_even, right_even);
141
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 std::vector<int> 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
146 return merged;
147 }
148
149 32 bool OvchinnikovMShellSortBatcherMergeOMP::ValidationImpl() {
150 32 return true;
151 }
152
153 32 bool OvchinnikovMShellSortBatcherMergeOMP::PreProcessingImpl() {
154 32 data_ = GetInput();
155 32 return true;
156 }
157
158
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 8 times.
 32 bool OvchinnikovMShellSortBatcherMergeOMP::RunImpl() {
159 constexpr std::size_t kMinSizeToSort = 2;
160
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 8 times.
 32 if (data_.size() < kMinSizeToSort) {
161 return true;
162 }
163
164 const std::size_t original_size = data_.size();
165 const std::size_t padded_size = NextPowerOfTwo(original_size);
166 24 data_.resize(padded_size, std::numeric_limits<int>::max());
167
168 24 auto halves = SplitInHalf(data_);
169 auto &left = halves.first;
170 auto &right = halves.second;
171
172 24 #pragma omp parallel sections default(none) shared(left, right)
173 {
174 #pragma omp section
175 ShellSort(left);
176 #pragma omp section
177 ShellSort(right);
178 }
179
180
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 data_ = BatcherOddEvenMerge(left, right);
181
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 data_.resize(original_size);
182 return true;
183 24 }
184
185
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 4 times.
 32 bool OvchinnikovMShellSortBatcherMergeOMP::PostProcessingImpl() {
186
1/2
✓ Branch 0 taken 28 times.
✗ Branch 1 not taken.
 28 if (!std::ranges::is_sorted(data_.begin(), data_.end())) {
187 return false;
188 }
189 32 GetOutput() = data_;
190 32 return true;
191 }
192
193 } // namespace ovchinnikov_m_shell_sort_batcher_merge
194