OpenTTD Source 20261112-master-gbcbec5e63f
linkgraphjob.cpp
Go to the documentation of this file.
1/*
2 * This file is part of OpenTTD.
3 * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
4 * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
5 * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <https://www.gnu.org/licenses/old-licenses/gpl-2.0>.
6 */
7
9
10#include "../stdafx.h"
11#include "../core/pool_func.hpp"
12#include "../station_func.h"
13#include "../thread.h"
14#include "../window_func.h"
15#include "linkgraphjob.h"
16#include "linkgraphschedule.h"
17
18#include "../safeguards.h"
19
20/* Initialize the link-graph-job-pool */
23
24
29/* static */ Path *Path::invalid_path = new Path(INVALID_NODE, true);
30
38LinkGraphJob::LinkGraphJob(LinkGraphJobID index, const LinkGraph &orig) :
40 /* Copying the link graph here also copies its index member.
41 * This is on purpose. */
42 link_graph(orig),
43 settings(_settings_game.linkgraph),
44 join_date(TimerGameEconomy::date + (_settings_game.linkgraph.recalc_time / EconomyTime::SECONDS_PER_DAY))
45{
46}
47
52void LinkGraphJob::EraseFlows(StationID from)
53{
54 for (NodeID node_id = 0; node_id < this->Size(); ++node_id) {
55 (*this)[node_id].flows.erase(from);
56 }
57}
58
64{
65 if (!StartNewThread(&this->thread, "ottd:linkgraph", &(LinkGraphSchedule::Run), this)) {
66 /* Of course this will hang a bit.
67 * On the other hand, if you want to play games which make this hang noticeably
68 * on a platform without threads then you'll probably get other problems first.
69 * OK:
70 * If someone comes and tells me that this hangs for them, I'll implement a
71 * smaller grained "Step" method for all handlers and add some more ticks where
72 * "Step" is called. No problem in principle. */
74 }
75}
76
81{
82 if (this->thread.joinable()) {
83 this->thread.join();
84 }
85}
86
91{
92 this->JoinThread();
93
94 /* Don't update stuff from other pools, when everything is being removed.
95 * Accessing other pools may be invalid. */
96 if (CleaningPool()) return;
97
98 /* If the job has been aborted, the job state is invalid.
99 * This should never be reached, as once the job has been marked as aborted
100 * the only valid job operation is to clear the LinkGraphJob pool. */
101 assert(!this->IsJobAborted());
102
103 /* Link graph has been merged into another one. */
104 if (!LinkGraph::IsValidID(this->link_graph.index)) return;
105
106 uint16_t size = this->Size();
107 for (NodeID node_id = 0; node_id < size; ++node_id) {
108 NodeAnnotation &from = this->nodes[node_id];
109
110 /* The station can have been deleted. Remove all flows originating from it then. */
112 if (st == nullptr) {
113 this->EraseFlows(from.base.station);
114 continue;
115 }
116
117 /* Link graph merging and station deletion may change around IDs. Make
118 * sure that everything is still consistent or ignore it otherwise. */
119 GoodsEntry &ge = st->goods[this->Cargo()];
120 if (ge.link_graph != this->link_graph.index || ge.node != node_id) {
121 this->EraseFlows(from.base.station);
122 continue;
123 }
124
126 FlowStatMap &flows = from.flows;
127 FlowStatMap &geflows = ge.GetOrCreateData().flows;
128
129 for (const auto &edge : from.edges) {
130 if (edge.Flow() == 0) continue;
131 NodeID dest_id = edge.base.dest_node;
132 StationID to = this->nodes[dest_id].base.station;
133 Station *st2 = Station::GetIfValid(to);
134 if (st2 == nullptr || st2->goods[this->Cargo()].link_graph != this->link_graph.index ||
135 st2->goods[this->Cargo()].node != dest_id ||
136 !(*lg)[node_id].HasEdgeTo(dest_id) ||
137 (*lg)[node_id][dest_id].LastUpdate() == EconomyTime::INVALID_DATE) {
138 /* Edge has been removed. Delete flows. */
139 std::vector<StationID> erased = flows.DeleteFlows(to);
140 /* Delete old flows for source stations which have been deleted
141 * from the new flows. This avoids flow cycles between old and
142 * new flows. */
143 for (const StationID &station : erased) geflows.erase(station);
144 } else if ((*lg)[node_id][dest_id].last_unrestricted_update == EconomyTime::INVALID_DATE) {
145 /* Edge is fully restricted. */
146 flows.RestrictFlows(to);
147 }
148 }
149
150 /* Swap shares and invalidate ones that are completely deleted. Don't
151 * really delete them as we could then end up with unroutable cargo
152 * somewhere. Do delete them and also reroute relevant cargo if
153 * automatic distribution has been turned off for that cargo. */
154 for (FlowStatMap::iterator it(geflows.begin()); it != geflows.end();) {
155 FlowStatMap::iterator new_it = flows.find(it->first);
156 if (new_it == flows.end()) {
157 if (_settings_game.linkgraph.GetDistributionType(this->Cargo()) != DistributionType::Manual) {
158 it->second.Invalidate();
159 ++it;
160 } else {
161 FlowStat shares(StationID::Invalid(), 1);
162 it->second.SwapShares(shares);
163 geflows.erase(it++);
164 for (FlowStat::SharesMap::const_iterator shares_it(shares.GetShares()->begin());
165 shares_it != shares.GetShares()->end(); ++shares_it) {
166 RerouteCargo(st, this->Cargo(), shares_it->second, st->index);
167 }
168 }
169 } else {
170 it->second.SwapShares(new_it->second);
171 flows.erase(new_it);
172 ++it;
173 }
174 }
175 geflows.insert(flows.begin(), flows.end());
176 if (ge.GetData().IsEmpty()) ge.ClearData();
177 InvalidateWindowData(WindowClass::StationView, st->index, this->Cargo());
178 }
179}
180
187{
188 uint size = this->Size();
189 this->nodes.reserve(size);
190 for (uint i = 0; i < size; ++i) {
191 this->nodes.emplace_back(this->link_graph.nodes[i], this->link_graph.Size());
192 }
193}
194
203void Path::Fork(Path *base, uint cap, int free_cap, uint dist)
204{
205 this->capacity = std::min(base->capacity, cap);
206 this->free_capacity = std::min(base->free_capacity, free_cap);
207 this->distance = base->distance + dist;
208 assert(this->distance > 0);
209 if (this->parent != base) {
210 this->Detach();
211 this->parent = base;
212 this->parent->num_children++;
213 }
214 this->origin = base->origin;
215}
216
225uint Path::AddFlow(uint new_flow, LinkGraphJob &job, uint max_saturation)
226{
227 if (this->parent != nullptr) {
228 LinkGraphJob::EdgeAnnotation &edge = job[this->parent->node][this->node];
229 if (max_saturation != UINT_MAX) {
230 uint usable_cap = edge.base.capacity * max_saturation / 100;
231 if (usable_cap > edge.Flow()) {
232 new_flow = std::min(new_flow, usable_cap - edge.Flow());
233 } else {
234 return 0;
235 }
236 }
237 new_flow = this->parent->AddFlow(new_flow, job, max_saturation);
238 if (this->flow == 0 && new_flow > 0) {
239 job[this->parent->node].paths.push_front(this);
240 }
241 edge.AddFlow(new_flow);
242 }
243 this->flow += new_flow;
244 return new_flow;
245}
246
252Path::Path(NodeID n, bool source) :
253 distance(source ? 0 : UINT_MAX),
254 capacity(source ? UINT_MAX : 0),
255 free_capacity(source ? INT_MAX : INT_MIN),
256 flow(0), node(n), origin(source ? n : INVALID_NODE),
257 num_children(0), parent(nullptr)
258{}
259
Storage class for Economy time constants.
Flow descriptions by origin stations.
std::vector< StationID > DeleteFlows(StationID via)
Delete all flows at a station for specific cargo and destination.
void RestrictFlows(StationID via)
Restrict all flows at a station for specific cargo and destination.
Flow statistics telling how much flow should be sent along a link.
const SharesMap * GetShares() const
Get the actual shares as a const pointer so that they can be iterated over.
Class for calculation jobs to be run on link graphs.
NodeAnnotationVector nodes
Extra node data necessary for link graph calculation.
~LinkGraphJob()
Join the link graph job and destroy it.
TimerGameEconomy::Date join_date
Date when the job is to be joined.
bool IsJobAborted() const
Check if job has been aborted.
void Init()
Initialize the link graph job: Resize nodes and edges and populate them.
LinkGraphJob(LinkGraphJobID index)
Bare constructor, only for save/load.
void SpawnThread()
Spawn a thread if possible and run the link graph job in the thread.
const LinkGraphSettings settings
Copy of _settings_game.linkgraph at spawn time.
CargoType Cargo() const
Get the cargo of the underlying link graph.
void EraseFlows(StationID from)
Erase all flows originating at a specific station.
NodeID Size() const
Get the size of the underlying link graph.
const LinkGraph link_graph
Link graph to by analyzed. Is copied when job is started and mustn't be modified later.
void JoinThread()
Join the calling thread with this job's thread if threading is enabled.
std::thread thread
Thread the job is running in or a default-constructed thread if it's running in the main thread.
static void Run(LinkGraphJob *job)
Run all handlers for the given Job.
A connected component of a link graph.
Definition linkgraph.h:35
A leg of a path in the link graph.
Path(NodeID n, bool source=false)
Create a leg of a path in the link graph.
void AddFlow(uint f)
Increase the flow on this leg only by the specified amount.
static Path * invalid_path
Static instance of an invalid path.
NodeID origin
Link graph node this path originates from.
uint num_children
Number of child legs that have been forked from this path.
void Detach()
Detach this path from its parent.
uint flow
Flow the current run of the mcf solver assigns.
uint distance
Sum(distance of all legs up to this one).
void Fork(Path *base, uint cap, int free_cap, uint dist)
Add this path as a new child to the given base path, thus making this path a "fork" of the base path.
NodeID node
Link graph node this leg passes.
uint capacity
This capacity is min(capacity) of all edges.
Path * parent
Parent leg of this one.
int free_capacity
This capacity is min(edge.capacity - edge.flow) for the current run of Dijkstra.
static constexpr TimerGame< struct Economy >::Date INVALID_DATE
Timer that is increased every 27ms, and counts towards economy time units, expressed in days / months...
@ Manual
Manual distribution. No link graph calculations are run.
Declaration of link graph job classes used for cargo distribution.
Pool< LinkGraphJob, LinkGraphJobID, 32 > LinkGraphJobPool
Type of the pool for link graph jobs.
LinkGraphJobPool _link_graph_job_pool
The actual pool with link graph jobs.
Declaration of link graph schedule used for cargo distribution.
Some methods of Pool are placed here in order to reduce compilation time and binary size.
#define INSTANTIATE_POOL_METHODS(name)
Force instantiation of pool methods so we don't get linker errors.
A number of safeguards to prevent using unsafe methods.
GameSettings _settings_game
Game settings of a running game or the scenario editor.
Definition settings.cpp:61
@ Path
Segment is a path segment.
Definition signal_func.h:58
void RerouteCargo(Station *st, CargoType cargo, StationID avoid, StationID avoid2)
Reroute cargo of type c at station st or in any vehicles unloading there.
Functions related to stations.
Definition of base types and functions in a cross-platform compatible way.
FlowStatMap flows
Planned flows through this station.
Stores station stats for a single cargo.
void ClearData()
Clear optional cargo packet/flow data.
NodeID node
ID of node in link graph referring to this goods entry.
const GoodsEntryData & GetData() const
Get optional cargo packet/flow data.
LinkGraphID link_graph
Link graph this station belongs to.
GoodsEntryData & GetOrCreateData()
Get optional cargo packet/flow data.
Annotation for a link graph edge.
const LinkGraph::BaseEdge & base
Reference to the edge that is annotated.
uint Flow() const
Get the total flow on the edge.
void AddFlow(uint flow)
Add some flow.
Annotation for a link graph node.
const LinkGraph::BaseNode & base
Reference to the node that is annotated.
std::vector< EdgeAnnotation > edges
Annotations for all edges originating at this node.
FlowStatMap flows
Planned flows to other nodes.
uint capacity
Capacity of the link.
Definition linkgraph.h:41
StationID station
Station ID.
Definition linkgraph.h:106
static LinkGraph * Get(auto index)
static Station * GetIfValid(auto index)
Station data structure.
std::array< GoodsEntry, NUM_CARGO > goods
Goods at this station.
Base of all threads.
bool StartNewThread(std::thread *thr, std::string_view name, TFn &&_Fx, TArgs &&... _Ax)
Start a new thread.
Definition thread.h:47
void InvalidateWindowData(WindowClass cls, WindowNumber number, int data, bool gui_scope)
Mark window data of the window of a given class and specific window number as invalid (in need of re-...
Definition window.cpp:3377
Window functions not directly related to making/drawing windows.