GCC Code Coverage Report

Directory: ./
File: tasks/krymova_k_lsd_sort_merge_double/stl/src/ops_stl.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 82 93 88.2%
Functions: 10 12 83.3%
Branches: 56 84 66.7%
Line Branch Exec Source
1 #include "krymova_k_lsd_sort_merge_double/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <cstdint>
5 #include <cstring>
6 #include <thread>
7 #include <vector>
8
9 #include "krymova_k_lsd_sort_merge_double/common/include/common.hpp"
10
11 namespace krymova_k_lsd_sort_merge_double {
12
13
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 KrymovaKLsdSortMergeDoubleSTL::KrymovaKLsdSortMergeDoubleSTL(const InType &in) {
14 SetTypeOfTask(GetStaticTypeOfTask());
15
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 GetInput() = in;
16 96 GetOutput() = OutType();
17 96 }
18
19 96 bool KrymovaKLsdSortMergeDoubleSTL::ValidationImpl() {
20 96 return !GetInput().empty();
21 }
22
23 96 bool KrymovaKLsdSortMergeDoubleSTL::PreProcessingImpl() {
24 96 GetOutput() = GetInput();
25 96 return true;
26 }
27
28 ✗ uint64_t KrymovaKLsdSortMergeDoubleSTL::DoubleToULL(double d) {
29 uint64_t ull = 0;
30 std::memcpy(&ull, &d, sizeof(double));
31
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 900160 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 900160 if ((ull & 0x8000000000000000ULL) != 0U) {
32 ✗ ull = ~ull;
33 } else {
34 900160 ull |= 0x8000000000000000ULL;
35 }
36 ✗ return ull;
37 }
38
39 ✗ double KrymovaKLsdSortMergeDoubleSTL::ULLToDouble(uint64_t ull) {
40
1/4
✓ Branch 0 taken 900160 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 900160 if ((ull & 0x8000000000000000ULL) != 0U) {
41 900160 ull &= 0x7FFFFFFFFFFFFFFFULL;
42 } else {
43 ✗ ull = ~ull;
44 }
45 double d = 0.0;
46 std::memcpy(&d, &ull, sizeof(double));
47 ✗ return d;
48 }
49
50 368 void KrymovaKLsdSortMergeDoubleSTL::LSDSortDoubleSequential(double *arr, int size) {
51
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 368 times.
 368 if (size <= 1) {
52 ✗ return;
53 }
54 const int k_bits_per_pass = 8;
55 const int k_radix = 1 << k_bits_per_pass;
56 const int k_passes = static_cast<int>(sizeof(double)) * 8 / k_bits_per_pass;
57 368 std::vector<uint64_t> ull_arr(size);
58
1/4
✓ Branch 1 taken 368 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 368 std::vector<uint64_t> ull_tmp(size);
59
2/2
✓ Branch 0 taken 900160 times.
✓ Branch 1 taken 368 times.
 900528 for (int i = 0; i < size; ++i) {
60
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 900160 times.
 1800320 ull_arr[i] = DoubleToULL(arr[i]);
61 }
62
1/4
✓ Branch 1 taken 368 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 368 std::vector<unsigned int> count(k_radix, 0U);
63
2/2
✓ Branch 0 taken 2944 times.
✓ Branch 1 taken 368 times.
 3312 for (int pass = 0; pass < k_passes; ++pass) {
64 2944 int shift = pass * k_bits_per_pass;
65
2/2
✓ Branch 0 taken 753664 times.
✓ Branch 1 taken 2944 times.
 756608 for (auto &val : count) {
66 753664 val = 0U;
67 }
68
2/2
✓ Branch 0 taken 7201280 times.
✓ Branch 1 taken 2944 times.
 7204224 for (int i = 0; i < size; ++i) {
69 7201280 unsigned int digit = (ull_arr[i] >> shift) & (k_radix - 1);
70 7201280 ++count[digit];
71 }
72
2/2
✓ Branch 0 taken 750720 times.
✓ Branch 1 taken 2944 times.
 753664 for (int i = 1; i < k_radix; ++i) {
73 750720 count[i] += count[i - 1];
74 }
75
2/2
✓ Branch 0 taken 7201280 times.
✓ Branch 1 taken 2944 times.
 7204224 for (int i = size - 1; i >= 0; --i) {
76 7201280 unsigned int digit = (ull_arr[i] >> shift) & (k_radix - 1);
77 7201280 ull_tmp[--count[digit]] = ull_arr[i];
78 }
79 ull_arr.swap(ull_tmp);
80 }
81
2/2
✓ Branch 0 taken 900160 times.
✓ Branch 1 taken 368 times.
 900528 for (int i = 0; i < size; ++i) {
82
1/2
✓ Branch 0 taken 900160 times.
✗ Branch 1 not taken.
 1800320 arr[i] = ULLToDouble(ull_arr[i]);
83 }
84 }
85
86 280 void KrymovaKLsdSortMergeDoubleSTL::MergeSections(double *left, const double *right, int left_size, int right_size) {
87 280 std::vector<double> temp(left_size);
88 280 std::copy(left, left + left_size, temp.begin());
89 int left_index = 0;
90 int right_index = 0;
91 int dest_index = 0;
92
2/2
✓ Branch 0 taken 900256 times.
✓ Branch 1 taken 280 times.
 900536 while (left_index < left_size && right_index < right_size) {
93
2/2
✓ Branch 0 taken 899456 times.
✓ Branch 1 taken 800 times.
 900256 if (temp[left_index] <= right[right_index]) {
94 899456 left[dest_index++] = temp[left_index++];
95 } else {
96 800 left[dest_index++] = right[right_index++];
97 }
98 }
99
2/2
✓ Branch 0 taken 800 times.
✓ Branch 1 taken 280 times.
 1080 while (left_index < left_size) {
100 800 left[dest_index++] = temp[left_index++];
101 }
102 280 }
103
104 88 void KrymovaKLsdSortMergeDoubleSTL::SortSectionsParallel(double *arr, int size, int portion, int num_threads) {
105
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 88 times.
 88 int num_blocks = (size + portion - 1) / portion;
106 int num_threads_used = (std::min)(num_threads, num_blocks);
107
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 88 times.
 88 if (num_threads_used <= 1) {
108 ✗ for (int start = 0; start < size; start += portion) {
109 ✗ int current_size = (std::min)(portion, size - start);
110 ✗ LSDSortDoubleSequential(arr + start, current_size);
111 }
112 ✗ return;
113 }
114 88 std::vector<std::thread> threads;
115 88 int blocks_per_thread = (num_blocks + num_threads_used - 1) / num_threads_used;
116
2/2
✓ Branch 0 taken 352 times.
✓ Branch 1 taken 88 times.
 440 for (int thread_id = 0; thread_id < num_threads_used; ++thread_id) {
117 352 int start_block = thread_id * blocks_per_thread;
118
1/2
✓ Branch 1 taken 352 times.
✗ Branch 2 not taken.
 352 int end_block = (std::min)(start_block + blocks_per_thread, num_blocks);
119
1/2
✓ Branch 1 taken 352 times.
✗ Branch 2 not taken.
 352 threads.emplace_back([&, start_block, end_block, portion, size, arr]() {
120
2/2
✓ Branch 0 taken 368 times.
✓ Branch 1 taken 352 times.
 720 for (int block = start_block; block < end_block; ++block) {
121 368 int start_pos = block * portion;
122 368 int current_size = (std::min)(portion, size - start_pos);
123 368 LSDSortDoubleSequential(arr + start_pos, current_size);
124 }
125 352 });
126 }
127
2/2
✓ Branch 0 taken 352 times.
✓ Branch 1 taken 88 times.
 440 for (auto &thr : threads) {
128
1/2
✓ Branch 1 taken 352 times.
✗ Branch 2 not taken.
 352 thr.join();
129 }
130 88 }
131
132 88 void KrymovaKLsdSortMergeDoubleSTL::IterativeMergeSort(double *arr, int size, int portion, int num_threads) {
133
1/2
✓ Branch 0 taken 88 times.
✗ Branch 1 not taken.
 88 if (size <= 1) {
134 return;
135 }
136 88 SortSectionsParallel(arr, size, portion, num_threads);
137
2/2
✓ Branch 0 taken 192 times.
✓ Branch 1 taken 88 times.
 280 for (int merge_size = portion; merge_size < size; merge_size *= 2) {
138
2/2
✓ Branch 0 taken 312 times.
✓ Branch 1 taken 192 times.
 504 for (int start_pos = 0; start_pos < size; start_pos += 2 * merge_size) {
139 int left_size = merge_size;
140
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 280 times.
 312 int right_size = (std::min)(merge_size, size - (start_pos + merge_size));
141
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 280 times.
 312 if (right_size <= 0) {
142 32 continue;
143 }
144 280 double *left = arr + start_pos;
145 280 const double *right = arr + start_pos + left_size;
146 280 MergeSections(left, right, left_size, right_size);
147 }
148 }
149 }
150
151
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 8 times.
 96 bool KrymovaKLsdSortMergeDoubleSTL::RunImpl() {
152 OutType &output = GetOutput();
153 96 int size = static_cast<int>(output.size());
154
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 8 times.
 96 if (size <= 1) {
155 return true;
156 }
157 88 int num_threads = (std::max)(1, static_cast<int>(std::thread::hardware_concurrency()));
158 88 num_threads = (std::min)(num_threads, size);
159 88 int portion = (std::max)(1, size / num_threads);
160 88 IterativeMergeSort(output.data(), size, portion, num_threads);
161 return true;
162 }
163
164 96 bool KrymovaKLsdSortMergeDoubleSTL::PostProcessingImpl() {
165 const OutType &output = GetOutput();
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 return true;
172 }
173
174 } // namespace krymova_k_lsd_sort_merge_double
175