GCC Code Coverage Report

Directory: ./
File: tasks/votincev_d_radixmerge_sort/tbb/src/ops_tbb.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 50 64 78.1%
Functions: 7 10 70.0%
Branches: 26 54 48.1%
Line Branch Exec Source
1 #include "votincev_d_radixmerge_sort/tbb/include/ops_tbb.hpp"
2
3 #include <tbb/tbb.h>
4
5 #include <algorithm>
6 #include <array>
7 #include <cstddef>
8 #include <cstdint>
9 #include <utility>
10 #include <vector>
11
12 #include "votincev_d_radixmerge_sort/common/include/common.hpp"
13
14 namespace votincev_d_radixmerge_sort {
15
16
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 VotincevDRadixMergeSortTBB::VotincevDRadixMergeSortTBB(const InType &in) {
17 SetTypeOfTask(GetStaticTypeOfTask());
18
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 GetInput() = in;
19 40 }
20
21 40 bool VotincevDRadixMergeSortTBB::ValidationImpl() {
22 40 return !GetInput().empty();
23 }
24
25 40 bool VotincevDRadixMergeSortTBB::PreProcessingImpl() {
26 40 return true;
27 }
28
29 // поразрядная сортировка для локальных блоков
30 40 void VotincevDRadixMergeSortTBB::LocalRadixSort(uint32_t *begin, uint32_t *end) {
31 40 auto n = static_cast<int32_t>(end - begin);
32
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 40 times.
 40 if (n <= 1) {
33 ✗ return;
34 }
35
36 40 uint32_t max_val = *std::max_element(begin, end);
37
38 40 std::vector<uint32_t> buffer(static_cast<size_t>(n));
39 uint32_t *src = begin;
40 uint32_t *dst = buffer.data();
41
42
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 40 times.
 112 for (int64_t exp = 1; (static_cast<int64_t>(max_val) / exp) > 0; exp *= 10) {
43 72 std::array<int32_t, 10> count{};
44
45
2/2
✓ Branch 0 taken 50800 times.
✓ Branch 1 taken 72 times.
 50872 for (int32_t i = 0; i < n; ++i) {
46
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 50800 times.
 50800 count.at(static_cast<size_t>((src[i] / exp) % 10))++;
47 }
48
2/2
✓ Branch 0 taken 648 times.
✓ Branch 1 taken 72 times.
 720 for (int32_t i = 1; i < 10; ++i) {
49 648 count.at(static_cast<size_t>(i)) += count.at(static_cast<size_t>(i - 1));
50 }
51
2/2
✓ Branch 0 taken 50800 times.
✓ Branch 1 taken 72 times.
 50872 for (int32_t i = n - 1; i >= 0; --i) {
52
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 50800 times.
 50800 auto digit = static_cast<size_t>((src[i] / exp) % 10);
53
54 50800 size_t target_idx = static_cast<size_t>(count.at(digit)) - 1;
55 50800 dst[target_idx] = src[i];
56
57 50800 count.at(digit)--;
58 }
59 std::swap(src, dst);
60 }
61
62
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 24 times.
 40 if (src != begin) {
63 16 std::copy(src, src + n, begin);
64 }
65 }
66
67 // слияние двух отсортированных участков
68 ✗ void VotincevDRadixMergeSortTBB::Merge(const uint32_t *src, uint32_t *dst, int32_t left, int32_t mid, int32_t right) {
69 int32_t i = left;
70 int32_t j = mid;
71 int32_t k = left;
72 ✗ while (i < mid && j < right) {
73 ✗ dst[k++] = (src[i] <= src[j]) ? src[i++] : src[j++];
74 }
75 ✗ while (i < mid) {
76 ✗ dst[k++] = src[i++];
77 }
78 ✗ while (j < right) {
79 ✗ dst[k++] = src[j++];
80 }
81 ✗ }
82
83 // параллельная сортировка слиянием(сортировка + слияние)
84 40 void VotincevDRadixMergeSortTBB::ParallelRadixMergeSort(uint32_t *data, int32_t left, int32_t right, uint32_t *temp) {
85 const int32_t grain_size = 4096; // порог для перехода на последовательную сортировку
86
87
1/2
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
 40 if (right - left <= grain_size) {
88 40 LocalRadixSort(data + left, data + right);
89 40 return;
90 }
91
92 ✗ int32_t mid = left + ((right - left) / 2);
93
94 // рекурсивно запускаются две задачи в параллель
95 ✗ tbb::parallel_invoke([&] { ParallelRadixMergeSort(data, left, mid, temp); },
96 ✗ [&] { ParallelRadixMergeSort(data, mid, right, temp); });
97
98 // слияние результатов
99 ✗ Merge(data, temp, left, mid, right);
100
101 // копируем в основной массив
102 ✗ std::copy(temp + left, temp + right, data + left);
103 }
104
105 40 bool VotincevDRadixMergeSortTBB::RunImpl() {
106 const auto &input = GetInput();
107 40 auto n = static_cast<int32_t>(input.size());
108
109 // поиск минимума
110 40 int32_t min_val = tbb::parallel_reduce(tbb::blocked_range<int32_t>(0, n), input[0],
111 40 [&](const tbb::blocked_range<int32_t> &r, int32_t local_min) {
112
2/2
✓ Branch 0 taken 22400 times.
✓ Branch 1 taken 6920 times.
 29320 for (int32_t i = r.begin(); i < r.end(); ++i) {
113
2/2
✓ Branch 0 taken 18202 times.
✓ Branch 1 taken 4198 times.
 40602 local_min = std::min(input[static_cast<size_t>(i)], local_min);
114 }
115 6920 return local_min;
116 40 }, [](int32_t a, int32_t b) { return std::min(a, b); });
117
118 // приведение к положительным uint32
119 40 std::vector<uint32_t> working_array(static_cast<size_t>(n));
120
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 tbb::parallel_for(0, n, [&](int32_t i) {
121 22400 working_array[static_cast<size_t>(i)] =
122 22400 static_cast<uint32_t>(input[static_cast<size_t>(i)]) - static_cast<uint32_t>(min_val);
123 });
124
125 // параллельная сортировка со слиянием
126
2/6
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 40 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 40 std::vector<uint32_t> temp_buffer(static_cast<size_t>(n));
127
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 ParallelRadixMergeSort(working_array.data(), 0, n, temp_buffer.data());
128
129 // восстановление исходных значений
130
1/4
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 40 std::vector<int32_t> result(static_cast<size_t>(n));
131
1/4
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 40 tbb::parallel_for(0, n, [&](int32_t i) {
132 22400 result[static_cast<size_t>(i)] =
133 22400 static_cast<int32_t>(working_array[static_cast<size_t>(i)] + static_cast<uint32_t>(min_val));
134 });
135
136 GetOutput() = std::move(result);
137 40 return true;
138 }
139
140 40 bool VotincevDRadixMergeSortTBB::PostProcessingImpl() {
141 40 return true;
142 }
143
144 } // namespace votincev_d_radixmerge_sort
145