GCC Code Coverage Report

Directory: ./
File: tasks/krymova_k_lsd_sort_merge_double/seq/src/ops_seq.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 65 73 89.0%
Functions: 8 11 72.7%
Branches: 49 72 68.1%
Line Branch Exec Source
1 #include "krymova_k_lsd_sort_merge_double/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <cstdint>
5 #include <cstring>
6 #include <vector>
7
8 #include "krymova_k_lsd_sort_merge_double/common/include/common.hpp"
9
10 namespace krymova_k_lsd_sort_merge_double {
11
12
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 KrymovaKLsdSortMergeDoubleSEQ::KrymovaKLsdSortMergeDoubleSEQ(const InType &in) {
13 SetTypeOfTask(GetStaticTypeOfTask());
14
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 GetInput() = in;
15 96 GetOutput() = OutType();
16 96 }
17
18 96 bool KrymovaKLsdSortMergeDoubleSEQ::ValidationImpl() {
19 96 return !GetInput().empty();
20 }
21
22 96 bool KrymovaKLsdSortMergeDoubleSEQ::PreProcessingImpl() {
23 96 GetOutput() = GetInput();
24 96 return true;
25 }
26
27 ✗ uint64_t KrymovaKLsdSortMergeDoubleSEQ::DoubleToULL(double d) {
28 uint64_t ull = 0;
29 std::memcpy(&ull, &d, sizeof(double));
30
31
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 900000 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 900000 if ((ull & 0x8000000000000000ULL) != 0U) {
32 ✗ ull = ~ull;
33 } else {
34 900000 ull |= 0x8000000000000000ULL;
35 }
36
37 ✗ return ull;
38 }
39
40 ✗ double KrymovaKLsdSortMergeDoubleSEQ::ULLToDouble(uint64_t ull) {
41
1/4
✓ Branch 0 taken 900000 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 900000 if ((ull & 0x8000000000000000ULL) != 0U) {
42 900000 ull &= 0x7FFFFFFFFFFFFFFFULL;
43 } else {
44 ✗ ull = ~ull;
45 }
46
47 double d = 0.0;
48 std::memcpy(&d, &ull, sizeof(double));
49 ✗ return d;
50 }
51
52 880 void KrymovaKLsdSortMergeDoubleSEQ::LSDSortDouble(double *arr, int size) {
53
2/2
✓ Branch 0 taken 160 times.
✓ Branch 1 taken 720 times.
 880 if (size <= 1) {
54 160 return;
55 }
56
57 const int k_bits_per_pass = 8;
58 const int k_radix = 1 << k_bits_per_pass;
59 const int k_passes = static_cast<int>(sizeof(double)) * 8 / k_bits_per_pass;
60
61 720 std::vector<uint64_t> ull_arr(size);
62
1/4
✓ Branch 1 taken 720 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 720 std::vector<uint64_t> ull_tmp(size);
63
64
2/2
✓ Branch 0 taken 900000 times.
✓ Branch 1 taken 720 times.
 900720 for (int i = 0; i < size; ++i) {
65
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 900000 times.
 1800000 ull_arr[i] = DoubleToULL(arr[i]);
66 }
67
68
1/4
✓ Branch 1 taken 720 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 720 std::vector<unsigned int> count(k_radix, 0U);
69
70
2/2
✓ Branch 0 taken 5760 times.
✓ Branch 1 taken 720 times.
 6480 for (int pass = 0; pass < k_passes; ++pass) {
71
1/2
✓ Branch 0 taken 5760 times.
✗ Branch 1 not taken.
 5760 int shift = pass * k_bits_per_pass;
72
73 std::ranges::fill(count, 0U);
74
75
2/2
✓ Branch 0 taken 7200000 times.
✓ Branch 1 taken 5760 times.
 7205760 for (int i = 0; i < size; ++i) {
76 7200000 unsigned int digit = (ull_arr[i] >> shift) & (k_radix - 1);
77 7200000 ++count[digit];
78 }
79
80
2/2
✓ Branch 0 taken 1468800 times.
✓ Branch 1 taken 5760 times.
 1474560 for (int i = 1; i < k_radix; ++i) {
81 1468800 count[i] += count[i - 1];
82 }
83
84
2/2
✓ Branch 0 taken 7200000 times.
✓ Branch 1 taken 5760 times.
 7205760 for (int i = size - 1; i >= 0; --i) {
85 7200000 unsigned int digit = (ull_arr[i] >> shift) & (k_radix - 1);
86 7200000 ull_tmp[--count[digit]] = ull_arr[i];
87 }
88
89 ull_arr.swap(ull_tmp);
90 }
91
92
2/2
✓ Branch 0 taken 900000 times.
✓ Branch 1 taken 720 times.
 900720 for (int i = 0; i < size; ++i) {
93
1/2
✓ Branch 0 taken 900000 times.
✗ Branch 1 not taken.
 1800000 arr[i] = ULLToDouble(ull_arr[i]);
94 }
95 }
96
97 792 void KrymovaKLsdSortMergeDoubleSEQ::MergeSections(double *left, const double *right, int left_size, int right_size) {
98 792 std::vector<double> temp(left_size);
99 792 std::copy(left, left + left_size, temp.begin());
100
101 int l = 0;
102 int r = 0;
103 int k = 0;
104
105
2/2
✓ Branch 0 taken 1889856 times.
✓ Branch 1 taken 792 times.
 1890648 while (l < left_size && r < right_size) {
106
2/2
✓ Branch 0 taken 1888656 times.
✓ Branch 1 taken 1200 times.
 1889856 if (temp[l] <= right[r]) {
107 1888656 left[k++] = temp[l++];
108 } else {
109 1200 left[k++] = right[r++];
110 }
111 }
112
113
2/2
✓ Branch 0 taken 1680 times.
✓ Branch 1 taken 792 times.
 2472 while (l < left_size) {
114 1680 left[k++] = temp[l++];
115 }
116 792 }
117
118 ✗ void KrymovaKLsdSortMergeDoubleSEQ::SortSections(double *arr, int size, int portion) {
119
2/4
✓ Branch 0 taken 880 times.
✓ Branch 1 taken 88 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 968 for (int i = 0; i < size; i += portion) {
120 880 int current_size = std::min(portion, size - i);
121 880 LSDSortDouble(arr + i, current_size);
122 }
123 ✗ }
124
125 88 void KrymovaKLsdSortMergeDoubleSEQ::IterativeMergeSort(double *arr, int size, int portion) {
126
1/2
✓ Branch 0 taken 88 times.
✗ Branch 1 not taken.
 88 if (size <= 1) {
127 return;
128 }
129
130 SortSections(arr, size, portion);
131
132
2/2
✓ Branch 0 taken 352 times.
✓ Branch 1 taken 88 times.
 440 for (int merge_size = portion; merge_size < size; merge_size *= 2) {
133
2/2
✓ Branch 0 taken 968 times.
✓ Branch 1 taken 352 times.
 1320 for (int i = 0; i < size; i += 2 * merge_size) {
134 int left_size = merge_size;
135
2/2
✓ Branch 0 taken 176 times.
✓ Branch 1 taken 792 times.
 968 int right_size = std::min(merge_size, size - (i + merge_size));
136
137
2/2
✓ Branch 0 taken 176 times.
✓ Branch 1 taken 792 times.
 968 if (right_size <= 0) {
138 176 continue;
139 }
140
141 792 double *left = arr + i;
142 792 const double *right = arr + i + left_size;
143
144 792 MergeSections(left, right, left_size, right_size);
145 }
146 }
147 }
148
149
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 8 times.
 96 bool KrymovaKLsdSortMergeDoubleSEQ::RunImpl() {
150 OutType &output = GetOutput();
151 96 int size = static_cast<int>(output.size());
152
153
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 8 times.
 96 if (size <= 1) {
154 return true;
155 }
156
157
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 72 times.
 88 int portion = std::max(1, size / 10);
158 88 IterativeMergeSort(output.data(), size, portion); // без tmp
159
160 88 return true;
161 }
162
163 96 bool KrymovaKLsdSortMergeDoubleSEQ::PostProcessingImpl() {
164 const OutType &output = GetOutput();
165
166
2/2
✓ Branch 0 taken 900072 times.
✓ Branch 1 taken 96 times.
 900168 for (size_t i = 1; i < output.size(); ++i) {
167
1/2
✓ Branch 0 taken 900072 times.
✗ Branch 1 not taken.
 900072 if (output[i] < output[i - 1]) {
168 return false;
169 }
170 }
171
172 return true;
173 }
174
175 } // namespace krymova_k_lsd_sort_merge_double
176