GCC Code Coverage Report

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