GCC Code Coverage Report

Directory: ./
File: tasks/golovanov_d_radix_merge/omp/src/radix_sort_omp.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 62 65 95.4%
Functions: 3 3 100.0%
Branches: 53 70 75.7%
Line Branch Exec Source
1 #include "../include/radix_sort_omp.hpp"
2
3 #include <omp.h>
4
5 #include <array>
6 #include <cstddef>
7 #include <cstdint>
8 #include <cstring>
9 #include <utility>
10 #include <vector>
11
12 #include "util/include/util.hpp"
13
14 namespace {
15 constexpr int kBytes = 8;
16 constexpr std::size_t kRadix = 256;
17 constexpr std::uint64_t kSignMask = 1ULL << 63;
18 constexpr std::uint64_t kByteMask = 0xFFULL;
19
20 std::uint64_t ToSortable(std::uint64_t bits) {
21
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 44 times.
 72 return ((bits & kSignMask) != 0U) ? ~bits : (bits ^ kSignMask);
22 }
23
24 std::uint64_t FromSortable(std::uint64_t bits) {
25 72 return ((bits & kSignMask) != 0U) ? (bits ^ kSignMask) : ~bits;
26 }
27 } // namespace
28
29 30 void RadixSortOMP::SortRange(std::vector<double> &arr, std::size_t left, std::size_t right) {
30
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 30 times.
 30 if (right <= left) {
31 ✗ return;
32 }
33
34 30 std::size_t n = right - left;
35 30 std::vector<std::uint64_t> data(n);
36
37
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 30 times.
 102 for (std::size_t i = 0; i < n; ++i) {
38 std::uint64_t bits = 0;
39
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 44 times.
 72 std::memcpy(&bits, &arr[left + i], sizeof(double));
40 72 data[i] = ToSortable(bits);
41 }
42
43
1/4
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 30 std::vector<std::uint64_t> buffer(n);
44
45
2/2
✓ Branch 0 taken 240 times.
✓ Branch 1 taken 30 times.
 270 for (int byte = 0; byte < kBytes; ++byte) {
46 240 std::array<std::size_t, kRadix> count{};
47
48
2/2
✓ Branch 0 taken 576 times.
✓ Branch 1 taken 240 times.
 816 for (std::size_t i = 0; i < n; ++i) {
49 576 auto b = static_cast<std::size_t>((data[i] >> (byte * 8)) & kByteMask);
50 576 ++count.at(b);
51 }
52
53 std::size_t sum = 0;
54
2/2
✓ Branch 0 taken 61440 times.
✓ Branch 1 taken 240 times.
 61680 for (std::size_t i = 0; i < kRadix; ++i) {
55 61440 std::size_t tmp = count.at(i);
56 61440 count.at(i) = sum;
57 61440 sum += tmp;
58 }
59
60
2/2
✓ Branch 0 taken 576 times.
✓ Branch 1 taken 240 times.
 816 for (std::size_t i = 0; i < n; ++i) {
61 576 auto b = static_cast<std::size_t>((data[i] >> (byte * 8)) & kByteMask);
62 576 buffer[count.at(b)++] = data[i];
63 }
64
65 data.swap(buffer);
66 }
67
68
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 30 times.
 102 for (std::size_t i = 0; i < n; ++i) {
69
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 28 times.
 72 std::uint64_t bits = FromSortable(data[i]);
70 72 std::memcpy(&arr[left + i], &bits, sizeof(double));
71 }
72 }
73
74 18 std::vector<double> RadixSortOMP::Merge(const std::vector<double> &a, const std::vector<double> &b) {
75
1/2
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
 18 std::vector<double> result;
76
1/2
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
 18 result.reserve(a.size() + b.size());
77
78 std::size_t i = 0;
79 std::size_t j = 0;
80
81
4/4
✓ Branch 0 taken 67 times.
✓ Branch 1 taken 9 times.
✓ Branch 2 taken 9 times.
✓ Branch 3 taken 58 times.
 76 while (i < a.size() && j < b.size()) {
82
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 22 times.
 58 if (a[i] <= b[j]) {
83 result.push_back(a[i]);
84 36 ++i;
85 } else {
86 result.push_back(b[j]);
87 22 ++j;
88 }
89 }
90
91
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 18 times.
 33 while (i < a.size()) {
92 result.push_back(a[i]);
93 15 ++i;
94 }
95
96
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 18 times.
 30 while (j < b.size()) {
97 result.push_back(b[j]);
98 12 ++j;
99 }
100
101 18 return result;
102 }
103
104
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 void RadixSortOMP::Sort(std::vector<double> &arr) {
105
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 if (arr.empty()) {
106 ✗ return;
107 }
108
109 12 int num_threads = ppc::util::GetNumThreads();
110 12 if (num_threads <= 0) {
111 num_threads = 1;
112 }
113
114
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 if (static_cast<std::size_t>(num_threads) > arr.size()) {
115 ✗ num_threads = static_cast<int>(arr.size());
116 }
117
118 12 std::vector<std::pair<std::size_t, std::size_t>> ranges(num_threads);
119
120 12 std::size_t base = arr.size() / static_cast<std::size_t>(num_threads);
121 12 std::size_t rem = arr.size() % static_cast<std::size_t>(num_threads);
122
123 std::size_t begin = 0;
124
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 12 times.
 42 for (std::size_t i = 0; i < ranges.size(); ++i) {
125
2/2
✓ Branch 0 taken 19 times.
✓ Branch 1 taken 11 times.
 30 std::size_t block_size = base + (i < rem ? 1 : 0);
126 30 ranges[i] = {begin, begin + block_size};
127 begin += block_size;
128 }
129
130
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 #pragma omp parallel default(none) shared(arr, ranges, num_threads) num_threads(ppc::util::GetNumThreads())
131 {
132 #pragma omp for schedule(static)
133 for (int i = 0; i < num_threads; ++i) {
134 SortRange(arr, ranges[i].first, ranges[i].second);
135 }
136 }
137
138
1/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 12 std::vector<std::vector<double>> parts(num_threads);
139
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 12 times.
 42 for (int i = 0; i < num_threads; ++i) {
140
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 parts[i] = std::vector<double>(arr.begin() + static_cast<std::ptrdiff_t>(ranges[i].first),
141
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 60 arr.begin() + static_cast<std::ptrdiff_t>(ranges[i].second));
142 }
143
144
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 12 times.
 27 while (parts.size() > 1) {
145 15 std::size_t pair_count = parts.size() / 2;
146 15 const int pair_count_int = static_cast<int>(pair_count);
147
1/2
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
 15 std::vector<std::vector<double>> next((parts.size() + 1) / 2);
148
149
3/4
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 3 times.
✓ Branch 4 taken 12 times.
 15 #pragma omp parallel default(none) shared(parts, next, pair_count_int) num_threads(ppc::util::GetNumThreads())
150 {
151 #pragma omp for schedule(static)
152 for (int i = 0; i < pair_count_int; ++i) {
153 const auto idx = static_cast<std::size_t>(i);
154 next[idx] = Merge(parts[2 * idx], parts[(2 * idx) + 1]);
155 }
156 }
157
158
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 12 times.
 15 if (parts.size() % 2 != 0) {
159 next.back() = std::move(parts.back());
160 }
161
162 15 parts = std::move(next);
163 15 }
164
165 arr = std::move(parts[0]);
166 12 }
167