GCC Code Coverage Report

Directory: ./
File: tasks/kondakov_v_shell_sort/tbb/src/ops_tbb.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 68 69 98.6%
Functions: 12 12 100.0%
Branches: 47 58 81.0%
Line Branch Exec Source
1 #include "kondakov_v_shell_sort/tbb/include/ops_tbb.hpp"
2
3 #include <oneapi/tbb/blocked_range.h>
4 #include <oneapi/tbb/parallel_for.h>
5
6 #include <algorithm>
7 #include <cstddef>
8 #include <utility>
9 #include <vector>
10
11 #include "kondakov_v_shell_sort/common/include/common.hpp"
12 #include "util/include/util.hpp"
13
14 namespace kondakov_v_shell_sort {
15
16 namespace {
17
18 struct RunBounds {
19 size_t begin;
20 size_t end;
21 };
22
23 115 void SortRunWithShellGaps(std::vector<int> &data) {
24 const size_t n = data.size();
25
2/2
✓ Branch 0 taken 103 times.
✓ Branch 1 taken 115 times.
 218 for (size_t gap = n / 2; gap > 0; gap /= 2) {
26
2/2
✓ Branch 0 taken 238 times.
✓ Branch 1 taken 103 times.
 341 for (size_t i = gap; i < n; ++i) {
27 238 int value = data[i];
28 size_t j = i;
29
4/4
✓ Branch 0 taken 291 times.
✓ Branch 1 taken 84 times.
✓ Branch 2 taken 137 times.
✓ Branch 3 taken 154 times.
 375 while (j >= gap && data[j - gap] > value) {
30 137 data[j] = data[j - gap];
31 j -= gap;
32 }
33 238 data[j] = value;
34 }
35 }
36 115 }
37
38 67 std::vector<int> MergeTwoSortedRuns(const std::vector<int> &left, const std::vector<int> &right) {
39 67 std::vector<int> result(left.size() + right.size());
40 size_t i = 0;
41 size_t j = 0;
42 size_t k = 0;
43
44
4/4
✓ Branch 0 taken 239 times.
✓ Branch 1 taken 29 times.
✓ Branch 2 taken 38 times.
✓ Branch 3 taken 201 times.
 268 while (i < left.size() && j < right.size()) {
45
2/2
✓ Branch 0 taken 81 times.
✓ Branch 1 taken 120 times.
 201 if (left[i] <= right[j]) {
46 81 result[k++] = left[i++];
47 } else {
48 120 result[k++] = right[j++];
49 }
50 }
51
52
2/2
✓ Branch 0 taken 67 times.
✓ Branch 1 taken 67 times.
 134 while (i < left.size()) {
53 67 result[k++] = left[i++];
54 }
55
56
2/2
✓ Branch 0 taken 49 times.
✓ Branch 1 taken 67 times.
 116 while (j < right.size()) {
57 49 result[k++] = right[j++];
58 }
59
60 67 return result;
61 }
62
63 size_t GetRunsCount(size_t data_size, int requested_threads) {
64
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 if (data_size == 0) {
65 return 0;
66 }
67 const int threads = std::max(1, requested_threads);
68
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 37 times.
 48 return std::min(static_cast<size_t>(threads), data_size);
69 }
70
71 37 std::vector<RunBounds> BuildBalancedRuns(size_t data_size, size_t runs_count) {
72 37 std::vector<RunBounds> bounds(runs_count);
73
2/2
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 37 times.
 141 for (size_t run = 0; run < runs_count; ++run) {
74 104 bounds[run] = RunBounds{.begin = (run * data_size) / runs_count, .end = ((run + 1) * data_size) / runs_count};
75 }
76 37 return bounds;
77 }
78
79 37 std::vector<std::vector<int>> MakeSortedRuns(const std::vector<int> &data, const std::vector<RunBounds> &bounds) {
80 37 std::vector<std::vector<int>> runs(bounds.size());
81
82 37 oneapi::tbb::parallel_for(oneapi::tbb::blocked_range<size_t>(0, bounds.size()),
83
1/2
✓ Branch 1 taken 37 times.
✗ Branch 2 not taken.
 141 [&](const oneapi::tbb::blocked_range<size_t> &range) {
84
2/2
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 104 times.
 208 for (size_t run = range.begin(); run != range.end(); ++run) {
85 104 const RunBounds &current = bounds[run];
86 104 runs[run] = std::vector<int>(data.begin() + static_cast<std::ptrdiff_t>(current.begin),
87 104 data.begin() + static_cast<std::ptrdiff_t>(current.end));
88 104 SortRunWithShellGaps(runs[run]);
89 }
90 104 });
91
92 37 return runs;
93 ✗ }
94
95 37 std::vector<int> MergeRunsByLevels(std::vector<std::vector<int>> runs) {
96
2/2
✓ Branch 0 taken 57 times.
✓ Branch 1 taken 37 times.
 94 while (runs.size() > 1) {
97 57 const size_t pairs_count = runs.size() / 2;
98 57 std::vector<std::vector<int>> next_level(pairs_count + (runs.size() % 2));
99
100 57 oneapi::tbb::parallel_for(oneapi::tbb::blocked_range<size_t>(0, pairs_count),
101
3/4
✓ Branch 1 taken 57 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 10 times.
✓ Branch 4 taken 47 times.
 124 [&](const oneapi::tbb::blocked_range<size_t> &range) {
102
2/2
✓ Branch 0 taken 67 times.
✓ Branch 1 taken 67 times.
 134 for (size_t pair = range.begin(); pair != range.end(); ++pair) {
103 134 next_level[pair] = MergeTwoSortedRuns(runs[2 * pair], runs[(2 * pair) + 1]);
104 }
105 67 });
106
107
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 47 times.
 57 if ((runs.size() % 2) != 0) {
108 next_level.back() = std::move(runs.back());
109 }
110 57 runs = std::move(next_level);
111 57 }
112
113 37 return std::move(runs.front());
114 }
115
116 } // namespace
117
118
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 KondakovVShellSortTBB::KondakovVShellSortTBB(const InType &in) {
119 SetTypeOfTask(GetStaticTypeOfTask());
120
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 GetInput() = in;
121
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 GetOutput() = in;
122 52 }
123
124 52 bool KondakovVShellSortTBB::ValidationImpl() {
125 52 return !GetInput().empty();
126 }
127
128 52 bool KondakovVShellSortTBB::PreProcessingImpl() {
129 52 GetOutput() = GetInput();
130 52 return true;
131 }
132
133
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 48 times.
 52 bool KondakovVShellSortTBB::RunImpl() {
134 std::vector<int> &data = GetOutput();
135
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 48 times.
 52 if (data.size() <= 1) {
136 return true;
137 }
138
139 48 const int num_threads = ppc::util::GetNumThreads();
140 const size_t runs_count = GetRunsCount(data.size(), num_threads);
141
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 37 times.
 48 if (runs_count <= 1) {
142 11 SortRunWithShellGaps(data);
143 return std::ranges::is_sorted(data);
144 }
145
146 37 const std::vector<RunBounds> bounds = BuildBalancedRuns(data.size(), runs_count);
147
3/8
✓ Branch 1 taken 37 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 37 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 37 times.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
 74 data = MergeRunsByLevels(MakeSortedRuns(data, bounds));
148 return std::ranges::is_sorted(data);
149 }
150
151 52 bool KondakovVShellSortTBB::PostProcessingImpl() {
152 52 return !GetOutput().empty();
153 }
154
155 } // namespace kondakov_v_shell_sort
156