GCC Code Coverage Report

Directory: ./
File: tasks/smetanin_d_hoare_even_odd_batchelor/omp/src/ops_omp.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 53 53 100.0%
Functions: 9 9 100.0%
Branches: 30 36 83.3%
Line Branch Exec Source
1 #include "smetanin_d_hoare_even_odd_batchelor/omp/include/ops_omp.hpp"
2
3 #include <stack>
4 #include <utility>
5 #include <vector>
6
7 #include "smetanin_d_hoare_even_odd_batchelor/common/include/common.hpp"
8
9 namespace smetanin_d_hoare_even_odd_batchelor {
10
11 namespace {
12
13 constexpr int kTaskCutoff = 1000;
14
15 44428 int HoarePartition(std::vector<int> &arr, int lo, int hi) {
16 44428 int pivot = arr[lo + ((hi - lo) / 2)];
17 44428 int i = lo - 1;
18 44428 int j = hi + 1;
19 while (true) {
20 172456 ++i;
21
2/2
✓ Branch 0 taken 234458 times.
✓ Branch 1 taken 172456 times.
 406914 while (arr[i] < pivot) {
22 234458 ++i;
23 }
24 172456 --j;
25
2/2
✓ Branch 0 taken 251740 times.
✓ Branch 1 taken 172456 times.
 424196 while (arr[j] > pivot) {
26 251740 --j;
27 }
28
2/2
✓ Branch 0 taken 44428 times.
✓ Branch 1 taken 128028 times.
 172456 if (i >= j) {
29 44428 return j;
30 }
31 std::swap(arr[i], arr[j]);
32 }
33 }
34
35 44428 void OddEvenMerge(std::vector<int> &arr, int lo, int hi) {
36 44428 int n = hi - lo + 1;
37
2/2
✓ Branch 0 taken 108875 times.
✓ Branch 1 taken 44428 times.
 153303 for (int step = 1; step < n; step *= 2) {
38
2/2
✓ Branch 0 taken 716921 times.
✓ Branch 1 taken 108875 times.
 825796 for (int i = lo; i + step <= hi; i += step * 2) {
39
2/2
✓ Branch 0 taken 241908 times.
✓ Branch 1 taken 475013 times.
 716921 if (arr[i] > arr[i + step]) {
40 std::swap(arr[i], arr[i + step]);
41 }
42 }
43 }
44 44428 }
45
46 100 void HoarSortBatcherSeq(std::vector<int> &arr, int lo, int hi) {
47 std::stack<std::pair<int, int>> stk;
48 stk.emplace(lo, hi);
49
2/2
✓ Branch 0 taken 88796 times.
✓ Branch 1 taken 100 times.
 88896 while (!stk.empty()) {
50 auto [l, r] = stk.top();
51 stk.pop();
52
2/2
✓ Branch 0 taken 44448 times.
✓ Branch 1 taken 44348 times.
 88796 if (l >= r) {
53 44448 continue;
54 }
55 44348 int p = HoarePartition(arr, l, r);
56
2/2
✓ Branch 0 taken 15514 times.
✓ Branch 1 taken 28834 times.
 44348 if ((p - l) > (r - p - 1)) {
57 stk.emplace(l, p);
58
1/2
✓ Branch 1 taken 15514 times.
✗ Branch 2 not taken.
 15514 stk.emplace(p + 1, r);
59 } else {
60
2/4
✓ Branch 1 taken 28834 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 28834 times.
✗ Branch 5 not taken.
 28834 stk.emplace(p + 1, r);
61 stk.emplace(l, p);
62 }
63 44348 OddEvenMerge(arr, l, r);
64 }
65 100 }
66
67 180 void HoarSortBatcherOMPImpl(std::vector<int> &arr, int lo, int hi) {
68
1/2
✓ Branch 0 taken 180 times.
✗ Branch 1 not taken.
 180 if (lo >= hi) {
69 return;
70 }
71
2/2
✓ Branch 0 taken 100 times.
✓ Branch 1 taken 80 times.
 180 if (hi - lo < kTaskCutoff) {
72 100 HoarSortBatcherSeq(arr, lo, hi);
73 100 return;
74 }
75 80 int p = HoarePartition(arr, lo, hi);
76 80 OddEvenMerge(arr, lo, hi);
77 80 #pragma omp task default(none) shared(arr) firstprivate(lo, p)
78 HoarSortBatcherOMPImpl(arr, lo, p);
79 80 #pragma omp task default(none) shared(arr) firstprivate(hi, p)
80 HoarSortBatcherOMPImpl(arr, p + 1, hi);
81 80 #pragma omp taskwait
82 }
83
84 } // namespace
85
86
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 SmetaninDHoarSortOMP::SmetaninDHoarSortOMP(const InType &in) {
87 SetTypeOfTask(GetStaticTypeOfTask());
88
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 GetInput() = in;
89 28 }
90
91 28 bool SmetaninDHoarSortOMP::ValidationImpl() {
92 28 return true;
93 }
94
95 28 bool SmetaninDHoarSortOMP::PreProcessingImpl() {
96 28 GetOutput() = GetInput();
97 28 return true;
98 }
99
100
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 8 times.
 28 bool SmetaninDHoarSortOMP::RunImpl() {
101 auto &data = GetOutput();
102 28 int n = static_cast<int>(data.size());
103
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 8 times.
 28 if (n > 1) {
104 20 #pragma omp parallel default(none) shared(data, n)
105 #pragma omp single
106 HoarSortBatcherOMPImpl(data, 0, n - 1);
107 }
108 28 return true;
109 }
110
111 28 bool SmetaninDHoarSortOMP::PostProcessingImpl() {
112 28 return true;
113 }
114
115 } // namespace smetanin_d_hoare_even_odd_batchelor
116