GCC Code Coverage Report

Directory: ./
File: tasks/rozenberg_a_quicksort_simple_merge/all/src/ops_all.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 101 101 100.0%
Functions: 11 11 100.0%
Branches: 82 108 75.9%
Line Branch Exec Source
1 #include "rozenberg_a_quicksort_simple_merge/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4 #include <omp.h>
5
6 #include <stack>
7 #include <utility>
8 #include <vector>
9
10 #include "rozenberg_a_quicksort_simple_merge/common/include/common.hpp"
11 #include "util/include/util.hpp"
12
13 namespace rozenberg_a_quicksort_simple_merge {
14
15 18 RozenbergAQuicksortSimpleMergeALL::RozenbergAQuicksortSimpleMergeALL(const InType &in) {
16 SetTypeOfTask(GetStaticTypeOfTask());
17
18 InType empty;
19 GetInput().swap(empty);
20
21
2/2
✓ Branch 0 taken 1354 times.
✓ Branch 1 taken 18 times.
 1372 for (const auto &elem : in) {
22 GetInput().push_back(elem);
23 }
24
25 GetOutput().clear();
26 18 }
27
28
1/2
✓ Branch 0 taken 18 times.
✗ Branch 1 not taken.
 18 bool RozenbergAQuicksortSimpleMergeALL::ValidationImpl() {
29
2/4
✓ Branch 0 taken 18 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 18 times.
 18 return (!(GetInput().empty())) && (GetOutput().empty());
30 }
31
32 18 bool RozenbergAQuicksortSimpleMergeALL::PreProcessingImpl() {
33 18 GetOutput().resize(GetInput().size());
34 18 return GetOutput().size() == GetInput().size();
35 }
36
37 548 std::pair<int, int> RozenbergAQuicksortSimpleMergeALL::Partition(InType &data, int left, int right) {
38 548 const int pivot = data[left + ((right - left) / 2)];
39 int i = left;
40 int j = right;
41
42
2/2
✓ Branch 0 taken 1397 times.
✓ Branch 1 taken 548 times.
 2493 while (i <= j) {
43
2/2
✓ Branch 0 taken 1358 times.
✓ Branch 1 taken 1397 times.
 2755 while (data[i] < pivot) {
44 1358 i++;
45 }
46
2/2
✓ Branch 0 taken 1241 times.
✓ Branch 1 taken 1397 times.
 2638 while (data[j] > pivot) {
47 1241 j--;
48 }
49
50
2/2
✓ Branch 0 taken 162 times.
✓ Branch 1 taken 1235 times.
 1397 if (i <= j) {
51 std::swap(data[i], data[j]);
52 1235 i++;
53 1235 j--;
54 }
55 }
56 548 return {i, j};
57 }
58
59 548 void RozenbergAQuicksortSimpleMergeALL::PushSubarrays(std::stack<std::pair<int, int>> &stack, int left, int right,
60 int i, int j) {
61
2/2
✓ Branch 0 taken 122 times.
✓ Branch 1 taken 426 times.
 548 if (j - left > right - i) {
62
1/2
✓ Branch 0 taken 122 times.
✗ Branch 1 not taken.
 122 if (left < j) {
63 stack.emplace(left, j);
64 }
65
2/2
✓ Branch 0 taken 65 times.
✓ Branch 1 taken 57 times.
 122 if (i < right) {
66 stack.emplace(i, right);
67 }
68 } else {
69
2/2
✓ Branch 0 taken 209 times.
✓ Branch 1 taken 217 times.
 426 if (i < right) {
70 stack.emplace(i, right);
71 }
72
2/2
✓ Branch 0 taken 130 times.
✓ Branch 1 taken 296 times.
 426 if (left < j) {
73 stack.emplace(left, j);
74 }
75 }
76 548 }
77
78 28 void RozenbergAQuicksortSimpleMergeALL::Quicksort(InType &data, int low, int high) {
79
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 22 times.
 28 if (low >= high) {
80 6 return;
81 }
82
83 std::stack<std::pair<int, int>> stack;
84
85 stack.emplace(low, high);
86
87
2/2
✓ Branch 0 taken 548 times.
✓ Branch 1 taken 22 times.
 570 while (!stack.empty()) {
88 const auto [left, right] = stack.top();
89 stack.pop();
90
91
1/2
✓ Branch 0 taken 548 times.
✗ Branch 1 not taken.
 548 if (left < right) {
92 548 const auto [i, j] = Partition(data, left, right);
93
1/2
✓ Branch 1 taken 548 times.
✗ Branch 2 not taken.
 548 PushSubarrays(stack, left, right, i, j);
94 }
95 }
96 }
97
98 9 InType RozenbergAQuicksortSimpleMergeALL::Merge(const InType &v1, const InType &v2) {
99
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 InType res;
100
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 res.reserve(v1.size() + v2.size());
101 auto it1 = v1.begin();
102 auto it2 = v2.begin();
103
4/4
✓ Branch 0 taken 618 times.
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 612 times.
✓ Branch 3 taken 6 times.
 621 while (it1 != v1.end() && it2 != v2.end()) {
104
2/2
✓ Branch 0 taken 330 times.
✓ Branch 1 taken 282 times.
 612 if (*it1 <= *it2) {
105 res.push_back(*it1++);
106 } else {
107 res.push_back(*it2++);
108 }
109 }
110
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 res.insert(res.end(), it1, v1.end());
111 9 res.insert(res.end(), it2, v2.end());
112 9 return res;
113 }
114
115 10 void RozenbergAQuicksortSimpleMergeALL::ThreadMerge(InType &data, int left, int mid, int right) {
116 10 std::vector<int> temp(right - left + 1);
117 int i = left;
118 10 int j = mid + 1;
119 int k = 0;
120
121
2/2
✓ Branch 0 taken 603 times.
✓ Branch 1 taken 10 times.
 613 while (i <= mid && j <= right) {
122
2/2
✓ Branch 0 taken 325 times.
✓ Branch 1 taken 278 times.
 603 if (data[i] <= data[j]) {
123 325 temp[k++] = data[i++];
124 } else {
125 278 temp[k++] = data[j++];
126 }
127 }
128
129
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 10 times.
 15 while (i <= mid) {
130 5 temp[k++] = data[i++];
131 }
132
2/2
✓ Branch 0 taken 58 times.
✓ Branch 1 taken 10 times.
 68 while (j <= right) {
133 58 temp[k++] = data[j++];
134 }
135
136
2/2
✓ Branch 0 taken 666 times.
✓ Branch 1 taken 10 times.
 676 for (int idx = 0; idx < k; ++idx) {
137 666 data[left + idx] = temp[idx];
138 }
139 10 }
140
141 18 void RozenbergAQuicksortSimpleMergeALL::ThreadQuicksort(InType &local_data) {
142 18 int num_threads = ppc::util::GetNumThreads();
143 18 int local_n = static_cast<int>(local_data.size());
144
145
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 8 times.
 18 if (local_n > num_threads) {
146 10 std::vector<int> thr_borders(num_threads + 1);
147 10 int thr_chunk = local_n / num_threads;
148
149
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 10 times.
 30 for (int i = 0; i < num_threads; i++) {
150 20 thr_borders[i] = i * thr_chunk;
151 }
152 10 thr_borders[num_threads] = local_n;
153
154 10 #pragma omp parallel for default(none) shared(local_data, thr_borders, num_threads) num_threads(num_threads)
155 for (int i = 0; i < num_threads; i++) {
156 Quicksort(local_data, thr_borders[i], thr_borders[i + 1] - 1);
157 }
158
159
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 for (int i = 1; i < num_threads; i++) {
160
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 ThreadMerge(local_data, 0, thr_borders[i] - 1, thr_borders[i + 1] - 1);
161 }
162 } else {
163 8 Quicksort(local_data, 0, local_n - 1);
164 }
165 18 }
166
167 18 bool RozenbergAQuicksortSimpleMergeALL::RunImpl() {
168 18 int rank = 0;
169 18 int size = 0;
170 18 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
171 18 MPI_Comm_size(MPI_COMM_WORLD, &size);
172
173 18 int n = 0;
174
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 9 times.
 18 if (rank == 0) {
175 9 n = static_cast<int>(GetInput().size());
176 }
177 18 MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
178
179 18 std::vector<int> send_counts(size);
180
1/4
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 18 std::vector<int> displs(size, 0);
181 18 int chunk = n / size;
182 18 int rem = n % size;
183
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 18 times.
 54 for (int i = 0; i < size; i++) {
184
4/4
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 10 times.
✓ Branch 2 taken 18 times.
✓ Branch 3 taken 18 times.
 62 send_counts[i] = chunk + (i < rem ? 1 : 0);
185
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 18 times.
 36 if (i > 0) {
186 18 displs[i] = displs[i - 1] + send_counts[i - 1];
187 }
188 }
189
190
1/4
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 18 std::vector<int> local_data(send_counts[rank]);
191
3/4
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 9 times.
✓ Branch 3 taken 18 times.
✗ Branch 4 not taken.
 27 MPI_Scatterv(rank == 0 ? GetInput().data() : nullptr, send_counts.data(), displs.data(), MPI_INT, local_data.data(),
192
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 9 times.
 18 send_counts[rank], MPI_INT, 0, MPI_COMM_WORLD);
193
194
1/2
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
 18 ThreadQuicksort(local_data);
195
196
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 9 times.
 18 if (rank != 0) {
197
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 MPI_Send(local_data.data(), static_cast<int>(local_data.size()), MPI_INT, 0, 0, MPI_COMM_WORLD);
198 } else {
199
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 InType total_data = local_data;
200
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 9 times.
 18 for (int i = 1; i < size; ++i) {
201
1/4
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 9 InType recv_buf(send_counts[i]);
202
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 MPI_Recv(recv_buf.data(), send_counts[i], MPI_INT, i, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
203
204
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 auto merged = Merge(total_data, recv_buf);
205 total_data.swap(merged);
206 }
207
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 GetOutput() = total_data;
208 }
209
210 18 return true;
211 }
212
213 18 bool RozenbergAQuicksortSimpleMergeALL::PostProcessingImpl() {
214 18 return true;
215 }
216
217 } // namespace rozenberg_a_quicksort_simple_merge
218