GCC Code Coverage Report

Directory: ./
File: tasks/vasiliev_m_shell_sort_batcher_merge/omp/src/ops_omp.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 73 73 100.0%
Functions: 11 11 100.0%
Branches: 59 82 72.0%
Line Branch Exec Source
1 #include "vasiliev_m_shell_sort_batcher_merge/omp/include/ops_omp.hpp"
2
3 #include <omp.h>
4
5 #include <algorithm>
6 #include <cmath>
7 #include <cstddef>
8 #include <vector>
9
10 #include "vasiliev_m_shell_sort_batcher_merge/common/include/common.hpp"
11
12 namespace vasiliev_m_shell_sort_batcher_merge {
13
14
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 VasilievMShellSortBatcherMergeOMP::VasilievMShellSortBatcherMergeOMP(const InType &in) {
15 SetTypeOfTask(GetStaticTypeOfTask());
16
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 GetInput() = in;
17 24 GetOutput() = OutType{};
18 24 }
19
20 24 bool VasilievMShellSortBatcherMergeOMP::ValidationImpl() {
21 24 return !GetInput().empty();
22 }
23
24
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 bool VasilievMShellSortBatcherMergeOMP::PreProcessingImpl() {
25 GetOutput().clear();
26 24 return true;
27 }
28
29
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 bool VasilievMShellSortBatcherMergeOMP::RunImpl() {
30 auto &vec = GetInput();
31 const size_t n = vec.size();
32
33
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 if (vec.empty()) {
34 return false;
35 }
36
37 24 std::vector<size_t> bounds = ChunkBoundaries(n, omp_get_max_threads());
38 24 size_t chunk_count = bounds.size() - 1;
39
40 24 ShellSort(vec, bounds);
41
42
1/4
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 24 std::vector<ValType> buffer(n);
43
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 24 times.
 54 for (size_t size = 1; size < chunk_count; size *= 2) {
44 30 CycleMerge(vec, buffer, bounds, size);
45 vec.swap(buffer);
46 }
47
48
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 GetOutput() = vec;
49 return true;
50 }
51
52 24 bool VasilievMShellSortBatcherMergeOMP::PostProcessingImpl() {
53 24 return true;
54 }
55
56 24 std::vector<size_t> VasilievMShellSortBatcherMergeOMP::ChunkBoundaries(size_t vec_size, int threads) {
57
4/4
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 23 times.
✓ Branch 2 taken 18 times.
✓ Branch 3 taken 6 times.
 25 size_t chunks = std::max(1, std::min(threads, static_cast<int>(vec_size)));
58
59 24 std::vector<size_t> bounds;
60
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 bounds.reserve(chunks + 1);
61
62 24 size_t chunk_size = vec_size / chunks;
63 24 size_t remainder = vec_size % chunks;
64
65
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 bounds.push_back(0);
66
67
2/2
✓ Branch 0 taken 59 times.
✓ Branch 1 taken 24 times.
 83 for (size_t i = 0; i < chunks; i++) {
68
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 44 times.
 59 if (i < remainder) {
69
1/2
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
 15 bounds.push_back(bounds.back() + chunk_size + 1);
70 } else {
71
1/4
✓ Branch 1 taken 44 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 44 bounds.push_back(bounds.back() + chunk_size);
72 }
73 }
74 24 return bounds;
75 }
76
77 24 void VasilievMShellSortBatcherMergeOMP::ShellSort(std::vector<ValType> &vec, std::vector<size_t> &bounds) {
78 24 size_t chunk_count = bounds.size() - 1;
79
80 24 #pragma omp parallel for default(none) shared(vec, bounds, chunk_count) schedule(static)
81 for (size_t chunk = 0; chunk < chunk_count; chunk++) {
82 size_t first = bounds[chunk];
83 size_t last = bounds[chunk + 1];
84 size_t n = last - first;
85
86 for (size_t gap = n / 2; gap > 0; gap /= 2) {
87 for (size_t i = first + gap; i < last; i++) {
88 ValType tmp = vec[i];
89 size_t j = i;
90 while (j >= first + gap && vec[j - gap] > tmp) {
91 vec[j] = vec[j - gap];
92 j -= gap;
93 }
94 vec[j] = tmp;
95 }
96 }
97 }
98 24 }
99
100 30 void VasilievMShellSortBatcherMergeOMP::CycleMerge(std::vector<ValType> &vec, std::vector<ValType> &buffer,
101 std::vector<size_t> &bounds, size_t size) {
102 30 const size_t chunk_count = bounds.size() - 1;
103
104 30 #pragma omp parallel for default(none) shared(vec, buffer, bounds, size, chunk_count) schedule(static)
105 for (size_t l_chunk = 0; l_chunk < chunk_count; l_chunk += (2 * size)) {
106 const size_t l = l_chunk;
107 const size_t mid = std::min(l + size, chunk_count);
108 const size_t r = std::min(l + (2 * size), chunk_count);
109
110 const size_t start = bounds[l];
111 const size_t middle = bounds[mid];
112 const size_t end = bounds[r];
113
114 if (mid == r) {
115 std::copy(vec.begin() + static_cast<std::ptrdiff_t>(start), vec.begin() + static_cast<std::ptrdiff_t>(end),
116 buffer.begin() + static_cast<std::ptrdiff_t>(start));
117 } else {
118 std::vector<ValType> l_vect(vec.begin() + static_cast<std::ptrdiff_t>(start),
119 vec.begin() + static_cast<std::ptrdiff_t>(middle));
120 std::vector<ValType> r_vect(vec.begin() + static_cast<std::ptrdiff_t>(middle),
121 vec.begin() + static_cast<std::ptrdiff_t>(end));
122
123 std::vector<ValType> merged = BatcherMerge(l_vect, r_vect);
124 for (size_t i = 0; i < merged.size(); i++) {
125 buffer[start + i] = merged[i];
126 }
127 }
128 }
129 30 }
130
131 35 std::vector<ValType> VasilievMShellSortBatcherMergeOMP::BatcherMerge(std::vector<ValType> &l, std::vector<ValType> &r) {
132 35 std::vector<ValType> even_l;
133 35 std::vector<ValType> odd_l;
134 35 std::vector<ValType> even_r;
135 35 std::vector<ValType> odd_r;
136
137
1/2
✓ Branch 1 taken 35 times.
✗ Branch 2 not taken.
 35 SplitEvenOdd(l, even_l, odd_l);
138
1/2
✓ Branch 1 taken 35 times.
✗ Branch 2 not taken.
 35 SplitEvenOdd(r, even_r, odd_r);
139
140
1/2
✓ Branch 1 taken 35 times.
✗ Branch 2 not taken.
 35 std::vector<ValType> even = Merge(even_l, even_r);
141
1/2
✓ Branch 1 taken 35 times.
✗ Branch 2 not taken.
 35 std::vector<ValType> odd = Merge(odd_l, odd_r);
142
143
1/2
✓ Branch 1 taken 35 times.
✗ Branch 2 not taken.
 35 std::vector<ValType> res;
144
1/2
✓ Branch 1 taken 35 times.
✗ Branch 2 not taken.
 35 res.reserve(l.size() + r.size());
145
146
3/4
✓ Branch 0 taken 35 times.
✓ Branch 1 taken 115 times.
✓ Branch 2 taken 35 times.
✗ Branch 3 not taken.
 150 for (size_t i = 0; i < even.size() || i < odd.size(); i++) {
147
1/2
✓ Branch 0 taken 115 times.
✗ Branch 1 not taken.
 115 if (i < even.size()) {
148 res.push_back(even[i]);
149 }
150
2/2
✓ Branch 0 taken 82 times.
✓ Branch 1 taken 33 times.
 115 if (i < odd.size()) {
151 res.push_back(odd[i]);
152 }
153 }
154
155
2/2
✓ Branch 0 taken 68 times.
✓ Branch 1 taken 35 times.
 103 for (size_t i = 1; i + 1 < res.size(); i += 2) {
156
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 36 times.
 68 if (res[i] > res[i + 1]) {
157 std::swap(res[i], res[i + 1]);
158 }
159 }
160
161 35 return res;
162 }
163
164 70 void VasilievMShellSortBatcherMergeOMP::SplitEvenOdd(std::vector<ValType> &vec, std::vector<ValType> &even,
165 std::vector<ValType> &odd) {
166 70 even.reserve(even.size() + (vec.size() / 2) + 1);
167 70 odd.reserve(odd.size() + (vec.size() / 2));
168
169
2/2
✓ Branch 0 taken 115 times.
✓ Branch 1 taken 70 times.
 185 for (size_t i = 0; i < vec.size(); i += 2) {
170 even.push_back(vec[i]);
171
2/2
✓ Branch 0 taken 82 times.
✓ Branch 1 taken 33 times.
 115 if (i + 1 < vec.size()) {
172 odd.push_back(vec[i + 1]);
173 }
174 }
175 70 }
176
177 70 std::vector<ValType> VasilievMShellSortBatcherMergeOMP::Merge(std::vector<ValType> &a, std::vector<ValType> &b) {
178 70 std::vector<ValType> merged;
179 size_t i = 0;
180 size_t j = 0;
181
4/4
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 150 times.
✓ Branch 2 taken 34 times.
✓ Branch 3 taken 116 times.
 186 while (i < a.size() && j < b.size()) {
182
2/2
✓ Branch 0 taken 73 times.
✓ Branch 1 taken 43 times.
 116 if (a[i] <= b[j]) {
183
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 71 times.
 73 merged.push_back(a[i++]);
184 } else {
185
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 40 times.
 43 merged.push_back(b[j++]);
186 }
187 }
188
189
2/2
✓ Branch 0 taken 41 times.
✓ Branch 1 taken 70 times.
 111 while (i < a.size()) {
190
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 34 times.
 41 merged.push_back(a[i++]);
191 }
192
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 70 times.
 110 while (j < b.size()) {
193
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 24 times.
 40 merged.push_back(b[j++]);
194 }
195
196 70 return merged;
197 }
198
199 } // namespace vasiliev_m_shell_sort_batcher_merge
200