GCC Code Coverage Report

Directory: ./
File: tasks/smetanin_d_hoare_even_odd_batchelor/tbb/src/ops_tbb.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 60 61 98.4%
Functions: 10 10 100.0%
Branches: 37 48 77.1%
Line Branch Exec Source
1 #include "smetanin_d_hoare_even_odd_batchelor/tbb/include/ops_tbb.hpp"
2
3 #include <oneapi/tbb/concurrent_vector.h>
4 #include <oneapi/tbb/parallel_for.h>
5
6 #include <cstddef>
7 #include <stack>
8 #include <utility>
9 #include <vector>
10
11 #include "smetanin_d_hoare_even_odd_batchelor/common/include/common.hpp"
12
13 namespace smetanin_d_hoare_even_odd_batchelor {
14
15 namespace {
16
17 constexpr int kTaskCutoff = 1000;
18
19 44428 int HoarePartition(std::vector<int> &arr, int lo, int hi) {
20 44428 int pivot = arr[lo + ((hi - lo) / 2)];
21 44428 int i = lo - 1;
22 44428 int j = hi + 1;
23 while (true) {
24 172894 ++i;
25
2/2
✓ Branch 0 taken 235021 times.
✓ Branch 1 taken 172894 times.
 407915 while (arr[i] < pivot) {
26 235021 ++i;
27 }
28 172894 --j;
29
2/2
✓ Branch 0 taken 233982 times.
✓ Branch 1 taken 172894 times.
 406876 while (arr[j] > pivot) {
30 233982 --j;
31 }
32
2/2
✓ Branch 0 taken 44428 times.
✓ Branch 1 taken 128466 times.
 172894 if (i >= j) {
33 44428 return j;
34 }
35 std::swap(arr[i], arr[j]);
36 }
37 }
38
39 44428 void OddEvenMerge(std::vector<int> &arr, int lo, int hi) {
40 44428 int n = hi - lo + 1;
41
2/2
✓ Branch 0 taken 108823 times.
✓ Branch 1 taken 44428 times.
 153251 for (int step = 1; step < n; step *= 2) {
42
2/2
✓ Branch 0 taken 700680 times.
✓ Branch 1 taken 108823 times.
 809503 for (int i = lo; i + step <= hi; i += step * 2) {
43
2/2
✓ Branch 0 taken 229332 times.
✓ Branch 1 taken 471348 times.
 700680 if (arr[i] > arr[i + step]) {
44 std::swap(arr[i], arr[i + step]);
45 }
46 }
47 }
48 44428 }
49
50 97 void HoarSortBatcherSeq(std::vector<int> &arr, int lo, int hi) {
51 std::stack<std::pair<int, int>> stk;
52 stk.emplace(lo, hi);
53
2/2
✓ Branch 0 taken 88799 times.
✓ Branch 1 taken 97 times.
 88896 while (!stk.empty()) {
54 auto [l, r] = stk.top();
55 stk.pop();
56
2/2
✓ Branch 0 taken 44448 times.
✓ Branch 1 taken 44351 times.
 88799 if (l >= r) {
57 44448 continue;
58 }
59 44351 int p = HoarePartition(arr, l, r);
60
2/2
✓ Branch 0 taken 15581 times.
✓ Branch 1 taken 28770 times.
 44351 if ((p - l) > (r - p - 1)) {
61 stk.emplace(l, p);
62
1/2
✓ Branch 1 taken 15581 times.
✗ Branch 2 not taken.
 15581 stk.emplace(p + 1, r);
63 } else {
64
2/4
✓ Branch 1 taken 28770 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 28770 times.
✗ Branch 5 not taken.
 28770 stk.emplace(p + 1, r);
65 stk.emplace(l, p);
66 }
67 44351 OddEvenMerge(arr, l, r);
68 }
69 97 }
70
71 20 void HoarSortBatcherTBBImpl(std::vector<int> &arr, int lo, int hi) {
72
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 20 times.
 20 if (lo >= hi) {
73 ✗ return;
74 }
75
76 20 std::vector<std::pair<int, int>> cur;
77
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 cur.emplace_back(lo, hi);
78
79
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 20 times.
 76 while (!cur.empty()) {
80 tbb::concurrent_vector<std::pair<int, int>> next;
81 const std::size_t cur_sz = cur.size();
82
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 tbb::parallel_for(static_cast<std::size_t>(0), cur_sz, [&](std::size_t idx) {
83
1/2
✓ Branch 0 taken 174 times.
✗ Branch 1 not taken.
 174 const int l = cur[idx].first;
84 174 const int r = cur[idx].second;
85
1/2
✓ Branch 0 taken 174 times.
✗ Branch 1 not taken.
 174 if (l >= r) {
86 return;
87 }
88
2/2
✓ Branch 0 taken 97 times.
✓ Branch 1 taken 77 times.
 174 if (r - l < kTaskCutoff) {
89 97 HoarSortBatcherSeq(arr, l, r);
90 97 return;
91 }
92 77 const int p = HoarePartition(arr, l, r);
93 77 OddEvenMerge(arr, l, r);
94 77 next.push_back({l, p});
95 77 next.push_back({p + 1, r});
96 });
97
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 cur.assign(next.begin(), next.end());
98 }
99 }
100
101 } // namespace
102
103
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 SmetaninDHoarSortTBB::SmetaninDHoarSortTBB(const InType &in) {
104 SetTypeOfTask(GetStaticTypeOfTask());
105
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 GetInput() = in;
106 28 }
107
108 28 bool SmetaninDHoarSortTBB::ValidationImpl() {
109 28 return true;
110 }
111
112 28 bool SmetaninDHoarSortTBB::PreProcessingImpl() {
113 28 GetOutput() = GetInput();
114 28 return true;
115 }
116
117
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 8 times.
 28 bool SmetaninDHoarSortTBB::RunImpl() {
118 auto &data = GetOutput();
119 28 int n = static_cast<int>(data.size());
120
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 8 times.
 28 if (n > 1) {
121 20 HoarSortBatcherTBBImpl(data, 0, n - 1);
122 }
123 28 return true;
124 }
125
126 28 bool SmetaninDHoarSortTBB::PostProcessingImpl() {
127 28 return true;
128 }
129
130 } // namespace smetanin_d_hoare_even_odd_batchelor
131