GCC Code Coverage Report

Directory: ./
File: tasks/egashin_k_radix_simple_merge/common/include/radix_utils.hpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 51 52 98.1%
Functions: 5 5 100.0%
Branches: 42 54 77.8%
Line Branch Exec Source
1 #pragma once
2
3 #include <algorithm>
4 #include <array>
5 #include <cstddef>
6 #include <cstdint>
7 #include <cstring>
8 #include <utility>
9 #include <vector>
10
11 namespace egashin_k_radix_simple_merge::radix_utils {
12
13 namespace detail {
14
15 constexpr uint64_t kSignBit = 0x8000000000000000ULL;
16
17 inline uint64_t ToSortable(double value) {
18 uint64_t bits = 0;
19 std::memcpy(&bits, &value, sizeof(value));
20
2/2
✓ Branch 0 taken 82 times.
✓ Branch 1 taken 156 times.
 238 return ((bits & kSignBit) != 0U) ? ~bits : (bits ^ kSignBit);
21 }
22
23 inline double FromSortable(uint64_t key) {
24 238 const uint64_t bits = ((key & kSignBit) != 0U) ? (key ^ kSignBit) : ~key;
25 double value = 0.0;
26 std::memcpy(&value, &bits, sizeof(value));
27 return value;
28 }
29
30 688 inline void CountingPass(const std::vector<uint64_t> &source, std::vector<uint64_t> &destination, int byte_index) {
31 688 std::array<size_t, 256> count{};
32
33
2/2
✓ Branch 0 taken 1904 times.
✓ Branch 1 taken 688 times.
 2592 for (uint64_t value : source) {
34 1904 const auto byte = static_cast<uint8_t>((value >> (byte_index * 8)) & 0xFFU);
35 1904 count.at(byte)++;
36 }
37
38 688 std::array<size_t, 256> position{};
39
2/2
✓ Branch 0 taken 175440 times.
✓ Branch 1 taken 688 times.
 176128 for (size_t i = 1; i < count.size(); ++i) {
40 175440 position.at(i) = position.at(i - 1) + count.at(i - 1);
41 }
42
43
2/2
✓ Branch 0 taken 1904 times.
✓ Branch 1 taken 688 times.
 2592 for (uint64_t value : source) {
44 1904 const auto byte = static_cast<uint8_t>((value >> (byte_index * 8)) & 0xFFU);
45 1904 destination[position.at(byte)++] = value;
46 }
47 688 }
48
49 } // namespace detail
50
51 inline int WorkerCount(size_t size, int requested) {
52
2/4
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 60 times.
✗ Branch 3 not taken.
 108 if (size == 0) {
53 return 1;
54 }
55 108 return std::min(std::max(requested, 1), static_cast<int>(size));
56 }
57
58 108 inline std::vector<std::pair<size_t, size_t>> MakeRanges(size_t size, int workers) {
59 108 std::vector<std::pair<size_t, size_t>> ranges(static_cast<size_t>(workers));
60 const auto worker_count = static_cast<size_t>(workers);
61 108 const size_t base = size / worker_count;
62 108 const size_t extra = size % worker_count;
63
64 size_t begin = 0;
65
2/2
✓ Branch 0 taken 192 times.
✓ Branch 1 taken 108 times.
 300 for (size_t i = 0; i < worker_count; ++i) {
66
2/2
✓ Branch 0 taken 150 times.
✓ Branch 1 taken 42 times.
 192 const size_t block = base + (i < extra ? 1 : 0);
67 192 ranges[i] = {begin, begin + block};
68 begin += block;
69 }
70
71 108 return ranges;
72 }
73
74 120 inline void SortRange(std::vector<double> &data, size_t left, size_t right) {
75
2/2
✓ Branch 0 taken 34 times.
✓ Branch 1 taken 86 times.
 120 if (right - left < 2) {
76 34 return;
77 }
78
79 const size_t size = right - left;
80 86 std::vector<uint64_t> keys(size);
81
1/4
✓ Branch 1 taken 86 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 86 std::vector<uint64_t> buffer(size);
82
83
2/2
✓ Branch 0 taken 238 times.
✓ Branch 1 taken 86 times.
 324 for (size_t i = 0; i < size; ++i) {
84
2/2
✓ Branch 0 taken 82 times.
✓ Branch 1 taken 156 times.
 476 keys[i] = detail::ToSortable(data[left + i]);
85 }
86
87 auto *source = &keys;
88 auto *destination = &buffer;
89
2/2
✓ Branch 0 taken 688 times.
✓ Branch 1 taken 86 times.
 774 for (int byte_index = 0; byte_index < 8; ++byte_index) {
90 688 detail::CountingPass(*source, *destination, byte_index);
91 std::swap(source, destination);
92 }
93
94
2/2
✓ Branch 0 taken 238 times.
✓ Branch 1 taken 86 times.
 324 for (size_t i = 0; i < size; ++i) {
95
2/2
✓ Branch 0 taken 156 times.
✓ Branch 1 taken 82 times.
 476 data[left + i] = detail::FromSortable((*source)[i]);
96 }
97 }
98
99 72 inline std::vector<double> Merge(const std::vector<double> &left, const std::vector<double> &right) {
100
1/2
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
 72 std::vector<double> result;
101
1/2
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
 72 result.reserve(left.size() + right.size());
102
103 size_t i = 0;
104 size_t j = 0;
105
4/4
✓ Branch 0 taken 250 times.
✓ Branch 1 taken 36 times.
✓ Branch 2 taken 214 times.
✓ Branch 3 taken 36 times.
 286 while (i < left.size() && j < right.size()) {
106
2/2
✓ Branch 0 taken 134 times.
✓ Branch 1 taken 80 times.
 214 if (left[i] <= right[j]) {
107
1/2
✓ Branch 0 taken 134 times.
✗ Branch 1 not taken.
 134 result.push_back(left[i++]);
108 } else {
109
1/2
✓ Branch 0 taken 80 times.
✗ Branch 1 not taken.
 80 result.push_back(right[j++]);
110 }
111 }
112
113
1/2
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
 72 result.insert(result.end(), left.begin() + static_cast<std::ptrdiff_t>(i), left.end());
114 72 result.insert(result.end(), right.begin() + static_cast<std::ptrdiff_t>(j), right.end());
115 72 return result;
116 }
117
118 48 inline std::vector<std::vector<double>> MakeParts(const std::vector<double> &data,
119 const std::vector<std::pair<size_t, size_t>> &ranges) {
120 48 std::vector<std::vector<double>> parts(ranges.size());
121
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 48 times.
 168 for (size_t i = 0; i < ranges.size(); ++i) {
122
1/2
✓ Branch 1 taken 120 times.
✗ Branch 2 not taken.
 120 parts[i] = std::vector<double>(data.begin() + static_cast<std::ptrdiff_t>(ranges[i].first),
123
1/2
✓ Branch 1 taken 120 times.
✗ Branch 2 not taken.
 240 data.begin() + static_cast<std::ptrdiff_t>(ranges[i].second));
124 }
125 48 return parts;
126 ✗ }
127
128 } // namespace egashin_k_radix_simple_merge::radix_utils
129