GCC Code Coverage Report

Line	Branch	Exec	Source
1			#include "shkryleva_s_shell_sort_simple_merge/omp/include/ops_omp.hpp"
2
3			#include <omp.h>
4
5			#include <algorithm>
6			#include <cstddef>
7			#include <vector>
8
9			#include "shkryleva_s_shell_sort_simple_merge/common/include/common.hpp"
10
11			namespace shkryleva_s_shell_sort_simple_merge {
12
13		✗	ShkrylevaSShellMergeOMP::ShkrylevaSShellMergeOMP(const InType &in) {
14			SetTypeOfTask(GetStaticTypeOfTask());
15		✗	GetInput() = in;
16			GetOutput() = {};
17		✗	}
18
19		✗	bool ShkrylevaSShellMergeOMP::ValidationImpl() {
20		✗	return true;
21			}
22
23		✗	bool ShkrylevaSShellMergeOMP::PreProcessingImpl() {
24		✗	input_data_ = GetInput();
25			output_data_.clear();
26		✗	return true;
27			}
28
29		✗	void ShkrylevaSShellMergeOMP::ShellSort(int left, int right, std::vector<int> &arr) {
30		✗	int sub_array_size = right - left + 1;
31			int gap = 1;
32
33		✗	while (gap <= sub_array_size / 3) {
34		✗	gap = (gap * 3) + 1;
35			}
36
37		✗	for (; gap > 0; gap /= 3) {
38		✗	for (int i = left + gap; i <= right; ++i) {
39		✗	int temp = arr[i];
40			int j = i;
41
42		✗	while (j >= left + gap && arr[j - gap] > temp) {
43		✗	arr[j] = arr[j - gap];
44			j -= gap;
45			}
46
47		✗	arr[j] = temp;
48			}
49			}
50		✗	}
51
52		✗	void ShkrylevaSShellMergeOMP::Merge(int left, int mid, int right, std::vector<int> &arr, std::vector<int> &buffer) {
53			int i = left;
54		✗	int j = mid + 1;
55			int k = 0;
56
57		✗	int merge_size = right - left + 1;
58
59		✗	if (buffer.size() < static_cast<size_t>(merge_size)) {
60		✗	buffer.resize(static_cast<size_t>(merge_size));
61			}
62
63		✗	while (i <= mid || j <= right) {
64		✗	if (i > mid) {
65		✗	buffer[k++] = arr[j++];
66		✗	} else if (j > right) {
67		✗	buffer[k++] = arr[i++];
68			} else {
69		✗	buffer[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
70			}
71			}
72
73		✗	for (int idx = 0; idx < k; ++idx) {
74		✗	arr[left + idx] = buffer[idx];
75			}
76		✗	}
77
78		✗	bool ShkrylevaSShellMergeOMP::RunImpl() {
79		✗	if (input_data_.empty()) {
80			output_data_.clear();
81		✗	return true;
82			}
83
84		✗	std::vector<int> arr = input_data_;
85
86		✗	int array_size = static_cast<int>(arr.size());
87		✗	int num_threads = omp_get_max_threads();
88
89		✗	int sub_arr_size = (array_size + num_threads - 1) / num_threads;
90
91		✗	#pragma omp parallel default(none) shared(arr, array_size, num_threads, sub_arr_size)
92			{
93			std::vector<int> buffer;
94
95			#pragma omp for schedule(dynamic)
96			for (int i = 0; i < num_threads; ++i) {
97			int left = i * sub_arr_size;
98			int right = std::min(left + sub_arr_size - 1, array_size - 1);
99
100			if (left < right) {
101			ShellSort(left, right, arr);
102			}
103			}
104
105			for (int size = sub_arr_size; size < array_size; size *= 2) {
106			#pragma omp for schedule(dynamic)
107			for (int left = 0; left < array_size; left += 2 * size) {
108			int mid = std::min(left + size - 1, array_size - 1);
109			int right = std::min(left + (2 * size) - 1, array_size - 1);
110
111			if (mid < right) {
112			Merge(left, mid, right, arr, buffer);
113			}
114			}
115			}
116			}
117
118		✗	output_data_ = arr;
119
120			return true;
121			}
122
123		✗	bool ShkrylevaSShellMergeOMP::PostProcessingImpl() {
124		✗	GetOutput() = output_data_;
125		✗	return true;
126			}
127
128			} // namespace shkryleva_s_shell_sort_simple_merge
129