GCC Code Coverage Report

Directory: ./
File: tasks/krymova_k_lsd_sort_merge_double/omp/src/ops_omp.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 65 71 91.5%
Functions: 8 11 72.7%
Branches: 51 72 70.8%
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 52 times.
✗ Branch 3 not taken.
 52 KrymovaKLsdSortMergeDoubleOMP::KrymovaKLsdSortMergeDoubleOMP(const InType &in) : num_threads_(omp_get_max_threads()) {
15 SetTypeOfTask(GetStaticTypeOfTask());
16
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 GetInput() = in;
17 52 GetOutput() = OutType();
18 52 }
19
20 52 bool KrymovaKLsdSortMergeDoubleOMP::ValidationImpl() {
21 52 return !GetInput().empty();
22 }
23
24 52 bool KrymovaKLsdSortMergeDoubleOMP::PreProcessingImpl() {
25 52 GetOutput() = GetInput();
26 52 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
2/4
✓ Branch 0 taken 400 times.
✓ Branch 1 taken 450040 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 450440 if ((ull & 0x8000000000000000ULL) != 0U) {
34 400 ull = ~ull;
35 } else {
36 450040 ull |= 0x8000000000000000ULL;
37 }
38
39 ✗ return ull;
40 }
41
42 ✗ double KrymovaKLsdSortMergeDoubleOMP::ULLToDouble(uint64_t ull) {
43
2/4
✓ Branch 0 taken 450040 times.
✓ Branch 1 taken 400 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 450440 if ((ull & 0x8000000000000000ULL) != 0U) {
44 450040 ull &= 0x7FFFFFFFFFFFFFFFULL;
45 } else {
46 400 ull = ~ull;
47 }
48
49 double d = 0.0;
50 std::memcpy(&d, &ull, sizeof(double));
51 ✗ return d;
52 }
53
54 329 void KrymovaKLsdSortMergeDoubleOMP::LSDSortDouble(double *arr, int size) {
55
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 289 times.
 329 if (size <= 1) {
56 40 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 289 std::vector<uint64_t> ull_arr(size);
64
1/4
✓ Branch 1 taken 289 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 289 std::vector<uint64_t> ull_tmp(size);
65
66
2/2
✓ Branch 0 taken 450440 times.
✓ Branch 1 taken 289 times.
 450729 for (int i = 0; i < size; ++i) {
67
2/2
✓ Branch 0 taken 400 times.
✓ Branch 1 taken 450040 times.
 900880 ull_arr[i] = DoubleToULL(arr[i]);
68 }
69
70
1/4
✓ Branch 1 taken 289 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 289 std::vector<unsigned int> count(k_radix, 0U);
71
72
2/2
✓ Branch 0 taken 2312 times.
✓ Branch 1 taken 289 times.
 2601 for (int pass = 0; pass < k_passes; ++pass) {
73
1/2
✓ Branch 0 taken 2312 times.
✗ Branch 1 not taken.
 2312 int shift = pass * k_bits_per_pass;
74
75 std::ranges::fill(count, 0U);
76
77
2/2
✓ Branch 0 taken 3603520 times.
✓ Branch 1 taken 2312 times.
 3605832 for (int i = 0; i < size; ++i) {
78 3603520 unsigned int digit = (ull_arr[i] >> shift) & (k_radix - 1);
79 3603520 ++count[digit];
80 }
81
82
2/2
✓ Branch 0 taken 589560 times.
✓ Branch 1 taken 2312 times.
 591872 for (int i = 1; i < k_radix; ++i) {
83 589560 count[i] += count[i - 1];
84 }
85
86
2/2
✓ Branch 0 taken 3603520 times.
✓ Branch 1 taken 2312 times.
 3605832 for (int i = size - 1; i >= 0; --i) {
87 3603520 unsigned int digit = (ull_arr[i] >> shift) & (k_radix - 1);
88 3603520 ull_tmp[--count[digit]] = ull_arr[i];
89 }
90
91 ull_arr.swap(ull_tmp);
92 }
93
94
2/2
✓ Branch 0 taken 450440 times.
✓ Branch 1 taken 289 times.
 450729 for (int i = 0; i < size; ++i) {
95
2/2
✓ Branch 0 taken 450040 times.
✓ Branch 1 taken 400 times.
 900880 arr[i] = ULLToDouble(ull_arr[i]);
96 }
97 }
98
99 281 void KrymovaKLsdSortMergeDoubleOMP::MergeSections(double *left, const double *right, int left_size, int right_size) {
100
1/2
✓ Branch 1 taken 281 times.
✗ Branch 2 not taken.
 281 std::vector<double> temp(left_size);
101
1/2
✓ Branch 0 taken 281 times.
✗ Branch 1 not taken.
 281 std::ranges::copy(left, left + left_size, temp.begin());
102
103 int l = 0;
104 int r = 0;
105 int k = 0;
106
107
2/2
✓ Branch 0 taken 1101698 times.
✓ Branch 1 taken 281 times.
 1101979 while (l < left_size && r < right_size) {
108
2/2
✓ Branch 0 taken 1100872 times.
✓ Branch 1 taken 826 times.
 1101698 if (temp[l] <= right[r]) {
109 1100872 left[k++] = temp[l++];
110 } else {
111 826 left[k++] = right[r++];
112 }
113 }
114
115
2/2
✓ Branch 0 taken 628 times.
✓ Branch 1 taken 281 times.
 909 while (l < left_size) {
116 628 left[k++] = temp[l++];
117 }
118 281 }
119
120 ✗ void KrymovaKLsdSortMergeDoubleOMP::SortSectionsParallel(double *arr, int size, int portion) {
121 48 #pragma omp parallel for default(none) shared(arr, size, portion)
122 for (int i = 0; i < size; i += portion) {
123 int current_size = std::min(portion, size - i);
124 LSDSortDouble(arr + i, current_size);
125 }
126 ✗ }
127
128 48 void KrymovaKLsdSortMergeDoubleOMP::IterativeMergeSort(double *arr, int size, int portion) {
129
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 if (size <= 1) {
130 return;
131 }
132
133 48 SortSectionsParallel(arr, size, portion);
134
135
2/2
✓ Branch 0 taken 131 times.
✓ Branch 1 taken 48 times.
 179 for (int merge_size = portion; merge_size < size; merge_size *= 2) {
136
2/2
✓ Branch 0 taken 328 times.
✓ Branch 1 taken 131 times.
 459 for (int i = 0; i < size; i += 2 * merge_size) {
137 int left_size = merge_size;
138
2/2
✓ Branch 0 taken 47 times.
✓ Branch 1 taken 281 times.
 328 int right_size = std::min(merge_size, size - (i + merge_size));
139
140
2/2
✓ Branch 0 taken 47 times.
✓ Branch 1 taken 281 times.
 328 if (right_size <= 0) {
141 47 continue;
142 }
143
144 281 double *left = arr + i;
145 281 const double *right = arr + i + left_size;
146
147 281 MergeSections(left, right, left_size, right_size);
148 }
149 }
150 }
151
152
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 4 times.
 52 bool KrymovaKLsdSortMergeDoubleOMP::RunImpl() {
153 OutType &output = GetOutput();
154 52 int size = static_cast<int>(output.size());
155
156
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 4 times.
 52 if (size <= 1) {
157 return true;
158 }
159
160 48 int portion = std::max(1, size / (num_threads_ * 2));
161 portion = std::min(portion, 5000);
162
163 48 IterativeMergeSort(output.data(), size, portion);
164
165 return true;
166 }
167
168 52 bool KrymovaKLsdSortMergeDoubleOMP::PostProcessingImpl() {
169 const OutType &output = GetOutput();
170
171
2/2
✓ Branch 0 taken 450432 times.
✓ Branch 1 taken 52 times.
 450484 for (size_t i = 1; i < output.size(); ++i) {
172
1/2
✓ Branch 0 taken 450432 times.
✗ Branch 1 not taken.
 450432 if (output[i] < output[i - 1]) {
173 return false;
174 }
175 }
176
177 return true;
178 }
179
180 } // namespace krymova_k_lsd_sort_merge_double
181