GCC Code Coverage Report

Directory: ./
File: tasks/posternak_a_radix_merge_sort/mpi/src/ops_mpi.cpp
Date: 2026-01-27 01:59:34
Exec Total Coverage
Lines: 79 79 100.0%
Functions: 9 9 100.0%
Branches: 51 78 65.4%
Line Branch Exec Source
1 #include "posternak_a_radix_merge_sort/mpi/include/ops_mpi.hpp"
2
3 #include <mpi.h>
4
5 #include <algorithm>
6 #include <cmath>
7 #include <cstddef>
8 #include <cstdint>
9 #include <utility>
10 #include <vector>
11
12 #include "posternak_a_radix_merge_sort/common/include/common.hpp"
13
14 namespace posternak_a_radix_merge_sort {
15
16
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 PosternakARadixMergeSortMPI::PosternakARadixMergeSortMPI(const InType &in) {
17 SetTypeOfTask(GetStaticTypeOfTask());
18
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 GetInput() = in;
19 40 }
20
21 40 bool PosternakARadixMergeSortMPI::ValidationImpl() {
22 const std::vector<int> &input = GetInput();
23 40 return !input.empty();
24 }
25
26 40 bool PosternakARadixMergeSortMPI::PreProcessingImpl() {
27 40 return true;
28 }
29
30 40 std::vector<uint32_t> PosternakARadixMergeSortMPI::RadixSortLocal(std::vector<int> &data) {
31 constexpr int kNumBytes = 4;
32 constexpr uint32_t kByteMask = 0xFFU;
33
34 40 std::vector<uint32_t> unsigned_data(data.size());
35
2/2
✓ Branch 0 taken 92 times.
✓ Branch 1 taken 40 times.
 132 for (size_t i = 0; i < data.size(); i++) {
36 92 unsigned_data[i] = static_cast<uint32_t>(data[i]) ^ 0x80000000U;
37 }
38
39
1/4
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 40 std::vector<uint32_t> buffer(data.size());
40
41
2/2
✓ Branch 0 taken 160 times.
✓ Branch 1 taken 40 times.
 200 for (int byte_index = 0; byte_index < kNumBytes; byte_index++) {
42
1/4
✓ Branch 1 taken 160 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 160 std::vector<int> count(256, 0);
43
2/2
✓ Branch 0 taken 368 times.
✓ Branch 1 taken 160 times.
 528 for (uint32_t value : unsigned_data) {
44 368 const auto current_byte = static_cast<uint8_t>((value >> (byte_index * 8)) & kByteMask);
45 368 ++count[current_byte];
46 }
47
48
2/2
✓ Branch 0 taken 40800 times.
✓ Branch 1 taken 160 times.
 40960 for (int i = 1; i < 256; ++i) {
49 40800 count[i] += count[i - 1];
50 }
51
52
2/2
✓ Branch 0 taken 368 times.
✓ Branch 1 taken 160 times.
 528 for (int i = static_cast<int>(unsigned_data.size()) - 1; i >= 0; i--) {
53 368 const auto current_byte = static_cast<uint8_t>((unsigned_data[i] >> (byte_index * 8)) & kByteMask);
54 368 buffer[--count[current_byte]] = unsigned_data[i];
55 }
56
57 unsigned_data.swap(buffer);
58 }
59
60 40 return unsigned_data;
61 }
62
63 40 std::vector<int> PosternakARadixMergeSortMPI::ConvertToSigned(const std::vector<uint32_t> &unsigned_data) {
64 40 std::vector<int> result(unsigned_data.size());
65
2/2
✓ Branch 0 taken 92 times.
✓ Branch 1 taken 40 times.
 132 for (size_t i = 0; i < unsigned_data.size(); i++) {
66 92 result[i] = static_cast<int>(unsigned_data[i] ^ 0x80000000U);
67 }
68 40 return result;
69 }
70
71 40 void PosternakARadixMergeSortMPI::CalculateCountsAndOffsets(int input_len, int size, std::vector<int> &counts,
72 std::vector<int> &offset) {
73 40 const int base = input_len / size;
74 40 const int extra = input_len % size;
75
76 40 counts.resize(size);
77 40 offset.resize(size, 0);
78
79
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 40 times.
 120 for (int i = 0; i < size; i++) {
80
4/4
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 28 times.
✓ Branch 2 taken 40 times.
✓ Branch 3 taken 40 times.
 132 counts[i] = base + (i < extra ? 1 : 0);
81
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 40 times.
 80 if (i > 0) {
82 40 offset[i] = offset[i - 1] + counts[i - 1];
83 }
84 }
85 40 }
86
87 20 void PosternakARadixMergeSortMPI::MergeSortedParts(std::vector<int> &result,
88 const std::vector<std::vector<int>> &sorted_proc_parts) {
89 20 std::vector<int> tmp;
90
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 20 times.
 40 for (size_t i = 1; i < sorted_proc_parts.size(); i++) {
91
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 tmp.resize(result.size() + sorted_proc_parts[i].size());
92 20 std::merge(result.begin(), result.end(), sorted_proc_parts[i].begin(), sorted_proc_parts[i].end(), tmp.begin());
93 result.swap(tmp);
94 }
95 20 }
96
97 40 bool PosternakARadixMergeSortMPI::RunImpl() {
98 40 int size = 0;
99 40 int rank = 0;
100 40 MPI_Comm_size(MPI_COMM_WORLD, &size);
101 40 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
102
103 40 int input_len = 0;
104 std::vector<int> *input = nullptr;
105
106
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 20 times.
 40 if (rank == 0) {
107 input = &GetInput();
108 20 input_len = static_cast<int>(input->size());
109 }
110
111 40 MPI_Bcast(&input_len, 1, MPI_INT, 0, MPI_COMM_WORLD);
112
113 40 std::vector<int> counts;
114 40 std::vector<int> offset;
115
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 CalculateCountsAndOffsets(input_len, size, counts, offset);
116
117
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 const int local_size = counts[rank];
118
1/4
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 40 std::vector<int> input_local(local_size);
119
120
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 20 times.
 40 if (rank == 0) {
121
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 MPI_Scatterv(input->data(), counts.data(), offset.data(), MPI_INT, input_local.data(), local_size, MPI_INT, 0,
122 MPI_COMM_WORLD);
123 } else {
124
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 MPI_Scatterv(nullptr, counts.data(), offset.data(), MPI_INT, input_local.data(), local_size, MPI_INT, 0,
125 MPI_COMM_WORLD);
126 }
127
128
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 std::vector<uint32_t> unsigned_sorted = RadixSortLocal(input_local);
129
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 std::vector<int> local_sorted = ConvertToSigned(unsigned_sorted);
130
131 40 std::vector<int> result;
132
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 20 times.
 40 if (rank == 0) {
133 20 std::vector<std::vector<int>> sorted_proc_parts;
134
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 sorted_proc_parts.reserve(static_cast<size_t>(size));
135 sorted_proc_parts.push_back(std::move(local_sorted));
136
137
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 20 times.
 40 for (int proc = 1; proc < size; proc++) {
138
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 std::vector<int> remote_sorted_proc_part(counts[proc]);
139
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 MPI_Recv(remote_sorted_proc_part.data(), counts[proc], MPI_INT, proc, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
140 sorted_proc_parts.push_back(std::move(remote_sorted_proc_part));
141 }
142
143 result = std::move(sorted_proc_parts[0]);
144
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 MergeSortedParts(result, sorted_proc_parts);
145 20 } else {
146
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 MPI_Send(local_sorted.data(), local_size, MPI_INT, 0, 0, MPI_COMM_WORLD);
147 }
148
149
1/4
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 40 std::vector<int> output(input_len);
150
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 20 times.
 40 if (rank == 0) {
151 output = std::move(result);
152 }
153
154
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 MPI_Bcast(output.data(), input_len, MPI_INT, 0, MPI_COMM_WORLD);
155 GetOutput() = std::move(output);
156
157 40 return true;
158 }
159
160 40 bool PosternakARadixMergeSortMPI::PostProcessingImpl() {
161 40 return true;
162 }
163
164 } // namespace posternak_a_radix_merge_sort
165