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/>.
8 /** @file linkgraphjob.cpp Definition of link graph job classes used for cargo distribution. */
10 #include "../stdafx.h"
11 #include "../core/pool_func.hpp"
12 #include "../window_func.h"
13 #include "linkgraphjob.h"
14 #include "linkgraphschedule.h"
16 #include "../safeguards.h"
18 /* Initialize the link-graph-job-pool */
19 LinkGraphJobPool
_link_graph_job_pool("LinkGraphJob");
20 INSTANTIATE_POOL_METHODS(LinkGraphJob
)
23 * Static instance of an invalid path.
24 * Note: This instance is created on task start.
25 * Lazy creation on first usage results in a data race between the CDist threads.
27 /* static */ Path
*Path::invalid_path
= new Path(INVALID_NODE
, true);
30 * Create a link graph job from a link graph. The link graph will be copied so
31 * that the calculations don't interfer with the normal operations on the
32 * original. The job is immediately started.
33 * @param orig Original LinkGraph to be copied.
35 LinkGraphJob::LinkGraphJob(const LinkGraph
&orig
) :
36 /* Copying the link graph here also copies its index member.
37 * This is on purpose. */
39 settings(_settings_game
.linkgraph
),
40 join_date(TimerGameEconomy::date
+ (_settings_game
.linkgraph
.recalc_time
/ EconomyTime::SECONDS_PER_DAY
)),
47 * Erase all flows originating at a specific node.
48 * @param from Node to erase flows for.
50 void LinkGraphJob::EraseFlows(NodeID from
)
52 for (NodeID node_id
= 0; node_id
< this->Size(); ++node_id
) {
53 (*this)[node_id
].flows
.erase(from
);
58 * Spawn a thread if possible and run the link graph job in the thread. If
59 * that's not possible run the job right now in the current thread.
61 void LinkGraphJob::SpawnThread()
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.
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. */
71 LinkGraphSchedule::Run(this);
76 * Join the calling thread with this job's thread if threading is enabled.
78 void LinkGraphJob::JoinThread()
80 if (this->thread
.joinable()) {
86 * Join the link graph job and destroy it.
88 LinkGraphJob::~LinkGraphJob()
92 /* Don't update stuff from other pools, when everything is being removed.
93 * Accessing other pools may be invalid. */
94 if (CleaningPool()) return;
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());
101 /* Link graph has been merged into another one. */
102 if (!LinkGraph::IsValidID(this->link_graph
.index
)) return;
104 uint16_t size
= this->Size();
105 for (NodeID node_id
= 0; node_id
< size
; ++node_id
) {
106 NodeAnnotation
&from
= this->nodes
[node_id
];
108 /* The station can have been deleted. Remove all flows originating from it then. */
109 Station
*st
= Station::GetIfValid(from
.base
.station
);
111 this->EraseFlows(node_id
);
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
);
123 LinkGraph
*lg
= LinkGraph::Get(ge
.link_graph
);
124 FlowStatMap
&flows
= from
.flows
;
125 FlowStatMap
&geflows
= ge
.GetOrCreateData().flows
;
127 for (const auto &edge
: from
.edges
) {
128 if (edge
.Flow() == 0) continue;
129 NodeID dest_id
= edge
.base
.dest_node
;
130 StationID to
= this->nodes
[dest_id
].base
.station
;
131 Station
*st2
= Station::GetIfValid(to
);
132 if (st2
== nullptr || st2
->goods
[this->Cargo()].link_graph
!= this->link_graph
.index
||
133 st2
->goods
[this->Cargo()].node
!= dest_id
||
134 !(*lg
)[node_id
].HasEdgeTo(dest_id
) ||
135 (*lg
)[node_id
][dest_id
].LastUpdate() == EconomyTime::INVALID_DATE
) {
136 /* Edge has been removed. Delete flows. */
137 StationIDStack erased
= flows
.DeleteFlows(to
);
138 /* Delete old flows for source stations which have been deleted
139 * from the new flows. This avoids flow cycles between old and
141 while (!erased
.IsEmpty()) geflows
.erase(erased
.Pop());
142 } else if ((*lg
)[node_id
][dest_id
].last_unrestricted_update
== EconomyTime::INVALID_DATE
) {
143 /* Edge is fully restricted. */
144 flows
.RestrictFlows(to
);
148 /* Swap shares and invalidate ones that are completely deleted. Don't
149 * really delete them as we could then end up with unroutable cargo
150 * somewhere. Do delete them and also reroute relevant cargo if
151 * automatic distribution has been turned off for that cargo. */
152 for (FlowStatMap::iterator
it(geflows
.begin()); it
!= geflows
.end();) {
153 FlowStatMap::iterator new_it
= flows
.find(it
->first
);
154 if (new_it
== flows
.end()) {
155 if (_settings_game
.linkgraph
.GetDistributionType(this->Cargo()) != DT_MANUAL
) {
156 it
->second
.Invalidate();
159 FlowStat
shares(INVALID_STATION
, 1);
160 it
->second
.SwapShares(shares
);
162 for (FlowStat::SharesMap::const_iterator
shares_it(shares
.GetShares()->begin());
163 shares_it
!= shares
.GetShares()->end(); ++shares_it
) {
164 RerouteCargo(st
, this->Cargo(), shares_it
->second
, st
->index
);
168 it
->second
.SwapShares(new_it
->second
);
173 geflows
.insert(flows
.begin(), flows
.end());
174 if (ge
.GetData().IsEmpty()) ge
.ClearData();
175 InvalidateWindowData(WC_STATION_VIEW
, st
->index
, this->Cargo());
180 * Initialize the link graph job: Resize nodes and edges and populate them.
181 * This is done after the constructor so that we can do it in the calculation
182 * thread without delaying the main game.
184 void LinkGraphJob::Init()
186 uint size
= this->Size();
187 this->nodes
.reserve(size
);
188 for (uint i
= 0; i
< size
; ++i
) {
189 this->nodes
.emplace_back(this->link_graph
.nodes
[i
], this->link_graph
.Size());
194 * Add this path as a new child to the given base path, thus making this path
195 * a "fork" of the base path.
196 * @param base Path to fork from.
197 * @param cap Maximum capacity of the new leg.
198 * @param free_cap Remaining free capacity of the new leg.
199 * @param dist Distance of the new leg.
201 void Path::Fork(Path
*base
, uint cap
, int free_cap
, uint dist
)
203 this->capacity
= std::min(base
->capacity
, cap
);
204 this->free_capacity
= std::min(base
->free_capacity
, free_cap
);
205 this->distance
= base
->distance
+ dist
;
206 assert(this->distance
> 0);
207 if (this->parent
!= base
) {
210 this->parent
->num_children
++;
212 this->origin
= base
->origin
;
216 * Push some flow along a path and register the path in the nodes it passes if
218 * @param new_flow Amount of flow to push.
219 * @param job Link graph job this node belongs to.
220 * @param max_saturation Maximum saturation of edges.
221 * @return Amount of flow actually pushed.
223 uint
Path::AddFlow(uint new_flow
, LinkGraphJob
&job
, uint max_saturation
)
225 if (this->parent
!= nullptr) {
226 LinkGraphJob::EdgeAnnotation
&edge
= job
[this->parent
->node
][this->node
];
227 if (max_saturation
!= UINT_MAX
) {
228 uint usable_cap
= edge
.base
.capacity
* max_saturation
/ 100;
229 if (usable_cap
> edge
.Flow()) {
230 new_flow
= std::min(new_flow
, usable_cap
- edge
.Flow());
235 new_flow
= this->parent
->AddFlow(new_flow
, job
, max_saturation
);
236 if (this->flow
== 0 && new_flow
> 0) {
237 job
[this->parent
->node
].paths
.push_front(this);
239 edge
.AddFlow(new_flow
);
241 this->flow
+= new_flow
;
246 * Create a leg of a path in the link graph.
247 * @param n Id of the link graph node this path passes.
248 * @param source If true, this is the first leg of the path.
250 Path::Path(NodeID n
, bool source
) :
251 distance(source
? 0 : UINT_MAX
),
252 capacity(source
? UINT_MAX
: 0),
253 free_capacity(source
? INT_MAX
: INT_MIN
),
254 flow(0), node(n
), origin(source
? n
: INVALID_NODE
),
255 num_children(0), parent(nullptr)