GCC Code Coverage Report

Directory: ./
File: tasks/yushkova_p_hoare_sorting_simple_merging/tbb/src/ops_tbb.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 89 93 95.7%
Functions: 13 13 100.0%
Branches: 64 100 64.0%
Line Branch Exec Source
1 #include "yushkova_p_hoare_sorting_simple_merging/tbb/include/ops_tbb.hpp"
2
3 #include <oneapi/tbb/blocked_range.h>
4 #include <oneapi/tbb/parallel_for.h>
5
6 #include <algorithm>
7 #include <cstddef>
8 #include <utility>
9 #include <vector>
10
11 #include "yushkova_p_hoare_sorting_simple_merging/common/include/common.hpp"
12
13 namespace yushkova_p_hoare_sorting_simple_merging {
14
15 namespace {
16 constexpr size_t kBlockSize = 64;
17 } // namespace
18
19
1/2
✓ Branch 1 taken 68 times.
✗ Branch 2 not taken.
 68 YushkovaPHoareSortingSimpleMergingTBB::YushkovaPHoareSortingSimpleMergingTBB(const InType &in) {
20 SetTypeOfTask(GetStaticTypeOfTask());
21
1/2
✓ Branch 1 taken 68 times.
✗ Branch 2 not taken.
 68 GetInput() = in;
22 GetOutput() = {};
23 68 }
24
25 2736 int YushkovaPHoareSortingSimpleMergingTBB::HoarePartition(std::vector<int> &values, int left, int right) {
26 2736 const int pivot = values[left + ((right - left) / 2)];
27 2736 int i = left - 1;
28 2736 int j = right + 1;
29
30 while (true) {
31 5420 ++i;
32
2/2
✓ Branch 0 taken 3692 times.
✓ Branch 1 taken 5420 times.
 9112 while (values[i] < pivot) {
33 3692 ++i;
34 }
35
36 5420 --j;
37
2/2
✓ Branch 0 taken 5264 times.
✓ Branch 1 taken 5420 times.
 10684 while (values[j] > pivot) {
38 5264 --j;
39 }
40
41
2/2
✓ Branch 0 taken 2736 times.
✓ Branch 1 taken 2684 times.
 5420 if (i >= j) {
42 2736 return j;
43 }
44
45 std::swap(values[i], values[j]);
46 }
47 }
48
49 80 void YushkovaPHoareSortingSimpleMergingTBB::HoareQuickSort(std::vector<int> &values, int left, int right) {
50
3/6
✓ Branch 0 taken 80 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 80 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 80 times.
 80 if (left >= right || static_cast<size_t>(left) >= values.size() || static_cast<size_t>(right) >= values.size()) {
51 ✗ return;
52 }
53
54 80 std::vector<std::pair<int, int>> stack;
55
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 stack.emplace_back(left, right);
56
57
2/2
✓ Branch 0 taken 5552 times.
✓ Branch 1 taken 80 times.
 5632 while (!stack.empty()) {
58 auto [current_left, current_right] = stack.back();
59 stack.pop_back();
60
61
2/2
✓ Branch 0 taken 2816 times.
✓ Branch 1 taken 2736 times.
 5552 if (current_left >= current_right) {
62 2816 continue;
63 }
64
65
2/4
✓ Branch 0 taken 2736 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2736 times.
✗ Branch 3 not taken.
 2736 if (current_left < 0 || static_cast<size_t>(current_right) >= values.size()) {
66 ✗ continue;
67 }
68
69 2736 const int partition_index = HoarePartition(values, current_left, current_right);
70
2/4
✓ Branch 0 taken 2736 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 2736 times.
 2736 if (partition_index < current_left || partition_index > current_right) {
71 ✗ continue;
72 }
73
74
2/2
✓ Branch 0 taken 240 times.
✓ Branch 1 taken 2496 times.
 2736 if ((partition_index - current_left) > (current_right - (partition_index + 1))) {
75
1/2
✓ Branch 1 taken 240 times.
✗ Branch 2 not taken.
 240 stack.emplace_back(current_left, partition_index);
76
1/2
✓ Branch 1 taken 240 times.
✗ Branch 2 not taken.
 240 stack.emplace_back(partition_index + 1, current_right);
77 } else {
78
1/4
✓ Branch 1 taken 2496 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 2496 stack.emplace_back(partition_index + 1, current_right);
79
1/2
✓ Branch 1 taken 2496 times.
✗ Branch 2 not taken.
 2496 stack.emplace_back(current_left, partition_index);
80 }
81 }
82 }
83
84 24 void YushkovaPHoareSortingSimpleMergingTBB::SimpleMerge(const std::vector<int> &source, std::vector<int> &destination,
85 size_t left, size_t middle, size_t right) {
86
2/4
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
 24 if (left >= right || middle > right || left >= middle) {
87 return;
88 }
89
90 size_t left_index = left;
91 size_t right_index = middle;
92 size_t destination_index = left;
93
94
2/2
✓ Branch 0 taken 1480 times.
✓ Branch 1 taken 24 times.
 1504 while (left_index < middle && right_index < right) {
95
2/2
✓ Branch 0 taken 736 times.
✓ Branch 1 taken 744 times.
 1480 if (source[left_index] <= source[right_index]) {
96 736 destination[destination_index++] = source[left_index++];
97 } else {
98 744 destination[destination_index++] = source[right_index++];
99 }
100 }
101
102
2/2
✓ Branch 0 taken 1312 times.
✓ Branch 1 taken 24 times.
 1336 while (left_index < middle) {
103 1312 destination[destination_index++] = source[left_index++];
104 }
105
106
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 24 times.
 64 while (right_index < right) {
107 40 destination[destination_index++] = source[right_index++];
108 }
109 }
110
111 88 void YushkovaPHoareSortingSimpleMergingTBB::SortBlockIfNeeded(std::vector<int> &data, size_t size, size_t block_index) {
112 88 const size_t block_start = block_index * kBlockSize;
113
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 8 times.
 88 const size_t block_end = std::min(block_start + kBlockSize, size);
114
4/6
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 8 times.
✓ Branch 2 taken 80 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 80 times.
✗ Branch 5 not taken.
 88 if (block_end > block_start + 1U && block_end <= size && block_start < size) {
115 80 HoareQuickSort(data, static_cast<int>(block_start), static_cast<int>(block_end - 1U));
116 }
117 88 }
118
119 64 void YushkovaPHoareSortingSimpleMergingTBB::SortBlocks(std::vector<int> &data, size_t size) {
120 64 const size_t block_count = (size + kBlockSize - 1U) / kBlockSize;
121 64 oneapi::tbb::parallel_for(oneapi::tbb::blocked_range<size_t>(0U, block_count),
122 64 [&data, size](const oneapi::tbb::blocked_range<size_t> &range) {
123
2/4
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 88 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 176 for (size_t block_index = range.begin(); block_index != range.end(); ++block_index) {
124
0/2
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 88 SortBlockIfNeeded(data, size, block_index);
125 }
126 });
127 64 }
128
129 32 void YushkovaPHoareSortingSimpleMergingTBB::MergeChunk(const std::vector<int> &source, std::vector<int> &destination,
130 size_t size, size_t merge_width, size_t merge_index) {
131 32 const size_t left = merge_index * 2U * merge_width;
132
1/2
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
 32 const size_t middle = std::min(left + merge_width, size);
133 32 const size_t right = std::min(left + (2U * merge_width), size);
134
135
1/2
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
 32 if (left >= size) {
136 return;
137 }
138
139
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 8 times.
 32 if (middle < right) {
140 24 SimpleMerge(source, destination, left, middle, right);
141
1/2
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
 8 } else if (left < right) {
142
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 8 times.
 20 for (size_t i = left; i < right; ++i) {
143 12 destination[i] = source[i];
144 }
145 }
146 }
147
148 24 void YushkovaPHoareSortingSimpleMergingTBB::MergePass(std::vector<int> &data, size_t size, size_t merge_width) {
149 24 std::vector<int> merged_data(size);
150 24 const size_t merge_count = (size + (2U * merge_width) - 1U) / (2U * merge_width);
151
152 24 oneapi::tbb::parallel_for(oneapi::tbb::blocked_range<size_t>(0U, merge_count),
153
2/6
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 24 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 56 [&data, size, merge_width, &merged_data](const oneapi::tbb::blocked_range<size_t> &range) {
154
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 32 times.
 64 for (size_t merge_index = range.begin(); merge_index != range.end(); ++merge_index) {
155 32 MergeChunk(data, merged_data, size, merge_width, merge_index);
156 }
157 32 });
158
159 data.swap(merged_data);
160 24 }
161
162 68 bool YushkovaPHoareSortingSimpleMergingTBB::ValidationImpl() {
163 68 return !GetInput().empty();
164 }
165
166 68 bool YushkovaPHoareSortingSimpleMergingTBB::PreProcessingImpl() {
167 68 data_ = GetInput();
168 GetOutput().clear();
169 68 return true;
170 }
171
172
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 68 times.
 68 bool YushkovaPHoareSortingSimpleMergingTBB::RunImpl() {
173 const size_t size = data_.size();
174
175
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 68 times.
 68 if (size == 0) {
176 GetOutput().clear();
177 ✗ return true;
178 }
179
180
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 64 times.
 68 if (size == 1) {
181 GetOutput().assign(1, data_[0]);
182 4 return true;
183 }
184
185 64 SortBlocks(data_, size);
186
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 64 times.
 88 for (size_t merge_width = kBlockSize; merge_width < size; merge_width *= 2) {
187 24 MergePass(data_, size, merge_width);
188 }
189
190
1/2
✓ Branch 0 taken 64 times.
✗ Branch 1 not taken.
 64 if (std::ranges::is_sorted(data_)) {
191 64 GetOutput() = data_;
192 64 return true;
193 }
194
195 return false;
196 }
197
198
1/2
✓ Branch 0 taken 68 times.
✗ Branch 1 not taken.
 68 bool YushkovaPHoareSortingSimpleMergingTBB::PostProcessingImpl() {
199
1/2
✓ Branch 0 taken 68 times.
✗ Branch 1 not taken.
 68 if (GetOutput().empty()) {
200 return false;
201 }
202 return std::ranges::is_sorted(GetOutput());
203 }
204
205 } // namespace yushkova_p_hoare_sorting_simple_merging
206