GCC Code Coverage Report

Directory: ./
File: tasks/akimov_i_radixsort_int_merge/stl/src/ops_stl.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 84 85 98.8%
Functions: 10 10 100.0%
Branches: 50 64 78.1%
Line Branch Exec Source
1 #include "akimov_i_radixsort_int_merge/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <array>
5 #include <cstddef>
6 #include <cstdint>
7 #include <iterator>
8 #include <thread>
9 #include <vector>
10
11 #include "akimov_i_radixsort_int_merge/common/include/common.hpp"
12 #include "util/include/util.hpp"
13
14 namespace akimov_i_radixsort_int_merge {
15
16 namespace {
17 144 void CountingSortStep(std::vector<int>::iterator in_begin, std::vector<int>::iterator in_end,
18 std::vector<int>::iterator out_begin, size_t byte_index) {
19 144 size_t shift = byte_index * 8;
20 144 std::array<size_t, 256> count = {0};
21
22
2/2
✓ Branch 0 taken 35520 times.
✓ Branch 1 taken 144 times.
 35664 for (auto it = in_begin; it != in_end; ++it) {
23 35520 auto raw_val = static_cast<unsigned int>(*it);
24 35520 unsigned int byte_val = (raw_val >> shift) & 0xFF;
25
26
2/2
✓ Branch 0 taken 8880 times.
✓ Branch 1 taken 26640 times.
 35520 if (byte_index == sizeof(int) - 1) {
27 8880 byte_val ^= 128;
28 }
29 35520 count.at(byte_val)++;
30 }
31
32 144 std::array<size_t, 256> prefix{};
33 prefix[0] = 0;
34
2/2
✓ Branch 0 taken 36720 times.
✓ Branch 1 taken 144 times.
 36864 for (int i = 1; i < 256; ++i) {
35 36720 prefix.at(i) = prefix.at(i - 1) + count.at(i - 1);
36 }
37
38
2/2
✓ Branch 0 taken 35520 times.
✓ Branch 1 taken 144 times.
 35664 for (auto it = in_begin; it != in_end; ++it) {
39 35520 auto raw_val = static_cast<unsigned int>(*it);
40 35520 unsigned int byte_val = (raw_val >> shift) & 0xFF;
41
42
2/2
✓ Branch 0 taken 8880 times.
✓ Branch 1 taken 26640 times.
 35520 if (byte_index == sizeof(int) - 1) {
43 8880 byte_val ^= 128;
44 }
45
46 35520 *(out_begin + static_cast<int64_t>(prefix.at(byte_val))) = *it;
47 35520 prefix.at(byte_val)++;
48 }
49 144 }
50
51
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 36 times.
 36 void RadixSortLocal(std::vector<int>::iterator begin, std::vector<int>::iterator end) {
52 36 size_t n = std::distance(begin, end);
53
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 36 times.
 36 if (n < 2) {
54 ✗ return;
55 }
56
57 36 std::vector<int> temp(n);
58
59
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 36 times.
 180 for (size_t i = 0; i < sizeof(int); ++i) {
60
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 72 times.
 144 if (i % 2 == 0) {
61 72 CountingSortStep(begin, end, temp.begin(), i);
62 } else {
63 72 CountingSortStep(temp.begin(), temp.end(), begin, i);
64 }
65 }
66 }
67
68 6 void MergeBlocks(std::vector<int> &arr, const std::vector<int> &offsets, int num_threads) {
69
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 6 times.
 16 for (int step = 1; step < num_threads; step *= 2) {
70 10 std::vector<std::thread> threads;
71 10 int reserve_size = (num_threads + (2 * step) - 1) / (2 * step);
72
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 threads.reserve(static_cast<size_t>(reserve_size));
73
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 10 times.
 24 for (int i = 0; i < num_threads; i += 2 * step) {
74
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 2 times.
 14 if (i + step < num_threads) {
75
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 threads.emplace_back([&arr, &offsets, i, step, num_threads]() {
76 12 auto begin = arr.begin() + offsets[i];
77 12 auto middle = arr.begin() + offsets[i + step];
78 12 int end_idx = std::min(i + (2 * step), num_threads);
79 12 auto end = arr.begin() + offsets[end_idx];
80 12 std::inplace_merge(begin, middle, end);
81 12 });
82 }
83 }
84
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 10 times.
 22 for (auto &t : threads) {
85
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 t.join();
86 }
87 10 }
88 6 }
89
90 } // namespace
91
92
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 AkimovIRadixSortIntMergeSTL::AkimovIRadixSortIntMergeSTL(const InType &in) {
93 SetTypeOfTask(GetStaticTypeOfTask());
94
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 GetInput() = in;
95 24 GetOutput() = OutType();
96 24 }
97
98 24 bool AkimovIRadixSortIntMergeSTL::ValidationImpl() {
99 24 return !GetInput().empty();
100 }
101
102 24 bool AkimovIRadixSortIntMergeSTL::PreProcessingImpl() {
103 24 GetOutput() = GetInput();
104 24 return true;
105 }
106
107
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 bool AkimovIRadixSortIntMergeSTL::RunImpl() {
108 auto &arr = GetOutput();
109 24 int n = static_cast<int>(arr.size());
110
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 if (n == 0) {
111 return true;
112 }
113
114 24 int num_threads = ppc::util::GetNumThreads();
115
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 14 times.
 24 if (n < num_threads * 100) {
116 num_threads = 1;
117 }
118
119
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 6 times.
 10 if (num_threads == 1) {
120 18 RadixSortLocal(arr.begin(), arr.end());
121 18 return true;
122 }
123
124 6 std::vector<int> offsets(num_threads + 1);
125 6 int chunk = n / num_threads;
126 6 int rem = n % num_threads;
127 int curr = 0;
128
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 6 times.
 24 for (int i = 0; i < num_threads; ++i) {
129
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 2 times.
 18 offsets[i] = curr;
130
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 2 times.
 34 curr += chunk + (i < rem ? 1 : 0);
131 }
132
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 offsets[num_threads] = n;
133
134 {
135 6 std::vector<std::thread> threads;
136
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 threads.reserve(static_cast<size_t>(num_threads));
137
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 6 times.
 24 for (int i = 0; i < num_threads; ++i) {
138
1/2
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
 18 threads.emplace_back([&arr, &offsets, i]() {
139 18 auto begin = arr.begin() + offsets[i];
140 18 auto end = arr.begin() + offsets[i + 1];
141 18 RadixSortLocal(begin, end);
142 18 });
143 }
144
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 6 times.
 24 for (auto &t : threads) {
145
1/2
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
 18 t.join();
146 }
147 6 }
148
149
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MergeBlocks(arr, offsets, num_threads);
150
151 return true;
152 }
153
154 24 bool AkimovIRadixSortIntMergeSTL::PostProcessingImpl() {
155 24 return true;
156 }
157
158 } // namespace akimov_i_radixsort_int_merge
159