GCC Code Coverage Report

Directory: ./
File: tasks/shekhirev_v_hoare_batcher_sort/omp/src/ops_omp.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 51 51 100.0%
Functions: 7 7 100.0%
Branches: 34 44 77.3%
Line Branch Exec Source
1 #include "shekhirev_v_hoare_batcher_sort/omp/include/ops_omp.hpp"
2
3 #include <omp.h>
4
5 #include <algorithm>
6 #include <climits>
7 #include <utility>
8 #include <vector>
9
10 #include "shekhirev_v_hoare_batcher_sort/common/include/common.hpp"
11
12 namespace shekhirev_v_hoare_batcher_sort {
13
14 namespace {
15
16 54 void HoareSort(std::vector<int> &arr, int low, int high) {
17 54 std::vector<std::pair<int, int>> stack;
18
1/2
✓ Branch 1 taken 54 times.
✗ Branch 2 not taken.
 54 stack.emplace_back(low, high);
19
20
2/2
✓ Branch 0 taken 9354 times.
✓ Branch 1 taken 54 times.
 9408 while (!stack.empty()) {
21 auto [l, h] = stack.back();
22 stack.pop_back();
23
24
2/2
✓ Branch 0 taken 4704 times.
✓ Branch 1 taken 4650 times.
 9354 if (l >= h) {
25 4704 continue;
26 }
27
28 4650 int pivot = arr[l + ((h - l) / 2)];
29 4650 int i = l - 1;
30 4650 int j = h + 1;
31
32 while (true) {
33
2/2
✓ Branch 0 taken 11245 times.
✓ Branch 1 taken 12789 times.
 24034 while (arr[++i] < pivot) {
34 }
35
2/2
✓ Branch 0 taken 13844 times.
✓ Branch 1 taken 12789 times.
 26633 while (arr[--j] > pivot) {
36 }
37
2/2
✓ Branch 0 taken 8139 times.
✓ Branch 1 taken 4650 times.
 12789 if (i >= j) {
38 break;
39 }
40 std::swap(arr[i], arr[j]);
41 }
42
43
1/2
✓ Branch 1 taken 4650 times.
✗ Branch 2 not taken.
 4650 stack.emplace_back(l, j);
44
1/4
✓ Branch 1 taken 4650 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 4650 stack.emplace_back(j + 1, h);
45 }
46 54 }
47
48 24 void BatcherMerge(std::vector<int> &a, int n_pow2, int chunk_size) {
49
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 24 times.
 48 for (int step_p = chunk_size; step_p < n_pow2; step_p *= 2) {
50
2/2
✓ Branch 0 taken 150 times.
✓ Branch 1 taken 24 times.
 174 for (int step_k = step_p; step_k >= 1; step_k /= 2) {
51 int start = step_k;
52 150 int num_blocks = (n_pow2 / (2 * step_k)) - 1;
53
54
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 126 times.
 150 if (step_k == step_p) {
55 start = 0;
56 num_blocks = n_pow2 / (2 * step_k);
57 }
58
59 150 int total_pairs = num_blocks * step_k;
60
61 150 #pragma omp parallel for default(none) shared(a, step_p, step_k, start, total_pairs)
62 for (int step = 0; step < total_pairs; ++step) {
63 int i = step % step_k;
64 int b = step / step_k;
65 int j = start + (b * (step_k * 2));
66
67 int idx1 = i + j;
68 int idx2 = i + j + step_k;
69
70 if ((idx1 / (step_p * 2)) == (idx2 / (step_p * 2)) && a[idx1] > a[idx2]) {
71 std::swap(a[idx1], a[idx2]);
72 }
73 }
74 }
75 }
76 24 }
77
78 } // namespace
79
80
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 ShekhirevHoareBatcherSortOMP::ShekhirevHoareBatcherSortOMP(const InType &in) {
81 SetTypeOfTask(GetStaticTypeOfTask());
82
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 GetInput() = in;
83 GetOutput().clear();
84 32 }
85
86 32 bool ShekhirevHoareBatcherSortOMP::ValidationImpl() {
87 32 return true;
88 }
89
90 32 bool ShekhirevHoareBatcherSortOMP::PreProcessingImpl() {
91 32 input_ = GetInput();
92 32 return true;
93 }
94
95
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 24 times.
 32 bool ShekhirevHoareBatcherSortOMP::RunImpl() {
96 32 int n = static_cast<int>(input_.size());
97
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 24 times.
 32 if (n <= 1) {
98 8 res_.assign(input_.begin(), input_.end());
99 8 return true;
100 }
101
102 int n_pow2 = 1;
103
2/2
✓ Branch 0 taken 156 times.
✓ Branch 1 taken 24 times.
 180 while (n_pow2 < n) {
104 156 n_pow2 *= 2;
105 }
106
107 24 std::vector<int> a(n_pow2, INT_MAX);
108
2/2
✓ Branch 0 taken 4420 times.
✓ Branch 1 taken 24 times.
 4444 for (int i = 0; i < n; i++) {
109 4420 a[i] = input_[i];
110 }
111
112 24 int num_threads = omp_get_max_threads();
113 24 if (num_threads <= 0) {
114 num_threads = 1;
115 }
116
117 int p_threads = 1;
118
3/4
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
 48 while ((p_threads * 2) <= num_threads && (p_threads * 2) <= n_pow2) {
119 p_threads *= 2;
120 }
121
122 24 int chunk_size = n_pow2 / p_threads;
123
124 24 #pragma omp parallel for default(none) shared(a, p_threads, chunk_size)
125 for (int i = 0; i < p_threads; i++) {
126 HoareSort(a, i * chunk_size, ((i + 1) * chunk_size) - 1);
127 }
128
129 24 BatcherMerge(a, n_pow2, chunk_size);
130
131
2/4
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 24 times.
✗ Branch 4 not taken.
 24 res_.assign(a.begin(), a.begin() + n);
132 return true;
133 }
134
135 32 bool ShekhirevHoareBatcherSortOMP::PostProcessingImpl() {
136 32 GetOutput() = res_;
137 32 return true;
138 }
139
140 } // namespace shekhirev_v_hoare_batcher_sort
141