OpenTTD Source  20241108-master-g80f628063a
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 <http://www.gnu.org/licenses/>.
6  */
7 
10 #include "../stdafx.h"
11 #include "../core/pool_func.hpp"
12 #include "../window_func.h"
13 #include "linkgraphjob.h"
14 #include "linkgraphschedule.h"
15 
16 #include "../safeguards.h"
17 
18 /* Initialize the link-graph-job-pool */
21 
22 
27 /* static */ Path *Path::invalid_path = new Path(INVALID_NODE, true);
28 
36  /* Copying the link graph here also copies its index member.
37  * This is on purpose. */
38  link_graph(orig),
39  settings(_settings_game.linkgraph),
40  join_date(TimerGameEconomy::date + (_settings_game.linkgraph.recalc_time / EconomyTime::SECONDS_PER_DAY)),
41  job_completed(false),
42  job_aborted(false)
43 {
44 }
45 
50 void LinkGraphJob::EraseFlows(NodeID from)
51 {
52  for (NodeID node_id = 0; node_id < this->Size(); ++node_id) {
53  (*this)[node_id].flows.erase(from);
54  }
55 }
56 
62 {
63  if (!StartNewThread(&this->thread, "ottd:linkgraph", &(LinkGraphSchedule::Run), this)) {
64  /* Of course this will hang a bit.
65  * On the other hand, if you want to play games which make this hang noticeably
66  * on a platform without threads then you'll probably get other problems first.
67  * OK:
68  * If someone comes and tells me that this hangs for them, I'll implement a
69  * smaller grained "Step" method for all handlers and add some more ticks where
70  * "Step" is called. No problem in principle. */
72  }
73 }
74 
79 {
80  if (this->thread.joinable()) {
81  this->thread.join();
82  }
83 }
84 
89 {
90  this->JoinThread();
91 
92  /* Don't update stuff from other pools, when everything is being removed.
93  * Accessing other pools may be invalid. */
94  if (CleaningPool()) return;
95 
96  /* If the job has been aborted, the job state is invalid.
97  * This should never be reached, as once the job has been marked as aborted
98  * the only valid job operation is to clear the LinkGraphJob pool. */
99  assert(!this->IsJobAborted());
100 
101  /* Link graph has been merged into another one. */
102  if (!LinkGraph::IsValidID(this->link_graph.index)) return;
103 
104  uint16_t size = this->Size();
105  for (NodeID node_id = 0; node_id < size; ++node_id) {
106  NodeAnnotation &from = this->nodes[node_id];
107 
108  /* The station can have been deleted. Remove all flows originating from it then. */
110  if (st == nullptr) {
111  this->EraseFlows(node_id);
112  continue;
113  }
114 
115  /* Link graph merging and station deletion may change around IDs. Make
116  * sure that everything is still consistent or ignore it otherwise. */
117  GoodsEntry &ge = st->goods[this->Cargo()];
118  if (ge.link_graph != this->link_graph.index || ge.node != node_id) {
119  this->EraseFlows(node_id);
120  continue;
121  }
122 
124  FlowStatMap &flows = from.flows;
125 
126  for (const auto &edge : from.edges) {
127  if (edge.Flow() == 0) continue;
128  NodeID dest_id = edge.base.dest_node;
129  StationID to = this->nodes[dest_id].base.station;
130  Station *st2 = Station::GetIfValid(to);
131  if (st2 == nullptr || st2->goods[this->Cargo()].link_graph != this->link_graph.index ||
132  st2->goods[this->Cargo()].node != dest_id ||
133  !(*lg)[node_id].HasEdgeTo(dest_id) ||
134  (*lg)[node_id][dest_id].LastUpdate() == EconomyTime::INVALID_DATE) {
135  /* Edge has been removed. Delete flows. */
136  StationIDStack erased = flows.DeleteFlows(to);
137  /* Delete old flows for source stations which have been deleted
138  * from the new flows. This avoids flow cycles between old and
139  * new flows. */
140  while (!erased.IsEmpty()) ge.flows.erase(erased.Pop());
141  } else if ((*lg)[node_id][dest_id].last_unrestricted_update == EconomyTime::INVALID_DATE) {
142  /* Edge is fully restricted. */
143  flows.RestrictFlows(to);
144  }
145  }
146 
147  /* Swap shares and invalidate ones that are completely deleted. Don't
148  * really delete them as we could then end up with unroutable cargo
149  * somewhere. Do delete them and also reroute relevant cargo if
150  * automatic distribution has been turned off for that cargo. */
151  for (FlowStatMap::iterator it(ge.flows.begin()); it != ge.flows.end();) {
152  FlowStatMap::iterator new_it = flows.find(it->first);
153  if (new_it == flows.end()) {
154  if (_settings_game.linkgraph.GetDistributionType(this->Cargo()) != DT_MANUAL) {
155  it->second.Invalidate();
156  ++it;
157  } else {
158  FlowStat shares(INVALID_STATION, 1);
159  it->second.SwapShares(shares);
160  ge.flows.erase(it++);
161  for (FlowStat::SharesMap::const_iterator shares_it(shares.GetShares()->begin());
162  shares_it != shares.GetShares()->end(); ++shares_it) {
163  RerouteCargo(st, this->Cargo(), shares_it->second, st->index);
164  }
165  }
166  } else {
167  it->second.SwapShares(new_it->second);
168  flows.erase(new_it);
169  ++it;
170  }
171  }
172  ge.flows.insert(flows.begin(), flows.end());
173  InvalidateWindowData(WC_STATION_VIEW, st->index, this->Cargo());
174  }
175 }
176 
183 {
184  uint size = this->Size();
185  this->nodes.reserve(size);
186  for (uint i = 0; i < size; ++i) {
187  this->nodes.emplace_back(this->link_graph.nodes[i], this->link_graph.Size());
188  }
189 }
190 
199 void Path::Fork(Path *base, uint cap, int free_cap, uint dist)
200 {
201  this->capacity = std::min(base->capacity, cap);
202  this->free_capacity = std::min(base->free_capacity, free_cap);
203  this->distance = base->distance + dist;
204  assert(this->distance > 0);
205  if (this->parent != base) {
206  this->Detach();
207  this->parent = base;
208  this->parent->num_children++;
209  }
210  this->origin = base->origin;
211 }
212 
221 uint Path::AddFlow(uint new_flow, LinkGraphJob &job, uint max_saturation)
222 {
223  if (this->parent != nullptr) {
224  LinkGraphJob::EdgeAnnotation &edge = job[this->parent->node][this->node];
225  if (max_saturation != UINT_MAX) {
226  uint usable_cap = edge.base.capacity * max_saturation / 100;
227  if (usable_cap > edge.Flow()) {
228  new_flow = std::min(new_flow, usable_cap - edge.Flow());
229  } else {
230  return 0;
231  }
232  }
233  new_flow = this->parent->AddFlow(new_flow, job, max_saturation);
234  if (this->flow == 0 && new_flow > 0) {
235  job[this->parent->node].paths.push_front(this);
236  }
237  edge.AddFlow(new_flow);
238  }
239  this->flow += new_flow;
240  return new_flow;
241 }
242 
248 Path::Path(NodeID n, bool source) :
249  distance(source ? 0 : UINT_MAX),
250  capacity(source ? UINT_MAX : 0),
251  free_capacity(source ? INT_MAX : INT_MIN),
252  flow(0), node(n), origin(source ? n : INVALID_NODE),
253  num_children(0), parent(nullptr)
254 {}
255 
Storage class for Economy time constants.
Flow descriptions by origin stations.
Definition: station_base.h:148
StationIDStack 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.
Definition: station_base.h:32
const SharesMap * GetShares() const
Get the actual shares as a const pointer so that they can be iterated over.
Definition: station_base.h:88
Class for calculation jobs to be run on link graphs.
Definition: linkgraphjob.h:29
NodeAnnotationVector nodes
Extra node data necessary for link graph calculation.
Definition: linkgraphjob.h:167
~LinkGraphJob()
Join the link graph job and destroy it.
LinkGraphJob()
Bare constructor, only for save/load.
Definition: linkgraphjob.h:180
bool IsJobAborted() const
Check if job has been aborted.
Definition: linkgraphjob.h:200
void Init()
Initialize the link graph job: Resize nodes and edges and populate them.
void SpawnThread()
Spawn a thread if possible and run the link graph job in the thread.
void EraseFlows(NodeID from)
Erase all flows originating at a specific node.
NodeID Size() const
Get the size of the underlying link graph.
Definition: linkgraphjob.h:245
const LinkGraph link_graph
Link graph to by analyzed. Is copied when job is started and mustn't be modified later.
Definition: linkgraphjob.h:163
CargoID Cargo() const
Get the cargo of the underlying link graph.
Definition: linkgraphjob.h:251
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.
Definition: linkgraphjob.h:165
static void Run(LinkGraphJob *job)
Run all handlers for the given Job.
A connected component of a link graph.
Definition: linkgraph.h:37
NodeVector nodes
Nodes in the component.
Definition: linkgraph.h:266
A leg of a path in the link graph.
Definition: linkgraphjob.h:275
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.
Definition: linkgraphjob.h:325
static Path * invalid_path
Static instance of an invalid path.
Definition: linkgraphjob.h:277
NodeID origin
Link graph node this path originates from.
Definition: linkgraphjob.h:361
uint num_children
Number of child legs that have been forked from this path.
Definition: linkgraphjob.h:362
void Detach()
Detach this path from its parent.
Definition: linkgraphjob.h:336
uint flow
Flow the current run of the mcf solver assigns.
Definition: linkgraphjob.h:359
uint distance
Sum(distance of all legs up to this one).
Definition: linkgraphjob.h:356
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.
Definition: linkgraphjob.h:360
uint capacity
This capacity is min(capacity) fom all edges.
Definition: linkgraphjob.h:357
Path * parent
Parent leg of this one.
Definition: linkgraphjob.h:363
int free_capacity
This capacity is min(edge.capacity - edge.flow) for the current run of Dijkstra.
Definition: linkgraphjob.h:358
Minimal stack that uses a pool to avoid pointers.
Titem Pop()
Pop an item from the stack.
bool IsEmpty() const
Check if the stack is empty.
static constexpr TimerGame< struct Economy >::Date INVALID_DATE
Representation of an invalid date.
Timer that is increased every 27ms, and counts towards economy time units, expressed in days / months...
fluid_settings_t * settings
FluidSynth settings handle.
Definition: fluidsynth.cpp:21
@ DT_MANUAL
Manual distribution. No link graph calculations are run.
Declaration of link graph job classes used for cargo distribution.
LinkGraphJobPool _link_graph_job_pool
The actual pool with link graph jobs.
Declaration of link graph schedule used for cargo distribution.
#define INSTANTIATE_POOL_METHODS(name)
Force instantiation of pool methods so we don't get linker errors.
Definition: pool_func.hpp:237
GameSettings _settings_game
Game settings of a running game or the scenario editor.
Definition: settings.cpp:57
void RerouteCargo(Station *st, CargoID c, StationID avoid, StationID avoid2)
Reroute cargo of type c at station st or in any vehicles unloading there.
LinkGraphSettings linkgraph
settings for link graph calculations
Stores station stats for a single cargo.
Definition: station_base.h:166
FlowStatMap flows
Planned flows through this station.
Definition: station_base.h:211
NodeID node
ID of node in link graph referring to this goods entry.
Definition: station_base.h:214
LinkGraphID link_graph
Link graph this station belongs to.
Definition: station_base.h:215
Annotation for a link graph edge.
Definition: linkgraphjob.h:42
const LinkGraph::BaseEdge & base
Reference to the edge that is annotated.
Definition: linkgraphjob.h:43
uint Flow() const
Get the total flow on the edge.
Definition: linkgraphjob.h:53
void AddFlow(uint flow)
Add some flow.
Definition: linkgraphjob.h:59
Annotation for a link graph node.
Definition: linkgraphjob.h:80
const LinkGraph::BaseNode & base
Reference to the node that is annotated.
Definition: linkgraphjob.h:81
std::vector< EdgeAnnotation > edges
Annotations for all edges originating at this node.
Definition: linkgraphjob.h:87
FlowStatMap flows
Planned flows to other nodes.
Definition: linkgraphjob.h:85
uint capacity
Capacity of the link.
Definition: linkgraph.h:43
StationID station
Station ID.
Definition: linkgraph.h:93
Tindex index
Index of this pool item.
Definition: pool_type.hpp:238
static Titem * Get(size_t index)
Returns Titem with given index.
Definition: pool_type.hpp:339
static bool CleaningPool()
Returns current state of pool cleaning - yes or no.
Definition: pool_type.hpp:318
static bool IsValidID(size_t index)
Tests whether given index can be used to get valid (non-nullptr) Titem.
Definition: pool_type.hpp:328
Base class for all pools.
Definition: pool_type.hpp:80
static Station * GetIfValid(size_t index)
Returns station if the index is a valid index for this station type.
Station data structure.
Definition: station_base.h:439
GoodsEntry goods[NUM_CARGO]
Goods at this station.
Definition: station_base.h:468
bool StartNewThread(std::thread *thr, const char *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:3211
@ WC_STATION_VIEW
Station view; Window numbers:
Definition: window_type.h:345