GCC Code Coverage Report

Directory: ./
File: tasks/tochilin_e_hoar_sort_sim_mer/omp/src/ops_omp.cpp
Date: 2026-04-02 17:12:27
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 32 times.
✗ Branch 2 not taken.
 32 TochilinEHoarSortSimMerOMP::TochilinEHoarSortSimMerOMP(const InType &in) {
15 SetTypeOfTask(GetStaticTypeOfTask());
16
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 GetInput() = in;
17 32 }
18
19 32 bool TochilinEHoarSortSimMerOMP::ValidationImpl() {
20 32 return !GetInput().empty();
21 }
22
23 32 bool TochilinEHoarSortSimMerOMP::PreProcessingImpl() {
24 32 GetOutput() = GetInput();
25 32 return true;
26 }
27
28 2720 std::pair<int, int> TochilinEHoarSortSimMerOMP::Partition(std::vector<int> &arr, int l, int r) {
29 int i = l;
30 int j = r;
31 2720 const int pivot = arr[(l + r) / 2];
32
33
2/2
✓ Branch 0 taken 6519 times.
✓ Branch 1 taken 2720 times.
 11959 while (i <= j) {
34
2/2
✓ Branch 0 taken 8190 times.
✓ Branch 1 taken 6519 times.
 14709 while (arr[i] < pivot) {
35 8190 ++i;
36 }
37
2/2
✓ Branch 0 taken 8794 times.
✓ Branch 1 taken 6519 times.
 15313 while (arr[j] > pivot) {
38 8794 --j;
39 }
40
2/2
✓ Branch 0 taken 657 times.
✓ Branch 1 taken 5862 times.
 6519 if (i <= j) {
41 std::swap(arr[i], arr[j]);
42 5862 ++i;
43 5862 --j;
44 }
45 }
46
47 2720 return {i, j};
48 }
49
50 604 void TochilinEHoarSortSimMerOMP::QuickSortOMP(std::vector<int> &arr, int low, int high, int depth_limit) {
51 604 std::vector<std::pair<int, int>> stack;
52
1/2
✓ Branch 1 taken 604 times.
✗ Branch 2 not taken.
 604 stack.emplace_back(low, high);
53
54
2/2
✓ Branch 0 taken 2818 times.
✓ Branch 1 taken 604 times.
 3422 while (!stack.empty()) {
55 const auto [l0, r0] = stack.back();
56 stack.pop_back();
57
58 2818 int l = l0;
59 2818 int r = r0;
60
61
2/2
✓ Branch 0 taken 98 times.
✓ Branch 1 taken 2720 times.
 2818 if (l >= r) {
62 98 continue;
63 }
64
65 2720 const std::pair<int, int> bounds = Partition(arr, l, r);
66 2720 int i = bounds.first;
67 2720 int j = bounds.second;
68
69 const bool spawn_tasks = depth_limit > 0;
70
71
2/2
✓ Branch 0 taken 270 times.
✓ Branch 1 taken 2450 times.
 2720 if (spawn_tasks) {
72 270 #pragma omp task default(none) shared(arr) firstprivate(l, j, depth_limit)
73 QuickSortOMP(arr, l, j, depth_limit - 1);
74
75 270 #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 1060 times.
✓ Branch 1 taken 1390 times.
 2450 if (l < j) {
79
1/2
✓ Branch 1 taken 1060 times.
✗ Branch 2 not taken.
 1060 stack.emplace_back(l, j);
80 }
81
2/2
✓ Branch 0 taken 1154 times.
✓ Branch 1 taken 1296 times.
 2450 if (i < r) {
82
1/2
✓ Branch 1 taken 1154 times.
✗ Branch 2 not taken.
 1154 stack.emplace_back(i, r);
83 }
84 }
85 }
86
87
1/2
✓ Branch 0 taken 604 times.
✗ Branch 1 not taken.
 604 #pragma omp taskwait
88 604 }
89
90 32 std::vector<int> TochilinEHoarSortSimMerOMP::MergeSortedVectors(const std::vector<int> &a, const std::vector<int> &b) {
91
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 std::vector<int> result;
92
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 result.reserve(a.size() + b.size());
93
94
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 std::ranges::merge(a, b, std::back_inserter(result));
95 32 return result;
96 }
97
98
1/2
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
 32 bool TochilinEHoarSortSimMerOMP::RunImpl() {
99 auto &data = GetOutput();
100
101
1/2
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
 32 if (data.empty()) {
102 return false;
103 }
104
105 32 const auto mid = static_cast<std::vector<int>::difference_type>(data.size() / 2);
106
107
1/2
✓ Branch 2 taken 32 times.
✗ Branch 3 not taken.
 32 std::vector<int> left(data.begin(), data.begin() + mid);
108
1/4
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 32 std::vector<int> right(data.begin() + mid, data.end());
109
110 32 #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 32 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 32 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 64 data = MergeSortedVectors(left, right);
120 return true;
121 }
122
123
1/2
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
 32 bool TochilinEHoarSortSimMerOMP::PostProcessingImpl() {
124 32 return std::ranges::is_sorted(GetOutput());
125 }
126
127 } // namespace tochilin_e_hoar_sort_sim_mer
128