GCC Code Coverage Report

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