GCC Code Coverage Report

Directory: ./
File: tasks/votincev_d_radixmerge_sort/omp/src/ops_omp.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 46 47 97.9%
Functions: 7 7 100.0%
Branches: 26 38 68.4%
Line Branch Exec Source
1 #include "votincev_d_radixmerge_sort/omp/include/ops_omp.hpp"
2
3 #include <omp.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 VotincevDRadixMergeSortOMP::VotincevDRadixMergeSortOMP(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 VotincevDRadixMergeSortOMP::ValidationImpl() {
22 40 return !GetInput().empty();
23 }
24
25 40 bool VotincevDRadixMergeSortOMP::PreProcessingImpl() {
26 40 return true;
27 }
28
29 100 void VotincevDRadixMergeSortOMP::LocalRadixSort(uint32_t *begin, uint32_t *end) {
30 100 auto n = static_cast<int32_t>(end - begin);
31
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 100 times.
 100 if (n <= 1) {
32 ✗ return;
33 }
34
35 100 uint32_t max_val = *std::max_element(begin, end);
36
37 100 std::vector<uint32_t> buffer(static_cast<size_t>(n));
38 uint32_t *src = begin;
39 uint32_t *dst = buffer.data();
40
41
2/2
✓ Branch 0 taken 180 times.
✓ Branch 1 taken 100 times.
 280 for (int64_t exp = 1; (static_cast<int64_t>(max_val) / exp) > 0; exp *= 10) {
42 180 std::array<int32_t, 10> count{};
43
44
2/2
✓ Branch 0 taken 50800 times.
✓ Branch 1 taken 180 times.
 50980 for (int32_t i = 0; i < n; ++i) {
45
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 50800 times.
 50800 count.at(static_cast<size_t>((src[i] / exp) % 10))++;
46 }
47
2/2
✓ Branch 0 taken 1620 times.
✓ Branch 1 taken 180 times.
 1800 for (int32_t i = 1; i < 10; ++i) {
48 1620 count.at(static_cast<size_t>(i)) += count.at(static_cast<size_t>(i - 1));
49 }
50
2/2
✓ Branch 0 taken 50800 times.
✓ Branch 1 taken 180 times.
 50980 for (int32_t i = n - 1; i >= 0; --i) {
51
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 50800 times.
 50800 auto digit = static_cast<size_t>((src[i] / exp) % 10);
52
53 50800 size_t target_idx = static_cast<size_t>(count.at(digit)) - 1;
54 50800 dst[target_idx] = src[i];
55
56 50800 count.at(digit)--;
57 }
58 std::swap(src, dst);
59 }
60
61
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 60 times.
 100 if (src != begin) {
62 40 std::copy(src, src + n, begin);
63 }
64 }
65
66 60 void VotincevDRadixMergeSortOMP::Merge(const uint32_t *src, uint32_t *dst, int32_t left, int32_t mid, int32_t right) {
67 int32_t i = left;
68 int32_t j = mid;
69 int32_t k = left;
70
2/2
✓ Branch 0 taken 23706 times.
✓ Branch 1 taken 60 times.
 23766 while (i < mid && j < right) {
71
2/2
✓ Branch 0 taken 13758 times.
✓ Branch 1 taken 9948 times.
 23706 dst[k++] = (src[i] <= src[j]) ? src[i++] : src[j++];
72 }
73
2/2
✓ Branch 0 taken 252 times.
✓ Branch 1 taken 60 times.
 312 while (i < mid) {
74 252 dst[k++] = src[i++];
75 }
76
2/2
✓ Branch 0 taken 2179 times.
✓ Branch 1 taken 60 times.
 2239 while (j < right) {
77 2179 dst[k++] = src[j++];
78 }
79 60 }
80
81 40 bool VotincevDRadixMergeSortOMP::RunImpl() {
82 const auto &input = GetInput();
83 40 auto n = static_cast<int32_t>(input.size());
84
85
1/2
✓ Branch 2 taken 40 times.
✗ Branch 3 not taken.
 40 std::vector<uint32_t> working_array(static_cast<size_t>(n));
86 40 int32_t min_val = input[0];
87
88 40 #pragma omp parallel for reduction(min : min_val) default(none) shared(n, input)
89 for (int32_t i = 0; i < n; ++i) {
90 min_val = std::min(input[i], min_val);
91 }
92
93 40 #pragma omp parallel for default(none) shared(n, working_array, input, min_val)
94 for (int32_t i = 0; i < n; ++i) {
95 working_array[static_cast<size_t>(i)] = static_cast<uint32_t>(input[i]) - static_cast<uint32_t>(min_val);
96 }
97
98
1/4
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 40 std::vector<uint32_t> temp_buffer(static_cast<size_t>(n));
99
100 40 #pragma omp parallel default(none) shared(n, working_array, temp_buffer)
101 {
102 int tid = omp_get_thread_num();
103 int n_threads = omp_get_num_threads();
104
105 int32_t items = n / n_threads;
106 int32_t rem = n % n_threads;
107 int32_t l = (tid * items) + std::min(tid, rem);
108 int32_t r = l + items + (tid < rem ? 1 : 0);
109
110 if (l < r) {
111 LocalRadixSort(working_array.data() + l, working_array.data() + r);
112 }
113
114 for (int32_t step = 1; step < n_threads; step *= 2) {
115 #pragma omp barrier
116 if ((tid % (2 * step) == 0) && (tid + step < n_threads)) {
117 int32_t m = ((tid + step) * items) + std::min(tid + step, rem);
118 int32_t next_tid = std::min(tid + (2 * step), n_threads);
119 int32_t next_r = (next_tid * items) + std::min(next_tid, rem);
120
121 Merge(working_array.data(), temp_buffer.data(), l, m, next_r);
122 std::copy(temp_buffer.data() + l, temp_buffer.data() + next_r, working_array.data() + l);
123 }
124 }
125 }
126
127
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));
128 40 #pragma omp parallel for default(none) shared(n, result, working_array, min_val)
129 for (int32_t i = 0; i < n; ++i) {
130 result[static_cast<size_t>(i)] =
131 static_cast<int32_t>(working_array[static_cast<size_t>(i)] + static_cast<uint32_t>(min_val));
132 }
133
134 GetOutput() = std::move(result);
135 40 return true;
136 }
137
138 40 bool VotincevDRadixMergeSortOMP::PostProcessingImpl() {
139 40 return true;
140 }
141
142 } // namespace votincev_d_radixmerge_sort
143