GCC Code Coverage Report

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