GCC Code Coverage Report

Directory: ./
File: tasks/spichek_d_radix_sort_for_integers_with_simple_merging/tbb/src/ops_tbb.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 53 53 100.0%
Functions: 6 6 100.0%
Branches: 43 64 67.2%
Line Branch Exec Source
1 #include "spichek_d_radix_sort_for_integers_with_simple_merging/tbb/include/ops_tbb.hpp"
2
3 #include <oneapi/tbb/parallel_for.h>
4 #include <tbb/tbb.h>
5
6 #include <algorithm>
7 #include <iterator>
8 #include <utility>
9 #include <vector>
10
11 #include "spichek_d_radix_sort_for_integers_with_simple_merging/common/include/common.hpp"
12 #include "util/include/util.hpp"
13
14 namespace spichek_d_radix_sort_for_integers_with_simple_merging {
15
16
1/2
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
 60 SpichekDRadixSortTBB::SpichekDRadixSortTBB(const InType &in) {
17 SetTypeOfTask(GetStaticTypeOfTask());
18
1/2
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
 60 GetInput() = in;
19 60 }
20
21 60 bool SpichekDRadixSortTBB::ValidationImpl() {
22 60 return !GetInput().empty();
23 }
24
25 60 bool SpichekDRadixSortTBB::PreProcessingImpl() {
26 60 GetOutput() = GetInput();
27 60 return true;
28 }
29
30
1/2
✓ Branch 0 taken 60 times.
✗ Branch 1 not taken.
 60 bool SpichekDRadixSortTBB::RunImpl() {
31
1/2
✓ Branch 0 taken 60 times.
✗ Branch 1 not taken.
 60 if (GetOutput().empty()) {
32 return true;
33 }
34
35 60 int num_threads = ppc::util::GetNumThreads();
36 60 int n = static_cast<int>(GetOutput().size());
37
38
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 45 times.
 60 if (num_threads <= 1 || n < num_threads) {
39 15 RadixSort(GetOutput());
40 15 return true;
41 }
42
43 45 std::vector<std::vector<int>> local_data(num_threads);
44 45 int base_size = n / num_threads;
45 45 int remainder = n % num_threads;
46
47
1/2
✓ Branch 1 taken 45 times.
✗ Branch 2 not taken.
 45 std::vector<int> counts(num_threads);
48
1/4
✓ Branch 1 taken 45 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 45 std::vector<int> displs(num_threads, 0);
49
50
2/2
✓ Branch 0 taken 135 times.
✓ Branch 1 taken 45 times.
 180 for (int i = 0; i < num_threads; ++i) {
51
4/4
✓ Branch 0 taken 115 times.
✓ Branch 1 taken 20 times.
✓ Branch 2 taken 90 times.
✓ Branch 3 taken 45 times.
 250 counts[i] = base_size + (i < remainder ? 1 : 0);
52
2/2
✓ Branch 0 taken 90 times.
✓ Branch 1 taken 45 times.
 135 if (i > 0) {
53 90 displs[i] = displs[i - 1] + counts[i - 1];
54 }
55
1/2
✓ Branch 1 taken 135 times.
✗ Branch 2 not taken.
 270 local_data[i] = std::vector<int>(GetOutput().begin() + displs[i], GetOutput().begin() + displs[i] + counts[i]);
56 }
57
58
1/4
✓ Branch 2 taken 45 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 180 tbb::parallel_for(0, num_threads, [&](int i) { RadixSort(local_data[i]); });
59
60 std::vector<int> result = std::move(local_data[0]);
61
2/2
✓ Branch 0 taken 90 times.
✓ Branch 1 taken 45 times.
 135 for (int i = 1; i < num_threads; ++i) {
62
1/2
✓ Branch 1 taken 90 times.
✗ Branch 2 not taken.
 90 std::vector<int> temp;
63
1/2
✓ Branch 1 taken 90 times.
✗ Branch 2 not taken.
 90 temp.reserve(result.size() + local_data[i].size());
64
1/2
✓ Branch 1 taken 90 times.
✗ Branch 2 not taken.
 90 std::ranges::merge(result, local_data[i], std::back_inserter(temp));
65 result = std::move(temp);
66 }
67
68 GetOutput() = std::move(result);
69 return true;
70 45 }
71
72
1/2
✓ Branch 0 taken 60 times.
✗ Branch 1 not taken.
 60 bool SpichekDRadixSortTBB::PostProcessingImpl() {
73 60 return std::ranges::is_sorted(GetOutput());
74 }
75
76
1/2
✓ Branch 0 taken 150 times.
✗ Branch 1 not taken.
 150 void SpichekDRadixSortTBB::RadixSort(std::vector<int> &data) {
77
1/2
✓ Branch 0 taken 150 times.
✗ Branch 1 not taken.
 150 if (data.empty()) {
78 return;
79 }
80
81 150 int min_val = *std::ranges::min_element(data);
82
2/2
✓ Branch 0 taken 100 times.
✓ Branch 1 taken 50 times.
 150 if (min_val < 0) {
83
2/2
✓ Branch 0 taken 83933 times.
✓ Branch 1 taken 100 times.
 84033 for (auto &x : data) {
84 83933 x -= min_val;
85 }
86 }
87
88 150 int max_val = *std::ranges::max_element(data);
89
90
2/2
✓ Branch 0 taken 270 times.
✓ Branch 1 taken 150 times.
 420 for (int shift = 0; (max_val >> shift) > 0; shift += 8) {
91 270 std::vector<int> output(data.size());
92
1/4
✓ Branch 1 taken 270 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 270 std::vector<int> count(256, 0);
93
94
2/2
✓ Branch 0 taken 219600 times.
✓ Branch 1 taken 270 times.
 219870 for (int x : data) {
95 219600 count[(x >> shift) & 255]++;
96 }
97
98
2/2
✓ Branch 0 taken 68850 times.
✓ Branch 1 taken 270 times.
 69120 for (int i = 1; i < 256; i++) {
99 68850 count[i] += count[i - 1];
100 }
101
102
2/2
✓ Branch 0 taken 219600 times.
✓ Branch 1 taken 270 times.
 219870 for (int i = static_cast<int>(data.size()) - 1; i >= 0; i--) {
103 219600 output[count[(data[i] >> shift) & 255] - 1] = data[i];
104 219600 count[(data[i] >> shift) & 255]--;
105 }
106
107 data = std::move(output);
108 }
109
110
2/2
✓ Branch 0 taken 100 times.
✓ Branch 1 taken 50 times.
 150 if (min_val < 0) {
111
2/2
✓ Branch 0 taken 83933 times.
✓ Branch 1 taken 100 times.
 84033 for (auto &x : data) {
112 83933 x += min_val;
113 }
114 }
115 }
116
117 } // namespace spichek_d_radix_sort_for_integers_with_simple_merging
118