GCC Code Coverage Report

Directory: ./
File: tasks/litvyakov_d_shell_sort/tbb/src/ops_tbb.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 41 41 100.0%
Functions: 8 8 100.0%
Branches: 28 40 70.0%
Line Branch Exec Source
1 #include "litvyakov_d_shell_sort/tbb/include/ops_tbb.hpp"
2
3 #include <tbb/tbb.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
12 namespace litvyakov_d_shell_sort {
13
14 48 void LitvyakovDShellSortTBB::BaseShellSort(std::vector<int>::iterator first, std::vector<int>::iterator last) {
15
2/2
✓ Branch 0 taken 192 times.
✓ Branch 1 taken 48 times.
 240 for (std::ptrdiff_t dist = (last - first) / 2; dist > 0; dist /= 2) {
16
2/2
✓ Branch 0 taken 25368 times.
✓ Branch 1 taken 192 times.
 25560 for (auto i = first + dist; i != last; ++i) {
17
4/4
✓ Branch 0 taken 43553 times.
✓ Branch 1 taken 2359 times.
✓ Branch 2 taken 20544 times.
✓ Branch 3 taken 23009 times.
 45912 for (auto j = i; j - first >= dist && (*j < *(j - dist)); j -= dist) {
18 std::swap(*j, *(j - dist));
19 }
20 }
21 }
22 48 }
23
24
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 std::vector<std::size_t> LitvyakovDShellSortTBB::GetBounds(std::size_t n, std::size_t parts) {
25
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 parts = std::max<std::size_t>(1, std::min(parts, n));
26
27 12 std::vector<std::size_t> bounds;
28
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 bounds.reserve(parts + 1);
29
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 bounds.push_back(0);
30
31 12 const std::size_t base = n / parts;
32 12 const std::size_t rem = n % parts;
33
34
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 12 times.
 60 for (std::size_t i = 0; i < parts; ++i) {
35
1/4
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 48 bounds.push_back(bounds.back() + base);
36
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 40 times.
 48 if (i < rem) {
37 8 bounds[i + 1]++;
38 }
39 }
40
41 12 return bounds;
42 }
43
44
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 LitvyakovDShellSortTBB::LitvyakovDShellSortTBB(const InType &in) {
45 SetTypeOfTask(GetStaticTypeOfTask());
46
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 GetInput() = in;
47 16 GetOutput() = std::vector<int>();
48 16 }
49
50 16 bool LitvyakovDShellSortTBB::ValidationImpl() {
51 const InType &vec = GetInput();
52 16 return !vec.empty();
53 }
54
55 16 bool LitvyakovDShellSortTBB::PreProcessingImpl() {
56 16 GetOutput() = GetInput();
57 16 return true;
58 }
59
60
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 4 times.
 16 bool LitvyakovDShellSortTBB::RunImpl() {
61 std::vector<int> &vec = GetOutput();
62
63
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 4 times.
 16 if (vec.size() <= 1) {
64 return true;
65 }
66
67 12 const auto threads = static_cast<std::size_t>(tbb::info::default_concurrency());
68 const std::size_t parts_count = std::min<std::size_t>(threads, vec.size());
69 12 const auto bounds = GetBounds(vec.size(), parts_count);
70
71
1/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 60 tbb::parallel_for(tbb::blocked_range<std::size_t>(0, parts_count), [&](const tbb::blocked_range<std::size_t> &range) {
72
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 48 times.
 96 for (std::size_t i = range.begin(); i != range.end(); ++i) {
73 48 const std::size_t l = bounds[i];
74 48 const std::size_t r = bounds[i + 1];
75 48 BaseShellSort(vec.begin() + static_cast<std::ptrdiff_t>(l), vec.begin() + static_cast<std::ptrdiff_t>(r));
76 }
77 48 });
78
79 // cppreference.com:
80 // void inplace_merge( BidirIt first, BidirIt middle, BidirIt last ),
81 // Merges two consecutive sorted ranges [first, middle) and [middle, last) into one sorted range [first, last).
82
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 12 times.
 48 for (std::size_t i = 1; i < parts_count; ++i) {
83 36 std::inplace_merge(vec.begin(), vec.begin() + static_cast<std::ptrdiff_t>(bounds[i]),
84 36 vec.begin() + static_cast<std::ptrdiff_t>(bounds[i + 1]));
85 }
86
87 return true;
88 }
89
90 16 bool LitvyakovDShellSortTBB::PostProcessingImpl() {
91 16 return true;
92 }
93
94 } // namespace litvyakov_d_shell_sort
95