GCC Code Coverage Report

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