| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #include "../include/radix_sort.hpp" | ||
| 2 | |||
| 3 | #include <array> | ||
| 4 | #include <cstdint> | ||
| 5 | #include <cstring> | ||
| 6 | #include <vector> | ||
| 7 | |||
| 8 | namespace { | ||
| 9 | constexpr int kBytes = 8; | ||
| 10 | constexpr std::size_t kRadix = 256; | ||
| 11 | constexpr std::uint64_t kSignMask = 1ULL << 63; | ||
| 12 | constexpr std::uint64_t kByteMask = 0xFFULL; | ||
| 13 | uint64_t ToSortable(uint64_t bits, const uint64_t sign_mask) { | ||
| 14 |
2/2✓ Branch 0 taken 56 times.
✓ Branch 1 taken 88 times.
|
144 | return ((bits & sign_mask) != 0U) ? ~bits : (bits ^ sign_mask); |
| 15 | } | ||
| 16 | |||
| 17 | uint64_t FromSortable(uint64_t bits, const uint64_t sign_mask) { | ||
| 18 | 144 | return ((bits & sign_mask) != 0U) ? (bits ^ sign_mask) : ~bits; | |
| 19 | } | ||
| 20 | } // namespace | ||
| 21 | |||
| 22 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
|
24 | void RadixSort::Sort(std::vector<double> &arr) { |
| 23 | const size_t n = arr.size(); | ||
| 24 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
|
24 | if (n == 0) { |
| 25 | ✗ | return; | |
| 26 | } | ||
| 27 | |||
| 28 | 24 | std::vector<uint64_t> data(n); | |
| 29 | |||
| 30 |
2/2✓ Branch 0 taken 144 times.
✓ Branch 1 taken 24 times.
|
168 | for (size_t i = 0; i < n; ++i) { |
| 31 | uint64_t bits = 0; | ||
| 32 | std::memcpy(&bits, &arr[i], sizeof(double)); | ||
| 33 | |||
| 34 | bits = ToSortable(bits, kSignMask); | ||
| 35 | |||
| 36 | 144 | data[i] = bits; | |
| 37 | } | ||
| 38 | |||
| 39 |
1/4✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
|
24 | std::vector<uint64_t> buffer(n); |
| 40 | |||
| 41 |
2/2✓ Branch 0 taken 192 times.
✓ Branch 1 taken 24 times.
|
216 | for (int byte = 0; byte < kBytes; ++byte) { |
| 42 | 192 | std::array<size_t, kRadix> count{}; | |
| 43 | |||
| 44 |
2/2✓ Branch 0 taken 1152 times.
✓ Branch 1 taken 192 times.
|
1344 | for (size_t i = 0; i < n; ++i) { |
| 45 | 1152 | const auto b = static_cast<size_t>((data[i] >> (byte * 8)) & kByteMask); | |
| 46 | 1152 | count.at(b)++; | |
| 47 | } | ||
| 48 | |||
| 49 | size_t sum = 0; | ||
| 50 |
2/2✓ Branch 0 taken 49152 times.
✓ Branch 1 taken 192 times.
|
49344 | for (auto &c : count) { |
| 51 | 49152 | size_t tmp = c; | |
| 52 | 49152 | c = sum; | |
| 53 | 49152 | sum += tmp; | |
| 54 | } | ||
| 55 | |||
| 56 |
2/2✓ Branch 0 taken 1152 times.
✓ Branch 1 taken 192 times.
|
1344 | for (size_t i = 0; i < n; ++i) { |
| 57 | 1152 | const auto b = static_cast<size_t>((data[i] >> (byte * 8)) & kByteMask); | |
| 58 | 1152 | buffer[count.at(b)++] = data[i]; | |
| 59 | } | ||
| 60 | |||
| 61 | data.swap(buffer); | ||
| 62 | } | ||
| 63 | |||
| 64 |
2/2✓ Branch 0 taken 144 times.
✓ Branch 1 taken 24 times.
|
168 | for (size_t i = 0; i < n; ++i) { |
| 65 |
2/2✓ Branch 0 taken 88 times.
✓ Branch 1 taken 56 times.
|
144 | uint64_t bits = data[i]; |
| 66 | |||
| 67 | 144 | bits = FromSortable(bits, kSignMask); | |
| 68 | |||
| 69 | std::memcpy(&arr[i], &bits, sizeof(double)); | ||
| 70 | } | ||
| 71 | } | ||
| 72 |