GCC Code Coverage Report

Directory: ./
File: tasks/spichek_d_radix_sort_for_integers_with_simple_merging/omp/src/ops_omp.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 53 53 100.0%
Functions: 6 6 100.0%
Branches: 42 62 67.7%
Line Branch Exec Source
1 #include "spichek_d_radix_sort_for_integers_with_simple_merging/omp/include/ops_omp.hpp"
2
3 #include <omp.h>
4
5 #include <algorithm>
6 #include <iterator>
7 #include <utility>
8 #include <vector>
9
10 #include "spichek_d_radix_sort_for_integers_with_simple_merging/common/include/common.hpp"
11 #include "util/include/util.hpp"
12
13 namespace spichek_d_radix_sort_for_integers_with_simple_merging {
14
15
1/2
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
 60 SpichekDRadixSortOMP::SpichekDRadixSortOMP(const InType &in) {
16 SetTypeOfTask(GetStaticTypeOfTask());
17
1/2
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
 60 GetInput() = in;
18 60 }
19
20 60 bool SpichekDRadixSortOMP::ValidationImpl() {
21 60 return !GetInput().empty();
22 }
23
24 60 bool SpichekDRadixSortOMP::PreProcessingImpl() {
25 60 GetOutput() = GetInput();
26 60 return true;
27 }
28
29
1/2
✓ Branch 0 taken 60 times.
✗ Branch 1 not taken.
 60 bool SpichekDRadixSortOMP::RunImpl() {
30
1/2
✓ Branch 0 taken 60 times.
✗ Branch 1 not taken.
 60 if (GetOutput().empty()) {
31 return true;
32 }
33
34 60 int num_threads = ppc::util::GetNumThreads();
35 60 int n = static_cast<int>(GetOutput().size());
36
37
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 45 times.
 60 if (num_threads <= 1 || n < num_threads) {
38 15 RadixSort(GetOutput());
39 15 return true;
40 }
41
42 45 std::vector<std::vector<int>> local_data(num_threads);
43 45 int base_size = n / num_threads;
44 45 int remainder = n % num_threads;
45
46
1/2
✓ Branch 1 taken 45 times.
✗ Branch 2 not taken.
 45 std::vector<int> counts(num_threads);
47
1/4
✓ Branch 1 taken 45 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 45 std::vector<int> displs(num_threads, 0);
48
49
2/2
✓ Branch 0 taken 135 times.
✓ Branch 1 taken 45 times.
 180 for (int i = 0; i < num_threads; ++i) {
50
4/4
✓ Branch 0 taken 115 times.
✓ Branch 1 taken 20 times.
✓ Branch 2 taken 90 times.
✓ Branch 3 taken 45 times.
 250 counts[i] = base_size + (i < remainder ? 1 : 0);
51
2/2
✓ Branch 0 taken 90 times.
✓ Branch 1 taken 45 times.
 135 if (i > 0) {
52 90 displs[i] = displs[i - 1] + counts[i - 1];
53 }
54
1/4
✓ Branch 1 taken 135 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 270 local_data[i] = std::vector<int>(GetOutput().begin() + displs[i], GetOutput().begin() + displs[i] + counts[i]);
55 }
56
57 45 #pragma omp parallel for num_threads(num_threads) default(none) shared(local_data, num_threads)
58 for (int i = 0; i < num_threads; ++i) {
59 RadixSort(local_data[i]);
60 }
61
62 std::vector<int> result = std::move(local_data[0]);
63
2/2
✓ Branch 0 taken 90 times.
✓ Branch 1 taken 45 times.
 135 for (int i = 1; i < num_threads; ++i) {
64
1/2
✓ Branch 1 taken 90 times.
✗ Branch 2 not taken.
 90 std::vector<int> temp;
65
1/2
✓ Branch 1 taken 90 times.
✗ Branch 2 not taken.
 90 temp.reserve(result.size() + local_data[i].size());
66
1/2
✓ Branch 1 taken 90 times.
✗ Branch 2 not taken.
 90 std::ranges::merge(result, local_data[i], std::back_inserter(temp));
67 result = std::move(temp);
68 }
69
70 GetOutput() = std::move(result);
71 return true;
72 45 }
73
74
1/2
✓ Branch 0 taken 60 times.
✗ Branch 1 not taken.
 60 bool SpichekDRadixSortOMP::PostProcessingImpl() {
75 60 return std::ranges::is_sorted(GetOutput());
76 }
77
78
1/2
✓ Branch 0 taken 150 times.
✗ Branch 1 not taken.
 150 void SpichekDRadixSortOMP::RadixSort(std::vector<int> &data) {
79
1/2
✓ Branch 0 taken 150 times.
✗ Branch 1 not taken.
 150 if (data.empty()) {
80 return;
81 }
82
83 150 int min_val = *std::ranges::min_element(data);
84
2/2
✓ Branch 0 taken 103 times.
✓ Branch 1 taken 47 times.
 150 if (min_val < 0) {
85
2/2
✓ Branch 0 taken 86958 times.
✓ Branch 1 taken 103 times.
 87061 for (auto &x : data) {
86 86958 x -= min_val;
87 }
88 }
89
90 150 int max_val = *std::ranges::max_element(data);
91
92
2/2
✓ Branch 0 taken 270 times.
✓ Branch 1 taken 150 times.
 420 for (int shift = 0; (max_val >> shift) > 0; shift += 8) {
93 270 std::vector<int> output(data.size());
94
1/4
✓ Branch 1 taken 270 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 270 std::vector<int> count(256, 0);
95
96
2/2
✓ Branch 0 taken 219600 times.
✓ Branch 1 taken 270 times.
 219870 for (int x : data) {
97 219600 count[(x >> shift) & 255]++;
98 }
99
100
2/2
✓ Branch 0 taken 68850 times.
✓ Branch 1 taken 270 times.
 69120 for (int i = 1; i < 256; i++) {
101 68850 count[i] += count[i - 1];
102 }
103
104
2/2
✓ Branch 0 taken 219600 times.
✓ Branch 1 taken 270 times.
 219870 for (int i = static_cast<int>(data.size()) - 1; i >= 0; i--) {
105 219600 output[count[(data[i] >> shift) & 255] - 1] = data[i];
106 219600 count[(data[i] >> shift) & 255]--;
107 }
108
109 data = std::move(output);
110 }
111
112
2/2
✓ Branch 0 taken 103 times.
✓ Branch 1 taken 47 times.
 150 if (min_val < 0) {
113
2/2
✓ Branch 0 taken 86958 times.
✓ Branch 1 taken 103 times.
 87061 for (auto &x : data) {
114 86958 x += min_val;
115 }
116 }
117 }
118
119 } // namespace spichek_d_radix_sort_for_integers_with_simple_merging
120