GCC Code Coverage Report

Directory: ./
File: tasks/shemetov_d_radix_odd_even_mergesort/tbb/src/ops_tbb.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 70 72 97.2%
Functions: 10 11 90.9%
Branches: 50 62 80.6%
Line Branch Exec Source
1 #include "shemetov_d_radix_odd_even_mergesort/tbb/include/ops_tbb.hpp"
2
3 #include <tbb/blocked_range.h>
4 #include <tbb/parallel_for.h>
5 #include <tbb/parallel_invoke.h>
6 #include <tbb/tbb.h>
7
8 #include <algorithm>
9 #include <climits>
10 #include <cstddef>
11 #include <vector>
12
13 #include "shemetov_d_radix_odd_even_mergesort/common/include/common.hpp"
14
15 namespace shemetov_d_radix_odd_even_mergesort {
16
17
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 ShemetovDRadixOddEvenMergeSortTBB::ShemetovDRadixOddEvenMergeSortTBB(const InType &in) {
18 SetTypeOfTask(GetStaticTypeOfTask());
19 GetInput() = in;
20 48 }
21
22 80 void ShemetovDRadixOddEvenMergeSortTBB::RadixSort(std::vector<int> &array, size_t left, size_t right) {
23
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 72 times.
 80 if (left >= right) {
24 8 return;
25 }
26
27 int maximum =
28
1/2
✓ Branch 0 taken 72 times.
✗ Branch 1 not taken.
 72 *std::ranges::max_element(array.begin() + static_cast<int>(left), array.begin() + static_cast<int>(right) + 1);
29
30 72 size_t segment = right - left + 1;
31
32 72 std::vector<int> buffer(segment);
33
1/4
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 72 std::vector<int> position(256, 0);
34
35
1/2
✓ Branch 0 taken 144 times.
✗ Branch 1 not taken.
 144 for (size_t merge_shift = 0; merge_shift < 32; merge_shift += 8) {
36
1/4
✓ Branch 1 taken 144 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 144 position.assign(256, 0);
37
38
2/2
✓ Branch 0 taken 1112 times.
✓ Branch 1 taken 144 times.
 1256 for (size_t i = left; i <= right; i += 1) {
39 1112 int apply_bitmask = (array[i] >> merge_shift) & 0xFF;
40
41 1112 position[apply_bitmask] += 1;
42 }
43
44
2/2
✓ Branch 0 taken 36720 times.
✓ Branch 1 taken 144 times.
 36864 for (size_t i = 1; i < 256; i += 1) {
45 36720 position[i] += position[i - 1];
46 }
47
48
2/2
✓ Branch 0 taken 1112 times.
✓ Branch 1 taken 144 times.
 1256 for (size_t i = segment; i > 0; i -= 1) {
49 1112 size_t current_index = left + i - 1;
50 1112 int apply_bitmask = (array[current_index] >> merge_shift) & 0xFF;
51
52 1112 buffer[position[apply_bitmask] -= 1] = array[current_index];
53 }
54
55
2/2
✓ Branch 0 taken 1112 times.
✓ Branch 1 taken 144 times.
 1256 for (size_t i = 0; i < segment; i += 1) {
56 1112 array[left + i] = buffer[i];
57 }
58
59
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 72 times.
 144 if ((maximum >> merge_shift) < 256) {
60 break;
61 }
62 }
63 }
64
65 ✗ void ShemetovDRadixOddEvenMergeSortTBB::ApplyFirstPass(std::vector<int> &array, size_t start_offset, size_t padding) {
66 260 tbb::parallel_for(tbb::blocked_range<size_t>(0, padding), [&](const tbb::blocked_range<size_t> &range) {
67
2/2
✓ Branch 0 taken 260 times.
✓ Branch 1 taken 260 times.
 520 for (size_t i = range.begin(); i != range.end(); ++i) {
68
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 216 times.
 260 if (array[start_offset + i] > array[start_offset + padding + i]) {
69 std::swap(array[start_offset + i], array[start_offset + padding + i]);
70 }
71 }
72 260 });
73 ✗ }
74
75 88 void ShemetovDRadixOddEvenMergeSortTBB::ApplyMainPass(std::vector<int> &array, size_t start_offset, size_t segment,
76 size_t padding) {
77 88 size_t step = padding * 2;
78 88 size_t num_blocks = (segment - padding) / step;
79
80 440 tbb::parallel_for(tbb::blocked_range<size_t>(0, num_blocks), [&](const tbb::blocked_range<size_t> &range) {
81
2/2
✓ Branch 0 taken 352 times.
✓ Branch 1 taken 352 times.
 704 for (size_t block = range.begin(); block != range.end(); ++block) {
82 352 size_t start_position = padding + (block * step);
83
84
2/2
✓ Branch 0 taken 596 times.
✓ Branch 1 taken 352 times.
 948 for (size_t i = 0; i < padding; i += 1) {
85
2/2
✓ Branch 0 taken 172 times.
✓ Branch 1 taken 424 times.
 596 if (array[start_offset + start_position + i] > array[start_offset + start_position + i + padding]) {
86 std::swap(array[start_offset + start_position + i], array[start_offset + start_position + i + padding]);
87 }
88 }
89 }
90 352 });
91 88 }
92
93 40 void ShemetovDRadixOddEvenMergeSortTBB::OddEvenMerge(std::vector<int> &array, size_t start_offset, size_t segment) {
94
1/2
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
 40 if (segment <= 1) {
95 return;
96 }
97
98 40 size_t padding = segment / 2;
99 40 ApplyFirstPass(array, start_offset, padding);
100
101
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 40 times.
 128 for (padding = segment / 4; padding > 0; padding /= 2) {
102 88 ApplyMainPass(array, start_offset, segment, padding);
103 }
104 }
105
106 48 bool ShemetovDRadixOddEvenMergeSortTBB::ValidationImpl() {
107 const auto &[size, array] = GetInput();
108
3/4
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 44 times.
 48 return size > 0 && static_cast<size_t>(size) == array.size();
109 }
110
111
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 4 times.
 48 bool ShemetovDRadixOddEvenMergeSortTBB::PreProcessingImpl() {
112 const auto &[size, array] = GetInput();
113
114
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 4 times.
 48 if (size == 0) {
115 return true;
116 }
117
118 44 array_ = array;
119
120 44 offset_ = *std::ranges::min_element(array_.begin(), array_.end());
121 44 size_ = static_cast<size_t>(size);
122 44 power_ = 1;
123
124
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 44 times.
 172 while (power_ < size_) {
125 128 power_ *= 2;
126 }
127
128
2/2
✓ Branch 0 taken 368 times.
✓ Branch 1 taken 44 times.
 412 for (size_t i = 0; i < size_; i += 1) {
129 368 array_[i] -= offset_;
130 }
131
132
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 20 times.
 44 if (power_ > size_) {
133 24 array_.resize(power_, INT_MAX);
134 }
135
136 return true;
137 }
138
139 48 bool ShemetovDRadixOddEvenMergeSortTBB::RunImpl() {
140
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 8 times.
 48 if (power_ <= 1) {
141 return true;
142 }
143
144 40 size_t middle = power_ / 2;
145
146 120 tbb::parallel_invoke([&]() { RadixSort(array_, 0, middle - 1); }, [&]() { RadixSort(array_, middle, power_ - 1); });
147
148 40 OddEvenMerge(array_, 0, power_);
149
150 return true;
151 }
152
153 48 bool ShemetovDRadixOddEvenMergeSortTBB::PostProcessingImpl() {
154
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 44 times.
 48 if (size_ == 0) {
155 return true;
156 }
157
158 44 array_.resize(size_);
159
160
2/2
✓ Branch 0 taken 368 times.
✓ Branch 1 taken 44 times.
 412 for (size_t i = 0; i < size_; i += 1) {
161 368 array_[i] += offset_;
162 }
163
164
1/2
✓ Branch 0 taken 44 times.
✗ Branch 1 not taken.
 44 if (!std::ranges::is_sorted(array_.begin(), array_.end())) {
165 return false;
166 }
167
168 44 GetOutput() = array_;
169 44 return true;
170 }
171
172 } // namespace shemetov_d_radix_odd_even_mergesort
173