GCC Code Coverage Report

Directory: ./
File: tasks/olesnitskiy_v_hoare_sort_simple_merge/tbb/src/ops_tbb.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 63 68 92.6%
Functions: 10 10 100.0%
Branches: 43 58 74.1%
Line Branch Exec Source
1 #include "olesnitskiy_v_hoare_sort_simple_merge/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 <stack>
9 #include <utility>
10 #include <vector>
11
12 #include "olesnitskiy_v_hoare_sort_simple_merge/common/include/common.hpp"
13
14 namespace olesnitskiy_v_hoare_sort_simple_merge {
15
16 namespace {
17
18 constexpr size_t kBlockSize = 64;
19
20 } // namespace
21
22
1/2
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
 60 OlesnitskiyVHoareSortSimpleMergeTBB::OlesnitskiyVHoareSortSimpleMergeTBB(const InType &in) {
23 SetTypeOfTask(GetStaticTypeOfTask());
24
1/2
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
 60 GetInput() = in;
25 GetOutput() = {};
26 60 }
27
28 820 int OlesnitskiyVHoareSortSimpleMergeTBB::HoarePartition(std::vector<int> &array, int left, int right) {
29 820 const int pivot = array[left + ((right - left) / 2)];
30 820 int i = left - 1;
31 820 int j = right + 1;
32
33 while (true) {
34 2016 ++i;
35
2/2
✓ Branch 0 taken 576 times.
✓ Branch 1 taken 2016 times.
 2592 while (array[i] < pivot) {
36 576 ++i;
37 }
38
39 2016 --j;
40
2/2
✓ Branch 0 taken 984 times.
✓ Branch 1 taken 2016 times.
 3000 while (array[j] > pivot) {
41 984 --j;
42 }
43
44
2/2
✓ Branch 0 taken 820 times.
✓ Branch 1 taken 1196 times.
 2016 if (i >= j) {
45 820 return j;
46 }
47
48 std::swap(array[i], array[j]);
49 }
50 }
51
52 56 void OlesnitskiyVHoareSortSimpleMergeTBB::HoareQuickSort(std::vector<int> &array, int left, int right) {
53 std::stack<std::pair<int, int>> stack;
54 stack.emplace(left, right);
55
56
2/2
✓ Branch 0 taken 1696 times.
✓ Branch 1 taken 56 times.
 1752 while (!stack.empty()) {
57 auto [current_left, current_right] = stack.top();
58 stack.pop();
59
60
2/2
✓ Branch 0 taken 876 times.
✓ Branch 1 taken 820 times.
 1696 if (current_left >= current_right) {
61 876 continue;
62 }
63
64 820 const int middle = HoarePartition(array, current_left, current_right);
65
66
2/2
✓ Branch 0 taken 76 times.
✓ Branch 1 taken 744 times.
 820 if ((middle - current_left) > (current_right - (middle + 1))) {
67 stack.emplace(current_left, middle);
68
1/2
✓ Branch 1 taken 76 times.
✗ Branch 2 not taken.
 76 stack.emplace(middle + 1, current_right);
69 } else {
70
2/4
✓ Branch 1 taken 744 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 744 times.
✗ Branch 5 not taken.
 744 stack.emplace(middle + 1, current_right);
71 stack.emplace(current_left, middle);
72 }
73 }
74 56 }
75
76 4 void OlesnitskiyVHoareSortSimpleMergeTBB::SimpleMerge(const std::vector<int> &source, std::vector<int> &destination,
77 size_t left, size_t middle, size_t right) {
78 size_t left_index = left;
79 size_t right_index = middle;
80 size_t destination_index = left;
81
82
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 while (left_index < middle && right_index < right) {
83
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
 4 if (source[left_index] <= source[right_index]) {
84 ✗ destination[destination_index++] = source[left_index++];
85 } else {
86 4 destination[destination_index++] = source[right_index++];
87 }
88 }
89
90
2/2
✓ Branch 0 taken 256 times.
✓ Branch 1 taken 4 times.
 260 while (left_index < middle) {
91 256 destination[destination_index++] = source[left_index++];
92 }
93
94
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
 4 while (right_index < right) {
95 ✗ destination[destination_index++] = source[right_index++];
96 }
97 4 }
98
99 60 bool OlesnitskiyVHoareSortSimpleMergeTBB::ValidationImpl() {
100 60 return !GetInput().empty();
101 }
102
103 60 bool OlesnitskiyVHoareSortSimpleMergeTBB::PreProcessingImpl() {
104 60 data_ = GetInput();
105 GetOutput().clear();
106 60 return true;
107 }
108
109
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 4 times.
 60 bool OlesnitskiyVHoareSortSimpleMergeTBB::RunImpl() {
110
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 4 times.
 60 if (data_.size() <= 1) {
111 return true;
112 }
113
114 const size_t size = data_.size();
115 56 const size_t block_count = (size + kBlockSize - 1) / kBlockSize;
116
117 116 oneapi::tbb::parallel_for(oneapi::tbb::blocked_range<size_t>(0, block_count), [this, size](const auto &range) {
118
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 60 times.
 120 for (size_t block_index = range.begin(); block_index != range.end(); ++block_index) {
119 60 size_t block_start = block_index * kBlockSize;
120
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 4 times.
 60 size_t block_end = std::min(block_start + kBlockSize, size);
121
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 4 times.
 60 if ((block_end - block_start) > 1) {
122 56 HoareQuickSort(data_, static_cast<int>(block_start), static_cast<int>(block_end - 1));
123 }
124 }
125 60 });
126
127
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 56 times.
 60 for (size_t merge_width = kBlockSize; merge_width < size; merge_width *= 2) {
128 4 std::vector<int> merged_data(size);
129 4 const size_t merge_count = (size + (2 * merge_width) - 1) / (2 * merge_width);
130
131 4 oneapi::tbb::parallel_for(oneapi::tbb::blocked_range<size_t>(0, merge_count),
132
2/6
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 4 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 8 [this, size, merge_width, &merged_data](const auto &range) {
133
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 for (size_t merge_index = range.begin(); merge_index != range.end(); ++merge_index) {
134 4 size_t left = merge_index * 2 * merge_width;
135
1/2
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
 4 size_t middle = std::min(left + merge_width, size);
136 4 size_t right = std::min(left + (2 * merge_width), size);
137
138
1/2
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
 4 if (middle < right) {
139 4 SimpleMerge(data_, merged_data, left, middle, right);
140 } else {
141 ✗ std::copy(data_.begin() + static_cast<std::ptrdiff_t>(left),
142 ✗ data_.begin() + static_cast<std::ptrdiff_t>(right),
143 ✗ merged_data.begin() + static_cast<std::ptrdiff_t>(left));
144 }
145 }
146 4 });
147
148 data_.swap(merged_data);
149 }
150
151 return true;
152 }
153
154
1/2
✓ Branch 0 taken 60 times.
✗ Branch 1 not taken.
 60 bool OlesnitskiyVHoareSortSimpleMergeTBB::PostProcessingImpl() {
155 const bool is_sorted = std::ranges::is_sorted(data_);
156
1/2
✓ Branch 0 taken 60 times.
✗ Branch 1 not taken.
 60 if (is_sorted) {
157 60 GetOutput() = data_;
158 }
159 60 return is_sorted;
160 }
161
162 } // namespace olesnitskiy_v_hoare_sort_simple_merge
163