GCC Code Coverage Report

Directory: ./
File: tasks/nalitov_d_dijkstras_algorithm/omp/src/ops_omp.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 47 51 92.2%
Functions: 8 8 100.0%
Branches: 16 32 50.0%
Line Branch Exec Source
1 #include "nalitov_d_dijkstras_algorithm/omp/include/ops_omp.hpp"
2
3 #include <omp.h>
4
5 #include <algorithm>
6 #include <cstdint>
7 #include <limits>
8 #include <vector>
9
10 #include "nalitov_d_dijkstras_algorithm/common/include/common.hpp"
11
12 namespace nalitov_d_dijkstras_algorithm {
13
14 namespace {
15
16 inline bool SafeAdd(InType a, InType b, InType &result) {
17 if (a > 0 && b > std::numeric_limits<InType>::max() - a) {
18 return false;
19 }
20 if (a < 0 && b < std::numeric_limits<InType>::min() - a) {
21 return false;
22 }
23 result = a + b;
24 return true;
25 }
26
27 inline InType GetEdgeWeight(InType from, InType to) {
28 if (from == to) {
29 return 0;
30 }
31 return (from > to) ? (from - to) : (to - from);
32 }
33
34 int GetWorkerCount() {
35 int worker_count = 1;
36 12 #pragma omp parallel default(none) shared(worker_count)
37 {
38 #pragma omp single
39 worker_count = omp_get_num_threads();
40 }
41 return worker_count;
42 }
43
44 48 InType SelectNextVertexOmp(std::vector<InType> &distances, std::vector<char> &processed, InType k_infinity,
45 int worker_count) {
46 48 const auto vertex_count = static_cast<InType>(distances.size());
47 48 std::vector<InType> thread_best_distance(worker_count, k_infinity);
48
1/4
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 48 std::vector<InType> thread_best_vertex(worker_count, -1);
49 InType selected_vertex = -1;
50
51
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 #pragma omp parallel default(none) shared(vertex_count, distances, processed, thread_best_distance, \
52 thread_best_vertex, worker_count, selected_vertex, k_infinity)
53 {
54 const int tid = omp_get_thread_num();
55 InType best_distance = std::numeric_limits<InType>::max();
56 InType best_vertex = -1;
57
58 #pragma omp for nowait
59 for (InType vertex_idx = 0; vertex_idx < vertex_count; ++vertex_idx) {
60 if (processed[vertex_idx] == 0 && distances[vertex_idx] < best_distance) {
61 best_distance = distances[vertex_idx];
62 best_vertex = vertex_idx;
63 }
64 }
65
66 thread_best_distance[tid] = best_distance;
67 thread_best_vertex[tid] = best_vertex;
68
69 #pragma omp barrier
70 #pragma omp single
71 {
72 InType best_global_distance = std::numeric_limits<InType>::max();
73 for (int thread_idx = 0; thread_idx < worker_count; ++thread_idx) {
74 if (thread_best_vertex[thread_idx] != -1 && (thread_best_distance[thread_idx] < best_global_distance ||
75 (thread_best_distance[thread_idx] == best_global_distance &&
76 thread_best_vertex[thread_idx] < selected_vertex))) {
77 best_global_distance = thread_best_distance[thread_idx];
78 selected_vertex = thread_best_vertex[thread_idx];
79 }
80 }
81 if (selected_vertex != -1 && best_global_distance != k_infinity) {
82 processed[selected_vertex] = 1;
83 } else {
84 selected_vertex = -1;
85 }
86 }
87 }
88 48 return selected_vertex;
89 }
90
91 48 void UpdateNeighborsOmp(InType anchor_vertex, std::vector<InType> &distances, const std::vector<char> &processed,
92 InType k_infinity) {
93 48 const auto vertex_count = static_cast<InType>(distances.size());
94 48 const InType anchor_distance = distances[anchor_vertex];
95
96 48 #pragma omp parallel for default(none) \
97 shared(anchor_vertex, distances, processed, vertex_count, k_infinity, anchor_distance)
98 for (InType neighbor = 0; neighbor < vertex_count; ++neighbor) {
99 if (processed[neighbor] == 0 && neighbor != anchor_vertex) {
100 const InType edge_weight = GetEdgeWeight(anchor_vertex, neighbor);
101 if (anchor_distance == k_infinity) {
102 continue;
103 }
104 InType new_distance = 0;
105 if (!SafeAdd(anchor_distance, edge_weight, new_distance)) {
106 continue;
107 }
108 distances[neighbor] = std::min(new_distance, distances[neighbor]);
109 }
110 }
111 48 }
112
113
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 OutType AccumulateReachableDistanceOmp(const std::vector<InType> &distances, InType k_infinity) {
114 int64_t aggregated_distance = 0;
115 12 const auto vertex_count = static_cast<InType>(distances.size());
116 12 #pragma omp parallel for reduction(+ : aggregated_distance) default(none) shared(distances, vertex_count, k_infinity)
117 for (InType vertex_idx = 0; vertex_idx < vertex_count; ++vertex_idx) {
118 if (distances[vertex_idx] != k_infinity) {
119 aggregated_distance += distances[vertex_idx];
120 }
121 }
122
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 if (aggregated_distance < 0 || aggregated_distance > std::numeric_limits<OutType>::max()) {
123 ✗ return -1;
124 }
125 return static_cast<OutType>(aggregated_distance);
126 }
127
128 } // namespace
129
130 12 NalitovDDijkstrasAlgorithmOmp::NalitovDDijkstrasAlgorithmOmp(const InType &in) {
131 SetTypeOfTask(GetStaticTypeOfTask());
132 12 GetInput() = in;
133 GetOutput() = 0;
134 12 }
135
136 12 bool NalitovDDijkstrasAlgorithmOmp::ValidationImpl() {
137 12 const InType n = GetInput();
138
139 constexpr InType kMaxVertices = 10000;
140
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 if (n <= 0 || n > kMaxVertices) {
141 return false;
142 }
143
144
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 if (GetOutput() != 0) {
145 ✗ return false;
146 }
147
148 return true;
149 }
150
151 12 bool NalitovDDijkstrasAlgorithmOmp::PreProcessingImpl() {
152 12 const InType n = GetInput();
153 12 const InType k_infinity = std::numeric_limits<InType>::max();
154 12 distances_.assign(n, k_infinity);
155
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 processed_.assign(n, 0);
156
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 if (!distances_.empty()) {
157 12 distances_[0] = 0;
158 }
159 12 GetOutput() = 0;
160 12 return true;
161 }
162
163 12 bool NalitovDDijkstrasAlgorithmOmp::RunImpl() {
164 12 const InType n = GetInput();
165
166
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 if (n <= 0) {
167 return false;
168 }
169
170
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 if (n == 1) {
171 ✗ GetOutput() = 0;
172 ✗ return true;
173 }
174
175 if (n < 2) {
176 return false;
177 }
178
179 const InType k_infinity = std::numeric_limits<InType>::max();
180
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 if (distances_.empty()) {
181 return false;
182 }
183 const int worker_count = GetWorkerCount();
184
185
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 12 times.
 60 for (InType iteration = 0; iteration < n; ++iteration) {
186 48 const InType current_vertex = SelectNextVertexOmp(distances_, processed_, k_infinity, worker_count);
187
188
2/4
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 48 if (current_vertex == -1 || distances_[current_vertex] == k_infinity) {
189 break;
190 }
191
192 48 UpdateNeighborsOmp(current_vertex, distances_, processed_, k_infinity);
193 }
194
195 12 const OutType total_sum = AccumulateReachableDistanceOmp(distances_, k_infinity);
196
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 if (total_sum < 0) {
197 return false;
198 }
199
200 12 GetOutput() = total_sum;
201 12 return true;
202 }
203
204 12 bool NalitovDDijkstrasAlgorithmOmp::PostProcessingImpl() {
205 12 return GetOutput() >= 0;
206 }
207
208 } // namespace nalitov_d_dijkstras_algorithm
209