GCC Code Coverage Report

Directory: ./
File: tasks/leonova_a_radix_merge_sort/stl/src/ops_stl.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 77 79 97.5%
Functions: 10 11 90.9%
Branches: 50 74 67.6%
Line Branch Exec Source
1 #include "leonova_a_radix_merge_sort/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <cstdint>
6 #include <future>
7 #include <vector>
8
9 #include "leonova_a_radix_merge_sort/common/include/common.hpp"
10 #include "util/include/util.hpp"
11
12 namespace leonova_a_radix_merge_sort {
13
14
1/2
✓ Branch 1 taken 256 times.
✗ Branch 2 not taken.
 256 LeonovaARadixMergeSortSTL::LeonovaARadixMergeSortSTL(const InType &in) {
15 SetTypeOfTask(GetStaticTypeOfTask());
16
1/2
✓ Branch 1 taken 256 times.
✗ Branch 2 not taken.
 256 GetInput() = in;
17
1/2
✓ Branch 1 taken 256 times.
✗ Branch 2 not taken.
 256 GetOutput() = std::vector<int64_t>(GetInput().size());
18 256 }
19
20 512 bool LeonovaARadixMergeSortSTL::ValidationImpl() {
21 512 return !GetInput().empty();
22 }
23
24 256 bool LeonovaARadixMergeSortSTL::PreProcessingImpl() {
25 256 return true;
26 }
27
28 256 bool LeonovaARadixMergeSortSTL::RunImpl() {
29
1/2
✓ Branch 1 taken 256 times.
✗ Branch 2 not taken.
 256 if (!ValidationImpl()) {
30 return false;
31 }
32 256 GetOutput() = GetInput();
33
2/2
✓ Branch 0 taken 240 times.
✓ Branch 1 taken 16 times.
 256 if (GetOutput().size() > 1) {
34 240 RadixMergeSort(GetOutput(), 0, GetOutput().size());
35 }
36 return true;
37 }
38
39 256 bool LeonovaARadixMergeSortSTL::PostProcessingImpl() {
40 256 return true;
41 }
42
43 inline uint64_t LeonovaARadixMergeSortSTL::ToUnsignedValue(int64_t value) {
44 2103850 return static_cast<uint64_t>(value) ^ kSignBitMask;
45 }
46
47 ✗ void LeonovaARadixMergeSortSTL::FillKeys(const std::vector<int64_t> &arr, size_t left, size_t size,
48 std::vector<uint64_t> &keys) {
49
2/4
✓ Branch 0 taken 2103850 times.
✓ Branch 1 taken 490 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 2104340 for (size_t index = 0; index < size; ++index) {
50 2103850 keys[index] = ToUnsignedValue(arr[left + index]);
51 }
52 ✗ }
53
54
1/2
✓ Branch 0 taken 3920 times.
✗ Branch 1 not taken.
 3920 void LeonovaARadixMergeSortSTL::CountBytes(const std::vector<uint64_t> &keys, size_t begin, size_t end, int shift,
55 std::vector<size_t> &counts) {
56 std::ranges::fill(counts, 0);
57
2/2
✓ Branch 0 taken 16830800 times.
✓ Branch 1 taken 3920 times.
 16834720 for (size_t index = begin; index < end; ++index) {
58 16830800 ++counts[(keys[index] >> shift) & 0xFFU];
59 }
60 3920 }
61
62 3920 void LeonovaARadixMergeSortSTL::ScatterBytes(const std::vector<uint64_t> &src_keys, const std::vector<int64_t> &src_arr,
63 size_t left, size_t begin, size_t end, int shift,
64 std::vector<size_t> &offsets, std::vector<int64_t> &dst_arr,
65 std::vector<uint64_t> &dst_keys) {
66
2/2
✓ Branch 0 taken 16830800 times.
✓ Branch 1 taken 3920 times.
 16834720 for (size_t index = begin; index < end; ++index) {
67 16830800 const size_t bucket = (src_keys[index] >> shift) & 0xFFU;
68 16830800 const size_t pos = offsets[bucket]++;
69 16830800 dst_arr[pos] = src_arr[left + index];
70 16830800 dst_keys[pos] = src_keys[index];
71 }
72 3920 }
73
74 588 void LeonovaARadixMergeSortSTL::RadixSort(std::vector<int64_t> &arr, size_t left, size_t right) {
75 588 const size_t size = right - left;
76
2/2
✓ Branch 0 taken 98 times.
✓ Branch 1 taken 490 times.
 588 if (size <= 1) {
77 98 return;
78 }
79
80 490 std::vector<uint64_t> keys(size);
81
1/4
✓ Branch 1 taken 490 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 490 std::vector<int64_t> tmp_arr(size);
82
1/4
✓ Branch 1 taken 490 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 490 std::vector<uint64_t> tmp_keys(size);
83
1/4
✓ Branch 1 taken 490 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 490 std::vector<size_t> counts(kNumCounters);
84
1/4
✓ Branch 1 taken 490 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 490 std::vector<size_t> offsets(kNumCounters);
85
86 FillKeys(arr, left, size, keys);
87
88
2/2
✓ Branch 0 taken 3920 times.
✓ Branch 1 taken 490 times.
 4410 for (int byte_pos = 0; byte_pos < kNumBytes; ++byte_pos) {
89 3920 const int shift = byte_pos * kByteSize;
90
91 3920 CountBytes(keys, 0, size, shift, counts);
92 size_t sum = 0;
93
2/2
✓ Branch 0 taken 1003520 times.
✓ Branch 1 taken 3920 times.
 1007440 for (size_t bndex = 0; bndex < kNumCounters; ++bndex) {
94 1003520 offsets[bndex] = sum;
95 1003520 sum += counts[bndex];
96 }
97
98 3920 ScatterBytes(keys, arr, left, 0, size, shift, offsets, tmp_arr, tmp_keys);
99
100 std::ranges::copy(tmp_arr, arr.begin() + static_cast<std::ptrdiff_t>(left));
101 keys.swap(tmp_keys);
102 }
103 }
104
105 328 void LeonovaARadixMergeSortSTL::SimpleMerge(std::vector<int64_t> &arr, size_t left, size_t mid, size_t right) {
106 328 std::vector<int64_t> merged(right - left);
107
108 size_t i = left;
109 size_t j = mid;
110 size_t k = 0;
111
112
2/2
✓ Branch 0 taken 1139844 times.
✓ Branch 1 taken 328 times.
 1140172 while (i < mid && j < right) {
113
2/2
✓ Branch 0 taken 822 times.
✓ Branch 1 taken 1139022 times.
 1139844 merged[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
114 }
115
2/2
✓ Branch 0 taken 1314256 times.
✓ Branch 1 taken 328 times.
 1314584 while (i < mid) {
116 1314256 merged[k++] = arr[i++];
117 }
118
2/2
✓ Branch 0 taken 488 times.
✓ Branch 1 taken 328 times.
 816 while (j < right) {
119 488 merged[k++] = arr[j++];
120 }
121
122 std::ranges::copy(merged, arr.begin() + static_cast<std::ptrdiff_t>(left));
123 328 }
124
125 240 void LeonovaARadixMergeSortSTL::RadixMergeSort(std::vector<int64_t> &arr, size_t left, size_t right) {
126 240 const size_t size = right - left;
127 240 const auto hw = static_cast<size_t>(std::max(1, ppc::util::GetNumThreads()));
128 const size_t num_threads = std::min(hw, size);
129 240 std::vector<size_t> boundaries(num_threads + 1);
130 240 const size_t chunk = (size + num_threads - 1) / num_threads;
131
2/2
✓ Branch 0 taken 828 times.
✓ Branch 1 taken 240 times.
 1068 for (size_t tndex = 0; tndex <= num_threads; ++tndex) {
132 828 boundaries[tndex] = left + std::min(tndex * chunk, size);
133 }
134
135 240 std::vector<std::future<void>> futures;
136
1/2
✓ Branch 1 taken 240 times.
✗ Branch 2 not taken.
 240 futures.reserve(num_threads);
137
138
2/2
✓ Branch 0 taken 588 times.
✓ Branch 1 taken 240 times.
 828 for (size_t tndex = 0; tndex < num_threads; ++tndex) {
139 588 const size_t l = boundaries[tndex];
140 588 const size_t r = boundaries[tndex + 1];
141
2/4
✓ Branch 1 taken 588 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 588 times.
✗ Branch 5 not taken.
 1764 futures.push_back(std::async(std::launch::async, [&arr, l, r] { RadixSort(arr, l, r); }));
142 }
143
144
2/2
✓ Branch 0 taken 588 times.
✓ Branch 1 taken 240 times.
 828 for (auto &f : futures) {
145
1/2
✓ Branch 1 taken 588 times.
✗ Branch 2 not taken.
 588 f.get();
146 }
147
148 size_t step = chunk;
149
2/2
✓ Branch 0 taken 290 times.
✓ Branch 1 taken 240 times.
 530 while (step < size) {
150 290 const size_t double_step = step * 2;
151 size_t pos = left;
152
2/2
✓ Branch 0 taken 400 times.
✓ Branch 1 taken 290 times.
 690 while (pos < right) {
153
2/2
✓ Branch 0 taken 328 times.
✓ Branch 1 taken 72 times.
 400 const size_t mid = std::min(pos + step, right);
154 400 const size_t end = std::min(pos + double_step, right);
155
2/2
✓ Branch 0 taken 328 times.
✓ Branch 1 taken 72 times.
 400 if (mid < end) {
156
1/2
✓ Branch 1 taken 328 times.
✗ Branch 2 not taken.
 328 SimpleMerge(arr, pos, mid, end);
157 }
158 pos += double_step;
159 }
160 step = double_step;
161 }
162 480 }
163
164 } // namespace leonova_a_radix_merge_sort
165