GCC Code Coverage Report

Directory: ./
File: tasks/kamaletdinov_r_bitwise_int/omp/src/ops_omp.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 61 61 100.0%
Functions: 8 8 100.0%
Branches: 49 72 68.1%
Line Branch Exec Source
1 #include "kamaletdinov_r_bitwise_int/omp/include/ops_omp.hpp"
2
3 #include <omp.h>
4
5 #include <algorithm>
6 #include <array>
7 #include <cstddef>
8 #include <vector>
9
10 #include "kamaletdinov_r_bitwise_int/common/include/common.hpp"
11
12 namespace kamaletdinov_r_bitwise_int {
13
14 namespace {
15
16 100 void CountingSortByDigit(std::vector<int> &arr, int exp) {
17 100 const int n = static_cast<int>(arr.size());
18 100 const int thread_count = omp_get_max_threads();
19 100 std::vector<std::array<int, 10>> local_counts(thread_count);
20
21 100 #pragma omp parallel default(none) shared(arr, exp, local_counts, n) num_threads(thread_count)
22 {
23 const int tid = omp_get_thread_num();
24 auto &current = local_counts.at(tid);
25 current.fill(0);
26
27 #pragma omp for schedule(static)
28 for (int i = 0; i < n; i++) {
29 const int digit = (arr.at(i) / exp) % 10;
30 current.at(digit)++;
31 }
32 }
33
34 100 std::array<int, 10> global_count = {};
35
2/2
✓ Branch 0 taken 250 times.
✓ Branch 1 taken 100 times.
 350 for (int thread_idx = 0; thread_idx < thread_count; thread_idx++) {
36
2/2
✓ Branch 0 taken 2500 times.
✓ Branch 1 taken 250 times.
 2750 for (int digit_idx = 0; digit_idx < 10; digit_idx++) {
37
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2500 times.
 2500 global_count.at(digit_idx) += local_counts.at(thread_idx).at(digit_idx);
38 }
39 }
40
41
2/2
✓ Branch 0 taken 900 times.
✓ Branch 1 taken 100 times.
 1000 for (int digit_idx = 1; digit_idx < 10; digit_idx++) {
42 900 global_count.at(digit_idx) += global_count.at(digit_idx - 1);
43 }
44
45 100 std::array<int, 10> global_start = {};
46
2/2
✓ Branch 0 taken 900 times.
✓ Branch 1 taken 100 times.
 1000 for (int digit_idx = 1; digit_idx < 10; digit_idx++) {
47 900 global_start.at(digit_idx) = global_count.at(digit_idx - 1);
48 }
49
50
1/4
✓ Branch 1 taken 100 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 100 std::vector<std::array<int, 10>> thread_offsets(thread_count);
51
2/2
✓ Branch 0 taken 1000 times.
✓ Branch 1 taken 100 times.
 1100 for (int digit_idx = 0; digit_idx < 10; digit_idx++) {
52 1000 int offset = global_start.at(digit_idx);
53
2/2
✓ Branch 0 taken 2500 times.
✓ Branch 1 taken 1000 times.
 3500 for (int thread_idx = 0; thread_idx < thread_count; thread_idx++) {
54
2/4
✗ Branch 0 not taken.
✓ Branch 1 taken 2500 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 2500 times.
 2500 thread_offsets.at(thread_idx).at(digit_idx) = offset;
55 2500 offset += local_counts.at(thread_idx).at(digit_idx);
56 }
57 }
58
59
1/4
✓ Branch 1 taken 100 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 100 std::vector<int> output(n);
60
61
1/2
✓ Branch 0 taken 100 times.
✗ Branch 1 not taken.
 100 #pragma omp parallel default(none) shared(arr, exp, output, n, thread_count, thread_offsets) num_threads(thread_count)
62 {
63 const int tid = omp_get_thread_num();
64 auto positions = thread_offsets.at(tid);
65
66 #pragma omp for schedule(static)
67 for (int i = 0; i < n; i++) {
68 const int digit = (arr.at(i) / exp) % 10;
69 output.at(positions.at(digit)++) = arr.at(i);
70 }
71 }
72
73 arr.swap(output);
74 100 }
75
76
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 4 times.
 64 void RadixSortPositiveParallel(std::vector<int> &arr) {
77
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 4 times.
 64 if (arr.empty()) {
78 return;
79 }
80
81 60 const int max_val = *std::ranges::max_element(arr);
82
1/2
✓ Branch 0 taken 100 times.
✗ Branch 1 not taken.
 100 for (int exp = 1; max_val / exp > 0; exp *= 10) {
83 100 CountingSortByDigit(arr, exp);
84
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 60 times.
 100 if (exp > max_val / 10) {
85 break;
86 }
87 }
88 }
89
90
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 32 times.
 40 void BitwiseSortParallel(std::vector<int> &arr) {
91
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 32 times.
 40 if (arr.size() <= 1) {
92 8 return;
93 }
94
95 32 std::vector<int> neg;
96
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 std::vector<int> pos;
97
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 neg.reserve(arr.size());
98
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 pos.reserve(arr.size());
99
100
2/2
✓ Branch 0 taken 5532 times.
✓ Branch 1 taken 32 times.
 5564 for (int value : arr) {
101
2/2
✓ Branch 0 taken 2740 times.
✓ Branch 1 taken 2792 times.
 5532 if (value < 0) {
102
1/4
✓ Branch 1 taken 2740 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 2740 neg.push_back(-value);
103 } else {
104 pos.push_back(value);
105 }
106 }
107
108
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 RadixSortPositiveParallel(neg);
109
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 RadixSortPositiveParallel(pos);
110
111 std::size_t index = 0;
112
2/2
✓ Branch 0 taken 2740 times.
✓ Branch 1 taken 32 times.
 2772 for (int i = static_cast<int>(neg.size()) - 1; i >= 0; i--) {
113
2/4
✗ Branch 0 not taken.
✓ Branch 1 taken 2740 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 2740 times.
 2740 arr.at(index++) = -neg.at(i);
114 }
115
2/2
✓ Branch 0 taken 2792 times.
✓ Branch 1 taken 32 times.
 2824 for (int value : pos) {
116
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2792 times.
 2792 arr.at(index++) = value;
117 }
118 }
119
120 } // namespace
121
122 40 KamaletdinovRBitwiseIntOMP::KamaletdinovRBitwiseIntOMP(const InType &in) {
123 SetTypeOfTask(GetStaticTypeOfTask());
124 40 GetInput() = in;
125 GetOutput() = 0;
126 40 }
127
128 40 bool KamaletdinovRBitwiseIntOMP::ValidationImpl() {
129 40 return GetInput() >= 0;
130 }
131
132 40 bool KamaletdinovRBitwiseIntOMP::PreProcessingImpl() {
133 40 const int n = GetInput();
134 40 data_.resize(n);
135
136 40 #pragma omp parallel for default(none) shared(n)
137 for (int i = 0; i < n; i++) {
138 data_.at(i) = (n / 2) - i;
139 }
140
141 40 return true;
142 }
143
144 40 bool KamaletdinovRBitwiseIntOMP::RunImpl() {
145 40 BitwiseSortParallel(data_);
146 40 return true;
147 }
148
149
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 4 times.
 40 bool KamaletdinovRBitwiseIntOMP::PostProcessingImpl() {
150 const bool sorted = std::ranges::is_sorted(data_);
151
1/2
✓ Branch 0 taken 36 times.
✗ Branch 1 not taken.
 40 GetOutput() = sorted ? GetInput() : 0;
152 40 return true;
153 }
154
155 } // namespace kamaletdinov_r_bitwise_int
156