GCC Code Coverage Report

Directory: ./
File: tasks/krasnopevtseva_v_hoare_batcher_sort/omp/src/ops_omp.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 71 78 91.0%
Functions: 9 10 90.0%
Branches: 35 50 70.0%
Line Branch Exec Source
1 #include "krasnopevtseva_v_hoare_batcher_sort/omp/include/ops_omp.hpp"
2
3 #include <omp.h>
4
5 #include <algorithm>
6 #include <cmath>
7 #include <cstddef>
8 #include <stack>
9 #include <utility>
10 #include <vector>
11
12 #include "krasnopevtseva_v_hoare_batcher_sort/common/include/common.hpp"
13 namespace krasnopevtseva_v_hoare_batcher_sort {
14
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 KrasnopevtsevaVHoareBatcherSortOMP::KrasnopevtsevaVHoareBatcherSortOMP(const InType &in) {
15 SetTypeOfTask(GetStaticTypeOfTask());
16
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 GetInput() = in;
17 24 GetOutput() = std::vector<int>();
18 24 }
19
20 24 bool KrasnopevtsevaVHoareBatcherSortOMP::ValidationImpl() {
21 const auto &input = GetInput();
22 24 return !input.empty();
23 }
24
25 24 bool KrasnopevtsevaVHoareBatcherSortOMP::PreProcessingImpl() {
26 24 GetOutput() = std::vector<int>();
27 24 return true;
28 }
29
30
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 bool KrasnopevtsevaVHoareBatcherSortOMP::RunImpl() {
31 const auto &input = GetInput();
32 std::size_t size = input.size();
33
34
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (size <= 1) {
35 ✗ GetOutput() = input;
36 ✗ return true;
37 }
38
39 24 std::vector<int> res = input;
40
41 24 int n = static_cast<int>(size);
42 24 int numthreads = omp_get_max_threads();
43 24 numthreads = std::min(n, numthreads);
44
45 24 int thread_input_size = n / numthreads;
46 24 int thread_input_remainder_size = n % numthreads;
47
48
1/4
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 24 std::vector<int *> pointers(numthreads);
49
1/4
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 24 std::vector<int> sizes(numthreads);
50
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 24 times.
 84 for (int i = 0; i < numthreads; ++i) {
51 60 std::ptrdiff_t offset = static_cast<std::ptrdiff_t>(i) * static_cast<std::ptrdiff_t>(thread_input_size);
52 60 pointers[i] = res.data() + offset;
53 60 sizes[i] = thread_input_size;
54 }
55 24 sizes[sizes.size() - 1] += thread_input_remainder_size;
56
57 24 #pragma omp parallel for default(none) shared(res, pointers, sizes, numthreads)
58 for (int i = 0; i < numthreads; ++i) {
59 int left = static_cast<int>(pointers[i] - res.data());
60 int right = left + sizes[i] - 1;
61 QuickSort(res, left, right);
62 }
63
64 24 BatcherMerge(thread_input_size, pointers, sizes, 32);
65
66 GetOutput() = std::move(res);
67 return true;
68 }
69
70 24 bool KrasnopevtsevaVHoareBatcherSortOMP::PostProcessingImpl() {
71 24 return true;
72 }
73
74 23 int KrasnopevtsevaVHoareBatcherSortOMP::Partition(std::vector<int> &arr, int first, int last) {
75 23 int i = first - 1;
76 23 int value = arr[last];
77
78
2/2
✓ Branch 0 taken 504 times.
✓ Branch 1 taken 23 times.
 527 for (int j = first; j <= last - 1; ++j) {
79
2/2
✓ Branch 0 taken 241 times.
✓ Branch 1 taken 263 times.
 504 if (arr[j] <= value) {
80 241 ++i;
81 241 std::swap(arr[i], arr[j]);
82 }
83 }
84 23 std::swap(arr[i + 1], arr[last]);
85 23 return i + 1;
86 }
87
88 66 void KrasnopevtsevaVHoareBatcherSortOMP::InsertionSort(std::vector<int> &arr, int first, int last) {
89
2/2
✓ Branch 0 taken 399 times.
✓ Branch 1 taken 66 times.
 465 for (int i = first + 1; i <= last; ++i) {
90 399 int key = arr[i];
91 399 int j = i - 1;
92
4/4
✓ Branch 0 taken 1258 times.
✓ Branch 1 taken 145 times.
✓ Branch 2 taken 1004 times.
✓ Branch 3 taken 254 times.
 1403 while (j >= first && arr[j] > key) {
93 1004 arr[j + 1] = arr[j];
94 1004 --j;
95 }
96 399 arr[j + 1] = key;
97 }
98 66 }
99
100 60 void KrasnopevtsevaVHoareBatcherSortOMP::QuickSort(std::vector<int> &arr, int first, int last) {
101 std::stack<std::pair<int, int>> stack;
102 stack.emplace(first, last);
103
104
2/2
✓ Branch 0 taken 106 times.
✓ Branch 1 taken 60 times.
 166 while (!stack.empty()) {
105 auto [l, r] = stack.top();
106 stack.pop();
107
108
2/2
✓ Branch 0 taken 17 times.
✓ Branch 1 taken 89 times.
 106 if (l >= r) {
109 83 continue;
110 }
111
112
2/2
✓ Branch 0 taken 66 times.
✓ Branch 1 taken 23 times.
 89 if (r - l < 16) {
113 66 InsertionSort(arr, l, r);
114 66 continue;
115 }
116
117 23 int iter = Partition(arr, l, r);
118
119
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 12 times.
 23 if (iter - l < r - iter) {
120
1/2
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
 11 stack.emplace(iter + 1, r);
121
1/2
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
 11 stack.emplace(l, iter - 1);
122 } else {
123
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 stack.emplace(l, iter - 1);
124
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 stack.emplace(iter + 1, r);
125 }
126 }
127 60 }
128
129 ✗ void KrasnopevtsevaVHoareBatcherSortOMP::BatcherMergeBlocksStep(int *left_pointer, int &left_size, int *right_pointer,
130 int &right_size) {
131 ✗ std::inplace_merge(left_pointer, right_pointer, right_pointer + right_size);
132 18 left_size += right_size;
133 18 }
134
135 24 void KrasnopevtsevaVHoareBatcherSortOMP::BatcherMerge(int thread_input_size, std::vector<int *> &pointers,
136 std::vector<int> &sizes, int par_if_greater) {
137 24 int pack = static_cast<int>(pointers.size());
138
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 24 times.
 48 for (int step = 1; pack > 1; step *= 2, pack /= 2) {
139 24 #pragma omp parallel for default(none) shared(pointers, sizes, pack, step, thread_input_size, \
140 24 par_if_greater) if ((thread_input_size / step) > par_if_greater)
141 for (int off = 0; off < pack / 2; ++off) {
142 auto idx1 = static_cast<std::size_t>(2 * step) * static_cast<std::size_t>(off);
143 auto idx2 = (static_cast<std::size_t>(2 * step) * static_cast<std::size_t>(off)) + static_cast<std::size_t>(step);
144 BatcherMergeBlocksStep(pointers[idx1], sizes[idx1], pointers[idx2], sizes[idx2]);
145 }
146
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 6 times.
 24 if ((pack / 2) - 1 == 0) {
147 18 BatcherMergeBlocksStep(pointers[0], sizes[sizes.size() - 1], pointers[pointers.size() - 1],
148 sizes[sizes.size() - 1]);
149
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 } else if ((pack / 2) % 2 != 0) {
150 ✗ auto idx1 = static_cast<std::size_t>(2 * step) * static_cast<std::size_t>((pack / 2) - 2);
151 ✗ auto idx2 = static_cast<std::size_t>(2 * step) * static_cast<std::size_t>((pack / 2) - 1);
152 ✗ BatcherMergeBlocksStep(pointers[idx1], sizes[idx1], pointers[idx2], sizes[idx2]);
153 }
154 }
155 24 }
156
157 } // namespace krasnopevtseva_v_hoare_batcher_sort
158