GCC Code Coverage Report

Directory: ./
File: tasks/ovsyannikov_n_shell_batcher/common/include/add_functs.hpp
Date: 2026-01-10 02:40:41
Exec Total Coverage
Lines: 65 65 100.0%
Functions: 7 7 100.0%
Branches: 55 74 74.3%
Line Branch Exec Source
1 #pragma once
2
3 #include <mpi.h>
4
5 #include <cstddef>
6 #include <utility>
7 #include <vector>
8
9 namespace ovsyannikov_n_shell_batcher {
10
11 3 inline std::vector<int> RecvVector(int src, int tag_base, MPI_Comm comm) {
12 3 int sz = 0;
13 3 MPI_Status status{};
14 3 MPI_Recv(&sz, 1, MPI_INT, src, tag_base, comm, &status);
15
16 3 std::vector<int> v(static_cast<std::size_t>(sz));
17
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
 3 if (sz > 0) {
18
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 MPI_Recv(v.data(), sz, MPI_INT, src, tag_base + 1, comm, &status);
19 }
20 3 return v;
21 }
22
23 3 inline void SendVector(int dst, int tag_base, const std::vector<int> &v, MPI_Comm comm) {
24 3 const int sz = static_cast<int>(v.size());
25 3 MPI_Send(&sz, 1, MPI_INT, dst, tag_base, comm);
26
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
 3 if (sz > 0) {
27 3 MPI_Send(v.data(), sz, MPI_INT, dst, tag_base + 1, comm);
28 }
29 3 }
30
31 30 inline void ShellSort(std::vector<int> *vec) {
32 auto &a = *vec;
33 const std::size_t n = a.size();
34
2/2
✓ Branch 0 taken 274 times.
✓ Branch 1 taken 30 times.
 304 for (std::size_t gap = n / 2; gap > 0; gap /= 2) {
35
2/2
✓ Branch 0 taken 1145540 times.
✓ Branch 1 taken 274 times.
 1145814 for (std::size_t i = gap; i < n; ++i) {
36 1145540 const int tmp = a[i];
37 std::size_t j = i;
38
4/4
✓ Branch 0 taken 2550606 times.
✓ Branch 1 taken 51434 times.
✓ Branch 2 taken 1456500 times.
✓ Branch 3 taken 1094106 times.
 2602040 while (j >= gap && a[j - gap] > tmp) {
39 1456500 a[j] = a[j - gap];
40 j -= gap;
41 }
42 1145540 a[j] = tmp;
43 }
44 }
45 30 }
46
47 struct Elem {
48 int val{};
49 bool pad{false};
50
51 17536 Elem(int value, bool padding) : val(value), pad(padding) {}
52 };
53
54 inline bool Greater(const Elem &lhs, const Elem &rhs) {
55
2/2
✓ Branch 0 taken 31152 times.
✓ Branch 1 taken 858960 times.
 890112 if (lhs.pad != rhs.pad) {
56
3/4
✓ Branch 0 taken 16628 times.
✓ Branch 1 taken 14524 times.
✓ Branch 2 taken 16628 times.
✗ Branch 3 not taken.
 31152 return lhs.pad && !rhs.pad;
57 }
58 858960 return lhs.val > rhs.val;
59 }
60
61
2/2
✓ Branch 0 taken 31152 times.
✓ Branch 1 taken 858960 times.
 890112 inline void CompareExchange(std::vector<Elem> *arr, std::size_t i, std::size_t j) {
62
2/2
✓ Branch 0 taken 266528 times.
✓ Branch 1 taken 592432 times.
 858960 if (Greater((*arr)[i], (*arr)[j])) {
63 std::swap((*arr)[i], (*arr)[j]);
64 }
65 890112 }
66
67 inline std::size_t NextPow2(std::size_t x) {
68 std::size_t p = 1;
69
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 3 times.
 31 while (p < x) {
70 28 p <<= 1U;
71 }
72 return p;
73 }
74
75 188 inline void OddEvenMergeStep(std::vector<Elem> *arr, std::size_t k, std::size_t j) {
76 const std::size_t n = arr->size();
77
2/2
✓ Branch 0 taken 1780224 times.
✓ Branch 1 taken 188 times.
 1780412 for (std::size_t i = 0; i < n; ++i) {
78 1780224 const std::size_t ixj = i ^ j;
79
2/2
✓ Branch 0 taken 890112 times.
✓ Branch 1 taken 890112 times.
 1780224 if (ixj > i) {
80
2/2
✓ Branch 0 taken 505184 times.
✓ Branch 1 taken 384928 times.
 890112 if ((i & k) == 0) {
81 505184 CompareExchange(arr, i, ixj);
82 } else {
83 384928 CompareExchange(arr, ixj, i);
84 }
85 }
86 }
87 188 }
88
89
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
 3 inline void OddEvenMergeNetwork(std::vector<Elem> *arr) {
90 const std::size_t n = arr->size();
91
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
 3 if (n <= 1) {
92 return;
93 }
94
95
2/2
✓ Branch 0 taken 31 times.
✓ Branch 1 taken 3 times.
 34 for (std::size_t k = 2; k <= n; k <<= 1U) {
96
2/2
✓ Branch 0 taken 188 times.
✓ Branch 1 taken 31 times.
 219 for (std::size_t j = (k >> 1U); j > 0; j >>= 1U) {
97 188 OddEvenMergeStep(arr, k, j);
98 }
99 }
100 }
101
102
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
 3 inline std::vector<int> BatcherOddEvenMerge(const std::vector<int> &a, const std::vector<int> &b) {
103 3 const std::size_t need = a.size() + b.size();
104
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
 3 const std::size_t half = NextPow2((a.size() > b.size()) ? a.size() : b.size());
105
106 3 std::vector<Elem> buffer;
107
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 buffer.reserve(2 * half);
108
109
2/2
✓ Branch 0 taken 8768 times.
✓ Branch 1 taken 3 times.
 8771 for (std::size_t i = 0; i < half; ++i) {
110
2/2
✓ Branch 0 taken 5550 times.
✓ Branch 1 taken 3218 times.
 8768 if (i < a.size()) {
111
1/2
✓ Branch 1 taken 5550 times.
✗ Branch 2 not taken.
 5550 buffer.emplace_back(a[i], false);
112 } else {
113
1/2
✓ Branch 1 taken 3218 times.
✗ Branch 2 not taken.
 3218 buffer.emplace_back(0, true);
114 }
115 }
116
2/2
✓ Branch 0 taken 8768 times.
✓ Branch 1 taken 3 times.
 8771 for (std::size_t i = 0; i < half; ++i) {
117
2/2
✓ Branch 0 taken 5550 times.
✓ Branch 1 taken 3218 times.
 8768 if (i < b.size()) {
118
1/2
✓ Branch 1 taken 5550 times.
✗ Branch 2 not taken.
 5550 buffer.emplace_back(b[i], false);
119 } else {
120
1/4
✓ Branch 1 taken 3218 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 3218 buffer.emplace_back(0, true);
121 }
122 }
123
124 3 OddEvenMergeNetwork(&buffer);
125
126 3 std::vector<int> out;
127
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 out.reserve(need);
128
1/2
✓ Branch 0 taken 11100 times.
✗ Branch 1 not taken.
 11100 for (const auto &elem : buffer) {
129
1/2
✓ Branch 0 taken 11100 times.
✗ Branch 1 not taken.
 11100 if (!elem.pad) {
130
1/2
✓ Branch 0 taken 11100 times.
✗ Branch 1 not taken.
 11100 out.push_back(elem.val);
131 }
132
2/2
✓ Branch 0 taken 11097 times.
✓ Branch 1 taken 3 times.
 11100 if (out.size() == need) {
133 break;
134 }
135 }
136 3 return out;
137 }
138
139 } // namespace ovsyannikov_n_shell_batcher
140