GCC Code Coverage Report

Directory: ./
File: tasks/krasnopevtseva_v_hoare_batcher_sort/tbb/src/ops_tbb.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 64 93 68.8%
Functions: 9 12 75.0%
Branches: 36 72 50.0%
Line Branch Exec Source
1 #include "krasnopevtseva_v_hoare_batcher_sort/tbb/include/ops_tbb.hpp"
2
3 #include <tbb/tbb.h>
4
5 #include <algorithm>
6 #include <cstddef>
7 #include <stack>
8 #include <thread>
9 #include <utility>
10 #include <vector>
11
12 #include "krasnopevtseva_v_hoare_batcher_sort/common/include/common.hpp"
13 #include "oneapi/tbb/parallel_for.h"
14
15 namespace krasnopevtseva_v_hoare_batcher_sort {
16
17
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 KrasnopevtsevaVHoareBatcherSortTBB::KrasnopevtsevaVHoareBatcherSortTBB(const InType &in) {
18 SetTypeOfTask(GetStaticTypeOfTask());
19
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 GetInput() = in;
20 24 GetOutput() = std::vector<int>();
21 24 }
22
23 24 bool KrasnopevtsevaVHoareBatcherSortTBB::ValidationImpl() {
24 const auto &input = GetInput();
25 24 return !input.empty();
26 }
27
28 24 bool KrasnopevtsevaVHoareBatcherSortTBB::PreProcessingImpl() {
29 24 GetOutput() = std::vector<int>();
30 24 return true;
31 }
32
33
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 bool KrasnopevtsevaVHoareBatcherSortTBB::RunImpl() {
34 const auto &input = GetInput();
35 std::size_t size = input.size();
36
37
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (size <= 1) {
38 ✗ GetOutput() = input;
39 ✗ return true;
40 }
41
42 24 int numthreads = static_cast<int>(std::thread::hardware_concurrency());
43
4/6
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 20 times.
✓ Branch 3 taken 4 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 4 times.
✗ Branch 7 not taken.
 24 static tbb::global_control control(tbb::global_control::max_allowed_parallelism, numthreads);
44
45 24 std::vector<int> res = input;
46
47
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 int n = static_cast<int>(size);
48 24 numthreads = std::min(n, numthreads);
49
50 24 int thread_input_size = n / numthreads;
51 24 int thread_input_remainder_size = n % numthreads;
52
53
1/4
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 24 std::vector<int *> pointers(numthreads);
54
1/4
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 24 std::vector<int> sizes(numthreads);
55
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 24 times.
 120 for (int i = 0; i < numthreads; ++i) {
56 96 auto offset = static_cast<std::ptrdiff_t>(i) * static_cast<std::ptrdiff_t>(thread_input_size);
57 96 pointers[i] = res.data() + offset;
58 96 sizes[i] = thread_input_size;
59 }
60 24 sizes[sizes.size() - 1] += thread_input_remainder_size;
61
62
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 216 tbb::parallel_for(tbb::blocked_range<int>(0, numthreads, 1), [&](const tbb::blocked_range<int> &r) {
63
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 96 times.
 192 for (int i = r.begin(); i < r.end(); ++i) {
64 96 int left = static_cast<int>(pointers[i] - res.data());
65 96 int right = left + sizes[i] - 1;
66 96 QuickSort(res, left, right);
67 }
68 ✗ }, tbb::simple_partitioner());
69
70
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 BatcherMerge(thread_input_size, pointers, sizes, 32);
71
72 GetOutput() = std::move(res);
73 return true;
74 }
75
76 24 bool KrasnopevtsevaVHoareBatcherSortTBB::PostProcessingImpl() {
77 24 return true;
78 }
79
80 ✗ int KrasnopevtsevaVHoareBatcherSortTBB::Partition(std::vector<int> &arr, int first, int last) {
81 ✗ int i = first - 1;
82 ✗ int value = arr[last];
83
84 ✗ for (int j = first; j <= last - 1; ++j) {
85 ✗ if (arr[j] <= value) {
86 ✗ ++i;
87 ✗ std::swap(arr[i], arr[j]);
88 }
89 }
90 ✗ std::swap(arr[i + 1], arr[last]);
91 ✗ return i + 1;
92 }
93
94 80 void KrasnopevtsevaVHoareBatcherSortTBB::InsertionSort(std::vector<int> &arr, int first, int last) {
95
2/2
✓ Branch 0 taken 400 times.
✓ Branch 1 taken 80 times.
 480 for (int i = first + 1; i <= last; ++i) {
96 400 int key = arr[i];
97 400 int j = i - 1;
98
4/4
✓ Branch 0 taken 1164 times.
✓ Branch 1 taken 164 times.
✓ Branch 2 taken 928 times.
✓ Branch 3 taken 236 times.
 1328 while (j >= first && arr[j] > key) {
99 928 arr[j + 1] = arr[j];
100 928 --j;
101 }
102 400 arr[j + 1] = key;
103 }
104 80 }
105
106 96 void KrasnopevtsevaVHoareBatcherSortTBB::QuickSort(std::vector<int> &arr, int first, int last) {
107 std::stack<std::pair<int, int>> stack;
108 stack.emplace(first, last);
109
110
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 96 times.
 192 while (!stack.empty()) {
111 auto [l, r] = stack.top();
112 stack.pop();
113
114
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 80 times.
 96 if (l >= r) {
115 96 continue;
116 }
117
118
1/2
✓ Branch 0 taken 80 times.
✗ Branch 1 not taken.
 80 if (r - l < 16) {
119 80 InsertionSort(arr, l, r);
120 80 continue;
121 }
122
123 ✗ int iter = Partition(arr, l, r);
124
125 ✗ if (iter - l < r - iter) {
126 ✗ stack.emplace(iter + 1, r);
127 ✗ stack.emplace(l, iter - 1);
128 } else {
129 ✗ stack.emplace(l, iter - 1);
130 ✗ stack.emplace(iter + 1, r);
131 }
132 }
133 96 }
134
135 ✗ void KrasnopevtsevaVHoareBatcherSortTBB::BatcherMergeBlocksStep(int *left_pointer, int &left_size, int *right_pointer,
136 int &right_size) {
137 ✗ std::inplace_merge(left_pointer, right_pointer, right_pointer + right_size);
138 96 left_size += right_size;
139 24 }
140
141 24 void KrasnopevtsevaVHoareBatcherSortTBB::BatcherMerge(int thread_input_size, std::vector<int *> &pointers,
142 std::vector<int> &sizes, int par_if_greater) {
143 24 int pack = static_cast<int>(pointers.size());
144
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 24 times.
 72 for (int step = 1; pack > 1; step *= 2, pack /= 2) {
145
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 if ((thread_input_size / step) > par_if_greater) {
146 ✗ tbb::parallel_for(tbb::blocked_range<int>(0, pack / 2, 1), [&](const tbb::blocked_range<int> &r) {
147 ✗ for (int off = r.begin(); off < r.end(); ++off) {
148 ✗ auto idx1 = static_cast<std::size_t>(2 * step) * static_cast<std::size_t>(off);
149 ✗ auto idx2 = idx1 + static_cast<std::size_t>(step);
150 ✗ BatcherMergeBlocksStep(pointers[idx1], sizes[idx1], pointers[idx2], sizes[idx2]);
151 }
152 ✗ }, tbb::simple_partitioner());
153 } else {
154
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 48 times.
 120 for (int off = 0; off < pack / 2; ++off) {
155 72 auto idx1 = static_cast<std::size_t>(2 * step) * static_cast<std::size_t>(off);
156 72 auto idx2 = idx1 + static_cast<std::size_t>(step);
157 72 BatcherMergeBlocksStep(pointers[idx1], sizes[idx1], pointers[idx2], sizes[idx2]);
158 }
159 }
160
161
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 24 times.
 48 if ((pack / 2) - 1 == 0) {
162 24 BatcherMergeBlocksStep(pointers[0], sizes[sizes.size() - 1], pointers[pointers.size() - 1],
163 sizes[sizes.size() - 1]);
164
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 } else if ((pack / 2) % 2 != 0) {
165 ✗ auto idx1 = static_cast<std::size_t>(2 * step) * static_cast<std::size_t>((pack / 2) - 2);
166 ✗ auto idx2 = static_cast<std::size_t>(2 * step) * static_cast<std::size_t>((pack / 2) - 1);
167 ✗ BatcherMergeBlocksStep(pointers[idx1], sizes[idx1], pointers[idx2], sizes[idx2]);
168 }
169 }
170 24 }
171
172 } // namespace krasnopevtseva_v_hoare_batcher_sort
173