GCC Code Coverage Report

Directory: ./
File: tasks/nikitina_v_hoar_sort_batcher/tbb/src/ops_tbb.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 79 83 95.2%
Functions: 11 11 100.0%
Branches: 60 86 69.8%
Line Branch Exec Source
1 #include "nikitina_v_hoar_sort_batcher/tbb/include/ops_tbb.hpp"
2
3 #include <tbb/tbb.h>
4
5 #include <algorithm>
6 #include <limits>
7 #include <utility>
8 #include <vector>
9
10 #include "nikitina_v_hoar_sort_batcher/common/include/common.hpp"
11
12 namespace nikitina_v_hoar_sort_batcher {
13
14 namespace {
15
16 48 void QuickSortHoare(std::vector<int> &arr, int low, int high) {
17
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 if (low >= high) {
18 ✗ return;
19 }
20 48 std::vector<std::pair<int, int>> stack;
21
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 stack.emplace_back(low, high);
22
23
2/2
✓ Branch 0 taken 240 times.
✓ Branch 1 taken 48 times.
 288 while (!stack.empty()) {
24 auto [l, h] = stack.back();
25 stack.pop_back();
26
27
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 96 times.
 240 if (l >= h) {
28 144 continue;
29 }
30
31 96 int pivot = arr[l + ((h - l) / 2)];
32 96 int i = l - 1;
33 96 int j = h + 1;
34
35 while (true) {
36 156 i++;
37
2/2
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 156 times.
 208 while (arr[i] < pivot) {
38 52 i++;
39 }
40
41 156 j--;
42
2/2
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 156 times.
 208 while (arr[j] > pivot) {
43 52 j--;
44 }
45
46
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 96 times.
 156 if (i >= j) {
47 break;
48 }
49 std::swap(arr[i], arr[j]);
50 }
51
52
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 stack.emplace_back(l, j);
53
1/4
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 96 stack.emplace_back(j + 1, h);
54 }
55 }
56
57 60 void CompareSplit(std::vector<int> &arr, int start1, int len1, int start2, int len2) {
58
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 60 times.
 60 if (len1 == 0 || len2 == 0) {
59 ✗ return;
60 }
61
62
1/2
✓ Branch 2 taken 60 times.
✗ Branch 3 not taken.
 60 std::vector<int> left_block(arr.begin() + start1, arr.begin() + start1 + len1);
63
1/4
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 60 std::vector<int> right_block(arr.begin() + start2, arr.begin() + start2 + len2);
64
65 int p1 = 0;
66 int p2 = 0;
67 int write1 = start1;
68 int write2 = start2;
69
70
2/2
✓ Branch 0 taken 360 times.
✓ Branch 1 taken 60 times.
 420 for (int i = 0; i < len1 + len2; ++i) {
71 int val = 0;
72
6/6
✓ Branch 0 taken 280 times.
✓ Branch 1 taken 80 times.
✓ Branch 2 taken 248 times.
✓ Branch 3 taken 32 times.
✓ Branch 4 taken 148 times.
✓ Branch 5 taken 100 times.
 360 if (p1 < len1 && (p2 == len2 || left_block[p1] <= right_block[p2])) {
73 180 val = left_block[p1++];
74 } else {
75 180 val = right_block[p2++];
76 }
77
78
2/2
✓ Branch 0 taken 180 times.
✓ Branch 1 taken 180 times.
 360 if (i < len1) {
79 180 arr[write1++] = val;
80 } else {
81 180 arr[write2++] = val;
82 }
83 }
84 }
85
86 36 void BuildPairs(std::vector<std::pair<int, int>> &pairs, int num_threads, int step_p, int step_k) {
87
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 36 times.
 84 for (int idx_j = step_k % step_p; idx_j + step_k < num_threads; idx_j += (step_k * 2)) {
88
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 48 times.
 108 for (int idx_i = 0; idx_i < std::min(step_k, num_threads - idx_j - step_k); idx_i++) {
89
1/2
✓ Branch 0 taken 60 times.
✗ Branch 1 not taken.
 60 if ((idx_j + idx_i) / (step_p * 2) == (idx_j + idx_i + step_k) / (step_p * 2)) {
90 60 pairs.emplace_back(idx_j + idx_i, idx_j + idx_i + step_k);
91 }
92 }
93 }
94 36 }
95
96 12 void BatcherMergePhase(std::vector<int> &output, const std::vector<int> &offsets, int num_threads) {
97
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 12 times.
 36 for (int step_p = 1; step_p < num_threads; step_p *= 2) {
98
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 24 times.
 60 for (int step_k = step_p; step_k > 0; step_k /= 2) {
99 36 std::vector<std::pair<int, int>> pairs;
100
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 36 BuildPairs(pairs, num_threads, step_p, step_k);
101
102 36 int num_pairs = static_cast<int>(pairs.size());
103
104 // TBB аналог: #pragma omp parallel for
105
2/6
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 36 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 96 tbb::parallel_for(tbb::blocked_range<int>(0, num_pairs), [&](const tbb::blocked_range<int> &r) {
106
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 60 times.
 120 for (int idx = r.begin(); idx != r.end(); ++idx) {
107 60 int block_a = pairs[idx].first;
108 60 int block_b = pairs[idx].second;
109 60 CompareSplit(output, offsets[block_a], offsets[block_a + 1] - offsets[block_a], offsets[block_b],
110 60 offsets[block_b + 1] - offsets[block_b]);
111 }
112 60 });
113 }
114 }
115 12 }
116
117 } // namespace
118
119
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 HoareSortBatcherTBB::HoareSortBatcherTBB(const InType &in) {
120 SetTypeOfTask(GetStaticTypeOfTask());
121
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 GetInput() = in;
122 16 }
123
124 16 bool HoareSortBatcherTBB::ValidationImpl() {
125 16 return true;
126 }
127
128 16 bool HoareSortBatcherTBB::PreProcessingImpl() {
129 16 GetOutput() = GetInput();
130 16 return true;
131 }
132
133
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 4 times.
 16 bool HoareSortBatcherTBB::RunImpl() {
134 auto &output = GetOutput();
135
136 16 int orig_n = static_cast<int>(output.size());
137
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 4 times.
 16 if (orig_n <= 1) {
138 return true;
139 }
140
141 int max_threads = tbb::this_task_arena::max_concurrency();
142 int t = 1;
143
3/4
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 12 times.
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
 36 while (t * 2 <= max_threads && t * 2 <= orig_n) {
144 t *= 2;
145 }
146
147
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 if (t == 1) {
148 ✗ QuickSortHoare(output, 0, orig_n - 1);
149 ✗ return true;
150 }
151
152 12 int pad = (t - (orig_n % t)) % t;
153
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 12 times.
 36 for (int i = 0; i < pad; ++i) {
154 24 output.push_back(std::numeric_limits<int>::max());
155 }
156
157 12 int n = orig_n + pad;
158 12 std::vector<int> offsets(t + 1, 0);
159 12 int chunk = n / t;
160
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 12 times.
 72 for (int i = 0; i <= t; ++i) {
161 60 offsets[i] = i * chunk;
162 }
163
164
1/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 60 tbb::parallel_for(tbb::blocked_range<int>(0, t), [&](const tbb::blocked_range<int> &r) {
165
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 48 times.
 96 for (int i = r.begin(); i != r.end(); ++i) {
166 48 QuickSortHoare(output, offsets[i], offsets[i + 1] - 1);
167 }
168 48 });
169
170
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 BatcherMergePhase(output, offsets, t);
171
172
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 output.resize(orig_n);
173
174 return true;
175 }
176
177 16 bool HoareSortBatcherTBB::PostProcessingImpl() {
178 16 return true;
179 }
180
181 } // namespace nikitina_v_hoar_sort_batcher
182