GCC Code Coverage Report

Directory: ./
File: tasks/trofimov_n_hoar_sort_batcher/stl/src/ops_stl.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 48 48 100.0%
Functions: 10 10 100.0%
Branches: 31 46 67.4%
Line Branch Exec Source
1 #include "trofimov_n_hoar_sort_batcher/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <thread>
6 #include <utility>
7 #include <vector>
8
9 #include "trofimov_n_hoar_sort_batcher/common/include/common.hpp"
10
11 namespace trofimov_n_hoar_sort_batcher {
12
13 namespace {
14
15 auto ItAt(std::vector<int> &arr, std::size_t index) {
16 return arr.begin() + static_cast<std::ptrdiff_t>(index);
17 }
18
19 unsigned int GetThreadsCount(std::size_t size) {
20 82 unsigned int threads_count = std::thread::hardware_concurrency();
21
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 82 times.
 82 if (threads_count == 0) {
22 threads_count = 2;
23 }
24 82 return std::min<unsigned int>(threads_count, static_cast<unsigned int>(size));
25 }
26
27 82 std::vector<std::pair<std::size_t, std::size_t>> BuildRanges(std::size_t size, unsigned int threads_count) {
28 82 const std::size_t chunk_size = (size + threads_count - 1) / static_cast<std::size_t>(threads_count);
29 82 std::vector<std::pair<std::size_t, std::size_t>> ranges;
30
1/2
✓ Branch 1 taken 82 times.
✗ Branch 2 not taken.
 82 ranges.reserve(threads_count);
31
32
2/2
✓ Branch 0 taken 262 times.
✓ Branch 1 taken 82 times.
 344 for (std::size_t begin = 0; begin < size; begin += chunk_size) {
33
1/2
✓ Branch 1 taken 262 times.
✗ Branch 2 not taken.
 262 const std::size_t end = std::min(begin + chunk_size, size);
34
1/2
✓ Branch 1 taken 262 times.
✗ Branch 2 not taken.
 262 ranges.emplace_back(begin, end);
35 }
36 82 return ranges;
37 }
38
39 82 void SortRangesInParallel(std::vector<int> &arr, const std::vector<std::pair<std::size_t, std::size_t>> &ranges) {
40
1/2
✓ Branch 1 taken 82 times.
✗ Branch 2 not taken.
 82 std::vector<std::thread> workers;
41
1/2
✓ Branch 1 taken 82 times.
✗ Branch 2 not taken.
 82 workers.reserve(ranges.size());
42
2/2
✓ Branch 0 taken 262 times.
✓ Branch 1 taken 82 times.
 344 for (const auto &[begin, end] : ranges) {
43
1/2
✓ Branch 1 taken 262 times.
✗ Branch 2 not taken.
 524 workers.emplace_back([&arr, begin, end]() { std::sort(ItAt(arr, begin), ItAt(arr, end)); });
44 }
45
2/2
✓ Branch 0 taken 262 times.
✓ Branch 1 taken 82 times.
 344 for (auto &worker : workers) {
46
1/2
✓ Branch 1 taken 262 times.
✗ Branch 2 not taken.
 262 worker.join();
47 }
48 82 }
49
50 82 void MergeSortedRanges(std::vector<int> &arr, std::vector<std::pair<std::size_t, std::size_t>> &ranges) {
51
2/2
✓ Branch 0 taken 156 times.
✓ Branch 1 taken 82 times.
 238 while (ranges.size() > 1) {
52
1/2
✓ Branch 1 taken 156 times.
✗ Branch 2 not taken.
 156 std::vector<std::pair<std::size_t, std::size_t>> merged_ranges;
53
1/2
✓ Branch 1 taken 156 times.
✗ Branch 2 not taken.
 156 merged_ranges.reserve((ranges.size() + 1) / 2);
54
55
2/2
✓ Branch 0 taken 230 times.
✓ Branch 1 taken 156 times.
 386 for (std::size_t i = 0; i < ranges.size(); i += 2) {
56
2/2
✓ Branch 0 taken 50 times.
✓ Branch 1 taken 180 times.
 230 if (i + 1 >= ranges.size()) {
57 merged_ranges.push_back(ranges[i]);
58 50 continue;
59 }
60
61 const auto [left_begin, left_end] = ranges[i];
62 const auto [right_begin, right_end] = ranges[i + 1];
63 180 std::inplace_merge(ItAt(arr, left_begin), ItAt(arr, left_end), ItAt(arr, right_end));
64
1/2
✓ Branch 1 taken 180 times.
✗ Branch 2 not taken.
 180 merged_ranges.emplace_back(left_begin, right_end);
65 }
66
67 ranges.swap(merged_ranges);
68 }
69 82 }
70
71
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 82 times.
 98 void ParallelSortByChunks(std::vector<int> &arr) {
72 const std::size_t size = arr.size();
73
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 82 times.
 98 if (size <= 1) {
74 16 return;
75 }
76
77 const unsigned int threads_count = GetThreadsCount(size);
78 82 auto ranges = BuildRanges(size, threads_count);
79
1/2
✓ Branch 1 taken 82 times.
✗ Branch 2 not taken.
 82 SortRangesInParallel(arr, ranges);
80
1/2
✓ Branch 1 taken 82 times.
✗ Branch 2 not taken.
 82 MergeSortedRanges(arr, ranges);
81 }
82
83 } // namespace
84
85
1/2
✓ Branch 1 taken 98 times.
✗ Branch 2 not taken.
 98 TrofimovNHoarSortBatcherSTL::TrofimovNHoarSortBatcherSTL(const InType &in) {
86 SetTypeOfTask(GetStaticTypeOfTask());
87
1/2
✓ Branch 1 taken 98 times.
✗ Branch 2 not taken.
 98 GetInput() = in;
88 98 }
89
90 98 bool TrofimovNHoarSortBatcherSTL::ValidationImpl() {
91 98 return true;
92 }
93
94 98 bool TrofimovNHoarSortBatcherSTL::PreProcessingImpl() {
95 98 GetOutput() = GetInput();
96 98 return true;
97 }
98
99 98 bool TrofimovNHoarSortBatcherSTL::RunImpl() {
100 auto &data = GetOutput();
101 98 ParallelSortByChunks(data);
102 98 return true;
103 }
104
105 98 bool TrofimovNHoarSortBatcherSTL::PostProcessingImpl() {
106 98 return true;
107 }
108
109 } // namespace trofimov_n_hoar_sort_batcher
110