GCC Code Coverage Report

Line	Branch	Exec	Source
1			#include "timofeev_n_radix_batcher_sort/stl/include/ops_stl.hpp"
2
3			#include <algorithm>
4			#include <climits>
5			#include <cstddef>
6			#include <thread>
7			#include <utility>
8			#include <vector>
9
10			#include "timofeev_n_radix_batcher_sort/common/include/common.hpp"
11
12			namespace timofeev_n_radix_batcher_sort_threads {
13
14		✗	TimofeevNRadixBatcherSTL::TimofeevNRadixBatcherSTL(const InType &in) {
15			SetTypeOfTask(GetStaticTypeOfTask());
16		✗	GetInput() = in;
17		✗	GetOutput() = in;
18		✗	}
19
20		✗	void TimofeevNRadixBatcherSTL::CompExch(int &a, int &b, int digit) {
21		✗	int b_r = b % (digit * 10) / digit;
22		✗	int a_r = a % (digit * 10) / digit;
23		✗	if (b_r < a_r) {
24			std::swap(a, b);
25			}
26		✗	}
27
28		✗	void TimofeevNRadixBatcherSTL::BubbleSort(std::vector<int> &arr, int digit, int left, int right) {
29		✗	for (int i = left; i <= right; i++) {
30		✗	for (int j = 0; j + 1 < right - left; j++) {
31		✗	CompExch(arr[left + j], arr[left + j + 1], digit);
32			}
33			}
34		✗	}
35
36		✗	void TimofeevNRadixBatcherSTL::ComparR(int &a, int &b) {
37		✗	if (a > b) {
38			std::swap(a, b);
39			}
40		✗	}
41
42		✗	void TimofeevNRadixBatcherSTL::OddEvenMerge(std::vector<int> &arr, int lft, int n) {
43		✗	if (n <= 1) {
44			return;
45			}
46
47		✗	int otstup = n / 2;
48		✗	for (int i = 0; i < otstup; i += 1) {
49		✗	if (arr[lft + i] > arr[lft + otstup + i]) {
50			std::swap(arr[lft + i], arr[lft + otstup + i]);
51			}
52			}
53
54		✗	for (otstup = n / 4; otstup > 0; otstup /= 2) {
55		✗	int h = otstup * 2;
56		✗	for (int start = otstup; start + otstup < n; start += h) {
57		✗	for (int i = 0; i < otstup; i += 1) {
58		✗	ComparR(arr[lft + start + i], arr[lft + start + i + otstup]);
59			}
60			}
61			}
62			}
63
64		✗	int TimofeevNRadixBatcherSTL::Loggo(int inputa) {
65			int count = 0;
66		✗	while (inputa > 1) {
67		✗	inputa /= 2;
68		✗	count++;
69			}
70		✗	return count;
71			}
72
73		✗	bool TimofeevNRadixBatcherSTL::ValidationImpl() {
74		✗	return GetInput().size() >= 2;
75			}
76
77		✗	bool TimofeevNRadixBatcherSTL::PreProcessingImpl() {
78		✗	return true;
79			}
80
81		✗	void TimofeevNRadixBatcherSTL::PrepAux(int &n, int &m, std::vector<int> &in, int &max_x, size_t &num_threads,
82			size_t &n_thr) {
83		✗	in = GetInput();
84		✗	n = static_cast<int>(in.size());
85		✗	m = n;
86
87		✗	while (n % 2 == 0) {
88		✗	n /= 2;
89			}
90		✗	if (n > 1) {
91			n = static_cast<int>(in.size());
92			int p = 1;
93		✗	while (p < n) {
94		✗	p *= 2;
95			}
96		✗	n = p;
97			} else {
98		✗	n = m;
99			}
100
101		✗	max_x = *(std::ranges::max_element(in.begin(), in.end()));
102		✗	if (n != m) {
103		✗	in.resize(n, max_x);
104			}
105
106		✗	n_thr = std::thread::hardware_concurrency();
107		✗	num_threads = 1;
108		✗	while (num_threads * 2 <= n_thr && n / num_threads >= 4) {
109		✗	num_threads *= 2;
110			}
111		✗	}
112
113		✗	void TimofeevNRadixBatcherSTL::BubbleSortAux(size_t &num_threads, int &max_x, std::vector<int> &r_in, size_t &piece,
114			std::vector<std::thread> &threads) {
115		✗	for (size_t t_s = 0; t_s < num_threads; ++t_s) {
116		✗	threads.emplace_back([&, t_s]() {
117		✗	for (int k = 1; k <= max_x; k *= 10) {
118		✗	BubbleSort(r_in, k, static_cast<int>(piece * t_s), static_cast<int>((piece * t_s) + piece));
119			}
120		✗	});
121			}
122		✗	}
123
124		✗	void TimofeevNRadixBatcherSTL::OddMergeAux(std::vector<int> &r_in, size_t &piece, std::vector<std::thread> &threads,
125			size_t &n_n) {
126		✗	for (size_t c_p = piece * 2; c_p <= n_n; c_p *= 2) {
127		✗	threads.clear();
128
129		✗	for (size_t i = 0; i < n_n; i += c_p) {
130		✗	threads.emplace_back([&, i]() { OddEvenMerge(r_in, static_cast<int>(i), static_cast<int>(c_p)); });
131			}
132
133		✗	for (auto &th : threads) {
134		✗	th.join();
135			}
136			}
137		✗	}
138
139		✗	void TimofeevNRadixBatcherSTL::HandleSTL(size_t &num_threads, size_t &n_n, size_t &m_m, int &max_x,
140			std::vector<int> &reff, std::vector<int> &r_in) {
141		✗	std::vector<std::thread> threads;
142
143		✗	size_t piece = n_n / num_threads;
144		✗	threads.reserve(num_threads);
145
146			BubbleSortAux(num_threads, max_x, r_in, piece, threads);
147
148		✗	for (auto &th : threads) {
149		✗	th.join();
150			}
151
152		✗	OddMergeAux(r_in, piece, threads, n_n);
153
154		✗	if (m_m != n_n) {
155		✗	r_in.resize(m_m);
156			}
157
158		✗	threads.clear();
159		✗	size_t chunk_size = r_in.size() / num_threads;
160		✗	if (chunk_size == 0) {
161			chunk_size = 1;
162			}
163
164		✗	for (size_t t_s = 0; t_s < num_threads; ++t_s) {
165		✗	size_t start = t_s * chunk_size;
166		✗	size_t end = (t_s == num_threads - 1) ? r_in.size() : (t_s + 1) * chunk_size;
167
168		✗	threads.emplace_back([&, start, end]() {
169		✗	for (size_t i = start; i < end; ++i) {
170		✗	reff[i] = r_in[i];
171			}
172			});
173			}
174
175		✗	for (auto &th : threads) {
176		✗	th.join();
177			}
178		✗	}
179
180		✗	bool TimofeevNRadixBatcherSTL::RunImpl() {
181		✗	std::vector<int> in;
182		✗	int n = 0;
183		✗	int m = 0;
184		✗	int max_x = 0;
185		✗	size_t n_thr = 0;
186		✗	size_t num_threads = 0;
187
188		✗	PrepAux(n, m, in, max_x, num_threads, n_thr);
189
190			std::vector<int> &r_in = in;
191		✗	size_t n_n = n;
192		✗	size_t m_m = m;
193			std::vector<int> &reff = GetInput();
194
195		✗	HandleSTL(num_threads, n_n, m_m, max_x, reff, r_in);
196
197		✗	GetOutput() = reff;
198		✗	return true;
199			}
200
201		✗	bool TimofeevNRadixBatcherSTL::PostProcessingImpl() {
202		✗	return true;
203			}
204
205			} // namespace timofeev_n_radix_batcher_sort_threads
206