GCC Code Coverage Report

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