GCC Code Coverage Report

Directory: ./
File: tasks/khruev_a_radix_sorting_int_bather_merge/seq/src/ops_seq.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 51 53 96.2%
Functions: 7 8 87.5%
Branches: 43 66 65.2%
Line Branch Exec Source
1 #include "khruev_a_radix_sorting_int_bather_merge/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <cstdint>
6 #include <limits>
7 #include <vector>
8
9 #include "khruev_a_radix_sorting_int_bather_merge/common/include/common.hpp"
10
11 namespace khruev_a_radix_sorting_int_bather_merge {
12
13 ✗ void KhruevARadixSortingIntBatherMergeSEQ::CompareExchange(std::vector<int> &a, size_t i, size_t j) {
14
4/6
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 216 times.
✓ Branch 2 taken 104 times.
✓ Branch 3 taken 296 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 648 if (a[i] > a[j]) {
15 std::swap(a[i], a[j]);
16 }
17 ✗ }
18
19 112 void KhruevARadixSortingIntBatherMergeSEQ::RadixSort(std::vector<int> &arr) {
20 const int bits = 8;
21 const int buckets = 1 << bits;
22 const int mask = buckets - 1;
23 const int passes = 32 / bits;
24
25 112 std::vector<int> temp(arr.size());
26 std::vector<int> *src = &arr;
27 std::vector<int> *dst = &temp;
28
29
2/2
✓ Branch 0 taken 448 times.
✓ Branch 1 taken 112 times.
 560 for (int pass = 0; pass < passes; pass++) {
30
1/4
✓ Branch 1 taken 448 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 448 std::vector<int> count(buckets, 0);
31 448 int shift = pass * bits;
32
33
2/2
✓ Branch 0 taken 1984 times.
✓ Branch 1 taken 448 times.
 2432 for (int x : *src) {
34 1984 uint32_t ux = static_cast<uint32_t>(x) ^ 0x80000000U;
35 1984 uint32_t digit = (ux >> shift) & mask;
36 1984 count[digit]++;
37 }
38
39
2/2
✓ Branch 0 taken 114240 times.
✓ Branch 1 taken 448 times.
 114688 for (int i = 1; i < buckets; i++) {
40 114240 count[i] += count[i - 1];
41 }
42
43
2/2
✓ Branch 0 taken 1984 times.
✓ Branch 1 taken 448 times.
 2432 for (size_t i = src->size(); i-- > 0;) {
44 1984 uint32_t ux = static_cast<uint32_t>((*src)[i]) ^ 0x80000000U;
45 1984 uint32_t digit = (ux >> shift) & mask;
46 1984 (*dst)[--count[digit]] = (*src)[i];
47 }
48
49 std::swap(src, dst);
50 }
51 112 }
52
53 56 void KhruevARadixSortingIntBatherMergeSEQ::OddEvenMerge(std::vector<int> &a, size_t n) {
54
2/2
✓ Branch 0 taken 160 times.
✓ Branch 1 taken 56 times.
 216 for (size_t po = n / 2; po > 0; po >>= 1) {
55
2/2
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 56 times.
 160 if (po == n / 2) {
56
2/2
✓ Branch 0 taken 248 times.
✓ Branch 1 taken 56 times.
 304 for (size_t i = 0; i < po; ++i) {
57
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 216 times.
 248 CompareExchange(a, i, i + po);
58 }
59 } else {
60
2/2
✓ Branch 0 taken 280 times.
✓ Branch 1 taken 104 times.
 384 for (size_t i = po; i < n - po; i += 2 * po) {
61
2/2
✓ Branch 0 taken 400 times.
✓ Branch 1 taken 280 times.
 680 for (size_t j = 0; j < po; ++j) {
62
2/2
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 296 times.
 400 CompareExchange(a, i + j, i + j + po);
63 }
64 }
65 }
66 }
67 56 }
68
69
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 KhruevARadixSortingIntBatherMergeSEQ::KhruevARadixSortingIntBatherMergeSEQ(const InType &in) {
70 SetTypeOfTask(GetStaticTypeOfTask());
71
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 GetInput() = in;
72 64 }
73
74 64 bool KhruevARadixSortingIntBatherMergeSEQ::ValidationImpl() {
75 64 return !GetInput().empty();
76 }
77
78 64 bool KhruevARadixSortingIntBatherMergeSEQ::PreProcessingImpl() {
79 64 GetOutput().resize(GetInput().size());
80 64 return true;
81 }
82
83 64 bool KhruevARadixSortingIntBatherMergeSEQ::RunImpl() {
84 64 std::vector<int> data = GetInput();
85 size_t original_size = data.size();
86
87
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 56 times.
 64 if (original_size <= 1) {
88
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 GetOutput() = data;
89 return true;
90 }
91
92 size_t pow2 = 1;
93
2/2
✓ Branch 0 taken 160 times.
✓ Branch 1 taken 56 times.
 216 while (pow2 < original_size) {
94 160 pow2 <<= 1;
95 }
96
97
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 data.resize(pow2, std::numeric_limits<int>::max());
98
99
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 size_t half = pow2 / 2;
100
101 auto half_dist = static_cast<std::ptrdiff_t>(half);
102
2/6
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 56 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 56 std::vector<int> left(data.begin(), data.begin() + half_dist);
103
1/4
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 56 std::vector<int> right(data.begin() + half_dist, data.end());
104
105
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 RadixSort(left);
106
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 RadixSort(right);
107
108 std::ranges::copy(left, data.begin());
109 std::ranges::copy(right, data.begin() + half_dist);
110
111 56 OddEvenMerge(data, data.size());
112
113
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 data.resize(original_size);
114
115
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 GetOutput() = data;
116
117 return true;
118 }
119
120 64 bool KhruevARadixSortingIntBatherMergeSEQ::PostProcessingImpl() {
121 64 return GetOutput().size() == GetInput().size();
122 }
123
124 } // namespace khruev_a_radix_sorting_int_bather_merge
125