GCC Code Coverage Report

Directory: ./
File: tasks/khruev_a_radix_sorting_int_bather_merge/stl/src/ops_stl.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 75 78 96.2%
Functions: 10 11 90.9%
Branches: 62 98 63.3%
Line Branch Exec Source
1 #include "khruev_a_radix_sorting_int_bather_merge/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <cstdint>
6 #include <limits>
7 #include <thread>
8 #include <vector>
9
10 #include "khruev_a_radix_sorting_int_bather_merge/common/include/common.hpp"
11
12 namespace khruev_a_radix_sorting_int_bather_merge {
13
14 // Анонимное пространство имён для вспомогательных функций, чтобы они не засоряли глобальный скоуп
15 namespace {
16
17 template <typename Func>
18
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 104 times.
 320 void RunInThreads(size_t total_tasks, size_t max_threads, Func task_func) {
19 size_t num_threads = std::min(max_threads, total_tasks);
20
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 104 times.
 320 if (num_threads <= 1) {
21
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 56 times.
 224 for (size_t task_idx = 0; task_idx < total_tasks; ++task_idx) {
22 96 task_func(task_idx);
23 }
24 112 return;
25 }
26
27 208 std::vector<std::thread> threads;
28
1/2
✓ Branch 1 taken 104 times.
✗ Branch 2 not taken.
 208 threads.reserve(num_threads);
29 208 size_t chunk_size = (total_tasks + num_threads - 1) / num_threads;
30
31
2/2
✓ Branch 0 taken 360 times.
✓ Branch 1 taken 104 times.
 928 for (size_t thread_idx = 0; thread_idx < num_threads; ++thread_idx) {
32 720 size_t start_idx = thread_idx * chunk_size;
33
1/2
✓ Branch 0 taken 360 times.
✗ Branch 1 not taken.
 720 size_t end_idx = std::min(start_idx + chunk_size, total_tasks);
34
35
1/2
✓ Branch 0 taken 360 times.
✗ Branch 1 not taken.
 720 if (start_idx < end_idx) {
36
1/2
✓ Branch 1 taken 360 times.
✗ Branch 2 not taken.
 1072 threads.emplace_back([start_idx, end_idx, &task_func]() {
37
4/4
✓ Branch 0 taken 232 times.
✓ Branch 1 taken 184 times.
✓ Branch 2 taken 240 times.
✓ Branch 3 taken 176 times.
 832 for (size_t task_idx = start_idx; task_idx < end_idx; ++task_idx) {
38 232 task_func(task_idx);
39 }
40 });
41 }
42 }
43
44
2/2
✓ Branch 0 taken 360 times.
✓ Branch 1 taken 104 times.
 928 for (auto &thread_obj : threads) {
45
1/2
✓ Branch 1 taken 360 times.
✗ Branch 2 not taken.
 720 thread_obj.join();
46 }
47 208 }
48
49 } // namespace
50
51 ✗ void KhruevARadixSortingIntBatherMergeSTL::CompareExchange(std::vector<int> &a, size_t i, size_t j) {
52
5/8
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 24 times.
✓ Branch 3 taken 216 times.
✓ Branch 4 taken 104 times.
✓ Branch 5 taken 296 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 648 if (a[i] > a[j]) {
53 std::swap(a[i], a[j]);
54 }
55 ✗ }
56
57 112 void KhruevARadixSortingIntBatherMergeSTL::RadixSort(std::vector<int> &arr) {
58 const int bits = 8;
59 const int buckets = 1 << bits;
60 const int mask = buckets - 1;
61 const int passes = 32 / bits;
62
63 112 std::vector<int> temp(arr.size());
64 std::vector<int> *src = &arr;
65 std::vector<int> *dst = &temp;
66
67
2/2
✓ Branch 0 taken 448 times.
✓ Branch 1 taken 112 times.
 560 for (int pass = 0; pass < passes; pass++) {
68
1/4
✓ Branch 1 taken 448 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 448 std::vector<int> count(buckets, 0);
69 448 int shift = pass * bits;
70
71
2/2
✓ Branch 0 taken 1984 times.
✓ Branch 1 taken 448 times.
 2432 for (int x : *src) {
72 1984 uint32_t ux = static_cast<uint32_t>(x) ^ 0x80000000U;
73 1984 uint32_t digit = (ux >> shift) & mask;
74 1984 count[digit]++;
75 }
76
77
2/2
✓ Branch 0 taken 114240 times.
✓ Branch 1 taken 448 times.
 114688 for (int i = 1; i < buckets; i++) {
78 114240 count[i] += count[i - 1];
79 }
80
81
2/2
✓ Branch 0 taken 1984 times.
✓ Branch 1 taken 448 times.
 2432 for (size_t i = src->size(); i-- > 0;) {
82 1984 uint32_t ux = static_cast<uint32_t>((*src)[i]) ^ 0x80000000U;
83 1984 uint32_t digit = (ux >> shift) & mask;
84 1984 (*dst)[--count[digit]] = (*src)[i];
85 }
86
87 std::swap(src, dst);
88 }
89 112 }
90
91 56 void KhruevARadixSortingIntBatherMergeSTL::OddEvenMerge(std::vector<int> &a, size_t n) {
92
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 56 times.
 56 if (n < 2) {
93 ✗ return;
94 }
95
96 56 size_t max_threads = std::thread::hardware_concurrency();
97
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 56 times.
 56 if (max_threads == 0) {
98 max_threads = 4;
99 }
100
101 56 size_t po = n / 2;
102
103
3/4
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 24 times.
✓ Branch 3 taken 216 times.
 304 RunInThreads(po, max_threads, [&](size_t i) { CompareExchange(a, i, i + po); });
104
105 56 po >>= 1;
106
107
2/2
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 56 times.
 160 for (; po > 0; po >>= 1) {
108 104 size_t num_blocks = (n - (2 * po)) / (2 * po);
109
110 104 RunInThreads(num_blocks, max_threads, [&](size_t block_idx) {
111 280 size_t i = po + (block_idx * 2 * po);
112
2/2
✓ Branch 0 taken 400 times.
✓ Branch 1 taken 280 times.
 680 for (size_t j = 0; j < po; ++j) {
113
2/2
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 296 times.
 400 CompareExchange(a, i + j, i + j + po);
114 }
115 280 });
116 }
117 }
118
119
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 KhruevARadixSortingIntBatherMergeSTL::KhruevARadixSortingIntBatherMergeSTL(const InType &in) {
120 SetTypeOfTask(GetStaticTypeOfTask());
121
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 GetInput() = in;
122 64 }
123
124 64 bool KhruevARadixSortingIntBatherMergeSTL::ValidationImpl() {
125 64 return !GetInput().empty();
126 }
127
128 64 bool KhruevARadixSortingIntBatherMergeSTL::PreProcessingImpl() {
129 64 GetOutput().resize(GetInput().size());
130 64 return true;
131 }
132
133 64 bool KhruevARadixSortingIntBatherMergeSTL::RunImpl() {
134 64 std::vector<int> data = GetInput();
135 size_t original_size = data.size();
136
137
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 56 times.
 64 if (original_size <= 1) {
138
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 GetOutput() = data;
139 return true;
140 }
141
142 size_t pow2 = 1;
143
2/2
✓ Branch 0 taken 160 times.
✓ Branch 1 taken 56 times.
 216 while (pow2 < original_size) {
144 160 pow2 <<= 1;
145 }
146
147
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 data.resize(pow2, std::numeric_limits<int>::max());
148
149
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 size_t half = pow2 / 2;
150 auto half_dist = static_cast<std::ptrdiff_t>(half);
151
152
2/6
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 56 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 56 std::vector<int> left(data.begin(), data.begin() + half_dist);
153
1/4
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 56 std::vector<int> right(data.begin() + half_dist, data.end());
154
155
1/4
✓ Branch 2 taken 56 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 112 std::thread left_thread([&]() { RadixSort(left); });
156
157
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 RadixSort(right);
158
159
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 left_thread.join();
160
161 std::ranges::copy(left, data.begin());
162 std::ranges::copy(right, data.begin() + half_dist);
163
164
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 OddEvenMerge(data, data.size());
165
166
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 data.resize(original_size);
167
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 GetOutput() = data;
168
169 return true;
170 }
171
172 64 bool KhruevARadixSortingIntBatherMergeSTL::PostProcessingImpl() {
173 64 return GetOutput().size() == GetInput().size();
174 }
175
176 } // namespace khruev_a_radix_sorting_int_bather_merge
177