Update: Translations from eints
[openttd-github.git] / src / linkgraph / linkgraphjob.cpp
blob33f474fb280d442cd993034f77d8ee34fede9c0e
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 */
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)
22 /**
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);
29 /**
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. */
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)
46 /**
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);
57 /**
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.
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. */
71 LinkGraphSchedule::Run(this);
75 /**
76 * Join the calling thread with this job's thread if threading is enabled.
78 void LinkGraphJob::JoinThread()
80 if (this->thread.joinable()) {
81 this->thread.join();
85 /**
86 * Join the link graph job and destroy it.
88 LinkGraphJob::~LinkGraphJob()
90 this->JoinThread();
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);
110 if (st == nullptr) {
111 this->EraseFlows(node_id);
112 continue;
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;
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
140 * new flows. */
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();
157 ++it;
158 } else {
159 FlowStat shares(INVALID_STATION, 1);
160 it->second.SwapShares(shares);
161 geflows.erase(it++);
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);
167 } else {
168 it->second.SwapShares(new_it->second);
169 flows.erase(new_it);
170 ++it;
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) {
208 this->Detach();
209 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
217 * successful.
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());
231 } else {
232 return 0;
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;
242 return 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)