GCC Code Coverage Report

Directory: ./
File: tasks/krymova_k_lsd_sort_merge_double/omp/src/ops_omp.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 58 66 87.9%
Functions: 8 11 72.7%
Branches: 41 66 62.1%
Line Branch Exec Source
1 #include "krymova_k_lsd_sort_merge_double/omp/include/ops_omp.hpp"
2
3 #include <omp.h>
4
5 #include <algorithm>
6 #include <cstdint>
7 #include <cstring>
8 #include <vector>
9
10 #include "krymova_k_lsd_sort_merge_double/common/include/common.hpp"
11
12 namespace krymova_k_lsd_sort_merge_double {
13
14
1/2
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 48 KrymovaKLsdSortMergeDoubleOMP::KrymovaKLsdSortMergeDoubleOMP(const InType &in) : num_threads_(omp_get_max_threads()) {
15 SetTypeOfTask(GetStaticTypeOfTask());
16
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 GetInput() = in;
17 48 GetOutput() = OutType();
18 48 }
19
20 48 bool KrymovaKLsdSortMergeDoubleOMP::ValidationImpl() {
21 48 return !GetInput().empty();
22 }
23
24 48 bool KrymovaKLsdSortMergeDoubleOMP::PreProcessingImpl() {
25 48 GetOutput() = GetInput();
26 48 return true;
27 }
28
29 ✗ uint64_t KrymovaKLsdSortMergeDoubleOMP::DoubleToULL(double d) {
30 uint64_t ull = 0;
31 std::memcpy(&ull, &d, sizeof(double));
32
33
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 450069 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 450069 if ((ull & 0x8000000000000000ULL) != 0U) {
34 ✗ ull = ~ull;
35 } else {
36 450069 ull |= 0x8000000000000000ULL;
37 }
38
39 ✗ return ull;
40 }
41
42 ✗ double KrymovaKLsdSortMergeDoubleOMP::ULLToDouble(uint64_t ull) {
43
1/4
✓ Branch 0 taken 450069 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 450069 if ((ull & 0x8000000000000000ULL) != 0U) {
44 450069 ull &= 0x7FFFFFFFFFFFFFFFULL;
45 } else {
46 ✗ ull = ~ull;
47 }
48
49 double d = 0.0;
50 std::memcpy(&d, &ull, sizeof(double));
51 ✗ return d;
52 }
53
54 123 void KrymovaKLsdSortMergeDoubleOMP::LSDSortDouble(double *arr, int size) {
55
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 112 times.
 123 if (size <= 1) {
56 11 return;
57 }
58
59 const int k_bits_per_pass = 8;
60 const int k_radix = 1 << k_bits_per_pass;
61 const int k_passes = static_cast<int>(sizeof(double)) * 8 / k_bits_per_pass;
62
63 112 std::vector<uint64_t> ull_arr(size);
64
1/4
✓ Branch 1 taken 112 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 112 std::vector<uint64_t> ull_tmp(size);
65
66
2/2
✓ Branch 0 taken 450069 times.
✓ Branch 1 taken 112 times.
 450181 for (int i = 0; i < size; ++i) {
67
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 450069 times.
 900138 ull_arr[i] = DoubleToULL(arr[i]);
68 }
69
70
1/4
✓ Branch 1 taken 112 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 112 std::vector<unsigned int> count(k_radix, 0U);
71
72
2/2
✓ Branch 0 taken 896 times.
✓ Branch 1 taken 112 times.
 1008 for (int pass = 0; pass < k_passes; ++pass) {
73
1/2
✓ Branch 0 taken 896 times.
✗ Branch 1 not taken.
 896 int shift = pass * k_bits_per_pass;
74
75 std::ranges::fill(count, 0U);
76
77
2/2
✓ Branch 0 taken 3600552 times.
✓ Branch 1 taken 896 times.
 3601448 for (int i = 0; i < size; ++i) {
78 3600552 unsigned int digit = (ull_arr[i] >> shift) & (k_radix - 1);
79 3600552 ++count[digit];
80 }
81
82
2/2
✓ Branch 0 taken 228480 times.
✓ Branch 1 taken 896 times.
 229376 for (int i = 1; i < k_radix; ++i) {
83 228480 count[i] += count[i - 1];
84 }
85
86
2/2
✓ Branch 0 taken 3600552 times.
✓ Branch 1 taken 896 times.
 3601448 for (int i = size - 1; i >= 0; --i) {
87 3600552 unsigned int digit = (ull_arr[i] >> shift) & (k_radix - 1);
88 3600552 ull_tmp[--count[digit]] = ull_arr[i];
89 }
90
91 ull_arr.swap(ull_tmp);
92 }
93
94
2/2
✓ Branch 0 taken 450069 times.
✓ Branch 1 taken 112 times.
 450181 for (int i = 0; i < size; ++i) {
95
1/2
✓ Branch 0 taken 450069 times.
✗ Branch 1 not taken.
 900138 arr[i] = ULLToDouble(ull_arr[i]);
96 }
97 }
98
99 79 void KrymovaKLsdSortMergeDoubleOMP::MergeSections(double *left, const double *right, int left_size, int right_size) {
100
1/2
✓ Branch 1 taken 79 times.
✗ Branch 2 not taken.
 79 std::vector<double> temp(left_size);
101
1/2
✓ Branch 0 taken 79 times.
✗ Branch 1 not taken.
 79 std::ranges::copy(left, left + left_size, temp.begin());
102
103 int left_index = 0;
104 int right_index = 0;
105 int dest_index = 0;
106
107
2/2
✓ Branch 0 taken 318740 times.
✓ Branch 1 taken 79 times.
 318819 while (left_index < left_size && right_index < right_size) {
108
2/2
✓ Branch 0 taken 318522 times.
✓ Branch 1 taken 218 times.
 318740 if (temp[left_index] <= right[right_index]) {
109 318522 left[dest_index++] = temp[left_index++];
110 } else {
111 218 left[dest_index++] = right[right_index++];
112 }
113 }
114
115
2/2
✓ Branch 0 taken 282 times.
✓ Branch 1 taken 79 times.
 361 while (left_index < left_size) {
116 282 left[dest_index++] = temp[left_index++];
117 }
118 79 }
119
120 ✗ void KrymovaKLsdSortMergeDoubleOMP::SortSectionsParallel(double *arr, int size, int portion) {
121 44 #pragma omp parallel for default(none) shared(arr, size, portion)
122 for (int block_start = 0; block_start < size; block_start += portion) {
123 int current_size = std::min(portion, size - block_start);
124 LSDSortDouble(arr + block_start, current_size);
125 }
126 ✗ }
127
128 44 void KrymovaKLsdSortMergeDoubleOMP::IterativeMergeSort(double *arr, int size, int portion) {
129
1/2
✓ Branch 0 taken 44 times.
✗ Branch 1 not taken.
 44 if (size <= 1) {
130 return;
131 }
132
133 44 SortSectionsParallel(arr, size, portion);
134
135
2/2
✓ Branch 0 taken 57 times.
✓ Branch 1 taken 44 times.
 101 for (int merge_size = portion; merge_size < size; merge_size *= 2) {
136 57 #pragma omp parallel for default(none) shared(arr, size, merge_size)
137 for (int pair_start = 0; pair_start < size; pair_start += 2 * merge_size) {
138 int left_size = merge_size;
139 int right_size = std::min(merge_size, size - (pair_start + merge_size));
140
141 if (right_size <= 0) {
142 continue;
143 }
144
145 double *left = arr + pair_start;
146 const double *right = arr + pair_start + left_size;
147
148 MergeSections(left, right, left_size, right_size);
149 }
150 }
151 }
152
153
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 4 times.
 48 bool KrymovaKLsdSortMergeDoubleOMP::RunImpl() {
154 OutType &output = GetOutput();
155 48 int size = static_cast<int>(output.size());
156
157
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 4 times.
 48 if (size <= 1) {
158 return true;
159 }
160
161 44 int portion = std::max(1, size / num_threads_);
162 portion = std::min(portion, 1000000);
163
164 44 IterativeMergeSort(output.data(), size, portion);
165
166 44 return true;
167 }
168
169 48 bool KrymovaKLsdSortMergeDoubleOMP::PostProcessingImpl() {
170 const OutType &output = GetOutput();
171
172
2/2
✓ Branch 0 taken 450036 times.
✓ Branch 1 taken 48 times.
 450084 for (size_t i = 1; i < output.size(); ++i) {
173
1/2
✓ Branch 0 taken 450036 times.
✗ Branch 1 not taken.
 450036 if (output[i] < output[i - 1]) {
174 return false;
175 }
176 }
177
178 return true;
179 }
180
181 } // namespace krymova_k_lsd_sort_merge_double
182