GCC Code Coverage Report

Directory: ./
File: tasks/golovanov_d_radix_merge/stl/src/radix_sort_stl.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 88 91 96.7%
Functions: 8 8 100.0%
Branches: 67 90 74.4%
Line Branch Exec Source
1 #include "../include/radix_sort_stl.hpp"
2
3 #include <algorithm>
4 #include <array>
5 #include <cstddef>
6 #include <cstdint>
7 #include <cstring>
8 #include <thread>
9 #include <utility>
10 #include <vector>
11
12 #include "util/include/util.hpp"
13
14 namespace golovanov_d_radix_merge {
15
16 namespace {
17 constexpr int kBytes = 8;
18 constexpr std::size_t kRadix = 256;
19 constexpr std::uint64_t kSignMask = 1ULL << 63;
20 constexpr std::uint64_t kByteMask = 0xFFULL;
21
22 std::uint64_t ToSortable(std::uint64_t bits) {
23
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 88 times.
 144 return ((bits & kSignMask) != 0U) ? ~bits : (bits ^ kSignMask);
24 }
25
26 std::uint64_t FromSortable(std::uint64_t bits) {
27 144 return ((bits & kSignMask) != 0U) ? (bits ^ kSignMask) : ~bits;
28 }
29
30 int GetThreadCount(std::size_t size) {
31
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 if (size == 0) {
32 return 1;
33 }
34
35 24 int num_threads = ppc::util::GetNumThreads();
36 24 if (num_threads <= 0) {
37 num_threads = 1;
38 }
39
40 24 const auto max_threads = static_cast<int>(size);
41 return std::min(num_threads, max_threads);
42 }
43
44 24 std::vector<std::pair<std::size_t, std::size_t>> BuildRanges(std::size_t size, int num_threads) {
45 24 if (num_threads <= 0) {
46 num_threads = 1;
47 }
48
49 24 const auto threads_count = static_cast<std::size_t>(num_threads);
50 24 std::vector<std::pair<std::size_t, std::size_t>> ranges(threads_count);
51
52 24 const std::size_t base = size / threads_count;
53 24 const std::size_t rem = size % threads_count;
54
55 std::size_t begin = 0;
56
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 24 times.
 84 for (std::size_t i = 0; i < ranges.size(); ++i) {
57
2/2
✓ Branch 0 taken 38 times.
✓ Branch 1 taken 22 times.
 60 const std::size_t block_size = base + ((i < rem) ? 1U : 0U);
58 60 ranges[i] = {begin, begin + block_size};
59 begin += block_size;
60 }
61
62 24 return ranges;
63 }
64
65 24 void SortParts(std::vector<double> &arr, const std::vector<std::pair<std::size_t, std::size_t>> &ranges) {
66
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 std::vector<std::thread> workers;
67
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 workers.reserve(ranges.size());
68
69
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 24 times.
 84 for (const auto &range : ranges) {
70
2/4
✓ Branch 2 taken 60 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 60 times.
✗ Branch 6 not taken.
 180 workers.emplace_back([&arr, range]() { RadixSortSTL::SortRange(arr, range.first, range.second); });
71 }
72
73
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 24 times.
 84 for (auto &worker : workers) {
74
1/2
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
 60 worker.join();
75 }
76 24 }
77
78 24 std::vector<std::vector<double>> CopyParts(const std::vector<double> &arr,
79 const std::vector<std::pair<std::size_t, std::size_t>> &ranges) {
80 24 std::vector<std::vector<double>> parts(ranges.size());
81
82
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 24 times.
 84 for (std::size_t i = 0; i < ranges.size(); ++i) {
83
1/2
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
 60 parts[i] = std::vector<double>(arr.begin() + static_cast<std::ptrdiff_t>(ranges[i].first),
84
1/2
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
 120 arr.begin() + static_cast<std::ptrdiff_t>(ranges[i].second));
85 }
86
87 24 return parts;
88 ✗ }
89
90 30 std::vector<std::vector<double>> MergeStep(const std::vector<std::vector<double>> &parts) {
91 30 const std::size_t pair_count = parts.size() / 2;
92 30 std::vector<std::vector<double>> next((parts.size() + 1) / 2);
93 30 std::vector<std::thread> workers;
94
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 workers.reserve(pair_count);
95
96
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 30 times.
 66 for (std::size_t i = 0; i < pair_count; ++i) {
97
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 72 workers.emplace_back([&parts, &next, i]() { next[i] = RadixSortSTL::Merge(parts[2 * i], parts[(2 * i) + 1]); });
98 }
99
100
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 30 times.
 66 for (auto &worker : workers) {
101
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 36 worker.join();
102 }
103
104
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 24 times.
 30 if ((parts.size() % 2U) != 0U) {
105
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 next.back() = parts.back();
106 }
107
108 30 return next;
109 30 }
110
111 } // namespace
112
113 60 void RadixSortSTL::SortRange(std::vector<double> &arr, std::size_t left, std::size_t right) {
114
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 60 times.
 60 if (right <= left) {
115 ✗ return;
116 }
117
118 60 const std::size_t n = right - left;
119 60 std::vector<std::uint64_t> data(n);
120
121
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 60 times.
 204 for (std::size_t i = 0; i < n; ++i) {
122 std::uint64_t bits = 0;
123
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 88 times.
 144 std::memcpy(&bits, &arr[left + i], sizeof(double));
124 144 data[i] = ToSortable(bits);
125 }
126
127
1/4
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 60 std::vector<std::uint64_t> buffer(n);
128
129
2/2
✓ Branch 0 taken 480 times.
✓ Branch 1 taken 60 times.
 540 for (int byte = 0; byte < kBytes; ++byte) {
130 480 std::array<std::size_t, kRadix> count{};
131
132
2/2
✓ Branch 0 taken 1152 times.
✓ Branch 1 taken 480 times.
 1632 for (std::size_t i = 0; i < n; ++i) {
133 1152 const auto bucket = static_cast<std::size_t>((data[i] >> (byte * 8)) & kByteMask);
134 1152 ++count.at(bucket);
135 }
136
137 std::size_t sum = 0;
138
2/2
✓ Branch 0 taken 122880 times.
✓ Branch 1 taken 480 times.
 123360 for (std::size_t i = 0; i < kRadix; ++i) {
139 122880 const std::size_t tmp = count.at(i);
140 122880 count.at(i) = sum;
141 122880 sum += tmp;
142 }
143
144
2/2
✓ Branch 0 taken 1152 times.
✓ Branch 1 taken 480 times.
 1632 for (std::size_t i = 0; i < n; ++i) {
145 1152 const auto bucket = static_cast<std::size_t>((data[i] >> (byte * 8)) & kByteMask);
146 1152 const std::size_t pos = count.at(bucket);
147 1152 buffer[pos] = data[i];
148 1152 ++count.at(bucket);
149 }
150
151 data.swap(buffer);
152 }
153
154
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 60 times.
 204 for (std::size_t i = 0; i < n; ++i) {
155
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 56 times.
 144 const std::uint64_t bits = FromSortable(data[i]);
156 144 std::memcpy(&arr[left + i], &bits, sizeof(double));
157 }
158 }
159
160 36 std::vector<double> RadixSortSTL::Merge(const std::vector<double> &a, const std::vector<double> &b) {
161
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 36 std::vector<double> result;
162
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 36 result.reserve(a.size() + b.size());
163
164 std::size_t i = 0;
165 std::size_t j = 0;
166
167
4/4
✓ Branch 0 taken 134 times.
✓ Branch 1 taken 18 times.
✓ Branch 2 taken 18 times.
✓ Branch 3 taken 116 times.
 152 while (i < a.size() && j < b.size()) {
168
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 44 times.
 116 if (a[i] <= b[j]) {
169 result.push_back(a[i]);
170 72 ++i;
171 } else {
172 result.push_back(b[j]);
173 44 ++j;
174 }
175 }
176
177
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 36 times.
 66 while (i < a.size()) {
178 result.push_back(a[i]);
179 30 ++i;
180 }
181
182
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 36 times.
 60 while (j < b.size()) {
183 result.push_back(b[j]);
184 24 ++j;
185 }
186
187 36 return result;
188 }
189
190
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 void RadixSortSTL::Sort(std::vector<double> &arr) {
191
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (arr.empty()) {
192 ✗ return;
193 }
194
195 const int num_threads = GetThreadCount(arr.size());
196 24 const auto ranges = BuildRanges(arr.size(), num_threads);
197
198
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 SortParts(arr, ranges);
199
200
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 std::vector<std::vector<double>> parts = CopyParts(arr, ranges);
201
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 24 times.
 54 while (parts.size() > 1) {
202
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 parts = MergeStep(parts);
203 }
204
205 arr = std::move(parts.front());
206 24 }
207
208 } // namespace golovanov_d_radix_merge
209