GCC Code Coverage Report

Directory: ./
File: tasks/yushkova_p_hoare_sorting_simple_merging/omp/src/ops_omp.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 61 61 100.0%
Functions: 8 8 100.0%
Branches: 48 62 77.4%
Line Branch Exec Source
1 #include "yushkova_p_hoare_sorting_simple_merging/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 "yushkova_p_hoare_sorting_simple_merging/common/include/common.hpp"
12
13 namespace yushkova_p_hoare_sorting_simple_merging {
14
15
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 YushkovaPHoareSortingSimpleMergingOMP::YushkovaPHoareSortingSimpleMergingOMP(const InType &in) {
16 SetTypeOfTask(GetStaticTypeOfTask());
17
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 GetInput() = in;
18 GetOutput().clear();
19 40 }
20
21 161 int YushkovaPHoareSortingSimpleMergingOMP::HoarePartition(std::vector<int> &values, int left, int right) {
22 161 const int pivot = values[left + ((right - left) / 2)];
23 161 int i = left - 1;
24 161 int j = right + 1;
25
26 while (true) {
27 286 ++i;
28
2/2
✓ Branch 0 taken 42 times.
✓ Branch 1 taken 286 times.
 328 while (values[i] < pivot) {
29 42 ++i;
30 }
31
32 286 --j;
33
2/2
✓ Branch 0 taken 103 times.
✓ Branch 1 taken 286 times.
 389 while (values[j] > pivot) {
34 103 --j;
35 }
36
37
2/2
✓ Branch 0 taken 161 times.
✓ Branch 1 taken 125 times.
 286 if (i >= j) {
38 161 return j;
39 }
40
41 std::swap(values[i], values[j]);
42 }
43 }
44
45 68 void YushkovaPHoareSortingSimpleMergingOMP::HoareQuickSort(std::vector<int> &values, int left, int right) {
46 std::stack<std::pair<int, int>> ranges;
47 ranges.emplace(left, right);
48
49
2/2
✓ Branch 0 taken 390 times.
✓ Branch 1 taken 68 times.
 458 while (!ranges.empty()) {
50 auto [current_left, current_right] = ranges.top();
51 ranges.pop();
52
53
2/2
✓ Branch 0 taken 229 times.
✓ Branch 1 taken 161 times.
 390 if (current_left >= current_right) {
54 229 continue;
55 }
56
57 161 const int partition_index = HoarePartition(values, current_left, current_right);
58
59
2/2
✓ Branch 0 taken 34 times.
✓ Branch 1 taken 127 times.
 161 if ((partition_index - current_left) > (current_right - (partition_index + 1))) {
60 ranges.emplace(current_left, partition_index);
61
1/2
✓ Branch 1 taken 34 times.
✗ Branch 2 not taken.
 34 ranges.emplace(partition_index + 1, current_right);
62 } else {
63
2/4
✓ Branch 1 taken 127 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 127 times.
✗ Branch 5 not taken.
 127 ranges.emplace(partition_index + 1, current_right);
64 ranges.emplace(current_left, partition_index);
65 }
66 }
67 68 }
68
69 51 void YushkovaPHoareSortingSimpleMergingOMP::Merge(std::vector<int> &values, int left, int mid, int right) {
70 51 std::vector<int> merged;
71 51 const int merged_size = (right - left) + 1;
72
1/2
✓ Branch 1 taken 51 times.
✗ Branch 2 not taken.
 51 merged.reserve(static_cast<std::size_t>(merged_size));
73
74 int left_index = left;
75 51 int right_index = mid + 1;
76
77
2/2
✓ Branch 0 taken 193 times.
✓ Branch 1 taken 51 times.
 244 while (left_index <= mid && right_index <= right) {
78
2/2
✓ Branch 0 taken 84 times.
✓ Branch 1 taken 109 times.
 193 if (values[left_index] <= values[right_index]) {
79
1/2
✓ Branch 0 taken 84 times.
✗ Branch 1 not taken.
 84 merged.push_back(values[left_index++]);
80 } else {
81
1/2
✓ Branch 0 taken 109 times.
✗ Branch 1 not taken.
 109 merged.push_back(values[right_index++]);
82 }
83 }
84
85
2/2
✓ Branch 0 taken 81 times.
✓ Branch 1 taken 51 times.
 132 while (left_index <= mid) {
86
1/2
✓ Branch 0 taken 81 times.
✗ Branch 1 not taken.
 81 merged.push_back(values[left_index++]);
87 }
88
89
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 51 times.
 69 while (right_index <= right) {
90
1/2
✓ Branch 0 taken 18 times.
✗ Branch 1 not taken.
 18 merged.push_back(values[right_index++]);
91 }
92
93
2/2
✓ Branch 0 taken 292 times.
✓ Branch 1 taken 51 times.
 343 for (std::size_t idx = 0; idx < merged.size(); ++idx) {
94 292 values[static_cast<std::size_t>(left) + idx] = merged[idx];
95 }
96 51 }
97
98 40 bool YushkovaPHoareSortingSimpleMergingOMP::ValidationImpl() {
99 40 return !GetInput().empty();
100 }
101
102 40 bool YushkovaPHoareSortingSimpleMergingOMP::PreProcessingImpl() {
103 40 GetOutput() = GetInput();
104 40 return true;
105 }
106
107
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 36 times.
 40 bool YushkovaPHoareSortingSimpleMergingOMP::RunImpl() {
108 std::vector<int> &values = GetOutput();
109 40 const int n = static_cast<int>(values.size());
110
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 36 times.
 40 if (n <= 1) {
111 return true;
112 }
113
114
2/2
✓ Branch 1 taken 9 times.
✓ Branch 2 taken 27 times.
 36 const int max_threads = std::max(1, omp_get_max_threads());
115 const int chunks = std::min(max_threads, n);
116
117
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 27 times.
 36 if (chunks == 1) {
118 9 HoareQuickSort(values, 0, n - 1);
119 return std::ranges::is_sorted(values);
120 }
121
122 27 std::vector<int> borders(static_cast<std::size_t>(chunks + 1));
123
2/2
✓ Branch 0 taken 105 times.
✓ Branch 1 taken 27 times.
 132 for (int i = 0; i <= chunks; ++i) {
124 105 borders[static_cast<std::size_t>(i)] = (i * n) / chunks;
125 }
126
127 27 #pragma omp parallel for default(none) shared(values, borders, chunks)
128 for (int chunk = 0; chunk < chunks; ++chunk) {
129 const int left = borders[static_cast<std::size_t>(chunk)];
130 const int right = borders[static_cast<std::size_t>(chunk) + 1] - 1;
131 if (left < right) {
132 HoareQuickSort(values, left, right);
133 }
134 }
135
136
2/2
✓ Branch 0 taken 51 times.
✓ Branch 1 taken 27 times.
 78 for (int i = 0; i < chunks - 1; ++i) {
137
1/2
✓ Branch 1 taken 51 times.
✗ Branch 2 not taken.
 51 const int mid = borders[static_cast<std::size_t>(i) + 1] - 1;
138 51 const int right = borders[static_cast<std::size_t>(i) + 2] - 1;
139
1/2
✓ Branch 1 taken 51 times.
✗ Branch 2 not taken.
 51 Merge(values, 0, mid, right);
140 }
141
142 return std::ranges::is_sorted(values);
143 }
144
145
1/2
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
 40 bool YushkovaPHoareSortingSimpleMergingOMP::PostProcessingImpl() {
146
1/2
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
 40 return !GetOutput().empty() && std::ranges::is_sorted(GetOutput());
147 }
148
149 } // namespace yushkova_p_hoare_sorting_simple_merging
150