GCC Code Coverage Report

Directory: ./
File: tasks/timofeev_n_radix_batcher_sort/omp/src/ops_omp.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 47 56 83.9%
Functions: 7 10 70.0%
Branches: 41 54 75.9%
Line Branch Exec Source
1 #include "timofeev_n_radix_batcher_sort/omp/include/ops_omp.hpp"
2
3 #include <omp.h>
4
5 #include <algorithm>
6 #include <climits>
7 #include <cstddef>
8 #include <utility>
9 #include <vector>
10
11 #include "timofeev_n_radix_batcher_sort/common/include/common.hpp"
12
13 namespace timofeev_n_radix_batcher_sort_threads {
14
15
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 TimofeevNRadixBatcherOMP::TimofeevNRadixBatcherOMP(const InType &in) {
16 SetTypeOfTask(GetStaticTypeOfTask());
17
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 GetInput() = in;
18
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 GetOutput() = in;
19 12 }
20
21 ✗ void TimofeevNRadixBatcherOMP::CompExch(int &a, int &b, int digit) {
22 1302 int b_r = b % (digit * 10) / digit;
23 1302 int a_r = a % (digit * 10) / digit;
24
2/4
✓ Branch 0 taken 194 times.
✓ Branch 1 taken 1108 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 1302 if (b_r < a_r) {
25 std::swap(a, b);
26 }
27 ✗ }
28
29 34 void TimofeevNRadixBatcherOMP::BubbleSort(std::vector<int> &arr, int digit, int left, int right) {
30
2/2
✓ Branch 0 taken 210 times.
✓ Branch 1 taken 34 times.
 244 for (int i = left; i <= right; i++) {
31
2/2
✓ Branch 0 taken 1302 times.
✓ Branch 1 taken 210 times.
 1512 for (int j = 0; j + 1 < right - left; j++) {
32
2/2
✓ Branch 0 taken 194 times.
✓ Branch 1 taken 1108 times.
 1302 CompExch(arr[left + j], arr[left + j + 1], digit);
33 }
34 }
35 34 }
36
37 ✗ void TimofeevNRadixBatcherOMP::ComparR(int &a, int &b) {
38
2/4
✓ Branch 0 taken 17 times.
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 81 if (a > b) {
39 std::swap(a, b);
40 }
41 ✗ }
42
43 13 void TimofeevNRadixBatcherOMP::OddEvenMerge(std::vector<int> &arr, int lft, int n) {
44
1/2
✓ Branch 0 taken 13 times.
✗ Branch 1 not taken.
 13 if (n <= 1) {
45 return;
46 }
47
48 13 int otstup = n / 2;
49
2/2
✓ Branch 0 taken 54 times.
✓ Branch 1 taken 13 times.
 67 for (int i = 0; i < otstup; i += 1) {
50
2/2
✓ Branch 0 taken 17 times.
✓ Branch 1 taken 37 times.
 54 if (arr[lft + i] > arr[lft + otstup + i]) {
51 std::swap(arr[lft + i], arr[lft + otstup + i]);
52 }
53 }
54
55
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 13 times.
 37 for (otstup = n / 4; otstup > 0; otstup /= 2) {
56 24 int h = otstup * 2;
57
2/2
✓ Branch 0 taken 58 times.
✓ Branch 1 taken 24 times.
 82 for (int start = otstup; start + otstup < n; start += h) {
58
2/2
✓ Branch 0 taken 81 times.
✓ Branch 1 taken 58 times.
 139 for (int i = 0; i < otstup; i += 1) {
59
2/2
✓ Branch 0 taken 17 times.
✓ Branch 1 taken 64 times.
 81 ComparR(arr[lft + start + i], arr[lft + start + i + otstup]);
60 }
61 }
62 }
63 }
64
65 ✗ int TimofeevNRadixBatcherOMP::Loggo(int inputa) {
66 int count = 0;
67 ✗ while (inputa > 1) {
68 ✗ inputa /= 2;
69 ✗ count++;
70 }
71 ✗ return count;
72 }
73
74 12 bool TimofeevNRadixBatcherOMP::ValidationImpl() {
75 12 return GetInput().size() >= 2;
76 }
77
78 12 bool TimofeevNRadixBatcherOMP::PreProcessingImpl() {
79 12 return true;
80 }
81
82 12 bool TimofeevNRadixBatcherOMP::RunImpl() {
83 12 std::vector<int> in = GetInput();
84 12 int n = static_cast<int>(in.size());
85 int m = n;
86
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 12 times.
 28 while (n % 2 == 0) {
87 16 n /= 2;
88 }
89
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 4 times.
 12 if (n > 1) {
90 n = static_cast<int>(in.size());
91 int p = 1;
92
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 8 times.
 28 while (p < n) {
93 20 p *= 2;
94 }
95 n = p;
96 } else {
97 n = m;
98 }
99 12 int max_x = *(std::ranges::max_element(in.begin(), in.end()));
100
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 4 times.
 12 if (n != m) {
101
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 in.resize(n, max_x);
102 }
103 12 size_t n_thr = omp_get_max_threads();
104 size_t num_threads = 1;
105
4/4
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 11 times.
✓ Branch 2 taken 11 times.
✓ Branch 3 taken 1 times.
 23 while (num_threads * 2 <= n_thr && n / num_threads >= 4) {
106 num_threads *= 2;
107 }
108 std::vector<int> &r_in = in;
109 12 size_t n_n = n;
110 12 size_t m_m = m;
111 std::vector<int> &reff = GetInput();
112
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 #pragma omp parallel num_threads(num_threads) default(none) shared(r_in, max_x, n_n, num_threads, m_m, reff)
113 {
114 size_t t_n = omp_get_thread_num();
115 size_t piece = n_n / num_threads;
116 for (int k = 1; k <= max_x; k *= 10) {
117 BubbleSort(r_in, k, static_cast<int>(piece * t_n), static_cast<int>((piece * t_n) + piece)); // [left; right)
118 }
119 #pragma omp barrier
120 size_t c_p = piece * 2;
121 for (; c_p <= n_n; c_p *= 2) {
122 #pragma omp for
123 for (size_t i = 0; i < n_n; i += c_p) {
124 OddEvenMerge(r_in, static_cast<int>(i), static_cast<int>(c_p));
125 }
126 #pragma omp barrier
127 }
128 if (t_n == 0 && m_m != n_n) {
129 r_in.resize(m_m);
130 }
131 #pragma omp barrier
132 #pragma omp for
133 for (size_t i = 0; i < r_in.size(); i++) {
134 reff[i] = r_in[i];
135 }
136 #pragma omp barrier
137 }
138
139
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 GetOutput() = reff;
140 12 return true;
141 }
142
143 12 bool TimofeevNRadixBatcherOMP::PostProcessingImpl() {
144 12 return true;
145 }
146
147 } // namespace timofeev_n_radix_batcher_sort_threads
148