GCC Code Coverage Report

Directory: ./
File: tasks/gasenin_l_djstra/stl/src/ops_stl.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 83 83 100.0%
Functions: 9 9 100.0%
Branches: 42 50 84.0%
Line Branch Exec Source
1 #include "gasenin_l_djstra/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <cstdint>
5 #include <cstdlib>
6 #include <limits>
7 #include <mutex>
8 #include <thread>
9 #include <vector>
10
11 #include "gasenin_l_djstra/common/include/common.hpp"
12 #include "util/include/util.hpp"
13
14 namespace gasenin_l_djstra {
15
16 24 GaseninLDjstraSTL::GaseninLDjstraSTL(const InType &in) {
17 SetTypeOfTask(GetStaticTypeOfTask());
18 24 GetInput() = in;
19 24 GetOutput() = 0;
20 24 }
21
22 24 bool GaseninLDjstraSTL::ValidationImpl() {
23 24 return GetInput() > 0;
24 }
25
26 24 bool GaseninLDjstraSTL::PreProcessingImpl() {
27 24 const InType n = GetInput();
28 24 const InType inf = std::numeric_limits<InType>::max();
29
30 24 dist_.assign(n, inf);
31 24 visited_.assign(n, 0);
32 24 dist_[0] = 0;
33
34 24 num_threads_ = ppc::util::GetNumThreads();
35 24 local_min_.assign(num_threads_, inf);
36 24 local_vert_.assign(num_threads_, -1);
37
38 24 generation_ = 0;
39 24 pending_ = 0;
40 24 phase_ = Phase::kIdle;
41
42 24 workers_.resize(num_threads_);
43
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 24 times.
 84 for (int thread_id = 0; thread_id < num_threads_; ++thread_id) {
44
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 60 times.
 60 workers_[thread_id] = std::thread(&GaseninLDjstraSTL::WorkerLoop, this, thread_id);
45 }
46
47 24 return true;
48 }
49
50 300 void GaseninLDjstraSTL::DoFindMin(int thread_id) {
51 300 const InType n = GetInput();
52 const InType inf = std::numeric_limits<InType>::max();
53
54 InType thread_min = inf;
55 InType thread_vert = -1;
56
2/2
✓ Branch 0 taken 664 times.
✓ Branch 1 taken 300 times.
 964 for (int idx = thread_id; idx < n; idx += num_threads_) {
57
4/4
✓ Branch 0 taken 392 times.
✓ Branch 1 taken 272 times.
✓ Branch 2 taken 186 times.
✓ Branch 3 taken 206 times.
 664 if (visited_[idx] == 0 && dist_[idx] < thread_min) {
58 thread_min = dist_[idx];
59 thread_vert = idx;
60 }
61 }
62 300 local_min_[thread_id] = thread_min;
63 300 local_vert_[thread_id] = thread_vert;
64 300 }
65
66 300 void GaseninLDjstraSTL::DoRelax(int thread_id) {
67 300 const InType n = GetInput();
68 const InType inf = std::numeric_limits<InType>::max();
69 300 const InType src = global_vertex_;
70
71
2/2
✓ Branch 0 taken 664 times.
✓ Branch 1 taken 300 times.
 964 for (int vertex = thread_id; vertex < n; vertex += num_threads_) {
72
4/6
✓ Branch 0 taken 272 times.
✓ Branch 1 taken 392 times.
✓ Branch 2 taken 272 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 272 times.
✗ Branch 5 not taken.
 664 if (visited_[vertex] == 0 && vertex != src && dist_[src] != inf) {
73
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 176 times.
 368 dist_[vertex] = std::min(dist_[vertex], dist_[src] + std::abs(src - vertex));
74 }
75 }
76 300 }
77
78 60 void GaseninLDjstraSTL::WorkerLoop(int thread_id) {
79 60 int my_gen = 0;
80
81 while (true) {
82 Phase current_phase{};
83 {
84 660 std::unique_lock<std::mutex> lock(mtx_);
85
2/2
✓ Branch 0 taken 618 times.
✓ Branch 1 taken 660 times.
 1278 cv_start_.wait(lock, [&] { return generation_ > my_gen; });
86 660 my_gen = generation_;
87
1/2
✓ Branch 0 taken 660 times.
✗ Branch 1 not taken.
 660 current_phase = phase_;
88 }
89
90
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 600 times.
 660 if (current_phase == Phase::kStop) {
91 60 return;
92 }
93
94
2/2
✓ Branch 0 taken 300 times.
✓ Branch 1 taken 300 times.
 600 if (current_phase == Phase::kFindMin) {
95 300 DoFindMin(thread_id);
96 } else {
97 300 DoRelax(thread_id);
98 }
99
100 {
101 std::scoped_lock<std::mutex> lock(mtx_);
102
2/2
✓ Branch 0 taken 240 times.
✓ Branch 1 taken 360 times.
 600 if (--pending_ == 0) {
103 240 cv_done_.notify_one();
104 }
105 }
106 600 }
107 }
108
109 240 void GaseninLDjstraSTL::Dispatch(Phase phase) {
110 {
111 240 std::scoped_lock<std::mutex> lock(mtx_);
112 240 phase_ = phase;
113 240 pending_ = num_threads_;
114 240 ++generation_;
115 240 cv_start_.notify_all();
116 }
117 std::unique_lock<std::mutex> lock(mtx_);
118
2/2
✓ Branch 0 taken 240 times.
✓ Branch 1 taken 240 times.
 480 cv_done_.wait(lock, [&] { return pending_ == 0; });
119 240 }
120
121 24 bool GaseninLDjstraSTL::RunImpl() {
122 24 const InType n = GetInput();
123 const InType inf = std::numeric_limits<InType>::max();
124
125
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 24 times.
 144 for (int iter = 0; iter < n; ++iter) {
126 120 Dispatch(Phase::kFindMin);
127
128 InType global_min = inf;
129 120 global_vertex_ = -1;
130
2/2
✓ Branch 0 taken 300 times.
✓ Branch 1 taken 120 times.
 420 for (int thread_idx = 0; thread_idx < num_threads_; ++thread_idx) {
131
2/2
✓ Branch 0 taken 156 times.
✓ Branch 1 taken 144 times.
 300 if (local_min_[thread_idx] < global_min) {
132 global_min = local_min_[thread_idx];
133 156 global_vertex_ = local_vert_[thread_idx];
134 }
135 }
136
137
2/4
✓ Branch 0 taken 120 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 120 times.
✗ Branch 3 not taken.
 120 if (global_vertex_ == -1 || global_min == inf) {
138 break;
139 }
140
141
1/2
✓ Branch 0 taken 120 times.
✗ Branch 1 not taken.
 120 visited_[global_vertex_] = 1;
142 std::ranges::fill(local_min_, inf);
143 std::ranges::fill(local_vert_, -1);
144
145 120 Dispatch(Phase::kRelax);
146 }
147
148 int64_t total_sum = 0;
149
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 24 times.
 144 for (int idx = 0; idx < n; ++idx) {
150
1/2
✓ Branch 0 taken 120 times.
✗ Branch 1 not taken.
 120 if (dist_[idx] != inf) {
151 120 total_sum += dist_[idx];
152 }
153 }
154 24 GetOutput() = static_cast<OutType>(total_sum);
155 24 return true;
156 }
157
158 24 bool GaseninLDjstraSTL::PostProcessingImpl() {
159 {
160 24 std::scoped_lock<std::mutex> lock(mtx_);
161 24 phase_ = Phase::kStop;
162 24 ++generation_;
163 24 cv_start_.notify_all();
164 }
165
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 24 times.
 84 for (auto &worker : workers_) {
166 60 worker.join();
167 }
168 24 workers_.clear();
169 24 return true;
170 }
171
172 } // namespace gasenin_l_djstra
173