GCC Code Coverage Report

Directory: ./
File: tasks/leonova_a_radix_merge_sort/seq/src/ops_seq.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 70 73 95.9%
Functions: 8 9 88.9%
Branches: 43 68 63.2%
Line Branch Exec Source
1 #include "leonova_a_radix_merge_sort/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <cstdint>
6 #include <vector>
7
8 #include "leonova_a_radix_merge_sort/common/include/common.hpp"
9
10 namespace leonova_a_radix_merge_sort {
11
12
1/2
✓ Branch 1 taken 256 times.
✗ Branch 2 not taken.
 256 LeonovaARadixMergeSortSEQ::LeonovaARadixMergeSortSEQ(const InType &in) {
13 SetTypeOfTask(GetStaticTypeOfTask());
14
1/2
✓ Branch 1 taken 256 times.
✗ Branch 2 not taken.
 256 GetInput() = in;
15
1/2
✓ Branch 1 taken 256 times.
✗ Branch 2 not taken.
 256 GetOutput() = std::vector<int64_t>(GetInput().size());
16 256 }
17
18 512 bool LeonovaARadixMergeSortSEQ::ValidationImpl() {
19 512 return !GetInput().empty();
20 }
21
22 256 bool LeonovaARadixMergeSortSEQ::PreProcessingImpl() {
23 256 return true;
24 }
25
26 256 bool LeonovaARadixMergeSortSEQ::RunImpl() {
27
1/2
✓ Branch 1 taken 256 times.
✗ Branch 2 not taken.
 256 if (!ValidationImpl()) {
28 return false;
29 }
30 256 GetOutput() = GetInput();
31
2/2
✓ Branch 0 taken 240 times.
✓ Branch 1 taken 16 times.
 256 if (GetOutput().size() > 1) {
32 240 RadixMergeSort(GetOutput(), 0, GetOutput().size());
33 }
34 return true;
35 }
36
37 256 bool LeonovaARadixMergeSortSEQ::PostProcessingImpl() {
38 256 return true;
39 }
40
41 ✗ uint64_t LeonovaARadixMergeSortSEQ::ToUnsigned(int64_t value) {
42 auto unsigned_value = static_cast<uint64_t>(value);
43 constexpr uint64_t kSignBitMask = 0x8000000000000000ULL;
44 2103928 return unsigned_value ^ kSignBitMask;
45 }
46
47 65904 void LeonovaARadixMergeSortSEQ::RadixSort(std::vector<int64_t> &arr, size_t left, size_t right) {
48 65904 size_t size = right - left;
49
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 65904 times.
 65904 if (size <= 1) {
50 ✗ return;
51 }
52
53 65904 std::vector<uint64_t> keys(size);
54
2/2
✓ Branch 0 taken 2103928 times.
✓ Branch 1 taken 65904 times.
 2169832 for (size_t index = 0; index < size; ++index) {
55 2103928 keys[index] = ToUnsigned(arr[left + index]);
56 }
57
58
1/4
✓ Branch 1 taken 65904 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 65904 std::vector<int64_t> temp_arr(size);
59
1/4
✓ Branch 1 taken 65904 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 65904 std::vector<uint64_t> temp_keys(size);
60
61
2/2
✓ Branch 0 taken 527232 times.
✓ Branch 1 taken 65904 times.
 593136 for (int byte_pos = 0; byte_pos < kNumBytes; ++byte_pos) {
62
1/4
✓ Branch 1 taken 527232 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 527232 std::vector<size_t> count(kNumCounters, 0);
63
64
2/2
✓ Branch 0 taken 16831424 times.
✓ Branch 1 taken 527232 times.
 17358656 for (size_t index = 0; index < size; ++index) {
65 16831424 uint8_t byte_val = (keys[index] >> (byte_pos * kByteSize)) & 0xFF;
66 16831424 ++count[byte_val];
67 }
68
69 size_t total = 0;
70
2/2
✓ Branch 0 taken 134971392 times.
✓ Branch 1 taken 527232 times.
 135498624 for (size_t &elem : count) {
71 134971392 size_t old_count = elem;
72 134971392 elem = total;
73 134971392 total += old_count;
74 }
75
76
2/2
✓ Branch 0 taken 16831424 times.
✓ Branch 1 taken 527232 times.
 17358656 for (size_t index = 0; index < size; ++index) {
77 16831424 uint8_t byte_val = (keys[index] >> (byte_pos * kByteSize)) & 0xFF;
78 16831424 size_t pos = count[byte_val]++;
79 16831424 temp_arr[pos] = arr[left + index];
80 16831424 temp_keys[pos] = keys[index];
81 }
82
83 auto left_it = arr.begin() + static_cast<typename std::vector<int64_t>::difference_type>(left);
84 std::ranges::copy(temp_arr, left_it);
85 keys.swap(temp_keys);
86 }
87 }
88
89 65664 void LeonovaARadixMergeSortSEQ::SimpleMerge(std::vector<int64_t> &arr, size_t left, size_t mid, size_t right) {
90 65664 size_t left_size = mid - left;
91 65664 size_t right_size = right - mid;
92
93 65664 std::vector<int64_t> merged(left_size + right_size);
94
95 size_t i = 0;
96 size_t j = 0;
97 size_t k = 0;
98
99
2/2
✓ Branch 0 taken 12588832 times.
✓ Branch 1 taken 65664 times.
 12654496 while (i < left_size && j < right_size) {
100
2/2
✓ Branch 0 taken 200 times.
✓ Branch 1 taken 12588632 times.
 12588832 if (arr[left + i] <= arr[mid + j]) {
101 200 merged[k++] = arr[left + i++];
102 } else {
103 12588632 merged[k++] = arr[mid + j++];
104 }
105 }
106
107
2/2
✓ Branch 0 taken 12588504 times.
✓ Branch 1 taken 65664 times.
 12654168 while (i < left_size) {
108 12588504 merged[k++] = arr[left + i++];
109 }
110
2/2
✓ Branch 0 taken 200 times.
✓ Branch 1 taken 65664 times.
 65864 while (j < right_size) {
111 200 merged[k++] = arr[mid + j++];
112 }
113
114 auto left_it = arr.begin() + static_cast<typename std::vector<int64_t>::difference_type>(left);
115 std::ranges::copy(merged, left_it);
116 65664 }
117
118 240 void LeonovaARadixMergeSortSEQ::RadixMergeSort(std::vector<int64_t> &arr, size_t left, size_t right) {
119 struct SortTask {
120 size_t left;
121 size_t right;
122 bool sorted;
123 };
124
125 240 std::vector<SortTask> stack;
126
1/2
✓ Branch 1 taken 240 times.
✗ Branch 2 not taken.
 240 stack.reserve(128);
127
1/2
✓ Branch 1 taken 240 times.
✗ Branch 2 not taken.
 240 stack.push_back({left, right, false});
128
129
2/2
✓ Branch 0 taken 197232 times.
✓ Branch 1 taken 240 times.
 197472 while (!stack.empty()) {
130
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 197232 times.
 197232 SortTask current = stack.back();
131 stack.pop_back();
132
133 197232 size_t size = current.right - current.left;
134
135
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 197232 times.
 197232 if (size <= 1) {
136 ✗ continue;
137 }
138
139
2/2
✓ Branch 0 taken 65904 times.
✓ Branch 1 taken 131328 times.
 197232 if (size <= kRadixThreshold) {
140
1/2
✓ Branch 1 taken 65904 times.
✗ Branch 2 not taken.
 65904 RadixSort(arr, current.left, current.right);
141 65904 continue;
142 }
143
144
2/2
✓ Branch 0 taken 65664 times.
✓ Branch 1 taken 65664 times.
 131328 if (!current.sorted) {
145 65664 size_t mid = current.left + (size / 2);
146
147
1/2
✓ Branch 1 taken 65664 times.
✗ Branch 2 not taken.
 65664 stack.push_back({current.left, current.right, true});
148
1/2
✓ Branch 1 taken 65664 times.
✗ Branch 2 not taken.
 65664 stack.push_back({mid, current.right, false});
149
1/4
✓ Branch 1 taken 65664 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 65664 stack.push_back({current.left, mid, false});
150 } else {
151 65664 size_t mid = current.left + (size / 2);
152
1/2
✓ Branch 1 taken 65664 times.
✗ Branch 2 not taken.
 65664 SimpleMerge(arr, current.left, mid, current.right);
153 }
154 }
155 240 }
156 } // namespace leonova_a_radix_merge_sort
157