GCC Code Coverage Report

Directory: ./
File: tasks/levonychev_i_radix_batcher_sort/tbb/src/ops_tbb.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 60 60 100.0%
Functions: 10 10 100.0%
Branches: 33 42 78.6%
Line Branch Exec Source
1 #include "levonychev_i_radix_batcher_sort/tbb/include/ops_tbb.hpp"
2
3 #include <tbb/blocked_range.h>
4 #include <tbb/global_control.h>
5 #include <tbb/parallel_for.h>
6 #include <tbb/parallel_invoke.h>
7
8 #include <algorithm>
9 #include <cstddef>
10 #include <ranges>
11 #include <vector>
12
13 #include "levonychev_i_radix_batcher_sort/common/include/common.hpp"
14 #include "util/include/util.hpp"
15
16 namespace levonychev_i_radix_batcher_sort {
17
18
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 LevonychevIRadixBatcherSortTBB::LevonychevIRadixBatcherSortTBB(const InType &in) {
19 SetTypeOfTask(GetStaticTypeOfTask());
20
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 GetInput() = in;
21 16 }
22
23 132 void LevonychevIRadixBatcherSortTBB::CountingSort(InType &arr, size_t byte_index) {
24 const size_t byte = 256;
25
1/2
✓ Branch 2 taken 132 times.
✗ Branch 3 not taken.
 132 std::vector<int> count(byte, 0);
26
1/4
✓ Branch 1 taken 132 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 132 OutType result(arr.size());
27
28 bool is_last_byte = (byte_index == (sizeof(int) - 1ULL));
29
2/2
✓ Branch 0 taken 384 times.
✓ Branch 1 taken 132 times.
 516 for (auto number : arr) {
30 384 int value_of_byte = (number >> (byte_index * 8ULL)) & 0xFF;
31
32
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 288 times.
 384 if (is_last_byte) {
33 96 value_of_byte ^= 0x80;
34 }
35
36 384 ++count[value_of_byte];
37 }
38
39
2/2
✓ Branch 0 taken 33660 times.
✓ Branch 1 taken 132 times.
 33792 for (size_t i = 1ULL; i < byte; ++i) {
40 33660 count[i] += count[i - 1];
41 }
42
43
2/2
✓ Branch 0 taken 384 times.
✓ Branch 1 taken 132 times.
 516 for (int &val : std::ranges::reverse_view(arr)) {
44 384 int value_of_byte = (val >> (byte_index * 8ULL)) & 0xFF;
45
46
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 288 times.
 384 if (is_last_byte) {
47 96 value_of_byte ^= 0x80;
48 }
49
50 384 result[--count[value_of_byte]] = val;
51 }
52
1/2
✓ Branch 1 taken 132 times.
✗ Branch 2 not taken.
 132 arr = result;
53 132 }
54
55 16 bool LevonychevIRadixBatcherSortTBB::ValidationImpl() {
56 16 return !GetInput().empty();
57 }
58
59 16 bool LevonychevIRadixBatcherSortTBB::PreProcessingImpl() {
60 16 return true;
61 }
62
63 75 void LevonychevIRadixBatcherSortTBB::BatcherCompareRange(std::vector<int> &arr, int j, int k, int p2) {
64 75 int range = std::min(k, static_cast<int>(arr.size()) - j - k);
65
2/2
✓ Branch 0 taken 123 times.
✓ Branch 1 taken 75 times.
 198 for (int i = 0; i < range; ++i) {
66 123 int idx1 = j + i;
67 123 int idx2 = j + i + k;
68
4/4
✓ Branch 0 taken 117 times.
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 75 times.
✓ Branch 3 taken 42 times.
 123 if ((idx1 & p2) == (idx2 & p2) && (arr[idx1] > arr[idx2])) {
69 std::swap(arr[idx1], arr[idx2]);
70 }
71 }
72 75 }
73
74 12 void LevonychevIRadixBatcherSortTBB::BatcherMergeIterative(std::vector<int> &arr, int start_p) {
75 12 int n = static_cast<int>(arr.size());
76
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 12 times.
 27 for (int pv = start_p; pv < n; pv <<= 1) {
77 15 int p2 = pv << 1;
78
2/2
✓ Branch 0 taken 39 times.
✓ Branch 1 taken 15 times.
 54 for (int k = pv; k > 0; k >>= 1) {
79 39 int num_iters = (n - k - (k % pv) + 2 * k - 1) / (2 * k);
80
81 39 tbb::parallel_for(0, num_iters, [&](int i) {
82 75 int j = (k % pv) + (i * (2 * k));
83 75 BatcherCompareRange(arr, j, k, p2);
84 75 });
85 }
86 }
87 12 }
88
89 16 bool LevonychevIRadixBatcherSortTBB::RunImpl() {
90 16 GetOutput() = GetInput();
91 16 int n = static_cast<int>(GetOutput().size());
92
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 4 times.
 16 if (n <= 1) {
93 return true;
94 }
95 12 int num_threads = ppc::util::GetNumThreads();
96 12 int grain = std::max(1, n / num_threads);
97
98 45 tbb::parallel_for(tbb::blocked_range<int>(0, n, grain), [&](const tbb::blocked_range<int> &r) {
99 int left = r.begin();
100 int right = r.end();
101
102 33 std::vector<int> local_block(GetOutput().begin() + left, GetOutput().begin() + right);
103
2/2
✓ Branch 0 taken 132 times.
✓ Branch 1 taken 33 times.
 165 for (size_t i = 0; i < sizeof(int); ++i) {
104
1/2
✓ Branch 1 taken 132 times.
✗ Branch 2 not taken.
 132 CountingSort(local_block, i);
105 }
106
1/2
✓ Branch 0 taken 33 times.
✗ Branch 1 not taken.
 33 std::ranges::copy(local_block, GetOutput().begin() + left);
107 33 });
108
109 int block_size = grain;
110 int start_p = 1;
111
2/2
✓ Branch 0 taken 21 times.
✓ Branch 1 taken 12 times.
 33 while (start_p < block_size) {
112 21 start_p <<= 1;
113 }
114
115 12 BatcherMergeIterative(GetOutput(), start_p);
116 12 return true;
117 }
118
119 16 bool LevonychevIRadixBatcherSortTBB::PostProcessingImpl() {
120 16 return true;
121 }
122
123 } // namespace levonychev_i_radix_batcher_sort
124