OpenTTD
linkgraphjob.cpp
Go to the documentation of this file.
1 /* $Id: linkgraphjob.cpp 27670 2016-10-30 17:29:33Z frosch $ */
2 
3 /*
4  * This file is part of OpenTTD.
5  * 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.
6  * 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.
7  * 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/>.
8  */
9 
12 #include "../stdafx.h"
13 #include "../core/pool_func.hpp"
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 
38  /* Copying the link graph here also copies its index member.
39  * This is on purpose. */
40  link_graph(orig),
41  settings(_settings_game.linkgraph),
42  thread(NULL),
43  join_date(_date + _settings_game.linkgraph.recalc_time)
44 {
45 }
46 
51 void LinkGraphJob::EraseFlows(NodeID from)
52 {
53  for (NodeID node_id = 0; node_id < this->Size(); ++node_id) {
54  (*this)[node_id].Flows().erase(from);
55  }
56 }
57 
63 {
64  if (!ThreadObject::New(&(LinkGraphSchedule::Run), this, &this->thread, "ottd:linkgraph")) {
65  this->thread = NULL;
66  /* Of course this will hang a bit.
67  * On the other hand, if you want to play games which make this hang noticably
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 him/her, 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 != NULL) {
83  this->thread->Join();
84  delete this->thread;
85  this->thread = NULL;
86  }
87 }
88 
93 {
94  this->JoinThread();
95 
96  /* Don't update stuff from other pools, when everything is being removed.
97  * Accessing other pools may be invalid. */
98  if (CleaningPool()) return;
99 
100  /* Link graph has been merged into another one. */
101  if (!LinkGraph::IsValidID(this->link_graph.index)) return;
102 
103  uint size = this->Size();
104  for (NodeID node_id = 0; node_id < size; ++node_id) {
105  Node from = (*this)[node_id];
106 
107  /* The station can have been deleted. Remove all flows originating from it then. */
108  Station *st = Station::GetIfValid(from.Station());
109  if (st == NULL) {
110  this->EraseFlows(node_id);
111  continue;
112  }
113 
114  /* Link graph merging and station deletion may change around IDs. Make
115  * sure that everything is still consistent or ignore it otherwise. */
116  GoodsEntry &ge = st->goods[this->Cargo()];
117  if (ge.link_graph != this->link_graph.index || ge.node != node_id) {
118  this->EraseFlows(node_id);
119  continue;
120  }
121 
123  FlowStatMap &flows = from.Flows();
124 
125  for (EdgeIterator it(from.Begin()); it != from.End(); ++it) {
126  if (from[it->first].Flow() == 0) continue;
127  StationID to = (*this)[it->first].Station();
128  Station *st2 = Station::GetIfValid(to);
129  if (st2 == NULL || st2->goods[this->Cargo()].link_graph != this->link_graph.index ||
130  st2->goods[this->Cargo()].node != it->first ||
131  (*lg)[node_id][it->first].LastUpdate() == INVALID_DATE) {
132  /* Edge has been removed. Delete flows. */
133  StationIDStack erased = flows.DeleteFlows(to);
134  /* Delete old flows for source stations which have been deleted
135  * from the new flows. This avoids flow cycles between old and
136  * new flows. */
137  while (!erased.IsEmpty()) ge.flows.erase(erased.Pop());
138  } else if ((*lg)[node_id][it->first].LastUnrestrictedUpdate() == INVALID_DATE) {
139  /* Edge is fully restricted. */
140  flows.RestrictFlows(to);
141  }
142  }
143 
144  /* Swap shares and invalidate ones that are completely deleted. Don't
145  * really delete them as we could then end up with unroutable cargo
146  * somewhere. Do delete them and also reroute relevant cargo if
147  * automatic distribution has been turned off for that cargo. */
148  for (FlowStatMap::iterator it(ge.flows.begin()); it != ge.flows.end();) {
149  FlowStatMap::iterator new_it = flows.find(it->first);
150  if (new_it == flows.end()) {
151  if (_settings_game.linkgraph.GetDistributionType(this->Cargo()) != DT_MANUAL) {
152  it->second.Invalidate();
153  ++it;
154  } else {
155  FlowStat shares(INVALID_STATION, 1);
156  it->second.SwapShares(shares);
157  ge.flows.erase(it++);
158  for (FlowStat::SharesMap::const_iterator shares_it(shares.GetShares()->begin());
159  shares_it != shares.GetShares()->end(); ++shares_it) {
160  RerouteCargo(st, this->Cargo(), shares_it->second, st->index);
161  }
162  }
163  } else {
164  it->second.SwapShares(new_it->second);
165  flows.erase(new_it);
166  ++it;
167  }
168  }
169  ge.flows.insert(flows.begin(), flows.end());
170  InvalidateWindowData(WC_STATION_VIEW, st->index, this->Cargo());
171  }
172 }
173 
180 {
181  uint size = this->Size();
182  this->nodes.Resize(size);
183  this->edges.Resize(size, size);
184  for (uint i = 0; i < size; ++i) {
185  this->nodes[i].Init(this->link_graph[i].Supply());
186  EdgeAnnotation *node_edges = this->edges[i];
187  for (uint j = 0; j < size; ++j) {
188  node_edges[j].Init();
189  }
190  }
191 }
192 
197 {
198  this->demand = 0;
199  this->flow = 0;
200  this->unsatisfied_demand = 0;
201 }
202 
209 {
210  this->undelivered_supply = supply;
211  new (&this->flows) FlowStatMap;
212  new (&this->paths) PathList;
213 }
214 
223 void Path::Fork(Path *base, uint cap, int free_cap, uint dist)
224 {
225  this->capacity = min(base->capacity, cap);
226  this->free_capacity = min(base->free_capacity, free_cap);
227  this->distance = base->distance + dist;
228  assert(this->distance > 0);
229  if (this->parent != base) {
230  this->Detach();
231  this->parent = base;
232  this->parent->num_children++;
233  }
234  this->origin = base->origin;
235 }
236 
245 uint Path::AddFlow(uint new_flow, LinkGraphJob &job, uint max_saturation)
246 {
247  if (this->parent != NULL) {
248  LinkGraphJob::Edge edge = job[this->parent->node][this->node];
249  if (max_saturation != UINT_MAX) {
250  uint usable_cap = edge.Capacity() * max_saturation / 100;
251  if (usable_cap > edge.Flow()) {
252  new_flow = min(new_flow, usable_cap - edge.Flow());
253  } else {
254  return 0;
255  }
256  }
257  new_flow = this->parent->AddFlow(new_flow, job, max_saturation);
258  if (this->flow == 0 && new_flow > 0) {
259  job[this->parent->node].Paths().push_front(this);
260  }
261  edge.AddFlow(new_flow);
262  }
263  this->flow += new_flow;
264  return new_flow;
265 }
266 
272 Path::Path(NodeID n, bool source) :
273  distance(source ? 0 : UINT_MAX),
274  capacity(source ? UINT_MAX : 0),
275  free_capacity(source ? INT_MAX : INT_MIN),
276  flow(0), node(n), origin(source ? n : INVALID_NODE),
277  num_children(0), parent(NULL)
278 {}
279 
GameSettings _settings_game
Game settings of a running game or the scenario editor.
Definition: settings.cpp:77
void Init()
Initialize a linkgraph job edge.
Minimal stack that uses a pool to avoid pointers.
int free_capacity
This capacity is min(edge.capacity - edge.flow) for the current run of Dijkstra.
Definition: linkgraphjob.h:428
A job edge.
Definition: linkgraphjob.h:77
Annotation for a link graph edge.
Definition: linkgraphjob.h:36
static Titem * Get(size_t index)
Returns Titem with given index.
Definition: pool_type.hpp:246
LinkGraphJobPool _link_graph_job_pool("LinkGraphJob")
The actual pool with link graph jobs.
uint Flow() const
Get the total flow on the edge.
Definition: linkgraphjob.h:105
Manual distribution. No link graph calculations are run.
StationIDStack DeleteFlows(StationID via)
Delete all flows at a station for specific cargo and destination.
Stores station stats for a single cargo.
Definition: station_base.h:170
Tindex index
Index of this pool item.
Definition: pool_type.hpp:147
void AddFlow(uint f)
Increase the flow on this leg only by the specified amount.
Definition: linkgraphjob.h:393
StationID Station() const
Get ID of station belonging to wrapped node.
Definition: linkgraph.h:159
GoodsEntry goods[NUM_CARGO]
Goods at this station.
Definition: station_base.h:472
A connected component of a link graph.
Definition: linkgraph.h:40
void Resize(uint num_items)
Set the size of the vector, effectively truncating items from the end or appending uninitialised ones...
void Init(uint supply)
Initialize a Linkgraph job node.
void RestrictFlows(StationID via)
Restrict all flows at a station for specific cargo and destination.
bool IsEmpty() const
Check if the stack is empty.
void Init()
Initialize the link graph job: Resize nodes and edges and populate them.
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...
void Resize(uint new_width, uint new_height)
Set the size to a specific width and height, preserving item positions as far as possible in the proc...
LinkGraphID link_graph
Link graph this station belongs to.
Definition: station_base.h:257
Path(NodeID n, bool source=false)
Create a leg of a path in the link graph.
uint distance
Sum(distance of all legs up to this one).
Definition: linkgraphjob.h:426
static const Date INVALID_DATE
Representation of an invalid date.
Definition: date_type.h:110
A leg of a path in the link graph.
Definition: linkgraphjob.h:344
Declaration of link graph schedule used for cargo distribution.
uint num_children
Number of child legs that have been forked from this path.
Definition: linkgraphjob.h:432
Titem Pop()
Pop an item from the stack.
NodeID node
ID of node in link graph referring to this goods entry.
Definition: station_base.h:258
ThreadObject * thread
Thread the job is running in or NULL if it&#39;s running in the main thread.
Definition: linkgraphjob.h:62
static void Run(void *j)
Run all handlers for the given Job.
Link graph job node.
Definition: linkgraphjob.h:184
Station view; Window numbers:
Definition: window_type.h:340
static Path * invalid_path
Static instance of an invalid path.
Definition: linkgraphjob.h:346
Declaration of link graph job classes used for cargo distribution.
static T min(const T a, const T b)
Returns the minimum of two values.
Definition: math_func.hpp:42
uint capacity
This capacity is min(capacity) fom all edges.
Definition: linkgraphjob.h:427
void SpawnThread()
Spawn a thread if possible and run the link graph job in the thread.
NodeID origin
Link graph node this path originates from.
Definition: linkgraphjob.h:431
void AddFlow(uint flow)
Add some flow.
Definition: linkgraphjob.h:111
Base class for all pools.
Definition: pool_type.hpp:83
CargoID Cargo() const
Get the cargo of the underlying link graph.
Definition: linkgraphjob.h:318
FlowStatMap flows
Planned flows through this station.
Definition: station_base.h:259
#define INSTANTIATE_POOL_METHODS(name)
Force instantiation of pool methods so we don&#39;t get linker errors.
Definition: pool_func.hpp:224
static bool CleaningPool()
Returns current state of pool cleaning - yes or no.
Definition: pool_type.hpp:225
virtual void Join()=0
Join this thread.
const LinkGraph link_graph
Link graph to by analyzed. Is copied when job is started and mustn&#39;t be modified later.
Definition: linkgraphjob.h:60
FlowStatMap & Flows()
Get the flows running through this node.
Definition: linkgraphjob.h:232
void EraseFlows(NodeID from)
Erase all flows originating at a specific node.
void JoinThread()
Join the calling thread with this job&#39;s thread if threading is enabled.
void RerouteCargo(Station *st, CargoID c, StationID avoid, StationID avoid2)
Reroute cargo of type c at station st or in any vehicles unloading there.
const SharesMap * GetShares() const
Get the actual shares as a const pointer so that they can be iterated over.
Definition: station_base.h:92
EdgeIterator End() const
Iterator for the "end" of the edge array.
Definition: linkgraphjob.h:220
Iterator for job edges.
Definition: linkgraphjob.h:147
uint Size() const
Get the size of the underlying link graph.
Definition: linkgraphjob.h:312
Flow statistics telling how much flow should be sent along a link.
Definition: station_base.h:36
LinkGraphJob()
Bare constructor, only for save/load.
Definition: linkgraphjob.h:269
static bool IsValidID(size_t index)
Tests whether given index can be used to get valid (non-NULL) Titem.
Definition: pool_type.hpp:235
Flow descriptions by origin stations.
Definition: station_base.h:152
EdgeAnnotationMatrix edges
Extra edge data necessary for link graph calculation.
Definition: linkgraphjob.h:65
uint Capacity() const
Get edge&#39;s capacity.
Definition: linkgraph.h:93
Date _date
Current date in days (day counter)
Definition: date.cpp:28
NodeAnnotationVector nodes
Extra node data necessary for link graph calculation.
Definition: linkgraphjob.h:64
static bool New(OTTDThreadFunc proc, void *param, ThreadObject **thread=NULL, const char *name=NULL)
Create a thread; proc will be called as first function inside the thread, with optional params...
EdgeIterator Begin() const
Iterator for the "begin" of the edge array.
Definition: linkgraphjob.h:213
Station data structure.
Definition: station_base.h:446
~LinkGraphJob()
Join the link graph job and destroy it.
LinkGraphSettings linkgraph
settings for link graph calculations
Class for calculation jobs to be run on link graphs.
Definition: linkgraphjob.h:31
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:3220
static Station * GetIfValid(size_t index)
Returns station if the index is a valid index for this station type.