GCC Code Coverage Report

Directory: ./
File: tasks/kamaletdinov_r_bitwise_int/all/src/ops_all.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 103 105 98.1%
Functions: 10 10 100.0%
Branches: 95 162 58.6%
Line Branch Exec Source
1 #include "kamaletdinov_r_bitwise_int/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4 #include <omp.h>
5
6 #include <algorithm>
7 #include <array>
8 #include <cstddef>
9 #include <vector>
10
11 #include "kamaletdinov_r_bitwise_int/common/include/common.hpp"
12
13 namespace kamaletdinov_r_bitwise_int {
14
15 namespace {
16
17 23 void CountingSortByDigitALL(std::vector<int> &arr, int exp) {
18 23 const int n = static_cast<int>(arr.size());
19 23 const int thread_count = omp_get_max_threads();
20 23 std::vector<std::array<int, 10>> local_counts(thread_count);
21
22 23 #pragma omp parallel default(none) shared(arr, exp, local_counts, n) num_threads(thread_count)
23 {
24 const int tid = omp_get_thread_num();
25 auto &current = local_counts.at(tid);
26 current.fill(0);
27
28 #pragma omp for schedule(static)
29 for (int i = 0; i < n; i++) {
30 const int digit = (arr.at(i) / exp) % 10;
31 current.at(digit)++;
32 }
33 }
34
35 23 std::array<int, 10> global_count = {};
36
2/2
✓ Branch 0 taken 46 times.
✓ Branch 1 taken 23 times.
 69 for (int ti = 0; ti < thread_count; ti++) {
37
2/2
✓ Branch 0 taken 460 times.
✓ Branch 1 taken 46 times.
 506 for (int di = 0; di < 10; di++) {
38
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 460 times.
 460 global_count.at(di) += local_counts.at(ti).at(di);
39 }
40 }
41
42 23 std::array<int, 10> global_start = {};
43
2/2
✓ Branch 0 taken 207 times.
✓ Branch 1 taken 23 times.
 230 for (int di = 1; di < 10; di++) {
44 207 global_start.at(di) = global_start.at(di - 1) + global_count.at(di - 1);
45 }
46
47
1/4
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 23 std::vector<std::array<int, 10>> thread_offsets(thread_count);
48
2/2
✓ Branch 0 taken 230 times.
✓ Branch 1 taken 23 times.
 253 for (int di = 0; di < 10; di++) {
49 230 int offset = global_start.at(di);
50
2/2
✓ Branch 0 taken 460 times.
✓ Branch 1 taken 230 times.
 690 for (int ti = 0; ti < thread_count; ti++) {
51
2/4
✗ Branch 0 not taken.
✓ Branch 1 taken 460 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 460 times.
 460 thread_offsets.at(ti).at(di) = offset;
52 460 offset += local_counts.at(ti).at(di);
53 }
54 }
55
56
1/4
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 23 std::vector<int> output(n);
57
58
1/2
✓ Branch 0 taken 23 times.
✗ Branch 1 not taken.
 23 #pragma omp parallel default(none) shared(arr, exp, output, n, thread_count, thread_offsets) num_threads(thread_count)
59 {
60 const int tid = omp_get_thread_num();
61 auto positions = thread_offsets.at(tid);
62
63 #pragma omp for schedule(static)
64 for (int i = 0; i < n; i++) {
65 const int digit = (arr.at(i) / exp) % 10;
66 output.at(positions.at(digit)++) = arr.at(i);
67 }
68 }
69
70 arr.swap(output);
71 23 }
72
73
2/2
✓ Branch 0 taken 17 times.
✓ Branch 1 taken 9 times.
 26 void RadixSortPositiveALL(std::vector<int> &arr) {
74
2/2
✓ Branch 0 taken 17 times.
✓ Branch 1 taken 9 times.
 26 if (arr.empty()) {
75 return;
76 }
77
78 17 int max_val = *std::ranges::max_element(arr);
79
2/2
✓ Branch 0 taken 23 times.
✓ Branch 1 taken 4 times.
 27 for (int exp = 1; max_val / exp > 0; exp *= 10) {
80 23 CountingSortByDigitALL(arr, exp);
81
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 13 times.
 23 if (exp > max_val / 10) {
82 break;
83 }
84 }
85 }
86
87
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 13 times.
 16 void LocalBitwiseSort(std::vector<int> &arr) {
88
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 13 times.
 16 if (arr.size() <= 1) {
89 3 return;
90 }
91
92 13 std::vector<int> neg;
93
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 std::vector<int> pos;
94
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 neg.reserve(arr.size());
95
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 pos.reserve(arr.size());
96
97
2/2
✓ Branch 0 taken 1380 times.
✓ Branch 1 taken 13 times.
 1393 for (int val : arr) {
98
2/2
✓ Branch 0 taken 684 times.
✓ Branch 1 taken 696 times.
 1380 if (val < 0) {
99
1/4
✓ Branch 1 taken 684 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 684 neg.push_back(-val);
100 } else {
101 pos.push_back(val);
102 }
103 }
104
105
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 RadixSortPositiveALL(neg);
106
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 RadixSortPositiveALL(pos);
107
108 std::size_t idx = 0;
109
2/2
✓ Branch 0 taken 684 times.
✓ Branch 1 taken 13 times.
 697 for (int i = static_cast<int>(neg.size()) - 1; i >= 0; i--) {
110
2/4
✗ Branch 0 not taken.
✓ Branch 1 taken 684 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 684 times.
 684 arr.at(idx++) = -neg.at(i);
111 }
112
2/2
✓ Branch 0 taken 696 times.
✓ Branch 1 taken 13 times.
 709 for (int v : pos) {
113
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 696 times.
 696 arr.at(idx++) = v;
114 }
115 }
116
117 8 std::vector<int> MergeSorted(const std::vector<int> &a, const std::vector<int> &b) {
118
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 std::vector<int> result;
119
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 result.reserve(a.size() + b.size());
120 std::size_t i = 0;
121 std::size_t j = 0;
122
3/4
✗ Branch 0 not taken.
✓ Branch 1 taken 698 times.
✓ Branch 2 taken 8 times.
✓ Branch 3 taken 690 times.
 698 while (i < a.size() && j < b.size()) {
123
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 690 times.
 690 if (a[i] <= b[j]) {
124 ✗ result.push_back(a[i++]);
125 } else {
126
1/2
✓ Branch 0 taken 690 times.
✗ Branch 1 not taken.
 690 result.push_back(b[j++]);
127 }
128 }
129
2/2
✓ Branch 0 taken 693 times.
✓ Branch 1 taken 8 times.
 701 while (i < a.size()) {
130
1/2
✓ Branch 0 taken 693 times.
✗ Branch 1 not taken.
 693 result.push_back(a[i++]);
131 }
132
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8 times.
 8 while (j < b.size()) {
133 ✗ result.push_back(b[j++]);
134 }
135 8 return result;
136 }
137
138 } // namespace
139
140 20 void BitwiseSortALL(std::vector<int> &arr) {
141 20 int rank = 0;
142 20 int size = 1;
143 20 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
144 20 MPI_Comm_size(MPI_COMM_WORLD, &size);
145
146 20 int total = static_cast<int>(arr.size());
147 20 MPI_Bcast(&total, 1, MPI_INT, 0, MPI_COMM_WORLD);
148
149
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 16 times.
 20 if (total <= 1) {
150 4 return;
151 }
152
153 16 std::vector<int> send_counts(size);
154
1/4
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 16 std::vector<int> displs(size);
155
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 16 times.
 48 for (int i = 0; i < size; i++) {
156
4/4
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 16 times.
✓ Branch 3 taken 16 times.
 58 send_counts[i] = (total / size) + (i < total % size ? 1 : 0);
157
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 16 times.
 32 displs[i] = (i == 0) ? 0 : displs[i - 1] + send_counts[i - 1];
158 }
159
160
1/4
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 16 std::vector<int> local_data(send_counts[rank]);
161
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 MPI_Scatterv(arr.data(), send_counts.data(), displs.data(), MPI_INT, local_data.data(), send_counts[rank], MPI_INT, 0,
162 MPI_COMM_WORLD);
163
164
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 LocalBitwiseSort(local_data);
165
166
2/6
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 16 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 16 std::vector<int> recv_counts(size);
167
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 MPI_Gather(&send_counts[rank], 1, MPI_INT, recv_counts.data(), 1, MPI_INT, 0, MPI_COMM_WORLD);
168
169
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 8 times.
 16 if (rank == 0) {
170
1/4
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 8 std::vector<int> all_data(total);
171
1/4
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 8 std::vector<int> recv_displs(size);
172
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 8 times.
 16 for (int i = 1; i < size; i++) {
173 8 recv_displs[i] = recv_displs[i - 1] + recv_counts[i - 1];
174 }
175
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 MPI_Gatherv(local_data.data(), send_counts[rank], MPI_INT, all_data.data(), recv_counts.data(), recv_displs.data(),
176 MPI_INT, 0, MPI_COMM_WORLD);
177
178
1/4
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 8 std::vector<int> merged = {all_data.begin(), all_data.begin() + recv_counts[0]};
179
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 8 times.
 16 for (int i = 1; i < size; i++) {
180
1/4
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 8 std::vector<int> chunk(all_data.begin() + recv_displs[i], all_data.begin() + recv_displs[i] + recv_counts[i]);
181
2/6
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 8 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 16 merged = MergeSorted(merged, chunk);
182 }
183
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 arr = merged;
184 } else {
185
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 MPI_Gatherv(local_data.data(), send_counts[rank], MPI_INT, nullptr, nullptr, nullptr, MPI_INT, 0, MPI_COMM_WORLD);
186
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 arr.resize(total);
187 }
188
189
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 MPI_Bcast(arr.data(), total, MPI_INT, 0, MPI_COMM_WORLD);
190 }
191
192 20 KamaletdinovRBitwiseIntALL::KamaletdinovRBitwiseIntALL(const InType &in) {
193 SetTypeOfTask(GetStaticTypeOfTask());
194 20 GetInput() = in;
195 GetOutput() = 0;
196 20 }
197
198 20 bool KamaletdinovRBitwiseIntALL::ValidationImpl() {
199 20 return GetInput() >= 0;
200 }
201
202 20 bool KamaletdinovRBitwiseIntALL::PreProcessingImpl() {
203 20 int n = GetInput();
204 20 data_.resize(n);
205
2/2
✓ Branch 0 taken 2768 times.
✓ Branch 1 taken 20 times.
 2788 for (int i = 0; i < n; i++) {
206 2768 data_[i] = (n / 2) - i;
207 }
208 20 return true;
209 }
210
211 20 bool KamaletdinovRBitwiseIntALL::RunImpl() {
212 20 BitwiseSortALL(data_);
213 20 return true;
214 }
215
216
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 2 times.
 20 bool KamaletdinovRBitwiseIntALL::PostProcessingImpl() {
217 bool sorted = std::ranges::is_sorted(data_);
218
1/2
✓ Branch 0 taken 18 times.
✗ Branch 1 not taken.
 20 GetOutput() = sorted ? GetInput() : 0;
219 20 return true;
220 }
221
222 } // namespace kamaletdinov_r_bitwise_int
223