GCC Code Coverage Report

Directory: ./
File: tasks/litvyakov_d_shell_sort/omp/src/ops_omp.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 37 37 100.0%
Functions: 7 7 100.0%
Branches: 26 34 76.5%
Line Branch Exec Source
1 #include "litvyakov_d_shell_sort/omp/include/ops_omp.hpp"
2
3 #include <omp.h>
4
5 #include <algorithm>
6 #include <cstddef>
7 #include <cstdio>
8 #include <vector>
9
10 #include "litvyakov_d_shell_sort/common/include/common.hpp"
11 #include "util/include/util.hpp"
12
13 namespace litvyakov_d_shell_sort {
14
15 30 void LitvyakovDShellSortOMP::BaseShellSort(std::vector<int>::iterator first, std::vector<int>::iterator last) {
16
2/2
✓ Branch 0 taken 139 times.
✓ Branch 1 taken 30 times.
 169 for (std::ptrdiff_t dist = (last - first) / 2; dist > 0; dist /= 2) {
17
2/2
✓ Branch 0 taken 29735 times.
✓ Branch 1 taken 139 times.
 29874 for (auto i = first + dist; i != last; ++i) {
18
4/4
✓ Branch 0 taken 53058 times.
✓ Branch 1 taken 2285 times.
✓ Branch 2 taken 25608 times.
✓ Branch 3 taken 27450 times.
 55343 for (auto j = i; j - first >= dist && (*j < *(j - dist)); j -= dist) {
19 std::swap(*j, *(j - dist));
20 }
21 }
22 }
23 30 }
24
25
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 std::vector<std::size_t> LitvyakovDShellSortOMP::GetBounds(std::size_t n, std::size_t parts) {
26
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 3 times.
 12 parts = std::max<std::size_t>(1, std::min(parts, n));
27
28 12 std::vector<std::size_t> bounds;
29
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 bounds.reserve(parts + 1);
30
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 bounds.push_back(0);
31
32 12 const std::size_t base = n / parts;
33 12 const std::size_t rem = n % parts;
34
35
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 12 times.
 42 for (std::size_t i = 0; i < parts; ++i) {
36
1/4
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 30 bounds.push_back(bounds.back() + base);
37
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 25 times.
 30 if (i < rem) {
38 5 bounds[i + 1]++;
39 }
40 }
41
42 12 return bounds;
43 }
44
45
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 LitvyakovDShellSortOMP::LitvyakovDShellSortOMP(const InType &in) {
46 SetTypeOfTask(GetStaticTypeOfTask());
47
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 GetInput() = in;
48 16 GetOutput() = std::vector<int>();
49 16 }
50
51 16 bool LitvyakovDShellSortOMP::ValidationImpl() {
52 const InType &vec = GetInput();
53 16 return !vec.empty();
54 }
55
56 16 bool LitvyakovDShellSortOMP::PreProcessingImpl() {
57 16 GetOutput() = GetInput();
58 16 return true;
59 }
60
61
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 4 times.
 16 bool LitvyakovDShellSortOMP::RunImpl() {
62 std::vector<int> &vec = GetOutput();
63
64
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 4 times.
 16 if (vec.size() <= 1) {
65 return true;
66 }
67
68 12 const std::size_t threads = std::max(1, ppc::util::GetNumThreads());
69 const std::size_t parts_count = std::min<std::size_t>(threads, vec.size());
70 12 const auto bounds = GetBounds(vec.size(), parts_count);
71 12 int parts_count_t = static_cast<int>(parts_count);
72
73 12 #pragma omp parallel for default(none) shared(vec, bounds, parts_count_t) schedule(static)
74 for (int i = 0; i < parts_count_t; ++i) {
75 const std::size_t l = bounds[i];
76 const std::size_t r = bounds[i + 1];
77 BaseShellSort(vec.begin() + static_cast<std::ptrdiff_t>(l), vec.begin() + static_cast<std::ptrdiff_t>(r));
78 }
79
80 // cppreference.com:
81 // void inplace_merge( BidirIt first, BidirIt middle, BidirIt last ),
82 // Merges two consecutive sorted ranges [first, middle) and [middle, last) into one sorted range [first, last).
83
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 12 times.
 30 for (std::size_t i = 1; i < parts_count; ++i) {
84 18 std::inplace_merge(vec.begin(), vec.begin() + static_cast<std::ptrdiff_t>(bounds[i]),
85 18 vec.begin() + static_cast<std::ptrdiff_t>(bounds[i + 1]));
86 }
87
88 return true;
89 }
90
91 16 bool LitvyakovDShellSortOMP::PostProcessingImpl() {
92 16 return true;
93 }
94
95 } // namespace litvyakov_d_shell_sort
96