GCC Code Coverage Report

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