GCC Code Coverage Report

Directory: ./
File: tasks/shekhirev_v_hoare_batcher_sort/tbb/src/ops_tbb.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 64 64 100.0%
Functions: 9 9 100.0%
Branches: 45 58 77.6%
Line Branch Exec Source
1 #include "shekhirev_v_hoare_batcher_sort/tbb/include/ops_tbb.hpp"
2
3 #include <tbb/tbb.h>
4
5 #include <algorithm>
6 #include <climits>
7 #include <utility>
8 #include <vector>
9
10 #include "shekhirev_v_hoare_batcher_sort/common/include/common.hpp"
11 #include "util/include/util.hpp"
12
13 namespace shekhirev_v_hoare_batcher_sort {
14
15 namespace {
16
17 54 void HoareSort(std::vector<int> &arr, int low, int high) {
18 54 std::vector<std::pair<int, int>> stack;
19
1/2
✓ Branch 1 taken 54 times.
✗ Branch 2 not taken.
 54 stack.emplace_back(low, high);
20
21
2/2
✓ Branch 0 taken 9354 times.
✓ Branch 1 taken 54 times.
 9408 while (!stack.empty()) {
22 auto [l, h] = stack.back();
23 stack.pop_back();
24
25
2/2
✓ Branch 0 taken 4704 times.
✓ Branch 1 taken 4650 times.
 9354 if (l >= h) {
26 4704 continue;
27 }
28
29 4650 int pivot = arr[l + ((h - l) / 2)];
30 4650 int i = l - 1;
31 4650 int j = h + 1;
32
33 while (true) {
34
2/2
✓ Branch 0 taken 11245 times.
✓ Branch 1 taken 12789 times.
 24034 while (arr[++i] < pivot) {
35 }
36
2/2
✓ Branch 0 taken 13844 times.
✓ Branch 1 taken 12789 times.
 26633 while (arr[--j] > pivot) {
37 }
38
2/2
✓ Branch 0 taken 8139 times.
✓ Branch 1 taken 4650 times.
 12789 if (i >= j) {
39 break;
40 }
41 std::swap(arr[i], arr[j]);
42 }
43
44
1/2
✓ Branch 1 taken 4650 times.
✗ Branch 2 not taken.
 4650 stack.emplace_back(l, j);
45
1/4
✓ Branch 1 taken 4650 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 4650 stack.emplace_back(j + 1, h);
46 }
47 54 }
48
49 void ProcessBatcherStep(std::vector<int> &a, int step_p, int step_k, int start, int total_pairs) {
50 16754 tbb::parallel_for(tbb::blocked_range<int>(0, total_pairs), [&](const tbb::blocked_range<int> &r) {
51
2/2
✓ Branch 0 taken 16754 times.
✓ Branch 1 taken 16754 times.
 33508 for (int step = r.begin(); step != r.end(); ++step) {
52 16754 int i = step % step_k;
53 16754 int b = step / step_k;
54 16754 int j = start + (b * (step_k * 2));
55
56 16754 int idx1 = i + j;
57 16754 int idx2 = i + j + step_k;
58
59
2/2
✓ Branch 0 taken 16466 times.
✓ Branch 1 taken 288 times.
 16754 if ((idx1 / (step_p * 2)) == (idx2 / (step_p * 2))) {
60
2/2
✓ Branch 0 taken 8650 times.
✓ Branch 1 taken 7816 times.
 16466 if (a[idx1] > a[idx2]) {
61 std::swap(a[idx1], a[idx2]);
62 }
63 }
64 }
65 16754 });
66 }
67
68 24 void BatcherMerge(std::vector<int> &a, int n_pow2, int chunk_size) {
69
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 24 times.
 48 for (int step_p = chunk_size; step_p < n_pow2; step_p *= 2) {
70
2/2
✓ Branch 0 taken 150 times.
✓ Branch 1 taken 24 times.
 174 for (int step_k = step_p; step_k >= 1; step_k /= 2) {
71 int start = step_k;
72 150 int num_blocks = (n_pow2 / (2 * step_k)) - 1;
73
74
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 126 times.
 150 if (step_k == step_p) {
75 start = 0;
76 num_blocks = n_pow2 / (2 * step_k);
77 }
78
79 150 int total_pairs = num_blocks * step_k;
80 150 ProcessBatcherStep(a, step_p, step_k, start, total_pairs);
81 }
82 }
83 24 }
84
85 } // namespace
86
87
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 ShekhirevHoareBatcherSortTBB::ShekhirevHoareBatcherSortTBB(const InType &in) {
88 SetTypeOfTask(GetStaticTypeOfTask());
89
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 GetInput() = in;
90 GetOutput().clear();
91 32 }
92
93 32 bool ShekhirevHoareBatcherSortTBB::ValidationImpl() {
94 32 return true;
95 }
96
97 32 bool ShekhirevHoareBatcherSortTBB::PreProcessingImpl() {
98 32 input_ = GetInput();
99 32 return true;
100 }
101
102
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 24 times.
 32 bool ShekhirevHoareBatcherSortTBB::RunImpl() {
103 32 int n = static_cast<int>(input_.size());
104
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 24 times.
 32 if (n <= 1) {
105 8 res_.assign(input_.begin(), input_.end());
106 8 return true;
107 }
108
109 int n_pow2 = 1;
110
2/2
✓ Branch 0 taken 156 times.
✓ Branch 1 taken 24 times.
 180 while (n_pow2 < n) {
111 156 n_pow2 *= 2;
112 }
113
114 24 std::vector<int> a(n_pow2, INT_MAX);
115
2/2
✓ Branch 0 taken 4420 times.
✓ Branch 1 taken 24 times.
 4444 for (int i = 0; i < n; i++) {
116 4420 a[i] = input_[i];
117 }
118
119
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 int num_threads = ppc::util::GetNumThreads();
120
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 tbb::global_control global_limit(tbb::global_control::max_allowed_parallelism, num_threads);
121
122 int p_threads = 1;
123
3/4
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
 48 while ((p_threads * 2) <= num_threads && (p_threads * 2) <= n_pow2) {
124 p_threads *= 2;
125 }
126
127 24 int chunk_size = n_pow2 / p_threads;
128
129
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 78 tbb::parallel_for(tbb::blocked_range<int>(0, p_threads), [&](const tbb::blocked_range<int> &r) {
130
2/2
✓ Branch 0 taken 54 times.
✓ Branch 1 taken 54 times.
 108 for (int i = r.begin(); i != r.end(); ++i) {
131 54 HoareSort(a, i * chunk_size, ((i + 1) * chunk_size) - 1);
132 }
133 54 });
134
135
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 BatcherMerge(a, n_pow2, chunk_size);
136
137
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 res_.assign(a.begin(), a.begin() + n);
138 return true;
139 }
140
141 32 bool ShekhirevHoareBatcherSortTBB::PostProcessingImpl() {
142 32 GetOutput() = res_;
143 32 return true;
144 }
145
146 } // namespace shekhirev_v_hoare_batcher_sort
147