GCC Code Coverage Report

Directory: ./
File: tasks/kondakov_v_shell_sort/stl/src/ops_stl.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 50 50 100.0%
Functions: 7 7 100.0%
Branches: 41 52 78.8%
Line Branch Exec Source
1 #include "kondakov_v_shell_sort/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <functional>
6 #include <thread>
7 #include <utility>
8 #include <vector>
9
10 #include "kondakov_v_shell_sort/common/include/common.hpp"
11 #include "util/include/util.hpp"
12
13 namespace kondakov_v_shell_sort {
14
15 namespace {
16
17 222 void ShellSort(std::vector<int> &data) {
18 const size_t n = data.size();
19
2/2
✓ Branch 0 taken 198 times.
✓ Branch 1 taken 222 times.
 420 for (size_t gap = n / 2; gap > 0; gap /= 2) {
20
2/2
✓ Branch 0 taken 464 times.
✓ Branch 1 taken 198 times.
 662 for (size_t i = gap; i < n; ++i) {
21 464 int value = data[i];
22 size_t j = i;
23
4/4
✓ Branch 0 taken 570 times.
✓ Branch 1 taken 168 times.
✓ Branch 2 taken 274 times.
✓ Branch 3 taken 296 times.
 738 while (j >= gap && data[j - gap] > value) {
24 274 data[j] = data[j - gap];
25 j -= gap;
26 }
27 464 data[j] = value;
28 }
29 }
30 222 }
31
32 130 void SimpleMerge(const std::vector<int> &left, const std::vector<int> &right, std::vector<int> &result) {
33 size_t i = 0;
34 size_t j = 0;
35 size_t k = 0;
36
37
4/4
✓ Branch 0 taken 458 times.
✓ Branch 1 taken 52 times.
✓ Branch 2 taken 78 times.
✓ Branch 3 taken 380 times.
 510 while (i < left.size() && j < right.size()) {
38
2/2
✓ Branch 0 taken 176 times.
✓ Branch 1 taken 204 times.
 380 if (left[i] <= right[j]) {
39 176 result[k++] = left[i++];
40 } else {
41 204 result[k++] = right[j++];
42 }
43 }
44
45
2/2
✓ Branch 0 taken 168 times.
✓ Branch 1 taken 130 times.
 298 while (i < left.size()) {
46 168 result[k++] = left[i++];
47 }
48
49
2/2
✓ Branch 0 taken 78 times.
✓ Branch 1 taken 130 times.
 208 while (j < right.size()) {
50 78 result[k++] = right[j++];
51 }
52 130 }
53
54 size_t CalcPartsCount(size_t data_size, int requested_threads) {
55
1/2
✓ Branch 0 taken 92 times.
✗ Branch 1 not taken.
 92 if (data_size == 0) {
56 return 0;
57 }
58 const int threads = std::max(1, requested_threads);
59
2/2
✓ Branch 0 taken 22 times.
✓ Branch 1 taken 70 times.
 92 return std::min(static_cast<size_t>(threads), data_size);
60 }
61
62 } // namespace
63
64
1/2
✓ Branch 1 taken 100 times.
✗ Branch 2 not taken.
 100 KondakovVShellSortSTL::KondakovVShellSortSTL(const InType &in) {
65 SetTypeOfTask(GetStaticTypeOfTask());
66
1/2
✓ Branch 1 taken 100 times.
✗ Branch 2 not taken.
 100 GetInput() = in;
67
1/2
✓ Branch 1 taken 100 times.
✗ Branch 2 not taken.
 100 GetOutput() = in;
68 100 }
69
70 100 bool KondakovVShellSortSTL::ValidationImpl() {
71 100 return !GetInput().empty();
72 }
73
74 100 bool KondakovVShellSortSTL::PreProcessingImpl() {
75 100 GetOutput() = GetInput();
76 100 return true;
77 }
78
79
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 92 times.
 100 bool KondakovVShellSortSTL::RunImpl() {
80 std::vector<int> &data = GetOutput();
81
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 92 times.
 100 if (data.size() <= 1) {
82 return true;
83 }
84
85 92 const int num_threads = ppc::util::GetNumThreads();
86 const size_t parts = CalcPartsCount(data.size(), num_threads);
87
2/2
✓ Branch 0 taken 22 times.
✓ Branch 1 taken 70 times.
 92 if (parts <= 1) {
88 22 ShellSort(data);
89 return std::ranges::is_sorted(data);
90 }
91
92 70 std::vector<std::vector<int>> segments(parts);
93 70 std::vector<std::thread> threads;
94
95
2/2
✓ Branch 0 taken 200 times.
✓ Branch 1 taken 70 times.
 270 for (size_t part = 0; part < parts; ++part) {
96 200 const size_t begin = (part * data.size()) / parts;
97
1/2
✓ Branch 1 taken 200 times.
✗ Branch 2 not taken.
 200 const size_t end = ((part + 1) * data.size()) / parts;
98 200 segments[part] = std::vector<int>(data.begin() + static_cast<std::ptrdiff_t>(begin),
99
1/2
✓ Branch 1 taken 200 times.
✗ Branch 2 not taken.
 200 data.begin() + static_cast<std::ptrdiff_t>(end));
100
1/2
✓ Branch 1 taken 200 times.
✗ Branch 2 not taken.
 200 threads.emplace_back(ShellSort, std::ref(segments[part]));
101 }
102
103
2/2
✓ Branch 0 taken 200 times.
✓ Branch 1 taken 70 times.
 270 for (auto &t : threads) {
104
1/2
✓ Branch 1 taken 200 times.
✗ Branch 2 not taken.
 200 t.join();
105 }
106
107 std::vector<int> merged = std::move(segments[0]);
108
2/2
✓ Branch 0 taken 130 times.
✓ Branch 1 taken 70 times.
 200 for (size_t i = 1; i < parts; ++i) {
109
1/4
✓ Branch 1 taken 130 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 130 std::vector<int> tmp(merged.size() + segments[i].size());
110 130 SimpleMerge(merged, segments[i], tmp);
111 merged = std::move(tmp);
112 }
113
114 data = std::move(merged);
115 return std::ranges::is_sorted(data);
116 70 }
117
118 100 bool KondakovVShellSortSTL::PostProcessingImpl() {
119 100 return !GetOutput().empty();
120 }
121
122 } // namespace kondakov_v_shell_sort
123