GCC Code Coverage Report

Directory: ./
File: tasks/nalitov_d_dijkstras_algorithm/tbb/src/ops_tbb.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 72 74 97.3%
Functions: 12 12 100.0%
Branches: 53 104 51.0%
Line Branch Exec Source
1 #include "nalitov_d_dijkstras_algorithm/tbb/include/ops_tbb.hpp"
2
3 #include <oneapi/tbb/blocked_range.h>
4 #include <oneapi/tbb/parallel_for.h>
5 #include <oneapi/tbb/parallel_reduce.h>
6
7 #include <algorithm>
8 #include <atomic>
9 #include <cstddef>
10 #include <cstdint>
11 #include <functional>
12 #include <utility>
13 #include <vector>
14
15 #include "nalitov_d_dijkstras_algorithm/common/include/common.hpp"
16
17 namespace nalitov_d_dijkstras_algorithm {
18
19 namespace {
20
21 struct BestVertex {
22 Cost cost{kInf};
23 NodeId vtx{-1};
24
25 [[nodiscard]] bool IsBetterThan(const BestVertex &other) const {
26
3/20
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✓ Branch 10 taken 100 times.
✓ Branch 11 taken 60 times.
✓ Branch 12 taken 100 times.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
 160 return cost < other.cost || (cost == other.cost && vtx != -1 && (other.vtx == -1 || vtx < other.vtx));
27 }
28
29 void Merge(const BestVertex &other) {
30 if (other.IsBetterThan(*this)) {
31 cost = other.cost;
32 ✗ vtx = other.vtx;
33 }
34 }
35 };
36
37 260 BestVertex FindLocalBestVertex(const std::vector<char> &visited, const std::vector<std::atomic<Cost>> &atomic_dist,
38 const tbb::blocked_range<int> &range, BestVertex acc) {
39
2/2
✓ Branch 0 taken 260 times.
✓ Branch 1 taken 260 times.
 520 for (int vi = range.begin(); vi < range.end(); ++vi) {
40
2/2
✓ Branch 0 taken 100 times.
✓ Branch 1 taken 160 times.
 260 const auto idx = static_cast<std::size_t>(vi);
41
42
2/2
✓ Branch 0 taken 100 times.
✓ Branch 1 taken 160 times.
 260 if (visited[idx] != 0) {
43 continue;
44 }
45
46 const Cost dist = atomic_dist[idx].load(std::memory_order_relaxed);
47
48 const BestVertex candidate{
49 .cost = dist,
50 .vtx = vi,
51 };
52
53 if (candidate.IsBetterThan(acc)) {
54 acc = candidate;
55 }
56 }
57
58 260 return acc;
59 }
60
61 60 BestVertex SelectBestVertex(const std::vector<char> &visited, const std::vector<std::atomic<Cost>> &atomic_dist,
62 int n) {
63 60 return tbb::parallel_reduce(tbb::blocked_range<int>(0, n), BestVertex{}, [&](const auto &range, BestVertex acc) {
64 260 return FindLocalBestVertex(visited, atomic_dist, range, acc);
65 60 }, [](BestVertex lhs, const BestVertex &rhs) {
66 lhs.Merge(rhs);
67 return lhs;
68 60 });
69 }
70
71 void RelaxEdge(std::atomic<Cost> &target, Cost candidate) {
72 Cost old = target.load(std::memory_order_relaxed);
73
74
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 while (candidate < old) {
75
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 if (target.compare_exchange_weak(old, candidate, std::memory_order_relaxed)) {
76 break;
77 }
78 }
79 }
80
81 60 void RelaxNeighbors(const std::vector<std::pair<NodeId, Cost>> &neighbors, Cost pivot_cost,
82 const std::vector<char> &visited, std::vector<std::atomic<Cost>> &atomic_dist) {
83 108 tbb::parallel_for(tbb::blocked_range<std::size_t>(0, neighbors.size()), [&](const auto &range) {
84
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 48 times.
 96 for (std::size_t ei = range.begin(); ei < range.end(); ++ei) {
85
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 const auto [target, weight] = neighbors[ei];
86 48 const auto target_idx = static_cast<std::size_t>(target);
87
88
2/4
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 48 if (visited[target_idx] != 0 || pivot_cost > kInf - weight) {
89 ✗ continue;
90 }
91
92 48 RelaxEdge(atomic_dist[target_idx], pivot_cost + weight);
93 }
94 48 });
95 60 }
96
97 16 std::int64_t SumDistances(const std::vector<std::atomic<Cost>> &atomic_dist, std::size_t n) {
98 32 return tbb::parallel_reduce(tbb::blocked_range<std::size_t>(0, n), std::int64_t{0},
99 76 [&](const auto &range, std::int64_t acc) {
100
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 60 times.
 120 for (std::size_t i = range.begin(); i < range.end(); ++i) {
101
1/2
✓ Branch 0 taken 60 times.
✗ Branch 1 not taken.
 60 const Cost dist = atomic_dist[i].load(std::memory_order_relaxed);
102
103
1/2
✓ Branch 0 taken 60 times.
✗ Branch 1 not taken.
 60 if (dist != kInf) {
104 60 acc += static_cast<std::int64_t>(dist);
105 }
106 }
107
108 60 return acc;
109 16 }, std::plus<>());
110 }
111
112 } // namespace
113
114
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 NalitovDDijkstrasAlgorithmTBB::NalitovDDijkstrasAlgorithmTBB(const InType &in) {
115 SetTypeOfTask(GetStaticTypeOfTask());
116 GetInput() = in;
117 16 GetOutput() = 0;
118 16 }
119
120 16 bool NalitovDDijkstrasAlgorithmTBB::ValidationImpl() {
121 const InType &in = GetInput();
122
123
3/6
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 16 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 16 times.
✗ Branch 5 not taken.
 16 if (in.n <= 0 || in.n > 10000 || in.source < 0 || in.source >= in.n) {
124 return false;
125 }
126
127 return std::ranges::all_of(in.arcs, [&in](const Arc &arc) {
128
5/10
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 48 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 48 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 48 times.
✗ Branch 9 not taken.
 48 return arc.from >= 0 && arc.to >= 0 && arc.from < in.n && arc.to < in.n && arc.weight >= 0;
129 });
130 }
131
132 16 bool NalitovDDijkstrasAlgorithmTBB::PreProcessingImpl() {
133 const InType &in = GetInput();
134 16 const auto vertex_count = static_cast<std::size_t>(in.n);
135
136 16 std::vector<std::size_t> out_degree(vertex_count, 0);
137
138
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 16 times.
 64 for (const Arc &arc : in.arcs) {
139 48 ++out_degree[static_cast<std::size_t>(arc.from)];
140 }
141
142
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 graph_.assign(vertex_count, {});
143
144
1/4
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 16 std::vector<std::atomic<std::size_t>> row_next(vertex_count);
145
146
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 16 times.
 76 for (std::size_t vi = 0; vi < vertex_count; ++vi) {
147
1/2
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
 60 graph_[vi].resize(out_degree[vi]);
148 row_next[vi].store(0, std::memory_order_relaxed);
149 }
150
151
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 64 tbb::parallel_for(tbb::blocked_range<std::size_t>(0, in.arcs.size()), [&](const auto &range) {
152
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 48 times.
 96 for (std::size_t ei = range.begin(); ei < range.end(); ++ei) {
153 48 const Arc &arc = in.arcs[ei];
154 48 const auto from = static_cast<std::size_t>(arc.from);
155
156 48 const std::size_t slot = row_next[from].fetch_add(1, std::memory_order_relaxed);
157 48 graph_[from][slot] = {arc.to, arc.weight};
158 }
159 48 });
160
161
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 dist_.assign(vertex_count, kInf);
162
1/4
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 16 visited_.assign(vertex_count, 0);
163
1/2
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
 16 dist_[static_cast<std::size_t>(in.source)] = 0;
164
165 16 return true;
166 }
167
168 16 bool NalitovDDijkstrasAlgorithmTBB::RunImpl() {
169 16 const int n = GetInput().n;
170 16 const auto vertex_count = static_cast<std::size_t>(n);
171
172 16 std::vector<std::atomic<Cost>> atomic_dist(vertex_count);
173
174
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 16 times.
 76 for (std::size_t vi = 0; vi < vertex_count; ++vi) {
175 60 atomic_dist[vi].store(dist_[vi], std::memory_order_relaxed);
176 }
177
178
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 16 times.
 76 for (int step = 0; step < n; ++step) {
179
1/2
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
 60 const BestVertex pivot = SelectBestVertex(visited_, atomic_dist, n);
180
181
2/4
✓ Branch 0 taken 60 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 60 times.
✗ Branch 3 not taken.
 60 if (pivot.vtx == -1 || pivot.cost == kInf) {
182 break;
183 }
184
185
1/2
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
 60 visited_[static_cast<std::size_t>(pivot.vtx)] = 1;
186
187 const auto &neighbors = graph_[static_cast<std::size_t>(pivot.vtx)];
188
1/2
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
 60 RelaxNeighbors(neighbors, pivot.cost, visited_, atomic_dist);
189 }
190
191
2/4
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 16 times.
✗ Branch 4 not taken.
 16 GetOutput() = static_cast<OutType>(SumDistances(atomic_dist, vertex_count));
192
193 16 return true;
194 }
195
196 16 bool NalitovDDijkstrasAlgorithmTBB::PostProcessingImpl() {
197 16 return GetOutput() >= 0;
198 }
199
200 } // namespace nalitov_d_dijkstras_algorithm
201