OpenTTD Source  12.0-beta2
linkgraphjob.h
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 #ifndef LINKGRAPHJOB_H
11 #define LINKGRAPHJOB_H
12 
13 #include "../thread.h"
14 #include "linkgraph.h"
15 #include <list>
16 #include <atomic>
17 
18 class LinkGraphJob;
19 class Path;
20 typedef std::list<Path *> PathList;
21 
26 
30 class LinkGraphJob : public LinkGraphJobPool::PoolItem<&_link_graph_job_pool>{
31 private:
35  struct EdgeAnnotation {
36  uint demand;
38  uint flow;
39  void Init();
40  };
41 
45  struct NodeAnnotation {
47  PathList paths;
49  void Init(uint supply);
50  };
51 
52  typedef std::vector<NodeAnnotation> NodeAnnotationVector;
54 
56  friend class LinkGraphSchedule;
57 
58 protected:
61  std::thread thread;
63  NodeAnnotationVector nodes;
65  std::atomic<bool> job_completed;
66  std::atomic<bool> job_aborted;
67 
68  void EraseFlows(NodeID from);
69  void JoinThread();
70  void SpawnThread();
71 
72 public:
73 
78  class Edge : public LinkGraph::ConstEdge {
79  private:
81  public:
89 
94  uint Demand() const { return this->anno.demand; }
95 
100  uint UnsatisfiedDemand() const { return this->anno.unsatisfied_demand; }
101 
106  uint Flow() const { return this->anno.flow; }
107 
112  void AddFlow(uint flow) { this->anno.flow += flow; }
113 
118  void RemoveFlow(uint flow)
119  {
120  assert(flow <= this->anno.flow);
121  this->anno.flow -= flow;
122  }
123 
128  void AddDemand(uint demand)
129  {
130  this->anno.demand += demand;
131  this->anno.unsatisfied_demand += demand;
132  }
133 
138  void SatisfyDemand(uint demand)
139  {
140  assert(demand <= this->anno.unsatisfied_demand);
141  this->anno.unsatisfied_demand -= demand;
142  }
143  };
144 
148  class EdgeIterator : public LinkGraph::BaseEdgeIterator<const LinkGraph::BaseEdge, Edge, EdgeIterator> {
150  public:
159  base_anno(base_anno) {}
160 
166  std::pair<NodeID, Edge> operator*() const
167  {
168  return std::pair<NodeID, Edge>(this->current, Edge(this->base[this->current], this->base_anno[this->current]));
169  }
170 
176  FakePointer operator->() const {
177  return FakePointer(this->operator*());
178  }
179  };
180 
185  class Node : public LinkGraph::ConstNode {
186  private:
189  public:
190 
196  Node (LinkGraphJob *lgj, NodeID node) :
198  node_anno(lgj->nodes[node]), edge_annos(lgj->edges[node])
199  {}
200 
207  Edge operator[](NodeID to) const { return Edge(this->edges[to], this->edge_annos[to]); }
208 
214  EdgeIterator Begin() const { return EdgeIterator(this->edges, this->edge_annos, index); }
215 
221  EdgeIterator End() const { return EdgeIterator(this->edges, this->edge_annos, INVALID_NODE); }
222 
227  uint UndeliveredSupply() const { return this->node_anno.undelivered_supply; }
228 
233  FlowStatMap &Flows() { return this->node_anno.flows; }
234 
239  const FlowStatMap &Flows() const { return this->node_anno.flows; }
240 
246  PathList &Paths() { return this->node_anno.paths; }
247 
252  const PathList &Paths() const { return this->node_anno.paths; }
253 
259  void DeliverSupply(NodeID to, uint amount)
260  {
261  this->node_anno.undelivered_supply -= amount;
262  (*this)[to].AddDemand(amount);
263  }
264  };
265 
271  join_date(INVALID_DATE), job_completed(false), job_aborted(false) {}
272 
273  LinkGraphJob(const LinkGraph &orig);
274  ~LinkGraphJob();
275 
276  void Init();
277 
283  inline bool IsJobCompleted() const { return this->job_completed.load(std::memory_order_acquire); }
284 
290  inline bool IsJobAborted() const { return this->job_aborted.load(std::memory_order_acquire); }
291 
298  inline void AbortJob() { this->job_aborted.store(true, std::memory_order_release); }
299 
304  inline bool IsScheduledToBeJoined() const { return this->join_date <= _date; }
305 
310  inline Date JoinDate() const { return join_date; }
311 
316  inline void ShiftJoinDate(int interval) { this->join_date += interval; }
317 
322  inline const LinkGraphSettings &Settings() const { return this->settings; }
323 
329  inline Node operator[](NodeID num) { return Node(this, num); }
330 
335  inline NodeID Size() const { return this->link_graph.Size(); }
336 
341  inline CargoID Cargo() const { return this->link_graph.Cargo(); }
342 
347  inline Date LastCompression() const { return this->link_graph.LastCompression(); }
348 
353  inline LinkGraphID LinkGraphIndex() const { return this->link_graph.index; }
354 
359  inline const LinkGraph &Graph() const { return this->link_graph; }
360 };
361 
365 class Path {
366 public:
368 
369  Path(NodeID n, bool source = false);
370  virtual ~Path() = default;
371 
373  inline NodeID GetNode() const { return this->node; }
374 
376  inline NodeID GetOrigin() const { return this->origin; }
377 
379  inline Path *GetParent() { return this->parent; }
380 
382  inline uint GetCapacity() const { return this->capacity; }
383 
385  inline int GetFreeCapacity() const { return this->free_capacity; }
386 
394  inline static int GetCapacityRatio(int free, uint total)
395  {
396  return Clamp(free, PATH_CAP_MIN_FREE, PATH_CAP_MAX_FREE) * PATH_CAP_MULTIPLIER / std::max(total, 1U);
397  }
398 
403  inline int GetCapacityRatio() const
404  {
405  return Path::GetCapacityRatio(this->free_capacity, this->capacity);
406  }
407 
409  inline uint GetDistance() const { return this->distance; }
410 
412  inline void ReduceFlow(uint f) { this->flow -= f; }
413 
415  inline void AddFlow(uint f) { this->flow += f; }
416 
418  inline uint GetFlow() const { return this->flow; }
419 
421  inline uint GetNumChildren() const { return this->num_children; }
422 
426  inline void Detach()
427  {
428  if (this->parent != nullptr) {
429  this->parent->num_children--;
430  this->parent = nullptr;
431  }
432  }
433 
434  uint AddFlow(uint f, LinkGraphJob &job, uint max_saturation);
435  void Fork(Path *base, uint cap, int free_cap, uint dist);
436 
437 protected:
438 
443  PATH_CAP_MULTIPLIER = 16,
444  PATH_CAP_MIN_FREE = (INT_MIN + 1) / PATH_CAP_MULTIPLIER,
445  PATH_CAP_MAX_FREE = (INT_MAX - 1) / PATH_CAP_MULTIPLIER
446  };
447 
448  uint distance;
449  uint capacity;
451  uint flow;
452  NodeID node;
453  NodeID origin;
456 };
457 
458 #endif /* LINKGRAPHJOB_H */
LinkGraph::NodeWrapper< const BaseNode, const BaseEdge >::edges
const BaseEdge * edges
Outgoing edges for wrapped node.
Definition: linkgraph.h:135
Path::GetCapacity
uint GetCapacity() const
Get the overall capacity of the path.
Definition: linkgraphjob.h:382
LinkGraphJob::Edge::Demand
uint Demand() const
Get the transport demand between end the points of the edge.
Definition: linkgraphjob.h:94
LinkGraphJob::NodeAnnotation::flows
FlowStatMap flows
Planned flows to other nodes.
Definition: linkgraphjob.h:48
Path::capacity
uint capacity
This capacity is min(capacity) fom all edges.
Definition: linkgraphjob.h:449
LinkGraphJob::EdgeAnnotation::demand
uint demand
Transport demand between the nodes.
Definition: linkgraphjob.h:36
Path
A leg of a path in the link graph.
Definition: linkgraphjob.h:365
Path::GetCapacityRatio
int GetCapacityRatio() const
Get capacity ratio of this path.
Definition: linkgraphjob.h:403
LinkGraph
A connected component of a link graph.
Definition: linkgraph.h:39
LinkGraphJob::Node
Link graph job node.
Definition: linkgraphjob.h:185
LinkGraphJob::nodes
NodeAnnotationVector nodes
Extra node data necessary for link graph calculation.
Definition: linkgraphjob.h:63
Path::invalid_path
static Path * invalid_path
Static instance of an invalid path.
Definition: linkgraphjob.h:367
LinkGraphJob::Edge::Flow
uint Flow() const
Get the total flow on the edge.
Definition: linkgraphjob.h:106
LinkGraphJob::Node::UndeliveredSupply
uint UndeliveredSupply() const
Get amount of supply that hasn't been delivered, yet.
Definition: linkgraphjob.h:227
LinkGraphJob::Settings
const LinkGraphSettings & Settings() const
Get the link graph settings for this component.
Definition: linkgraphjob.h:322
LinkGraphJob
Class for calculation jobs to be run on link graphs.
Definition: linkgraphjob.h:30
LinkGraphSchedule
Definition: linkgraphschedule.h:36
LinkGraphJob::IsJobCompleted
bool IsJobCompleted() const
Check if job has actually finished.
Definition: linkgraphjob.h:283
Pool::PoolItem::index
Tindex index
Index of this pool item.
Definition: pool_type.hpp:235
LinkGraphJob::~LinkGraphJob
~LinkGraphJob()
Join the link graph job and destroy it.
Definition: linkgraphjob.cpp:88
LinkGraph::ConstNode
Constant node class.
Definition: linkgraph.h:345
LinkGraphJob::EdgeAnnotation::Init
void Init()
Initialize a linkgraph job edge.
Definition: linkgraphjob.cpp:197
LinkGraphJob::job_completed
std::atomic< bool > job_completed
Is the job still running. This is accessed by multiple threads and reads may be stale.
Definition: linkgraphjob.h:65
LinkGraphJob::Edge::SatisfyDemand
void SatisfyDemand(uint demand)
Satisfy some demand.
Definition: linkgraphjob.h:138
Path::Fork
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.
Definition: linkgraphjob.cpp:224
LinkGraphJob::JoinThread
void JoinThread()
Join the calling thread with this job's thread if threading is enabled.
Definition: linkgraphjob.cpp:78
LinkGraphJob::EdgeAnnotation::flow
uint flow
Planned flow over this edge.
Definition: linkgraphjob.h:38
Path::GetCapacityRatio
static int GetCapacityRatio(int free, uint total)
Get ratio of free * 16 (so that we get fewer 0) / max(total capacity, 1) (so that we don't divide by ...
Definition: linkgraphjob.h:394
Path::origin
NodeID origin
Link graph node this path originates from.
Definition: linkgraphjob.h:453
LinkGraphJob::EdgeIterator::EdgeIterator
EdgeIterator(const LinkGraph::BaseEdge *base, EdgeAnnotation *base_anno, NodeID current)
Constructor.
Definition: linkgraphjob.h:157
LinkGraph::Size
NodeID Size() const
Get the current size of the component.
Definition: linkgraph.h:505
LinkGraphSettings
Definition: settings_type.h:525
LinkGraphJob::NodeAnnotation::paths
PathList paths
Paths through this node, sorted so that those with flow == 0 are in the back.
Definition: linkgraphjob.h:47
Path::GetFreeCapacity
int GetFreeCapacity() const
Get the free capacity of the path.
Definition: linkgraphjob.h:385
LinkGraphJob::edges
EdgeAnnotationMatrix edges
Extra edge data necessary for link graph calculation.
Definition: linkgraphjob.h:64
LinkGraphJob::join_date
Date join_date
Date when the job is to be joined.
Definition: linkgraphjob.h:62
LinkGraphJob::settings
const LinkGraphSettings settings
Copy of _settings_game.linkgraph at spawn time.
Definition: linkgraphjob.h:60
LinkGraphJob::operator[]
Node operator[](NodeID num)
Get a node abstraction with the specified id.
Definition: linkgraphjob.h:329
Path::parent
Path * parent
Parent leg of this one.
Definition: linkgraphjob.h:455
LinkGraphJob::GetLinkGraphJobDesc
friend SaveLoadTable GetLinkGraphJobDesc()
Get a SaveLoad array for a link graph job.
Definition: linkgraph_sl.cpp:167
LinkGraphJob::LinkGraphIndex
LinkGraphID LinkGraphIndex() const
Get the ID of the underlying link graph.
Definition: linkgraphjob.h:353
LinkGraphJob::Graph
const LinkGraph & Graph() const
Get a reference to the underlying link graph.
Definition: linkgraphjob.h:359
LinkGraphJob::Node::Node
Node(LinkGraphJob *lgj, NodeID node)
Constructor.
Definition: linkgraphjob.h:196
LinkGraph::EdgeWrapper
Wrapper for an edge (const or not) allowing retrieval, but no modification.
Definition: linkgraph.h:77
LinkGraphJob::Size
NodeID Size() const
Get the size of the underlying link graph.
Definition: linkgraphjob.h:335
Path::GetParent
Path * GetParent()
Get the parent leg of this one.
Definition: linkgraphjob.h:379
LinkGraph::BaseEdgeIterator< const LinkGraph::BaseEdge, Edge, EdgeIterator >::BaseEdgeIterator
BaseEdgeIterator(const LinkGraph::BaseEdge *base, NodeID current)
Constructor.
Definition: linkgraph.h:221
LinkGraphJob::AbortJob
void AbortJob()
Abort job.
Definition: linkgraphjob.h:298
_date
Date _date
Current date in days (day counter)
Definition: date.cpp:28
LinkGraphJob::SpawnThread
void SpawnThread()
Spawn a thread if possible and run the link graph job in the thread.
Definition: linkgraphjob.cpp:61
LinkGraphJob::NodeAnnotation::undelivered_supply
uint undelivered_supply
Amount of supply that hasn't been distributed yet.
Definition: linkgraphjob.h:46
span
A trimmed down version of what std::span will be in C++20.
Definition: span_type.hpp:60
LinkGraph::EdgeWrapper::edge
Tedge & edge
Actual edge to be used.
Definition: linkgraph.h:79
LinkGraphJob::ShiftJoinDate
void ShiftJoinDate(int interval)
Change the join date on date cheating.
Definition: linkgraphjob.h:316
LinkGraphJob::EdgeAnnotation::unsatisfied_demand
uint unsatisfied_demand
Demand over this edge that hasn't been satisfied yet.
Definition: linkgraphjob.h:37
LinkGraphJob::EdgeAnnotation
Annotation for a link graph edge.
Definition: linkgraphjob.h:35
LinkGraphJob::Node::Paths
const PathList & Paths() const
Get a constant version of the paths this node is part of.
Definition: linkgraphjob.h:252
SmallMatrix< EdgeAnnotation >
LinkGraphJob::IsScheduledToBeJoined
bool IsScheduledToBeJoined() const
Check if job is supposed to be finished.
Definition: linkgraphjob.h:304
Date
int32 Date
The type to store our dates in.
Definition: date_type.h:14
LinkGraph::BaseEdge
An edge in the link graph.
Definition: linkgraph.h:62
LinkGraphJob::link_graph
const LinkGraph link_graph
Link graph to by analyzed. Is copied when job is started and mustn't be modified later.
Definition: linkgraphjob.h:59
_settings_game
GameSettings _settings_game
Game settings of a running game or the scenario editor.
Definition: settings.cpp:53
LinkGraph::Cargo
CargoID Cargo() const
Get the cargo ID this component's link graph refers to.
Definition: linkgraph.h:517
LinkGraphJob::thread
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:61
LinkGraphJob::Node::edge_annos
EdgeAnnotation * edge_annos
Edge annotations belonging to this node.
Definition: linkgraphjob.h:188
LinkGraph::BaseEdgeIterator
Base class for iterating across outgoing edges of a node.
Definition: linkgraph.h:188
LinkGraphJob::Edge
A job edge.
Definition: linkgraphjob.h:78
LinkGraphJob::EdgeIterator::operator->
FakePointer operator->() const
Dereference.
Definition: linkgraphjob.h:176
LinkGraphJob::Node::Paths
PathList & Paths()
Get the paths this node is part of.
Definition: linkgraphjob.h:246
LinkGraphJob::Edge::UnsatisfiedDemand
uint UnsatisfiedDemand() const
Get the transport demand that hasn't been satisfied by flows, yet.
Definition: linkgraphjob.h:100
Path::PathCapacityBoundaries
PathCapacityBoundaries
Some boundaries to clamp against in order to avoid integer overflows.
Definition: linkgraphjob.h:442
LinkGraphJob::EdgeIterator::base_anno
EdgeAnnotation * base_anno
Array of annotations to be (indirectly) iterated.
Definition: linkgraphjob.h:149
Path::flow
uint flow
Flow the current run of the mcf solver assigns.
Definition: linkgraphjob.h:451
LinkGraph::LastCompression
Date LastCompression() const
Get date of last compression.
Definition: linkgraph.h:511
Path::distance
uint distance
Sum(distance of all legs up to this one).
Definition: linkgraphjob.h:448
LinkGraphJob::Node::DeliverSupply
void DeliverSupply(NodeID to, uint amount)
Deliver some supply, adding demand to the respective edge.
Definition: linkgraphjob.h:259
Clamp
static T Clamp(const T a, const T min, const T max)
Clamp a value between an interval.
Definition: math_func.hpp:77
Pool
Base class for all pools.
Definition: pool_type.hpp:81
LinkGraphJob::EdgeIterator::operator*
std::pair< NodeID, Edge > operator*() const
Dereference.
Definition: linkgraphjob.h:166
LinkGraphJob::NodeAnnotation
Annotation for a link graph node.
Definition: linkgraphjob.h:45
LinkGraphJob::Node::Flows
FlowStatMap & Flows()
Get the flows running through this node.
Definition: linkgraphjob.h:233
LinkGraphJob::Node::operator[]
Edge operator[](NodeID to) const
Retrieve an edge starting at this node.
Definition: linkgraphjob.h:207
LinkGraph::BaseEdgeIterator< const LinkGraph::BaseEdge, Edge, EdgeIterator >::current
NodeID current
Current offset in edges array.
Definition: linkgraph.h:191
INVALID_DATE
static const Date INVALID_DATE
Representation of an invalid date.
Definition: date_type.h:111
LinkGraphJob::Node::End
EdgeIterator End() const
Iterator for the "end" of the edge array.
Definition: linkgraphjob.h:221
LinkGraphJob::IsJobAborted
bool IsJobAborted() const
Check if job has been aborted.
Definition: linkgraphjob.h:290
Path::AddFlow
void AddFlow(uint f)
Increase the flow on this leg only by the specified amount.
Definition: linkgraphjob.h:415
LinkGraphJob::Edge::RemoveFlow
void RemoveFlow(uint flow)
Remove some flow.
Definition: linkgraphjob.h:118
LinkGraphJob::Node::node_anno
NodeAnnotation & node_anno
Annotation being wrapped.
Definition: linkgraphjob.h:187
FlowStatMap
Flow descriptions by origin stations.
Definition: station_base.h:149
LinkGraph::BaseEdgeIterator< const LinkGraph::BaseEdge, Edge, EdgeIterator >::base
const LinkGraph::BaseEdge * base
Array of edges being iterated.
Definition: linkgraph.h:190
linkgraph.h
LinkGraphJob::LastCompression
Date LastCompression() const
Get the date when the underlying link graph was last compressed.
Definition: linkgraphjob.h:347
LinkGraphJob::Edge::anno
EdgeAnnotation & anno
Annotation being wrapped.
Definition: linkgraphjob.h:80
Path::Path
Path(NodeID n, bool source=false)
Create a leg of a path in the link graph.
Definition: linkgraphjob.cpp:273
Path::free_capacity
int free_capacity
This capacity is min(edge.capacity - edge.flow) for the current run of Dijkstra.
Definition: linkgraphjob.h:450
LinkGraphJob::JoinDate
Date JoinDate() const
Get the date when the job should be finished.
Definition: linkgraphjob.h:310
_link_graph_job_pool
LinkGraphJobPool _link_graph_job_pool
The actual pool with link graph jobs.
CargoID
byte CargoID
Cargo slots to indicate a cargo type within a game.
Definition: cargo_type.h:20
LinkGraphJob::Cargo
CargoID Cargo() const
Get the cargo of the underlying link graph.
Definition: linkgraphjob.h:341
LinkGraphJob::EraseFlows
void EraseFlows(NodeID from)
Erase all flows originating at a specific node.
Definition: linkgraphjob.cpp:50
LinkGraphJob::job_aborted
std::atomic< bool > job_aborted
Has the job been aborted. This is accessed by multiple threads and reads may be stale.
Definition: linkgraphjob.h:66
LinkGraphJob::Node::Begin
EdgeIterator Begin() const
Iterator for the "begin" of the edge array.
Definition: linkgraphjob.h:214
free
static void free(const void *ptr)
Version of the standard free that accepts const pointers.
Definition: stdafx.h:460
Path::GetNumChildren
uint GetNumChildren() const
Get the number of "forked off" child legs of this one.
Definition: linkgraphjob.h:421
Path::Detach
void Detach()
Detach this path from its parent.
Definition: linkgraphjob.h:426
Path::node
NodeID node
Link graph node this leg passes.
Definition: linkgraphjob.h:452
Path::ReduceFlow
void ReduceFlow(uint f)
Reduce the flow on this leg only by the specified amount.
Definition: linkgraphjob.h:412
LinkGraphJob::EdgeIterator
Iterator for job edges.
Definition: linkgraphjob.h:148
Pool::PoolItem
Base class for all PoolItems.
Definition: pool_type.hpp:234
Path::num_children
uint num_children
Number of child legs that have been forked from this path.
Definition: linkgraphjob.h:454
LinkGraphJob::Edge::Edge
Edge(const LinkGraph::BaseEdge &edge, EdgeAnnotation &anno)
Constructor.
Definition: linkgraphjob.h:87
LinkGraph::NodeWrapper< const BaseNode, const BaseEdge >::index
NodeID index
ID of wrapped node.
Definition: linkgraph.h:136
LinkGraphJob::Edge::AddDemand
void AddDemand(uint demand)
Add some (not yet satisfied) demand.
Definition: linkgraphjob.h:128
LinkGraphJob::Init
void Init()
Initialize the link graph job: Resize nodes and edges and populate them.
Definition: linkgraphjob.cpp:180
LinkGraphJob::LinkGraphJob
LinkGraphJob()
Bare constructor, only for save/load.
Definition: linkgraphjob.h:270
Path::GetDistance
uint GetDistance() const
Get the overall distance of the path.
Definition: linkgraphjob.h:409
Path::GetOrigin
NodeID GetOrigin() const
Get the overall origin of the path.
Definition: linkgraphjob.h:376
Path::GetFlow
uint GetFlow() const
Get the flow on this leg.
Definition: linkgraphjob.h:418
LinkGraph::NodeWrapper< const BaseNode, const BaseEdge >::node
const BaseNode & node
Node being wrapped.
Definition: linkgraph.h:134
LinkGraphJob::Node::Flows
const FlowStatMap & Flows() const
Get a constant version of the flows running through this node.
Definition: linkgraphjob.h:239
LinkGraphJob::NodeAnnotation::Init
void Init(uint supply)
Initialize a Linkgraph job node.
Definition: linkgraphjob.cpp:209
LinkGraphJobPool
Pool< LinkGraphJob, LinkGraphJobID, 32, 0xFFFF > LinkGraphJobPool
Type of the pool for link graph jobs.
Definition: linkgraphjob.h:23
LinkGraphJob::Edge::AddFlow
void AddFlow(uint flow)
Add some flow.
Definition: linkgraphjob.h:112
Path::GetNode
NodeID GetNode() const
Get the node this leg passes.
Definition: linkgraphjob.h:373