GCC Code Coverage Report

Directory: ./
File: tasks/rozenberg_a_quicksort_simple_merge/tbb/src/ops_tbb.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 68 68 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
14 namespace rozenberg_a_quicksort_simple_merge {
15
16 36 RozenbergAQuicksortSimpleMergeTBB::RozenbergAQuicksortSimpleMergeTBB(const InType &in) {
17 SetTypeOfTask(GetStaticTypeOfTask());
18
19 InType empty;
20 GetInput().swap(empty);
21
22
2/2
✓ Branch 0 taken 2708 times.
✓ Branch 1 taken 36 times.
 2744 for (const auto &elem : in) {
23 GetInput().push_back(elem);
24 }
25
26 GetOutput().clear();
27 36 }
28
29
1/2
✓ Branch 0 taken 36 times.
✗ Branch 1 not taken.
 36 bool RozenbergAQuicksortSimpleMergeTBB::ValidationImpl() {
30
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());
31 }
32
33 36 bool RozenbergAQuicksortSimpleMergeTBB::PreProcessingImpl() {
34 36 GetOutput().resize(GetInput().size());
35 36 return GetOutput().size() == GetInput().size();
36 }
37
38 2196 std::pair<int, int> RozenbergAQuicksortSimpleMergeTBB::Partition(InType &data, int left, int right) {
39 2196 const int pivot = data[left + ((right - left) / 2)];
40 int i = left;
41 int j = right;
42
43
2/2
✓ Branch 0 taken 5580 times.
✓ Branch 1 taken 2196 times.
 9972 while (i <= j) {
44
2/2
✓ Branch 0 taken 5436 times.
✓ Branch 1 taken 5580 times.
 11016 while (data[i] < pivot) {
45 5436 i++;
46 }
47
2/2
✓ Branch 0 taken 5028 times.
✓ Branch 1 taken 5580 times.
 10608 while (data[j] > pivot) {
48 5028 j--;
49 }
50
51
2/2
✓ Branch 0 taken 624 times.
✓ Branch 1 taken 4956 times.
 5580 if (i <= j) {
52 std::swap(data[i], data[j]);
53 4956 i++;
54 4956 j--;
55 }
56 }
57 2196 return {i, j};
58 }
59
60 2196 void RozenbergAQuicksortSimpleMergeTBB::PushSubarrays(std::stack<std::pair<int, int>> &stack, int left, int right,
61 int i, int j) {
62
2/2
✓ Branch 0 taken 480 times.
✓ Branch 1 taken 1716 times.
 2196 if (j - left > right - i) {
63
1/2
✓ Branch 0 taken 480 times.
✗ Branch 1 not taken.
 480 if (left < j) {
64 stack.emplace(left, j);
65 }
66
2/2
✓ Branch 0 taken 252 times.
✓ Branch 1 taken 228 times.
 480 if (i < right) {
67 stack.emplace(i, right);
68 }
69 } else {
70
2/2
✓ Branch 0 taken 852 times.
✓ Branch 1 taken 864 times.
 1716 if (i < right) {
71 stack.emplace(i, right);
72 }
73
2/2
✓ Branch 0 taken 532 times.
✓ Branch 1 taken 1184 times.
 1716 if (left < j) {
74 stack.emplace(left, j);
75 }
76 }
77 2196 }
78
79 84 void RozenbergAQuicksortSimpleMergeTBB::Quicksort(InType &data, int low, int high) {
80
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 80 times.
 84 if (low >= high) {
81 4 return;
82 }
83
84 std::stack<std::pair<int, int>> stack;
85
86 stack.emplace(low, high);
87
88
2/2
✓ Branch 0 taken 2196 times.
✓ Branch 1 taken 80 times.
 2276 while (!stack.empty()) {
89 const auto [left, right] = stack.top();
90 stack.pop();
91
92
1/2
✓ Branch 0 taken 2196 times.
✗ Branch 1 not taken.
 2196 if (left < right) {
93 2196 const auto [i, j] = Partition(data, left, right);
94
1/2
✓ Branch 1 taken 2196 times.
✗ Branch 2 not taken.
 2196 PushSubarrays(stack, left, right, i, j);
95 }
96 }
97 }
98
99 48 void RozenbergAQuicksortSimpleMergeTBB::Merge(InType &data, int left, int mid, int right) {
100 48 std::vector<int> temp(right - left + 1);
101 int i = left;
102 48 int j = mid + 1;
103 int k = 0;
104
105
2/2
✓ Branch 0 taken 5564 times.
✓ Branch 1 taken 48 times.
 5612 while (i <= mid && j <= right) {
106
2/2
✓ Branch 0 taken 3896 times.
✓ Branch 1 taken 1668 times.
 5564 if (data[i] <= data[j]) {
107 3896 temp[k++] = data[i++];
108 } else {
109 1668 temp[k++] = data[j++];
110 }
111 }
112
113
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 48 times.
 88 while (i <= mid) {
114 40 temp[k++] = data[i++];
115 }
116
2/2
✓ Branch 0 taken 316 times.
✓ Branch 1 taken 48 times.
 364 while (j <= right) {
117 316 temp[k++] = data[j++];
118 }
119
120
2/2
✓ Branch 0 taken 5920 times.
✓ Branch 1 taken 48 times.
 5968 for (int idx = 0; idx < k; ++idx) {
121 5920 data[left + idx] = temp[idx];
122 }
123 48 }
124
125 36 bool RozenbergAQuicksortSimpleMergeTBB::RunImpl() {
126 36 InType data = GetInput();
127
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 36 int n = static_cast<int>(data.size());
128 int num_threads = tbb::info::default_concurrency();
129
130
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 36 tbb::global_control control(tbb::global_control::max_allowed_parallelism, num_threads);
131
132
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 16 times.
 36 if (n < num_threads * 2) {
133
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 Quicksort(data, 0, n - 1);
134
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 GetOutput() = data;
135 return true;
136 }
137
138 // Create chunk borders container
139
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 std::vector<int> borders(num_threads + 1);
140 16 int chunk_size = n / num_threads;
141
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 16 times.
 80 for (int i = 0; i < num_threads; i++) {
142 64 borders[i] = i * chunk_size;
143 }
144 16 borders[num_threads] = n;
145
146 // Sort local chunks
147
1/4
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 80 tbb::parallel_for(tbb::blocked_range<int>(0, num_threads), [&](const tbb::blocked_range<int> &range) {
148
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 64 times.
 128 for (int i = range.begin(); i != range.end(); i++) {
149 64 Quicksort(data, borders[i], borders[i + 1] - 1);
150 }
151 64 });
152
153 // Merge sorted chunks
154
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 16 times.
 64 for (int i = 1; i < num_threads; i++) {
155
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 Merge(data, 0, borders[i] - 1, borders[i + 1] - 1);
156 }
157
158
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 GetOutput() = data;
159 return true;
160 }
161
162 36 bool RozenbergAQuicksortSimpleMergeTBB::PostProcessingImpl() {
163 36 return true;
164 }
165
166 } // namespace rozenberg_a_quicksort_simple_merge
167