GCC Code Coverage Report

Line	Branch	Exec	Source
1			#include "gusev_d_double_sort_even_odd_batcher/seq/include/ops_seq.hpp"
2
3			#include <algorithm>
4			#include <array>
5			#include <bit>
6			#include <cstddef>
7			#include <cstdint>
8			#include <iterator>
9			#include <vector>
10
11			namespace {
12
13			uint64_t DoubleToSortableKey(double value) {
14			const auto bits = std::bit_cast<uint64_t>(value);
15			const uint64_t sign_mask = 0x8000000000000000ULL;
16		✗	return (bits & sign_mask) == 0 ? (bits ^ sign_mask) : (~bits);
17			}
18
19		✗	void RadixSortDoubles(std::vector<double> &data) {
20		✗	if (data.size() < 2) {
21		✗	return;
22			}
23
24		✗	std::vector<double> buffer(data.size());
25			std::vector<double> *src = &data;
26			std::vector<double> *dst = &buffer;
27
28		✗	for (int byte = 0; byte < 8; ++byte) {
29		✗	std::array<size_t, 256> count{};
30		✗	const int shift = byte * 8;
31
32		✗	for (double value : *src) {
33		✗	const auto bucket = static_cast<uint8_t>((DoubleToSortableKey(value) >> shift) & 0xFFULL);
34		✗	count.at(bucket)++;
35			}
36
37			size_t prefix = 0;
38		✗	for (size_t &bucket_count : count) {
39		✗	const size_t current = bucket_count;
40		✗	bucket_count = prefix;
41		✗	prefix += current;
42			}
43
44		✗	for (double value : *src) {
45		✗	const auto bucket = static_cast<uint8_t>((DoubleToSortableKey(value) >> shift) & 0xFFULL);
46		✗	const auto position = count.at(bucket)++;
47		✗	dst->at(position) = value;
48			}
49
50			std::swap(src, dst);
51			}
52
53		✗	if (src != &data) {
54		✗	data = *src;
55			}
56			}
57
58		✗	void SplitByGlobalParity(const std::vector<double> &source, size_t global_offset, std::vector<double> &even_values,
59			std::vector<double> &odd_values) {
60		✗	for (size_t i = 0; i < source.size(); ++i) {
61		✗	if (((global_offset + i) % 2) == 0) {
62			even_values.push_back(source[i]);
63			} else {
64			odd_values.push_back(source[i]);
65			}
66			}
67		✗	}
68
69		✗	std::vector<double> InterleaveEvenOdd(const std::vector<double> &even_values, const std::vector<double> &odd_values,
70			size_t total_size) {
71		✗	std::vector<double> result(total_size);
72			size_t even_idx = 0;
73			size_t odd_idx = 0;
74
75		✗	for (size_t i = 0; i < total_size; ++i) {
76		✗	if ((i % 2) == 0) {
77		✗	result[i] = even_values[even_idx++];
78			} else {
79		✗	result[i] = odd_values[odd_idx++];
80			}
81			}
82
83		✗	return result;
84			}
85
86		✗	void OddEvenFinalize(std::vector<double> &data) {
87		✗	for (size_t phase = 0; phase < data.size(); ++phase) {
88		✗	const size_t start = phase % 2;
89		✗	for (size_t i = start; i + 1 < data.size(); i += 2) {
90		✗	if (data[i] > data[i + 1]) {
91			std::swap(data[i], data[i + 1]);
92			}
93			}
94			}
95		✗	}
96
97		✗	std::vector<double> MergeBatcherEvenOdd(const std::vector<double> &left, const std::vector<double> &right) {
98		✗	const size_t total_size = left.size() + right.size();
99		✗	std::vector<double> left_even;
100		✗	std::vector<double> left_odd;
101		✗	std::vector<double> right_even;
102		✗	std::vector<double> right_odd;
103		✗	left_even.reserve((left.size() + 1) / 2);
104		✗	left_odd.reserve(left.size() / 2);
105		✗	right_even.reserve((right.size() + 1) / 2);
106		✗	right_odd.reserve(right.size() / 2);
107
108		✗	SplitByGlobalParity(left, 0, left_even, left_odd);
109		✗	SplitByGlobalParity(right, left.size(), right_even, right_odd);
110
111		✗	std::vector<double> merged_even;
112		✗	std::vector<double> merged_odd;
113		✗	merged_even.reserve(left_even.size() + right_even.size());
114		✗	merged_odd.reserve(left_odd.size() + right_odd.size());
115
116		✗	std::ranges::merge(left_even, right_even, std::back_inserter(merged_even));
117		✗	std::ranges::merge(left_odd, right_odd, std::back_inserter(merged_odd));
118
119		✗	auto result = InterleaveEvenOdd(merged_even, merged_odd, total_size);
120		✗	OddEvenFinalize(result);
121		✗	return result;
122			}
123
124			} // namespace
125
126			namespace gusev_d_double_sort_even_odd_batcher_task_threads {
127
128		✗	DoubleSortEvenOddBatcherSEQ::DoubleSortEvenOddBatcherSEQ(const InType &in) {
129			SetTypeOfTask(GetStaticTypeOfTask());
130		✗	GetInput() = in;
131			GetOutput() = {};
132		✗	}
133
134		✗	bool DoubleSortEvenOddBatcherSEQ::ValidationImpl() {
135		✗	return GetOutput().empty();
136			}
137
138		✗	bool DoubleSortEvenOddBatcherSEQ::PreProcessingImpl() {
139		✗	input_data_ = GetInput();
140			result_data_.clear();
141		✗	return true;
142			}
143
144		✗	bool DoubleSortEvenOddBatcherSEQ::RunImpl() {
145		✗	if (input_data_.empty()) {
146			result_data_.clear();
147		✗	return true;
148			}
149
150		✗	const size_t mid = input_data_.size() / 2;
151		✗	std::vector<double> left(input_data_.begin(), input_data_.begin() + static_cast<std::ptrdiff_t>(mid));
152		✗	std::vector<double> right(input_data_.begin() + static_cast<std::ptrdiff_t>(mid), input_data_.end());
153
154		✗	RadixSortDoubles(left);
155		✗	RadixSortDoubles(right);
156		✗	result_data_ = MergeBatcherEvenOdd(left, right);
157
158			return true;
159			}
160
161		✗	bool DoubleSortEvenOddBatcherSEQ::PostProcessingImpl() {
162		✗	GetOutput() = result_data_;
163		✗	return true;
164			}
165
166			} // namespace gusev_d_double_sort_even_odd_batcher_task_threads
167