src/linkgraph/linkgraphjob.cpp

   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
   8 /** @file linkgraphjob.cpp Definition of link graph job classes used for cargo distribution. */
   9
  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 */
  19 LinkGraphJobPool _link_graph_job_pool("LinkGraphJob");
  20 INSTANTIATE_POOL_METHODS(LinkGraphJob)
  21
  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.
  26  */
  27 /* static */ Path *Path::invalid_path = new Path(INVALID_NODE, true);
  28
  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.
  34  */
  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)
  43 {
  44 }
  45
  46 /**
  47  * Erase all flows originating at a specific node.
  48  * @param from Node to erase flows for.
  49  */
  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
  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.
  60  */
  61 void LinkGraphJob::SpawnThread()
  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. */
  71                 LinkGraphSchedule::Run(this);
  72         }
  73 }
  74
  75 /**
  76  * Join the calling thread with this job's thread if threading is enabled.
  77  */
  78 void LinkGraphJob::JoinThread()
  79 {
  80         if (this->thread.joinable()) {
  81                 this->thread.join();
  82         }
  83 }
  84
  85 /**
  86  * Join the link graph job and destroy it.
  87  */
  88 LinkGraphJob::~LinkGraphJob()
  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. */
 109                 Station *st = Station::GetIfValid(from.base.station);
 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
 123                 LinkGraph *lg = LinkGraph::Get(ge.link_graph);
 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
 177 /**
 178  * Initialize the link graph job: Resize nodes and edges and populate them.
 179  * This is done after the constructor so that we can do it in the calculation
 180  * thread without delaying the main game.
 181  */
 182 void LinkGraphJob::Init()
 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
 191 /**
 192  * Add this path as a new child to the given base path, thus making this path
 193  * a "fork" of the base path.
 194  * @param base Path to fork from.
 195  * @param cap Maximum capacity of the new leg.
 196  * @param free_cap Remaining free capacity of the new leg.
 197  * @param dist Distance of the new leg.
 198  */
 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
 213 /**
 214  * Push some flow along a path and register the path in the nodes it passes if
 215  * successful.
 216  * @param new_flow Amount of flow to push.
 217  * @param job Link graph job this node belongs to.
 218  * @param max_saturation Maximum saturation of edges.
 219  * @return Amount of flow actually pushed.
 220  */
 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
 243 /**
 244  * Create a leg of a path in the link graph.
 245  * @param n Id of the link graph node this path passes.
 246  * @param source If true, this is the first leg of the path.
 247  */
 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