GCC Code Coverage Report

Directory: ./
File: tasks/tochilin_e_hoar_sort_sim_mer/omp/src/ops_omp.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 53 53 100.0%
Functions: 8 8 100.0%
Branches: 34 54 63.0%
Line Branch Exec Source
1 #include "tochilin_e_hoar_sort_sim_mer/omp/include/ops_omp.hpp"
2
3 #include <omp.h>
4
5 #include <algorithm>
6 #include <iterator>
7 #include <utility>
8 #include <vector>
9
10 #include "tochilin_e_hoar_sort_sim_mer/common/include/common.hpp"
11
12 namespace tochilin_e_hoar_sort_sim_mer {
13
14
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 TochilinEHoarSortSimMerOMP::TochilinEHoarSortSimMerOMP(const InType &in) {
15 SetTypeOfTask(GetStaticTypeOfTask());
16
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 GetInput() = in;
17 40 }
18
19 40 bool TochilinEHoarSortSimMerOMP::ValidationImpl() {
20 40 return !GetInput().empty();
21 }
22
23 40 bool TochilinEHoarSortSimMerOMP::PreProcessingImpl() {
24 40 GetOutput() = GetInput();
25 40 return true;
26 }
27
28 13216 std::pair<int, int> TochilinEHoarSortSimMerOMP::Partition(std::vector<int> &arr, int l, int r) {
29 int i = l;
30 int j = r;
31 13216 const int pivot = arr[(l + r) / 2];
32
33
2/2
✓ Branch 0 taken 40552 times.
✓ Branch 1 taken 13216 times.
 66984 while (i <= j) {
34
2/2
✓ Branch 0 taken 50484 times.
✓ Branch 1 taken 40552 times.
 91036 while (arr[i] < pivot) {
35 50484 ++i;
36 }
37
2/2
✓ Branch 0 taken 57636 times.
✓ Branch 1 taken 40552 times.
 98188 while (arr[j] > pivot) {
38 57636 --j;
39 }
40
2/2
✓ Branch 0 taken 3944 times.
✓ Branch 1 taken 36608 times.
 40552 if (i <= j) {
41 std::swap(arr[i], arr[j]);
42 36608 ++i;
43 36608 --j;
44 }
45 }
46
47 13216 return {i, j};
48 }
49
50 848 void TochilinEHoarSortSimMerOMP::QuickSortOMP(std::vector<int> &arr, int low, int high, int depth_limit) {
51 848 std::vector<std::pair<int, int>> stack;
52
1/2
✓ Branch 1 taken 848 times.
✗ Branch 2 not taken.
 848 stack.emplace_back(low, high);
53
54
2/2
✓ Branch 0 taken 13312 times.
✓ Branch 1 taken 848 times.
 14160 while (!stack.empty()) {
55 const auto [l0, r0] = stack.back();
56 stack.pop_back();
57
58 13312 int l = l0;
59 13312 int r = r0;
60
61
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 13216 times.
 13312 if (l >= r) {
62 96 continue;
63 }
64
65 13216 const std::pair<int, int> bounds = Partition(arr, l, r);
66 13216 int i = bounds.first;
67 13216 int j = bounds.second;
68
69 const bool spawn_tasks = depth_limit > 0;
70
71
2/2
✓ Branch 0 taken 384 times.
✓ Branch 1 taken 12832 times.
 13216 if (spawn_tasks) {
72 384 #pragma omp task default(none) shared(arr) firstprivate(l, j, depth_limit)
73 QuickSortOMP(arr, l, j, depth_limit - 1);
74
75 384 #pragma omp task default(none) shared(arr) firstprivate(i, r, depth_limit)
76 QuickSortOMP(arr, i, r, depth_limit - 1);
77 } else {
78
2/2
✓ Branch 0 taken 6136 times.
✓ Branch 1 taken 6696 times.
 12832 if (l < j) {
79
1/2
✓ Branch 1 taken 6136 times.
✗ Branch 2 not taken.
 6136 stack.emplace_back(l, j);
80 }
81
2/2
✓ Branch 0 taken 6328 times.
✓ Branch 1 taken 6504 times.
 12832 if (i < r) {
82
1/2
✓ Branch 1 taken 6328 times.
✗ Branch 2 not taken.
 6328 stack.emplace_back(i, r);
83 }
84 }
85 }
86
87
1/2
✓ Branch 0 taken 848 times.
✗ Branch 1 not taken.
 848 #pragma omp taskwait
88 848 }
89
90 40 std::vector<int> TochilinEHoarSortSimMerOMP::MergeSortedVectors(const std::vector<int> &a, const std::vector<int> &b) {
91
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 std::vector<int> result;
92
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 result.reserve(a.size() + b.size());
93
94
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 std::ranges::merge(a, b, std::back_inserter(result));
95 40 return result;
96 }
97
98
1/2
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
 40 bool TochilinEHoarSortSimMerOMP::RunImpl() {
99 auto &data = GetOutput();
100
101
1/2
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
 40 if (data.empty()) {
102 return false;
103 }
104
105 40 const auto mid = static_cast<std::vector<int>::difference_type>(data.size() / 2);
106
107
1/2
✓ Branch 2 taken 40 times.
✗ Branch 3 not taken.
 40 std::vector<int> left(data.begin(), data.begin() + mid);
108
1/4
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 40 std::vector<int> right(data.begin() + mid, data.end());
109
110 40 #pragma omp parallel default(none) shared(left, right)
111 {
112 #pragma omp single
113 {
114 QuickSortOMP(left, 0, static_cast<int>(left.size()) - 1, 3);
115 QuickSortOMP(right, 0, static_cast<int>(right.size()) - 1, 3);
116 }
117 }
118
119
2/6
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 40 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 80 data = MergeSortedVectors(left, right);
120 return true;
121 }
122
123
1/2
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
 40 bool TochilinEHoarSortSimMerOMP::PostProcessingImpl() {
124 40 return std::ranges::is_sorted(GetOutput());
125 }
126
127 } // namespace tochilin_e_hoar_sort_sim_mer
128