GCC Code Coverage Report

Directory: ./
File: tasks/shemetov_d_radix_odd_even_mergesort/omp/src/ops_omp.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 61 61 100.0%
Functions: 7 7 100.0%
Branches: 49 54 90.7%
Line Branch Exec Source
1 #include "shemetov_d_radix_odd_even_mergesort/omp/include/ops_omp.hpp"
2
3 #include <omp.h>
4
5 #include <algorithm>
6 #include <climits>
7 #include <cstddef>
8 #include <vector>
9
10 #include "shemetov_d_radix_odd_even_mergesort/common/include/common.hpp"
11
12 namespace shemetov_d_radix_odd_even_mergesort {
13
14
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 ShemetovDRadixOddEvenMergeSortOMP::ShemetovDRadixOddEvenMergeSortOMP(const InType &in) {
15 SetTypeOfTask(GetStaticTypeOfTask());
16 GetInput() = in;
17 48 }
18
19 88 void ShemetovDRadixOddEvenMergeSortOMP::RadixSort(std::vector<int> &array, size_t left, size_t right,
20 std::vector<int> &buffer, std::vector<int> &position) {
21
2/2
✓ Branch 0 taken 74 times.
✓ Branch 1 taken 14 times.
 88 if (left >= right) {
22 return;
23 }
24
25 74 int maximum = *std::ranges::max_element(array.begin(), array.end());
26
27 74 size_t segment = right - left + 1;
28
29 74 buffer.resize(segment);
30
1/2
✓ Branch 0 taken 224 times.
✗ Branch 1 not taken.
 224 for (size_t merge_shift = 0; merge_shift < 32; merge_shift += 8) {
31 224 position.assign(256, 0);
32
33
2/2
✓ Branch 0 taken 1694 times.
✓ Branch 1 taken 224 times.
 1918 for (size_t i = left; i <= right; i += 1) {
34 1694 int apply_bitmask = (array[i] >> merge_shift) & 0xFF;
35
36 1694 position[apply_bitmask] += 1;
37 }
38
39
2/2
✓ Branch 0 taken 57120 times.
✓ Branch 1 taken 224 times.
 57344 for (size_t i = 1; i < 256; i += 1) {
40 57120 position[i] += position[i - 1];
41 }
42
43
2/2
✓ Branch 0 taken 1694 times.
✓ Branch 1 taken 224 times.
 1918 for (size_t i = segment; i > 0; i -= 1) {
44 1694 size_t current_index = left + i - 1;
45 1694 int apply_bitmask = (array[current_index] >> merge_shift) & 0xFF;
46
47 1694 buffer[position[apply_bitmask] -= 1] = array[current_index];
48 }
49
50
2/2
✓ Branch 0 taken 1694 times.
✓ Branch 1 taken 224 times.
 1918 for (size_t i = 0; i < segment; i += 1) {
51 1694 array[left + i] = buffer[i];
52 }
53
54
2/2
✓ Branch 0 taken 150 times.
✓ Branch 1 taken 74 times.
 224 if ((maximum >> merge_shift) < 256) {
55 break;
56 }
57 }
58 }
59
60 48 void ShemetovDRadixOddEvenMergeSortOMP::OddEvenMerge(std::vector<int> &array, size_t start_offset, size_t segment) {
61
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 if (segment <= 1) {
62 return;
63 }
64
65 48 size_t padding = segment / 2;
66
67
2/2
✓ Branch 0 taken 259 times.
✓ Branch 1 taken 48 times.
 307 for (size_t i = 0; i < padding; i += 1) {
68
2/2
✓ Branch 0 taken 50 times.
✓ Branch 1 taken 209 times.
 259 if (array[start_offset + i] > array[start_offset + padding + i]) {
69 std::swap(array[start_offset + i], array[start_offset + padding + i]);
70 }
71 }
72
73
2/2
✓ Branch 0 taken 92 times.
✓ Branch 1 taken 48 times.
 140 for (padding = segment / 4; padding > 0; padding /= 2) {
74 92 size_t step = padding * 2;
75
76
2/2
✓ Branch 0 taken 330 times.
✓ Branch 1 taken 92 times.
 422 for (size_t start_position = padding; start_position < segment - padding; start_position += step) {
77
2/2
✓ Branch 0 taken 541 times.
✓ Branch 1 taken 330 times.
 871 for (size_t i = 0; i < padding; i += 1) {
78
2/2
✓ Branch 0 taken 136 times.
✓ Branch 1 taken 405 times.
 541 if (array[start_offset + start_position + i] > array[start_offset + start_position + i + padding]) {
79 std::swap(array[start_offset + start_position + i], array[start_offset + start_position + i + padding]);
80 }
81 }
82 }
83 }
84 }
85
86 48 bool ShemetovDRadixOddEvenMergeSortOMP::ValidationImpl() {
87 const auto &[size, array] = GetInput();
88
3/4
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 44 times.
 48 return size > 0 && static_cast<size_t>(size) == array.size();
89 }
90
91
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 4 times.
 48 bool ShemetovDRadixOddEvenMergeSortOMP::PreProcessingImpl() {
92 const auto &[size, array] = GetInput();
93
94
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 4 times.
 48 if (size == 0) {
95 return true;
96 }
97
98 44 array_ = array;
99
100 44 offset_ = *std::ranges::min_element(array_.begin(), array_.end());
101 44 size_ = static_cast<size_t>(size);
102 44 power_ = 1;
103
104
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 44 times.
 172 while (power_ < size_) {
105 128 power_ *= 2;
106 }
107
108
2/2
✓ Branch 0 taken 368 times.
✓ Branch 1 taken 44 times.
 412 for (size_t i = 0; i < size_; i += 1) {
109 368 array_[i] -= offset_;
110 }
111
112
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 20 times.
 44 if (power_ > size_) {
113 24 array_.resize(power_, INT_MAX);
114 }
115
116 return true;
117 }
118
119 48 bool ShemetovDRadixOddEvenMergeSortOMP::RunImpl() {
120
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 8 times.
 48 if (power_ <= 1) {
121 return true;
122 }
123
124 40 size_t threads = omp_get_max_threads();
125
126 size_t limit = 1;
127
2/2
✓ Branch 0 taken 39 times.
✓ Branch 1 taken 40 times.
 79 while (limit * 2 <= std::min(threads, power_)) {
128 limit *= 2;
129 }
130
131 40 size_t chunk_size = power_ / limit;
132
133 40 std::vector<int> &ref_array = array_;
134 size_t ref_power = power_;
135
136 40 #pragma omp parallel num_threads(limit) default(none) shared(ref_array, ref_power, chunk_size, limit)
137 {
138 size_t thread_num = omp_get_thread_num();
139 size_t left = thread_num * chunk_size;
140 size_t right = left + chunk_size - 1;
141
142 std::vector<int> buffer;
143 std::vector<int> position;
144
145 RadixSort(ref_array, left, right, buffer, position);
146 #pragma omp barrier
147 for (size_t segment = chunk_size * 2; segment <= ref_power; segment *= 2) {
148 #pragma omp for
149 for (size_t i = 0; i < ref_power; i += segment) {
150 OddEvenMerge(ref_array, i, segment);
151 }
152 #pragma omp barrier
153 }
154 }
155
156 40 return true;
157 }
158
159 48 bool ShemetovDRadixOddEvenMergeSortOMP::PostProcessingImpl() {
160
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 44 times.
 48 if (size_ == 0) {
161 return true;
162 }
163
164 44 array_.resize(size_);
165
166
2/2
✓ Branch 0 taken 368 times.
✓ Branch 1 taken 44 times.
 412 for (size_t i = 0; i < size_; i += 1) {
167 368 array_[i] += offset_;
168 }
169
170
1/2
✓ Branch 0 taken 44 times.
✗ Branch 1 not taken.
 44 if (!std::ranges::is_sorted(array_.begin(), array_.end())) {
171 return false;
172 }
173
174 44 GetOutput() = array_;
175 44 return true;
176 }
177
178 } // namespace shemetov_d_radix_odd_even_mergesort
179