GCC Code Coverage Report

Directory: ./
File: tasks/nikitina_v_hoar_sort_batcher/omp/src/ops_omp.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 73 75 97.3%
Functions: 9 9 100.0%
Branches: 55 74 74.3%
Line Branch Exec Source
1 #include "nikitina_v_hoar_sort_batcher/omp/include/ops_omp.hpp"
2
3 #include <omp.h>
4
5 #include <algorithm>
6 #include <limits>
7 #include <utility>
8 #include <vector>
9
10 #include "nikitina_v_hoar_sort_batcher/common/include/common.hpp"
11
12 namespace nikitina_v_hoar_sort_batcher {
13
14 namespace {
15
16 27 void QuickSortHoare(std::vector<int> &arr, int low, int high) {
17
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 27 times.
 27 if (low >= high) {
18 ✗ return;
19 }
20 27 std::vector<std::pair<int, int>> stack;
21
1/2
✓ Branch 1 taken 27 times.
✗ Branch 2 not taken.
 27 stack.emplace_back(low, high);
22
23
2/2
✓ Branch 0 taken 233 times.
✓ Branch 1 taken 27 times.
 260 while (!stack.empty()) {
24 auto [l, h] = stack.back();
25 stack.pop_back();
26
27
2/2
✓ Branch 0 taken 130 times.
✓ Branch 1 taken 103 times.
 233 if (l >= h) {
28 130 continue;
29 }
30
31 103 int pivot = arr[l + ((h - l) / 2)];
32 103 int i = l - 1;
33 103 int j = h + 1;
34
35 while (true) {
36 176 i++;
37
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 176 times.
 236 while (arr[i] < pivot) {
38 60 i++;
39 }
40
41 176 j--;
42
2/2
✓ Branch 0 taken 124 times.
✓ Branch 1 taken 176 times.
 300 while (arr[j] > pivot) {
43 124 j--;
44 }
45
46
2/2
✓ Branch 0 taken 73 times.
✓ Branch 1 taken 103 times.
 176 if (i >= j) {
47 break;
48 }
49 std::swap(arr[i], arr[j]);
50 }
51
52
1/2
✓ Branch 1 taken 103 times.
✗ Branch 2 not taken.
 103 stack.emplace_back(l, j);
53
1/4
✓ Branch 1 taken 103 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 103 stack.emplace_back(j + 1, h);
54 }
55 }
56
57 21 void CompareSplit(std::vector<int> &arr, int start1, int len1, int start2, int len2) {
58
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 21 times.
 21 if (len1 == 0 || len2 == 0) {
59 ✗ return;
60 }
61
62
1/2
✓ Branch 2 taken 21 times.
✗ Branch 3 not taken.
 21 std::vector<int> left_block(arr.begin() + start1, arr.begin() + start1 + len1);
63
1/4
✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 21 std::vector<int> right_block(arr.begin() + start2, arr.begin() + start2 + len2);
64
65 int p1 = 0;
66 int p2 = 0;
67 int write1 = start1;
68 int write2 = start2;
69
70
2/2
✓ Branch 0 taken 154 times.
✓ Branch 1 taken 21 times.
 175 for (int i = 0; i < len1 + len2; ++i) {
71 int val = 0;
72
6/6
✓ Branch 0 taken 124 times.
✓ Branch 1 taken 30 times.
✓ Branch 2 taken 116 times.
✓ Branch 3 taken 8 times.
✓ Branch 4 taken 69 times.
✓ Branch 5 taken 47 times.
 154 if (p1 < len1 && (p2 == len2 || left_block[p1] <= right_block[p2])) {
73 77 val = left_block[p1++];
74 } else {
75 77 val = right_block[p2++];
76 }
77
78
2/2
✓ Branch 0 taken 77 times.
✓ Branch 1 taken 77 times.
 154 if (i < len1) {
79 77 arr[write1++] = val;
80 } else {
81 77 arr[write2++] = val;
82 }
83 }
84 }
85
86 15 void BuildPairs(std::vector<std::pair<int, int>> &pairs, int num_threads, int step_p, int step_k) {
87
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 15 times.
 33 for (int idx_j = step_k % step_p; idx_j + step_k < num_threads; idx_j += (step_k * 2)) {
88
2/2
✓ Branch 0 taken 21 times.
✓ Branch 1 taken 18 times.
 39 for (int idx_i = 0; idx_i < std::min(step_k, num_threads - idx_j - step_k); idx_i++) {
89
1/2
✓ Branch 0 taken 21 times.
✗ Branch 1 not taken.
 21 if ((idx_j + idx_i) / (step_p * 2) == (idx_j + idx_i + step_k) / (step_p * 2)) {
90 21 pairs.emplace_back(idx_j + idx_i, idx_j + idx_i + step_k);
91 }
92 }
93 }
94 15 }
95
96 9 void BatcherMergePhase(std::vector<int> &output, const std::vector<int> &offsets, int num_threads) {
97
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 9 times.
 21 for (int step_p = 1; step_p < num_threads; step_p *= 2) {
98
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 12 times.
 27 for (int step_k = step_p; step_k > 0; step_k /= 2) {
99 15 std::vector<std::pair<int, int>> pairs;
100
1/2
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
 15 BuildPairs(pairs, num_threads, step_p, step_k);
101
102 15 int num_pairs = static_cast<int>(pairs.size());
103
104
1/2
✓ Branch 0 taken 15 times.
✗ Branch 1 not taken.
 15 #pragma omp parallel for num_threads(num_threads) default(none) shared(output, offsets, pairs, num_pairs)
105 for (int idx = 0; idx < num_pairs; ++idx) {
106 int block_a = pairs[idx].first;
107 int block_b = pairs[idx].second;
108 CompareSplit(output, offsets[block_a], offsets[block_a + 1] - offsets[block_a], offsets[block_b],
109 offsets[block_b + 1] - offsets[block_b]);
110 }
111 }
112 }
113 9 }
114
115 } // namespace
116
117
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 HoareSortBatcherOMP::HoareSortBatcherOMP(const InType &in) {
118 SetTypeOfTask(GetStaticTypeOfTask());
119
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 GetInput() = in;
120 16 }
121
122 16 bool HoareSortBatcherOMP::ValidationImpl() {
123 16 return true;
124 }
125
126 16 bool HoareSortBatcherOMP::PreProcessingImpl() {
127 16 GetOutput() = GetInput();
128 16 return true;
129 }
130
131
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 4 times.
 16 bool HoareSortBatcherOMP::RunImpl() {
132 auto &output = GetOutput();
133
134 16 int orig_n = static_cast<int>(output.size());
135
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 4 times.
 16 if (orig_n <= 1) {
136 return true;
137 }
138
139 12 int max_threads = omp_get_max_threads();
140 int t = 1;
141
3/4
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
✓ Branch 2 taken 12 times.
✗ Branch 3 not taken.
 24 while (t * 2 <= max_threads && t * 2 <= orig_n) {
142 t *= 2;
143 }
144
145
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 9 times.
 12 if (t == 1) {
146 3 QuickSortHoare(output, 0, orig_n - 1);
147 3 return true;
148 }
149
150 9 int pad = (t - (orig_n % t)) % t;
151
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 9 times.
 19 for (int i = 0; i < pad; ++i) {
152 10 output.push_back(std::numeric_limits<int>::max());
153 }
154
155 9 int n = orig_n + pad;
156 9 std::vector<int> offsets(t + 1, 0);
157 9 int chunk = n / t;
158
2/2
✓ Branch 0 taken 33 times.
✓ Branch 1 taken 9 times.
 42 for (int i = 0; i <= t; ++i) {
159 33 offsets[i] = i * chunk;
160 }
161
162 std::vector<int> &local_output = output;
163
164 9 #pragma omp parallel for num_threads(t) default(none) shared(local_output, offsets, t)
165 for (int i = 0; i < t; ++i) {
166 QuickSortHoare(local_output, offsets[i], offsets[i + 1] - 1);
167 }
168
169
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 BatcherMergePhase(output, offsets, t);
170
171
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 output.resize(orig_n);
172
173 return true;
174 }
175
176 16 bool HoareSortBatcherOMP::PostProcessingImpl() {
177 16 return true;
178 }
179
180 } // namespace nikitina_v_hoar_sort_batcher
181