GCC Code Coverage Report

Directory: ./
File: tasks/sosnina_a_radix_simple_merge/omp/src/ops_omp.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 61 61 100.0%
Functions: 7 7 100.0%
Branches: 47 54 87.0%
Line Branch Exec Source
1 #include "sosnina_a_radix_simple_merge/omp/include/ops_omp.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <cstdint>
6 #include <utility>
7 #include <vector>
8
9 #include "sosnina_a_radix_simple_merge/common/include/common.hpp"
10 #include "util/include/util.hpp"
11
12 namespace sosnina_a_radix_simple_merge {
13
14 namespace {
15
16 constexpr int kRadixBits = 8;
17 constexpr int kRadixSize = 1 << kRadixBits;
18 constexpr int kNumPasses = sizeof(int) / sizeof(uint8_t);
19 constexpr uint32_t kSignFlip = 0x80000000U;
20
21 448 void RadixSortLSD(std::vector<int> &data, std::vector<int> &buffer) {
22 size_t idx = 0;
23
2/2
✓ Branch 0 taken 1322 times.
✓ Branch 1 taken 448 times.
 1770 for (int elem : data) {
24 1322 buffer[idx++] = static_cast<int>(static_cast<uint32_t>(elem) ^ kSignFlip);
25 }
26 std::swap(data, buffer);
27
28
2/2
✓ Branch 0 taken 1792 times.
✓ Branch 1 taken 448 times.
 2240 for (int pass = 0; pass < kNumPasses; ++pass) {
29 1792 std::vector<int> count(kRadixSize + 1, 0);
30
31
2/2
✓ Branch 0 taken 5288 times.
✓ Branch 1 taken 1792 times.
 7080 for (auto elem : data) {
32 5288 auto digit = static_cast<uint8_t>((static_cast<uint32_t>(elem) >> (pass * kRadixBits)) & 0xFF);
33 5288 ++count[digit + 1];
34 }
35
36
2/2
✓ Branch 0 taken 458752 times.
✓ Branch 1 taken 1792 times.
 460544 for (int i = 1; i <= kRadixSize; ++i) {
37 458752 count[i] += count[i - 1];
38 }
39
40
2/2
✓ Branch 0 taken 5288 times.
✓ Branch 1 taken 1792 times.
 7080 for (auto elem : data) {
41 5288 auto digit = static_cast<uint8_t>((static_cast<uint32_t>(elem) >> (pass * kRadixBits)) & 0xFF);
42 5288 buffer[count[digit]++] = elem;
43 }
44
45 std::swap(data, buffer);
46 }
47
48
2/2
✓ Branch 0 taken 1322 times.
✓ Branch 1 taken 448 times.
 1770 for (int &elem : data) {
49 1322 elem = static_cast<int>(static_cast<uint32_t>(elem) ^ kSignFlip);
50 }
51 448 }
52
53 262 void SimpleMerge(const std::vector<int> &left, const std::vector<int> &right, std::vector<int> &result) {
54 size_t i = 0;
55 size_t j = 0;
56 size_t k = 0;
57
58
4/4
✓ Branch 0 taken 1035 times.
✓ Branch 1 taken 157 times.
✓ Branch 2 taken 105 times.
✓ Branch 3 taken 930 times.
 1192 while (i < left.size() && j < right.size()) {
59
2/2
✓ Branch 0 taken 600 times.
✓ Branch 1 taken 330 times.
 930 if (left[i] <= right[j]) {
60 600 result[k++] = left[i++];
61 } else {
62 330 result[k++] = right[j++];
63 }
64 }
65
66
2/2
✓ Branch 0 taken 293 times.
✓ Branch 1 taken 262 times.
 555 while (i < left.size()) {
67 293 result[k++] = left[i++];
68 }
69
70
2/2
✓ Branch 0 taken 315 times.
✓ Branch 1 taken 262 times.
 577 while (j < right.size()) {
71 315 result[k++] = right[j++];
72 }
73 262 }
74
75 } // namespace
76
77
1/2
✓ Branch 1 taken 198 times.
✗ Branch 2 not taken.
 198 SosninaATestTaskOMP::SosninaATestTaskOMP(const InType &in) {
78 SetTypeOfTask(GetStaticTypeOfTask());
79
1/2
✓ Branch 1 taken 198 times.
✗ Branch 2 not taken.
 198 GetInput() = in;
80
1/2
✓ Branch 1 taken 198 times.
✗ Branch 2 not taken.
 198 GetOutput() = in;
81 198 }
82
83 198 bool SosninaATestTaskOMP::ValidationImpl() {
84 198 return !GetInput().empty();
85 }
86
87 198 bool SosninaATestTaskOMP::PreProcessingImpl() {
88 198 GetOutput() = GetInput();
89 198 return true;
90 }
91
92
2/2
✓ Branch 0 taken 186 times.
✓ Branch 1 taken 12 times.
 198 bool SosninaATestTaskOMP::RunImpl() {
93 std::vector<int> &data = GetOutput();
94
2/2
✓ Branch 0 taken 186 times.
✓ Branch 1 taken 12 times.
 198 if (data.size() <= 1) {
95 return true;
96 }
97
98
2/2
✓ Branch 1 taken 45 times.
✓ Branch 2 taken 141 times.
 186 const int num_threads = ppc::util::GetNumThreads();
99
2/2
✓ Branch 0 taken 45 times.
✓ Branch 1 taken 141 times.
 186 const int num_parts = std::min(num_threads, static_cast<int>(data.size()));
100
101
2/2
✓ Branch 0 taken 45 times.
✓ Branch 1 taken 141 times.
 186 if (num_parts <= 1) {
102 45 std::vector<int> buffer(data.size());
103
1/2
✓ Branch 1 taken 45 times.
✗ Branch 2 not taken.
 45 RadixSortLSD(data, buffer);
104 return std::ranges::is_sorted(data);
105 }
106
107 141 std::vector<std::vector<int>> parts(num_parts);
108 141 const size_t base_size = data.size() / num_parts;
109 141 const size_t remainder = data.size() % num_parts;
110 size_t pos = 0;
111
112
2/2
✓ Branch 0 taken 403 times.
✓ Branch 1 taken 141 times.
 544 for (int i = 0; i < num_parts; ++i) {
113 403 const size_t part_size = base_size + (std::cmp_less(i, remainder) ? 1 : 0);
114
1/2
✓ Branch 1 taken 403 times.
✗ Branch 2 not taken.
 403 parts[i].assign(data.begin() + static_cast<std::ptrdiff_t>(pos),
115
1/2
✓ Branch 1 taken 403 times.
✗ Branch 2 not taken.
 403 data.begin() + static_cast<std::ptrdiff_t>(pos + part_size));
116 pos += part_size;
117 }
118
119 141 #pragma omp parallel for num_threads(num_parts) default(none) shared(parts, num_parts)
120 for (int i = 0; i < num_parts; ++i) {
121 std::vector<int> buffer(parts[i].size());
122 RadixSortLSD(parts[i], buffer);
123 }
124
125 std::vector<std::vector<int>> current = std::move(parts);
126
2/2
✓ Branch 0 taken 223 times.
✓ Branch 1 taken 141 times.
 364 while (current.size() > 1) {
127 223 const size_t half = (current.size() + 1) / 2;
128
1/2
✓ Branch 1 taken 223 times.
✗ Branch 2 not taken.
 223 std::vector<std::vector<int>> next(half);
129
130
2/2
✓ Branch 0 taken 43 times.
✓ Branch 1 taken 180 times.
 223 #pragma omp parallel for default(none) shared(current, next) schedule(static)
131 for (size_t i = 0; i < current.size() / 2; ++i) {
132 next[i].resize(current[2 * i].size() + current[(2 * i) + 1].size());
133 SimpleMerge(current[2 * i], current[(2 * i) + 1], next[i]);
134 }
135
2/2
✓ Branch 0 taken 43 times.
✓ Branch 1 taken 180 times.
 223 if (current.size() % 2 == 1) {
136 43 next[half - 1] = std::move(current.back());
137 }
138 223 current = std::move(next);
139 223 }
140
141 data = std::move(current[0]);
142 return std::ranges::is_sorted(data);
143 141 }
144
145 198 bool SosninaATestTaskOMP::PostProcessingImpl() {
146 198 return !GetOutput().empty();
147 }
148
149 } // namespace sosnina_a_radix_simple_merge
150