GCC Code Coverage Report

Directory: ./
File: tasks/litvyakov_d_shell_sort/all/src/ops_all.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 85 86 98.8%
Functions: 8 8 100.0%
Branches: 58 82 70.7%
Line Branch Exec Source
1 #include "litvyakov_d_shell_sort/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4 #include <omp.h>
5
6 #include <algorithm>
7 #include <cstddef>
8 #include <cstdio>
9 #include <vector>
10
11 #include "litvyakov_d_shell_sort/common/include/common.hpp"
12 #include "util/include/util.hpp"
13
14 namespace litvyakov_d_shell_sort {
15
16 12 void LitvyakovDShellSortALL::BaseShellSort(std::vector<int>::iterator first, std::vector<int>::iterator last) {
17
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 12 times.
 60 for (std::ptrdiff_t dist = (last - first) / 2; dist > 0; dist /= 2) {
18
2/2
✓ Branch 0 taken 6342 times.
✓ Branch 1 taken 48 times.
 6390 for (auto i = first + dist; i != last; ++i) {
19
4/4
✓ Branch 0 taken 10818 times.
✓ Branch 1 taken 557 times.
✓ Branch 2 taken 5033 times.
✓ Branch 3 taken 5785 times.
 11375 for (auto j = i; j - first >= dist && (*j < *(j - dist)); j -= dist) {
20 std::swap(*j, *(j - dist));
21 }
22 }
23 }
24 12 }
25
26
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 std::vector<std::size_t> LitvyakovDShellSortALL::GetBounds(std::size_t n, std::size_t parts) {
27
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 parts = std::max<std::size_t>(1, std::min(parts, n));
28
29 6 std::vector<std::size_t> bounds;
30
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 bounds.reserve(parts + 1);
31
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 bounds.push_back(0);
32
33 6 const std::size_t base = n / parts;
34 6 const std::size_t rem = n % parts;
35
36
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 6 times.
 18 for (std::size_t i = 0; i < parts; ++i) {
37
1/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 12 bounds.push_back(bounds.back() + base);
38
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 10 times.
 12 if (i < rem) {
39 2 bounds[i + 1]++;
40 }
41 }
42
43 6 return bounds;
44 }
45
46
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 void LitvyakovDShellSortALL::ShellSortMerge(std::vector<int> &vec) {
47
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 if (vec.empty()) {
48 ✗ return;
49 }
50 6 const std::size_t threads = std::max(1, ppc::util::GetNumThreads());
51 const std::size_t parts_count = std::min<std::size_t>(threads, vec.size());
52 6 const auto bounds = GetBounds(vec.size(), parts_count);
53 6 int parts_count_t = static_cast<int>(parts_count);
54
55 6 #pragma omp parallel for default(none) shared(vec, bounds, parts_count_t) schedule(static)
56 for (int i = 0; i < parts_count_t; ++i) {
57 const std::size_t l = bounds[i];
58 const std::size_t r = bounds[i + 1];
59 BaseShellSort(vec.begin() + static_cast<std::ptrdiff_t>(l), vec.begin() + static_cast<std::ptrdiff_t>(r));
60 }
61
62
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 for (std::size_t i = 1; i < parts_count; ++i) {
63 6 std::inplace_merge(vec.begin(), vec.begin() + static_cast<std::ptrdiff_t>(bounds[i]),
64 6 vec.begin() + static_cast<std::ptrdiff_t>(bounds[i + 1]));
65 }
66 }
67
68
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 LitvyakovDShellSortALL::LitvyakovDShellSortALL(const InType &in) {
69 SetTypeOfTask(GetStaticTypeOfTask());
70
71 8 int world_rank = 0;
72
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);
73
74
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 if (world_rank == 0) {
75
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 GetInput() = in;
76 } else {
77 4 GetInput() = InType();
78 }
79 8 GetOutput() = std::vector<int>();
80 8 }
81
82 8 bool LitvyakovDShellSortALL::ValidationImpl() {
83 8 int world_rank = 0;
84 8 MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);
85
86
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 if (world_rank == 0) {
87 const InType &vec = GetInput();
88 4 return !vec.empty();
89 }
90 return true;
91 }
92
93 8 bool LitvyakovDShellSortALL::PreProcessingImpl() {
94 8 int world_rank = 0;
95 8 MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);
96
97
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 if (world_rank == 0) {
98 4 GetOutput() = GetInput();
99 }
100 8 return true;
101 }
102
103 8 bool LitvyakovDShellSortALL::RunImpl() {
104 8 int world_rank = 0;
105 8 int world_size = 0;
106 8 MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);
107 8 MPI_Comm_size(MPI_COMM_WORLD, &world_size);
108
109 std::vector<int> &vec = GetOutput();
110
111 8 int n = 0;
112
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 if (world_rank == 0) {
113 4 n = static_cast<int>(vec.size());
114 }
115
116 8 MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
117
118
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 2 times.
 8 if (n <= 1) {
119 return true;
120 }
121
122 6 std::vector<int> sendcounts(world_size, 0);
123
1/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 6 std::vector<int> displs(world_size, 0);
124 6 int base = n / world_size;
125 6 int rem = n % world_size;
126 int current_displ = 0;
127
128
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 6 times.
 18 for (int i = 0; i < world_size; ++i) {
129
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 24 sendcounts[i] = base + (i < rem ? 1 : 0);
130 12 displs[i] = current_displ;
131 12 current_displ += sendcounts[i];
132 }
133
134
1/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 6 std::vector<int> local_vec(sendcounts[world_rank]);
135
136
3/4
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
✓ Branch 3 taken 6 times.
✗ Branch 4 not taken.
 9 MPI_Scatterv(world_rank == 0 ? vec.data() : nullptr, sendcounts.data(), displs.data(), MPI_INT, local_vec.data(),
137
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 sendcounts[world_rank], MPI_INT, 0, MPI_COMM_WORLD);
138
139
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 ShellSortMerge(local_vec);
140
141
3/4
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
✓ Branch 3 taken 6 times.
✗ Branch 4 not taken.
 9 MPI_Gatherv(local_vec.data(), sendcounts[world_rank], MPI_INT, world_rank == 0 ? vec.data() : nullptr,
142 sendcounts.data(), displs.data(), MPI_INT, 0, MPI_COMM_WORLD);
143
144
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (world_rank == 0) {
145
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 for (int i = 1; i < world_size; ++i) {
146
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
 3 if (sendcounts[i] > 0) {
147 3 std::inplace_merge(
148 vec.begin(), vec.begin() + static_cast<std::ptrdiff_t>(displs[i]),
149 3 vec.begin() + static_cast<std::ptrdiff_t>(displs[i]) + static_cast<std::ptrdiff_t>(sendcounts[i]));
150 }
151 }
152 }
153
154 return true;
155 }
156
157 8 bool LitvyakovDShellSortALL::PostProcessingImpl() {
158 8 int world_rank = 0;
159 8 MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);
160
161 std::vector<int> &vec = GetOutput();
162 8 int n = 0;
163
164
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 if (world_rank == 0) {
165 4 n = static_cast<int>(vec.size());
166 }
167
168 8 MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
169
170
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 if (world_rank != 0) {
171 4 vec.resize(n);
172 }
173
174
1/2
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
 8 if (n > 0) {
175 8 MPI_Bcast(vec.data(), n, MPI_INT, 0, MPI_COMM_WORLD);
176 }
177
178 8 return true;
179 }
180
181 } // namespace litvyakov_d_shell_sort
182