GCC Code Coverage Report

Directory: ./
File: tasks/frolova_s_radix_sort_double/stl/src/ops_stl.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 61 62 98.4%
Functions: 9 9 100.0%
Branches: 39 62 62.9%
Line Branch Exec Source
1 #include "frolova_s_radix_sort_double/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <array>
5 #include <atomic>
6 #include <bit>
7 #include <cstddef>
8 #include <cstdint>
9 #include <thread>
10 #include <utility>
11 #include <vector>
12
13 #include "frolova_s_radix_sort_double/common/include/common.hpp"
14
15 namespace frolova_s_radix_sort_double {
16
17 namespace {
18
19 constexpr int kRadix = 256;
20 constexpr int kNumBits = 8;
21 constexpr int kNumPasses = sizeof(std::uint64_t);
22
23 640 std::array<int, kRadix> ComputeHistogram(const std::vector<double> &data, int pass, unsigned int num_threads) {
24 640 std::array<std::atomic<int>, kRadix> count{};
25 640 const std::size_t n = data.size();
26 640 std::vector<std::thread> threads;
27 640 std::size_t chunk_size = (n + num_threads - 1) / num_threads;
28
29
2/2
✓ Branch 0 taken 2560 times.
✓ Branch 1 taken 640 times.
 3200 for (unsigned int tid = 0; tid < num_threads; ++tid) {
30 2560 std::size_t start = tid * chunk_size;
31
1/2
✓ Branch 0 taken 2560 times.
✗ Branch 1 not taken.
 2560 if (start >= n) {
32 break;
33 }
34
1/2
✓ Branch 1 taken 2560 times.
✗ Branch 2 not taken.
 2560 std::size_t end = std::min(start + chunk_size, n);
35
1/2
✓ Branch 1 taken 2560 times.
✗ Branch 2 not taken.
 2560 threads.emplace_back([&, start, end]() {
36
2/2
✓ Branch 0 taken 266240 times.
✓ Branch 1 taken 2560 times.
 268800 for (std::size_t i = start; i < end; ++i) {
37 266240 auto bits = std::bit_cast<std::uint64_t>(data[i]);
38 266240 int byte = static_cast<int>((bits >> (pass * kNumBits)) & 0xFF);
39 266240 count.at(byte).fetch_add(1, std::memory_order_relaxed);
40 }
41 2560 });
42 }
43
2/2
✓ Branch 0 taken 2560 times.
✓ Branch 1 taken 640 times.
 3200 for (auto &t : threads) {
44
1/2
✓ Branch 1 taken 2560 times.
✗ Branch 2 not taken.
 2560 t.join();
45 }
46
47 640 std::array<int, kRadix> result{};
48
2/2
✓ Branch 0 taken 163840 times.
✓ Branch 1 taken 640 times.
 164480 for (int i = 0; i < kRadix; ++i) {
49 163840 result.at(i) = count.at(i).load();
50 }
51 640 return result;
52 640 }
53
54 std::array<int, kRadix> BuildOffsets(const std::array<int, kRadix> &histogram) {
55 640 std::array<int, kRadix> offsets{};
56 int total = 0;
57
2/2
✓ Branch 0 taken 163840 times.
✓ Branch 1 taken 640 times.
 164480 for (int i = 0; i < kRadix; ++i) {
58 163840 offsets.at(i) = total;
59 163840 total += histogram.at(i);
60 }
61 return offsets;
62 }
63
64 640 void Distribute(const std::vector<double> &src, std::vector<double> &dst, std::array<int, kRadix> &offsets, int pass) {
65
3/4
✗ Branch 0 not taken.
✓ Branch 1 taken 266240 times.
✓ Branch 2 taken 266240 times.
✓ Branch 3 taken 640 times.
 266880 for (double val : src) {
66 auto bits = std::bit_cast<std::uint64_t>(val);
67 266240 int byte = static_cast<int>((bits >> (pass * kNumBits)) & 0xFF);
68
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 266240 times.
 266240 dst.at(offsets.at(byte)++) = val;
69 }
70 640 }
71
72 80 void FixNegativeOrder(std::vector<double> &data) {
73 80 std::vector<double> negative;
74
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 std::vector<double> positive;
75
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 negative.reserve(data.size());
76
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 positive.reserve(data.size());
77
78
2/2
✓ Branch 0 taken 33280 times.
✓ Branch 1 taken 80 times.
 33360 for (double val : data) {
79
2/2
✓ Branch 0 taken 7928 times.
✓ Branch 1 taken 25352 times.
 33280 if (val < 0.0) {
80 negative.push_back(val);
81 } else {
82 positive.push_back(val);
83 }
84 }
85 std::ranges::reverse(negative);
86
87 data.clear();
88
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 data.insert(data.end(), negative.begin(), negative.end());
89
1/2
✓ Branch 0 taken 80 times.
✗ Branch 1 not taken.
 80 data.insert(data.end(), positive.begin(), positive.end());
90 80 } // для тестов
91
92 } // namespace
93
94
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 FrolovaSRadixSortDoubleSTL::FrolovaSRadixSortDoubleSTL(const InType &in) {
95 SetTypeOfTask(GetStaticTypeOfTask());
96
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 GetInput() = in;
97 80 }
98
99 80 bool FrolovaSRadixSortDoubleSTL::ValidationImpl() {
100 80 return !GetInput().empty();
101 }
102
103 80 bool FrolovaSRadixSortDoubleSTL::PreProcessingImpl() {
104 80 return true;
105 }
106
107
1/2
✓ Branch 0 taken 80 times.
✗ Branch 1 not taken.
 80 bool FrolovaSRadixSortDoubleSTL::RunImpl() {
108 const std::vector<double> &input = GetInput();
109
1/2
✓ Branch 0 taken 80 times.
✗ Branch 1 not taken.
 80 if (input.empty()) {
110 return false;
111 }
112
113 80 std::vector<double> working = input;
114 const std::size_t n = working.size();
115
116 80 unsigned int num_threads = std::thread::hardware_concurrency();
117
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 80 times.
 80 if (num_threads == 0) {
118 num_threads = 2;
119 }
120
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 80 times.
 80 if (num_threads > n) {
121 ✗ num_threads = static_cast<unsigned int>(n);
122 }
123
124
1/4
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 80 std::vector<double> temp(n);
125
126
2/2
✓ Branch 0 taken 640 times.
✓ Branch 1 taken 80 times.
 720 for (int pass = 0; pass < kNumPasses; ++pass) {
127
1/2
✓ Branch 1 taken 640 times.
✗ Branch 2 not taken.
 640 auto histogram = ComputeHistogram(working, pass, num_threads);
128 auto offsets = BuildOffsets(histogram);
129
1/2
✓ Branch 1 taken 640 times.
✗ Branch 2 not taken.
 640 Distribute(working, temp, offsets, pass);
130 working.swap(temp);
131 }
132
133
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 FixNegativeOrder(working);
134
135 GetOutput() = std::move(working);
136 return true;
137 }
138
139 80 bool FrolovaSRadixSortDoubleSTL::PostProcessingImpl() {
140 80 return true;
141 }
142
143 } // namespace frolova_s_radix_sort_double
144