GCC Code Coverage Report

Directory: ./
File: tasks/rozenberg_a_quicksort_simple_merge/tbb/src/ops_tbb.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 69 69 100.0%
Functions: 10 10 100.0%
Branches: 54 70 77.1%
Line Branch Exec Source
1 #include "rozenberg_a_quicksort_simple_merge/tbb/include/ops_tbb.hpp"
2
3 #include <oneapi/tbb/blocked_range.h>
4 #include <oneapi/tbb/global_control.h>
5 #include <oneapi/tbb/parallel_for.h>
6 #include <tbb/tbb.h>
7
8 #include <stack>
9 #include <utility>
10 #include <vector>
11
12 #include "rozenberg_a_quicksort_simple_merge/common/include/common.hpp"
13 #include "util/include/util.hpp"
14
15 namespace rozenberg_a_quicksort_simple_merge {
16
17 36 RozenbergAQuicksortSimpleMergeTBB::RozenbergAQuicksortSimpleMergeTBB(const InType &in) {
18 SetTypeOfTask(GetStaticTypeOfTask());
19
20 InType empty;
21 GetInput().swap(empty);
22
23
2/2
✓ Branch 0 taken 2708 times.
✓ Branch 1 taken 36 times.
 2744 for (const auto &elem : in) {
24 GetInput().push_back(elem);
25 }
26
27 GetOutput().clear();
28 36 }
29
30
1/2
✓ Branch 0 taken 36 times.
✗ Branch 1 not taken.
 36 bool RozenbergAQuicksortSimpleMergeTBB::ValidationImpl() {
31
2/4
✓ Branch 0 taken 36 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 36 times.
 36 return (!(GetInput().empty())) && (GetOutput().empty());
32 }
33
34 36 bool RozenbergAQuicksortSimpleMergeTBB::PreProcessingImpl() {
35 36 GetOutput().resize(GetInput().size());
36 36 return GetOutput().size() == GetInput().size();
37 }
38
39 2260 std::pair<int, int> RozenbergAQuicksortSimpleMergeTBB::Partition(InType &data, int left, int right) {
40 2260 const int pivot = data[left + ((right - left) / 2)];
41 int i = left;
42 int j = right;
43
44
2/2
✓ Branch 0 taken 6204 times.
✓ Branch 1 taken 2260 times.
 10724 while (i <= j) {
45
2/2
✓ Branch 0 taken 5951 times.
✓ Branch 1 taken 6204 times.
 12155 while (data[i] < pivot) {
46 5951 i++;
47 }
48
2/2
✓ Branch 0 taken 5612 times.
✓ Branch 1 taken 6204 times.
 11816 while (data[j] > pivot) {
49 5612 j--;
50 }
51
52
2/2
✓ Branch 0 taken 591 times.
✓ Branch 1 taken 5613 times.
 6204 if (i <= j) {
53 std::swap(data[i], data[j]);
54 5613 i++;
55 5613 j--;
56 }
57 }
58 2260 return {i, j};
59 }
60
61 2260 void RozenbergAQuicksortSimpleMergeTBB::PushSubarrays(std::stack<std::pair<int, int>> &stack, int left, int right,
62 int i, int j) {
63
2/2
✓ Branch 0 taken 525 times.
✓ Branch 1 taken 1735 times.
 2260 if (j - left > right - i) {
64
1/2
✓ Branch 0 taken 525 times.
✗ Branch 1 not taken.
 525 if (left < j) {
65 stack.emplace(left, j);
66 }
67
2/2
✓ Branch 0 taken 281 times.
✓ Branch 1 taken 244 times.
 525 if (i < right) {
68 stack.emplace(i, right);
69 }
70 } else {
71
2/2
✓ Branch 0 taken 842 times.
✓ Branch 1 taken 893 times.
 1735 if (i < right) {
72 stack.emplace(i, right);
73 }
74
2/2
✓ Branch 0 taken 554 times.
✓ Branch 1 taken 1181 times.
 1735 if (left < j) {
75 stack.emplace(left, j);
76 }
77 }
78 2260 }
79
80 62 void RozenbergAQuicksortSimpleMergeTBB::Quicksort(InType &data, int low, int high) {
81
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 58 times.
 62 if (low >= high) {
82 4 return;
83 }
84
85 std::stack<std::pair<int, int>> stack;
86
87 stack.emplace(low, high);
88
89
2/2
✓ Branch 0 taken 2260 times.
✓ Branch 1 taken 58 times.
 2318 while (!stack.empty()) {
90 const auto [left, right] = stack.top();
91 stack.pop();
92
93
1/2
✓ Branch 0 taken 2260 times.
✗ Branch 1 not taken.
 2260 if (left < right) {
94 2260 const auto [i, j] = Partition(data, left, right);
95
1/2
✓ Branch 1 taken 2260 times.
✗ Branch 2 not taken.
 2260 PushSubarrays(stack, left, right, i, j);
96 }
97 }
98 }
99
100 26 void RozenbergAQuicksortSimpleMergeTBB::Merge(InType &data, int left, int mid, int right) {
101 26 std::vector<int> temp(right - left + 1);
102 int i = left;
103 26 int j = mid + 1;
104 int k = 0;
105
106
2/2
✓ Branch 0 taken 3022 times.
✓ Branch 1 taken 26 times.
 3048 while (i <= mid && j <= right) {
107
2/2
✓ Branch 0 taken 1953 times.
✓ Branch 1 taken 1069 times.
 3022 if (data[i] <= data[j]) {
108 1953 temp[k++] = data[i++];
109 } else {
110 1069 temp[k++] = data[j++];
111 }
112 }
113
114
2/2
✓ Branch 0 taken 19 times.
✓ Branch 1 taken 26 times.
 45 while (i <= mid) {
115 19 temp[k++] = data[i++];
116 }
117
2/2
✓ Branch 0 taken 205 times.
✓ Branch 1 taken 26 times.
 231 while (j <= right) {
118 205 temp[k++] = data[j++];
119 }
120
121
2/2
✓ Branch 0 taken 3246 times.
✓ Branch 1 taken 26 times.
 3272 for (int idx = 0; idx < k; ++idx) {
122 3246 data[left + idx] = temp[idx];
123 }
124 26 }
125
126 36 bool RozenbergAQuicksortSimpleMergeTBB::RunImpl() {
127 36 InType data = GetInput();
128 36 int n = static_cast<int>(data.size());
129
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 36 int num_threads = ppc::util::GetNumThreads();
130
131
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 36 tbb::global_control control(tbb::global_control::max_allowed_parallelism, num_threads);
132
133
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 22 times.
 36 if (n < num_threads * 2) {
134
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 Quicksort(data, 0, n - 1);
135
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 GetOutput() = data;
136 return true;
137 }
138
139 // Create chunk borders container
140
1/2
✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
 22 std::vector<int> borders(num_threads + 1);
141 22 int chunk_size = n / num_threads;
142
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 22 times.
 70 for (int i = 0; i < num_threads; i++) {
143 48 borders[i] = i * chunk_size;
144 }
145 22 borders[num_threads] = n;
146
147 // Sort local chunks
148
1/4
✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 70 tbb::parallel_for(tbb::blocked_range<int>(0, num_threads), [&](const tbb::blocked_range<int> &range) {
149
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 48 times.
 96 for (int i = range.begin(); i != range.end(); i++) {
150 48 Quicksort(data, borders[i], borders[i + 1] - 1);
151 }
152 48 });
153
154 // Merge sorted chunks
155
2/2
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 22 times.
 48 for (int i = 1; i < num_threads; i++) {
156
1/2
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
 26 Merge(data, 0, borders[i] - 1, borders[i + 1] - 1);
157 }
158
159
1/2
✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
 22 GetOutput() = data;
160 return true;
161 }
162
163 36 bool RozenbergAQuicksortSimpleMergeTBB::PostProcessingImpl() {
164 36 return true;
165 }
166
167 } // namespace rozenberg_a_quicksort_simple_merge
168