GCC Code Coverage Report

Line	Branch	Exec	Source
1			#include "shkryleva_s_shell_sort_simple_merge/tbb/include/ops_tbb.hpp"
2
3			#include <oneapi/tbb/info.h>
4			#include <oneapi/tbb/task_arena.h>
5			#include <oneapi/tbb/task_group.h>
6
7			#include <algorithm>
8			#include <cstddef>
9			#include <thread>
10			#include <utility>
11			#include <vector>
12
13			#include "shkryleva_s_shell_sort_simple_merge/common/include/common.hpp"
14			namespace shkryleva_s_shell_sort_simple_merge {
15
16		✗	ShkrylevaSShellMergeTBB::ShkrylevaSShellMergeTBB(const InType &in) {
17			SetTypeOfTask(GetStaticTypeOfTask());
18		✗	GetInput() = in;
19			GetOutput() = {};
20		✗	}
21
22		✗	bool ShkrylevaSShellMergeTBB::ValidationImpl() {
23		✗	return true;
24			}
25
26		✗	bool ShkrylevaSShellMergeTBB::PreProcessingImpl() {
27		✗	input_data_ = GetInput();
28			output_data_.clear();
29		✗	return true;
30			}
31
32		✗	void ShkrylevaSShellMergeTBB::ShellSort(int left, int right, std::vector<int> &arr) {
33		✗	int sub_array_size = right - left + 1;
34			int gap = 1;
35
36		✗	while (gap <= sub_array_size / 3) {
37		✗	gap = (gap * 3) + 1;
38			}
39
40		✗	for (; gap > 0; gap /= 3) {
41		✗	for (int i = left + gap; i <= right; ++i) {
42		✗	int temp = arr[i];
43			int j = i;
44
45		✗	while (j >= left + gap && arr[j - gap] > temp) {
46		✗	arr[j] = arr[j - gap];
47			j -= gap;
48			}
49
50		✗	arr[j] = temp;
51			}
52			}
53		✗	}
54
55		✗	void ShkrylevaSShellMergeTBB::Merge(int left, int mid, int right, std::vector<int> &arr, std::vector<int> &buffer) {
56			int i = left;
57		✗	int j = mid + 1;
58			int k = 0;
59
60		✗	int merge_size = right - left + 1;
61
62		✗	if (static_cast<std::size_t>(merge_size) > buffer.size()) {
63		✗	buffer.resize(static_cast<std::size_t>(merge_size));
64			}
65
66		✗	while (i <= mid || j <= right) {
67		✗	if (i > mid) {
68		✗	buffer[k++] = arr[j++];
69		✗	} else if (j > right) {
70		✗	buffer[k++] = arr[i++];
71			} else {
72		✗	buffer[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
73			}
74			}
75
76		✗	for (int idx = 0; idx < k; ++idx) {
77		✗	arr[left + idx] = buffer[idx];
78			}
79		✗	}
80
81		✗	bool ShkrylevaSShellMergeTBB::RunImpl() {
82		✗	if (input_data_.empty()) {
83			output_data_.clear();
84		✗	return true;
85			}
86
87		✗	std::vector<int> arr = input_data_;
88		✗	const int array_size = static_cast<int>(arr.size());
89
90			// Определение максимального количества потоков
91			// Используем TBB, если доступно, иначе std::thread
92		✗	int max_threads = tbb::info::default_concurrency();
93		✗	if (max_threads <= 0) {
94		✗	max_threads = static_cast<int>(std::thread::hardware_concurrency());
95		✗	if (max_threads <= 0) {
96		✗	max_threads = 4;
97			}
98			}
99
100			int threads = std::min(max_threads, array_size);
101		✗	const int sub_arr_size = (array_size + threads - 1) / threads;
102
103			// Разбиение на сегменты
104		✗	std::vector<std::pair<int, int>> segments;
105		✗	segments.reserve(threads);
106		✗	for (int idx = 0; idx < threads; ++idx) {
107		✗	int left = idx * sub_arr_size;
108		✗	int right = std::min(left + sub_arr_size - 1, array_size - 1);
109		✗	segments.emplace_back(left, right);
110			}
111
112			// Параллельная сортировка каждого сегмента
113			tbb::task_arena arena(threads);
114		✗	arena.execute([&] {
115			tbb::task_group tg;
116		✗	for (const auto &seg : segments) {
117		✗	int l = seg.first;
118		✗	int r = seg.second;
119		✗	tg.run([&arr, l, r] { ShellSort(l, r, arr); });
120			}
121		✗	tg.wait();
122		✗	});
123
124			// Последовательное слияние отсортированных сегментов
125		✗	std::vector<int> buffer;
126		✗	int current_end = segments.front().second;
127		✗	for (std::size_t i = 1; i < segments.size(); ++i) {
128		✗	int next_end = segments[i].second;
129		✗	Merge(0, current_end, next_end, arr, buffer);
130			current_end = next_end;
131			}
132
133		✗	output_data_ = arr;
134			return true;
135			}
136
137		✗	bool ShkrylevaSShellMergeTBB::PostProcessingImpl() {
138		✗	GetOutput() = output_data_;
139		✗	return true;
140			}
141
142			} // namespace shkryleva_s_shell_sort_simple_merge
143