GCC Code Coverage Report

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