GCC Code Coverage Report

Directory: ./
File: tasks/olesnitskiy_v_hoare_sort_simple_merge/omp/src/ops_omp.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 51 53 96.2%
Functions: 8 8 100.0%
Branches: 35 48 72.9%
Line Branch Exec Source
1 #include "olesnitskiy_v_hoare_sort_simple_merge/omp/include/ops_omp.hpp"
2
3 #include <omp.h>
4
5 #include <algorithm>
6 #include <cstddef>
7 #include <stack>
8 #include <utility>
9 #include <vector>
10
11 #include "olesnitskiy_v_hoare_sort_simple_merge/common/include/common.hpp"
12
13 namespace olesnitskiy_v_hoare_sort_simple_merge {
14
15
1/2
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
 60 OlesnitskiyVHoareSortSimpleMergeOMP::OlesnitskiyVHoareSortSimpleMergeOMP(const InType &in) {
16 SetTypeOfTask(GetStaticTypeOfTask());
17
1/2
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
 60 GetInput() = in;
18 GetOutput() = {};
19 60 }
20
21 820 int OlesnitskiyVHoareSortSimpleMergeOMP::HoarePartition(std::vector<int> &array, int left, int right) {
22 820 const int pivot = array[left + ((right - left) / 2)];
23 820 int i = left - 1;
24 820 int j = right + 1;
25
26 while (true) {
27 2016 ++i;
28
2/2
✓ Branch 0 taken 576 times.
✓ Branch 1 taken 2016 times.
 2592 while (array[i] < pivot) {
29 576 ++i;
30 }
31
32 2016 --j;
33
2/2
✓ Branch 0 taken 984 times.
✓ Branch 1 taken 2016 times.
 3000 while (array[j] > pivot) {
34 984 --j;
35 }
36
37
2/2
✓ Branch 0 taken 820 times.
✓ Branch 1 taken 1196 times.
 2016 if (i >= j) {
38 820 return j;
39 }
40
41 std::swap(array[i], array[j]);
42 }
43 }
44
45 56 void OlesnitskiyVHoareSortSimpleMergeOMP::HoareQuickSort(std::vector<int> &array, int left, int right) {
46 std::stack<std::pair<int, int>> stack;
47 stack.emplace(left, right);
48
49
2/2
✓ Branch 0 taken 1696 times.
✓ Branch 1 taken 56 times.
 1752 while (!stack.empty()) {
50 auto [current_left, current_right] = stack.top();
51 stack.pop();
52
53
2/2
✓ Branch 0 taken 876 times.
✓ Branch 1 taken 820 times.
 1696 if (current_left >= current_right) {
54 876 continue;
55 }
56
57 820 const int middle = HoarePartition(array, current_left, current_right);
58
59
2/2
✓ Branch 0 taken 76 times.
✓ Branch 1 taken 744 times.
 820 if ((middle - current_left) > (current_right - (middle + 1))) {
60 stack.emplace(current_left, middle);
61
1/2
✓ Branch 1 taken 76 times.
✗ Branch 2 not taken.
 76 stack.emplace(middle + 1, current_right);
62 } else {
63
2/4
✓ Branch 1 taken 744 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 744 times.
✗ Branch 5 not taken.
 744 stack.emplace(middle + 1, current_right);
64 stack.emplace(current_left, middle);
65 }
66 }
67 56 }
68
69 4 std::vector<int> OlesnitskiyVHoareSortSimpleMergeOMP::SimpleMerge(const std::vector<int> &left_part,
70 const std::vector<int> &right_part) {
71
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 std::vector<int> result;
72
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 result.reserve(left_part.size() + right_part.size());
73
74 std::size_t left_index = 0;
75 std::size_t right_index = 0;
76
77
3/4
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 4 times.
✓ Branch 3 taken 4 times.
 8 while (left_index < left_part.size() && right_index < right_part.size()) {
78
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
 4 if (left_part[left_index] <= right_part[right_index]) {
79 result.push_back(left_part[left_index]);
80 ✗ ++left_index;
81 } else {
82 result.push_back(right_part[right_index]);
83 4 ++right_index;
84 }
85 }
86
87
2/2
✓ Branch 0 taken 256 times.
✓ Branch 1 taken 4 times.
 260 while (left_index < left_part.size()) {
88 result.push_back(left_part[left_index]);
89 256 ++left_index;
90 }
91
92
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
 4 while (right_index < right_part.size()) {
93 result.push_back(right_part[right_index]);
94 ✗ ++right_index;
95 }
96
97 4 return result;
98 }
99
100 60 bool OlesnitskiyVHoareSortSimpleMergeOMP::ValidationImpl() {
101 60 return !GetInput().empty();
102 }
103
104 60 bool OlesnitskiyVHoareSortSimpleMergeOMP::PreProcessingImpl() {
105 60 data_ = GetInput();
106 GetOutput().clear();
107 60 return true;
108 }
109
110
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 4 times.
 60 bool OlesnitskiyVHoareSortSimpleMergeOMP::RunImpl() {
111
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 4 times.
 60 if (data_.size() <= 1) {
112 return true;
113 }
114
115 constexpr std::size_t kBlockSize = 64;
116 56 auto &data = data_;
117 56 const std::size_t size = data.size();
118
119 56 #pragma omp parallel for default(none) shared(size, data)
120 for (std::size_t block_start = 0; block_start < size; block_start += kBlockSize) {
121 const std::size_t block_end = std::min(block_start + kBlockSize, size);
122 if ((block_end - block_start) > 1) {
123 HoareQuickSort(data, static_cast<int>(block_start), static_cast<int>(block_end - 1));
124 }
125 }
126
127
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 56 times.
 60 for (std::size_t merge_width = kBlockSize; merge_width < size; merge_width *= 2) {
128 4 std::vector<int> merged_data(size);
129
130
1/2
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
 4 #pragma omp parallel for default(none) shared(merge_width, size, merged_data, data)
131 for (std::size_t left = 0; left < size; left += (2 * merge_width)) {
132 const std::size_t middle = std::min(left + merge_width, size);
133 const std::size_t right = std::min(left + (2 * merge_width), size);
134
135 if (middle < right) {
136 std::vector<int> left_part(data.begin() + static_cast<std::ptrdiff_t>(left),
137 data.begin() + static_cast<std::ptrdiff_t>(middle));
138 std::vector<int> right_part(data.begin() + static_cast<std::ptrdiff_t>(middle),
139 data.begin() + static_cast<std::ptrdiff_t>(right));
140 std::vector<int> merged_part = SimpleMerge(left_part, right_part);
141 for (std::size_t idx = 0; idx < merged_part.size(); ++idx) {
142 merged_data[left + idx] = merged_part[idx];
143 }
144 } else {
145 std::copy(data.begin() + static_cast<std::ptrdiff_t>(left), data.begin() + static_cast<std::ptrdiff_t>(right),
146 merged_data.begin() + static_cast<std::ptrdiff_t>(left));
147 }
148 }
149
150 data.swap(merged_data);
151 }
152
153 return true;
154 }
155
156
1/2
✓ Branch 0 taken 60 times.
✗ Branch 1 not taken.
 60 bool OlesnitskiyVHoareSortSimpleMergeOMP::PostProcessingImpl() {
157
1/2
✓ Branch 0 taken 60 times.
✗ Branch 1 not taken.
 60 if (!std::ranges::is_sorted(data_)) {
158 return false;
159 }
160 60 GetOutput() = data_;
161 60 return true;
162 }
163
164 } // namespace olesnitskiy_v_hoare_sort_simple_merge
165