GCC Code Coverage Report

Directory: ./
File: tasks/gasenin_l_djstra/omp/src/ops_omp.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 30 30 100.0%
Functions: 6 6 100.0%
Branches: 5 10 50.0%
Line Branch Exec Source
1 #include "gasenin_l_djstra/omp/include/ops_omp.hpp"
2
3 #include <omp.h>
4
5 #include <algorithm>
6 #include <cstdint>
7 #include <cstdlib>
8 #include <limits>
9 #include <vector>
10
11 #include "gasenin_l_djstra/common/include/common.hpp"
12
13 namespace gasenin_l_djstra {
14
15 namespace {
16
17 int GetNumThreads() {
18 int num_threads = 1;
19
20 12 #pragma omp parallel default(none) shared(num_threads)
21 {
22 #pragma omp single
23 num_threads = omp_get_num_threads();
24 }
25
26 return num_threads;
27 }
28
29 60 InType FindGlobalVertexOMP(const InType n, const InType inf, std::vector<InType> &dist, std::vector<char> &visited,
30 const int num_threads) {
31 60 std::vector<InType> local_min(num_threads, inf);
32
1/4
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 60 std::vector<InType> local_vertex(num_threads, -1);
33
34 InType global_vertex = -1;
35
36
1/2
✓ Branch 0 taken 60 times.
✗ Branch 1 not taken.
 60 #pragma omp parallel default(none) shared(n, inf, dist, visited, local_min, local_vertex, global_vertex, num_threads)
37 {
38 const int thread_id = omp_get_thread_num();
39
40 InType thread_min = inf;
41 InType thread_vertex = -1;
42
43 #pragma omp for nowait
44 for (int index = 0; index < n; ++index) {
45 if (visited[index] == 0 && dist[index] < thread_min) {
46 thread_min = dist[index];
47 thread_vertex = index;
48 }
49 }
50
51 local_min[thread_id] = thread_min;
52 local_vertex[thread_id] = thread_vertex;
53
54 #pragma omp barrier
55
56 #pragma omp single
57 {
58 InType global_min = inf;
59
60 for (int thread_idx = 0; thread_idx < num_threads; ++thread_idx) {
61 if (local_min[thread_idx] < global_min) {
62 global_min = local_min[thread_idx];
63 global_vertex = local_vertex[thread_idx];
64 }
65 }
66
67 if (global_vertex != -1 && global_min != inf) {
68 visited[global_vertex] = 1;
69 } else {
70 global_vertex = -1;
71 }
72 }
73 }
74
75 60 return global_vertex;
76 }
77
78 void RelaxEdgesOMP(const InType n, const InType inf, const InType global_vertex, std::vector<InType> &dist,
79 std::vector<char> &visited) {
80 60 #pragma omp parallel for default(none) shared(n, inf, global_vertex, dist, visited)
81 for (int vertex = 0; vertex < n; ++vertex) {
82 if (visited[vertex] == 0 && vertex != global_vertex) {
83 const InType weight = std::abs(global_vertex - vertex);
84
85 if (dist[global_vertex] != inf) {
86 const InType new_dist = dist[global_vertex] + weight;
87 dist[vertex] = std::min(dist[vertex], new_dist);
88 }
89 }
90 }
91 }
92
93 int64_t CalculateTotalSumOMP(const InType n, const InType inf, std::vector<InType> &dist) {
94 int64_t total_sum = 0;
95
96 12 #pragma omp parallel for reduction(+ : total_sum) default(none) shared(n, inf, dist)
97 for (int i = 0; i < n; ++i) {
98 if (dist[i] != inf) {
99 total_sum += dist[i];
100 }
101 }
102
103 return total_sum;
104 }
105
106 } // namespace
107
108 12 GaseninLDjstraOMP::GaseninLDjstraOMP(const InType &in) {
109 SetTypeOfTask(GetStaticTypeOfTask());
110 12 GetInput() = in;
111 GetOutput() = 0;
112 12 }
113
114 12 bool GaseninLDjstraOMP::ValidationImpl() {
115 12 return GetInput() > 0;
116 }
117
118 12 bool GaseninLDjstraOMP::PreProcessingImpl() {
119 12 const InType n = GetInput();
120 12 const InType inf = std::numeric_limits<InType>::max();
121
122 12 dist_.assign(n, inf);
123 12 visited_.assign(n, 0);
124
125 12 dist_[0] = 0;
126 12 return true;
127 }
128
129 12 bool GaseninLDjstraOMP::RunImpl() {
130 12 const InType n = GetInput();
131 const InType inf = std::numeric_limits<InType>::max();
132
133 const int num_threads = GetNumThreads();
134
135
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 12 times.
 72 for (int iteration = 0; iteration < n; ++iteration) {
136 60 InType global_vertex = FindGlobalVertexOMP(n, inf, dist_, visited_, num_threads);
137
138
1/2
✓ Branch 0 taken 60 times.
✗ Branch 1 not taken.
 60 if (global_vertex == -1) {
139 break;
140 }
141
142 RelaxEdgesOMP(n, inf, global_vertex, dist_, visited_);
143 }
144
145 12 const int64_t total_sum = CalculateTotalSumOMP(n, inf, dist_);
146
147 12 GetOutput() = static_cast<OutType>(total_sum);
148 12 return true;
149 }
150
151 12 bool GaseninLDjstraOMP::PostProcessingImpl() {
152 12 return true;
153 }
154
155 } // namespace gasenin_l_djstra
156