GCC Code Coverage Report

Directory: ./
File: tasks/kondakov_v_shell_sort/omp/src/ops_omp.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 42 42 100.0%
Functions: 7 7 100.0%
Branches: 33 40 82.5%
Line Branch Exec Source
1 #include "kondakov_v_shell_sort/omp/include/ops_omp.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <utility>
6 #include <vector>
7
8 #include "kondakov_v_shell_sort/common/include/common.hpp"
9 #include "util/include/util.hpp"
10
11 namespace kondakov_v_shell_sort {
12
13 namespace {
14
15 115 void ShellSort(std::vector<int> &data) {
16 const size_t n = data.size();
17
2/2
✓ Branch 0 taken 103 times.
✓ Branch 1 taken 115 times.
 218 for (size_t gap = n / 2; gap > 0; gap /= 2) {
18
2/2
✓ Branch 0 taken 238 times.
✓ Branch 1 taken 103 times.
 341 for (size_t i = gap; i < n; ++i) {
19 238 int value = data[i];
20 size_t j = i;
21
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) {
22 137 data[j] = data[j - gap];
23 j -= gap;
24 }
25 238 data[j] = value;
26 }
27 }
28 115 }
29
30 67 void SimpleMerge(const std::vector<int> &left, const std::vector<int> &right, std::vector<int> &result) {
31 size_t i = 0;
32 size_t j = 0;
33 size_t k = 0;
34
35
4/4
✓ Branch 0 taken 236 times.
✓ Branch 1 taken 27 times.
✓ Branch 2 taken 40 times.
✓ Branch 3 taken 196 times.
 263 while (i < left.size() && j < right.size()) {
36
2/2
✓ Branch 0 taken 91 times.
✓ Branch 1 taken 105 times.
 196 if (left[i] <= right[j]) {
37 91 result[k++] = left[i++];
38 } else {
39 105 result[k++] = right[j++];
40 }
41 }
42
43
2/2
✓ Branch 0 taken 85 times.
✓ Branch 1 taken 67 times.
 152 while (i < left.size()) {
44 85 result[k++] = left[i++];
45 }
46
47
2/2
✓ Branch 0 taken 42 times.
✓ Branch 1 taken 67 times.
 109 while (j < right.size()) {
48 42 result[k++] = right[j++];
49 }
50 67 }
51
52 size_t CalcPartsCount(size_t data_size, int requested_threads) {
53
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 if (data_size == 0) {
54 return 0;
55 }
56 const int threads = std::max(1, requested_threads);
57
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 37 times.
 48 return std::min(static_cast<size_t>(threads), data_size);
58 }
59
60 } // namespace
61
62
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 KondakovVShellSortOMP::KondakovVShellSortOMP(const InType &in) {
63 SetTypeOfTask(GetStaticTypeOfTask());
64
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 GetInput() = in;
65
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 GetOutput() = in;
66 52 }
67
68 52 bool KondakovVShellSortOMP::ValidationImpl() {
69 52 return !GetInput().empty();
70 }
71
72 52 bool KondakovVShellSortOMP::PreProcessingImpl() {
73 52 GetOutput() = GetInput();
74 52 return true;
75 }
76
77
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 48 times.
 52 bool KondakovVShellSortOMP::RunImpl() {
78 std::vector<int> &data = GetOutput();
79
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 48 times.
 52 if (data.size() <= 1) {
80 return true;
81 }
82
83 48 const int num_threads = ppc::util::GetNumThreads();
84 const size_t parts = CalcPartsCount(data.size(), num_threads);
85
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 37 times.
 48 if (parts <= 1) {
86 11 ShellSort(data);
87 return std::ranges::is_sorted(data);
88 }
89
90 37 std::vector<std::vector<int>> segments(parts);
91
92 37 #pragma omp parallel for default(none) shared(data, segments, parts) num_threads(num_threads) schedule(static)
93 for (size_t part = 0; part < parts; ++part) {
94 const size_t begin = (part * data.size()) / parts;
95 const size_t end = ((part + 1) * data.size()) / parts;
96 segments[part] = std::vector<int>(data.begin() + static_cast<std::ptrdiff_t>(begin),
97 data.begin() + static_cast<std::ptrdiff_t>(end));
98 ShellSort(segments[part]);
99 }
100
101 std::vector<int> merged = std::move(segments[0]);
102
2/2
✓ Branch 0 taken 67 times.
✓ Branch 1 taken 37 times.
 104 for (size_t i = 1; i < parts; ++i) {
103
1/4
✓ Branch 1 taken 67 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 67 std::vector<int> tmp(merged.size() + segments[i].size());
104 67 SimpleMerge(merged, segments[i], tmp);
105 merged = std::move(tmp);
106 }
107
108 data = std::move(merged);
109 return std::ranges::is_sorted(data);
110 37 }
111
112 52 bool KondakovVShellSortOMP::PostProcessingImpl() {
113 52 return !GetOutput().empty();
114 }
115
116 } // namespace kondakov_v_shell_sort
117