src/linkgraph/linkgraphjob.cpp

   1 /* $Id$ */
   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
  10 /** @file linkgraphjob.cpp Definition of link graph job classes used for cargo distribution. */
  11
  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 */
  21 LinkGraphJobPool _link_graph_job_pool("LinkGraphJob");
  22 INSTANTIATE_POOL_METHODS(LinkGraphJob)
  23
  24 /**
  25 * Static instance of an invalid path.
  26 * Note: This instance is created on task start.
  27 *       Lazy creation on first usage results in a data race between the CDist threads.
  28 */
  29 /* static */ Path *Path::invalid_path = new Path(INVALID_NODE, true);
  30
  31 static Ticks GetLinkGraphJobJoinDateTicks(uint duration_multiplier)
  32 {
  33         Ticks ticks = _settings_game.linkgraph.recalc_time * DAY_TICKS * duration_multiplier;
  34         ticks /= std::max(_settings_game.economy.daylength, (uint8)1);
  35
  36         return ticks + (_date * DAY_TICKS) + _date_fract;
  37 }
  38
  39 /**
  40 * Create a link graph job from a link graph. The link graph will be copied so
  41 * that the calculations don't interfer with the normal operations on the
  42 * original. The job is immediately started.
  43 * @param orig Original LinkGraph to be copied.
  44 */
  45 LinkGraphJob::LinkGraphJob(const LinkGraph &orig, uint duration_multiplier) :
  46         /* Copying the link graph here also copies its index member.
  47         * This is on purpose. */
  48         link_graph(orig),
  49         settings(_settings_game.linkgraph),
  50         join_date_ticks(GetLinkGraphJobJoinDateTicks(duration_multiplier)),
  51         start_date_ticks((_date * DAY_TICKS) + _date_fract),
  52         job_completed(false),
  53         abort_job(false)
  54 {
  55 }
  56
  57 /**
  58 * Erase all flows originating at a specific node.
  59 * @param from Node to erase flows for.
  60 */
  61 void LinkGraphJob::EraseFlows(NodeID from)
  62 {
  63         for (NodeID node_id = 0; node_id < this->Size(); ++node_id) {
  64                 (*this)[node_id].Flows().erase(from);
  65         }
  66 }
  67
  68 void LinkGraphJob::SetJobGroup(std::shared_ptr<LinkGraphJobGroup> group)
  69 {
  70         this->group = std::move(group);
  71 }
  72
  73 /**
  74 * Join the calling thread with this job's thread if threading is enabled.
  75 */
  76 void LinkGraphJob::JoinThread()
  77 {
  78         if (this->group != nullptr) {
  79                 this->group->JoinThread();
  80                 this->group.reset();
  81         }
  82 }
  83
  84 /**
  85 * Join the link graph job thread, if not already joined.
  86 */
  87 LinkGraphJob::~LinkGraphJob()
  88 {
  89         this->JoinThread();
  90 }
  91
  92 /**
  93 * Join the link graph job thread, then merge/apply it.
  94 */
  95 void LinkGraphJob::FinaliseJob()
  96 {
  97         this->JoinThread();
  98
  99         /* Link graph has been merged into another one. */
 100         if (!LinkGraph::IsValidID(this->link_graph.index)) return;
 101
 102         uint size = this->Size();
 103         for (NodeID node_id = 0; node_id < size; ++node_id) {
 104                 Node from = (*this)[node_id];
 105
 106                 /* The station can have been deleted. Remove all flows originating from it then. */
 107                 Station *st = Station::GetIfValid(from.Station());
 108                 if (st == nullptr) {
 109                         this->EraseFlows(node_id);
 110                         continue;
 111                 }
 112
 113                 /* Link graph merging and station deletion may change around IDs. Make
 114                 * sure that everything is still consistent or ignore it otherwise. */
 115                 GoodsEntry &ge = st->goods[this->Cargo()];
 116                 if (ge.link_graph != this->link_graph.index || ge.node != node_id) {
 117                         this->EraseFlows(node_id);
 118                         continue;
 119                 }
 120
 121                 LinkGraph *lg = LinkGraph::Get(ge.link_graph);
 122                 FlowStatMap &flows = from.Flows();
 123
 124                 for (EdgeIterator it(from.Begin()); it != from.End(); ++it) {
 125                         if (from[it->first].Flow() == 0) continue;
 126                         StationID to = (*this)[it->first].Station();
 127                         Station *st2 = Station::GetIfValid(to);
 128                         if (st2 == nullptr || st2->goods[this->Cargo()].link_graph != this->link_graph.index ||
 129                                 st2->goods[this->Cargo()].node != it->first ||
 130                                 (*lg)[node_id][it->first].LastUpdate() == INVALID_DATE) {
 131                                 /* Edge has been removed. Delete flows. */
 132                                 StationIDStack erased = flows.DeleteFlows(to);
 133                                 /* Delete old flows for source stations which have been deleted
 134                                 * from the new flows. This avoids flow cycles between old and
 135                                 * new flows. */
 136                                 while (!erased.IsEmpty()) ge.flows.erase(erased.Pop());
 137                         }
 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                                 }
 155                                 else {
 156                                         FlowStat shares(INVALID_STATION, 1);
 157                                         it->second.SwapShares(shares);
 158                                         ge.flows.erase(it++);
 159                                         for (FlowStat::SharesMap::const_iterator shares_it(shares.GetShares()->begin());
 160                                                 shares_it != shares.GetShares()->end(); ++shares_it) {
 161                                                 RerouteCargo(st, this->Cargo(), shares_it->second, st->index);
 162                                         }
 163                                 }
 164                         }
 165                         else {
 166                                 it->second.SwapShares(new_it->second);
 167                                 flows.erase(new_it);
 168                                 ++it;
 169                         }
 170                 }
 171                 ge.flows.insert(flows.begin(), flows.end());
 172                 InvalidateWindowData(WC_STATION_VIEW, st->index, this->Cargo());
 173         }
 174 }
 175
 176 /**
 177 * Check if job has actually finished.
 178 * This is allowed to spuriously return an incorrect value.
 179 * @return True if job has actually finished.
 180 */
 181 bool LinkGraphJob::IsJobCompleted() const
 182 {
 183 #if defined(__GNUC__) || defined(__clang__)
 184         return __atomic_load_n(&job_completed, __ATOMIC_RELAXED);
 185 #else
 186         return job_completed;
 187 #endif
 188 }
 189
 190 /**
 191 * Check if job has been requested to be aborted.
 192 * This is allowed to spuriously return a falsely negative value.
 193 * @return True if job abort has been requested.
 194 */
 195 bool LinkGraphJob::IsJobAborted() const
 196 {
 197 #if defined(__GNUC__) || defined(__clang__)
 198         return __atomic_load_n(&abort_job, __ATOMIC_RELAXED);
 199 #else
 200         return abort_job;
 201 #endif
 202 }
 203
 204 /**
 205 * Abort job.
 206 * The job may exit early at the next available opportunity.
 207 * After this method has been called the state of the job is undefined, and the only valid operation
 208 * is to join the thread and discard the job data.
 209 */
 210 void LinkGraphJob::AbortJob()
 211 {
 212         /*
 213         * Note that this it not guaranteed to be an atomic write and there are no memory barriers or other protections.
 214         * Readers of this variable in another thread may see an out of date value.
 215         * However this is OK as if this method is called the state of the job/thread does not matter anyway.
 216         */
 217
 218 #if defined(__GNUC__) || defined(__clang__)
 219         __atomic_store_n(&(abort_job), true, __ATOMIC_RELAXED);
 220 #else
 221         abort_job = true;
 222 #endif
 223 }
 224
 225 /**
 226 * Initialize the link graph job: Resize nodes and edges and populate them.
 227 * This is done after the constructor so that we can do it in the calculation
 228 * thread without delaying the main game.
 229 */
 230 void LinkGraphJob::Init()
 231 {
 232         uint size = this->Size();
 233         this->nodes.resize(size);
 234         this->edges.Resize(size, size);
 235         for (uint i = 0; i < size; ++i) {
 236                 this->nodes[i].Init(this->link_graph[i].Supply());
 237                 EdgeAnnotation *node_edges = this->edges[i];
 238                 for (uint j = 0; j < size; ++j) {
 239                         node_edges[j].Init();
 240                 }
 241         }
 242 }
 243
 244 /**
 245 * Initialize a linkgraph job edge.
 246 */
 247 void LinkGraphJob::EdgeAnnotation::Init()
 248 {
 249         this->demand = 0;
 250         this->flow = 0;
 251         this->unsatisfied_demand = 0;
 252 }
 253
 254 /**
 255 * Initialize a Linkgraph job node. The underlying memory is expected to be
 256 * freshly allocated, without any constructors having been called.
 257 * @param supply Initial undelivered supply.
 258 */
 259 void LinkGraphJob::NodeAnnotation::Init(uint supply)
 260 {
 261         this->undelivered_supply = supply;
 262 }
 263
 264 /**
 265 * Add this path as a new child to the given base path, thus making this path
 266 * a "fork" of the base path.
 267 * @param base Path to fork from.
 268 * @param cap Maximum capacity of the new leg.
 269 * @param free_cap Remaining free capacity of the new leg.
 270 * @param dist Distance of the new leg.
 271 */
 272 void Path::Fork(Path *base, uint cap, int free_cap, uint dist)
 273 {
 274         this->capacity = min(base->capacity, cap);
 275         this->free_capacity = min(base->free_capacity, free_cap);
 276         this->distance = base->distance + dist;
 277         assert(this->distance > 0);
 278         if (this->parent != base) {
 279                 this->Detach();
 280                 this->parent = base;
 281                 this->parent->num_children++;
 282         }
 283         this->origin = base->origin;
 284 }
 285
 286 /**
 287 * Push some flow along a path and register the path in the nodes it passes if
 288 * successful.
 289 * @param new_flow Amount of flow to push.
 290 * @param job Link graph job this node belongs to.
 291 * @param max_saturation Maximum saturation of edges.
 292 * @return Amount of flow actually pushed.
 293 */
 294 uint Path::AddFlow(uint new_flow, LinkGraphJob &job, uint max_saturation)
 295 {
 296         if (this->parent != nullptr) {
 297                 LinkGraphJob::Edge edge = job[this->parent->node][this->node];
 298                 if (max_saturation != UINT_MAX) {
 299                         uint usable_cap = edge.Capacity() * max_saturation / 100;
 300                         if (usable_cap > edge.Flow()) {
 301                                 new_flow = min(new_flow, usable_cap - edge.Flow());
 302                         }
 303                         else {
 304                                 return 0;
 305                         }
 306                 }
 307                 new_flow = this->parent->AddFlow(new_flow, job, max_saturation);
 308                 if (this->flow == 0 && new_flow > 0) {
 309                         job[this->parent->node].Paths().push_back(this);
 310                 }
 311                 edge.AddFlow(new_flow);
 312         }
 313         this->flow += new_flow;
 314         return new_flow;
 315 }
 316
 317 /**
 318 * Create a leg of a path in the link graph.
 319 * @param n Id of the link graph node this path passes.
 320 * @param source If true, this is the first leg of the path.
 321 */
 322 Path::Path(NodeID n, bool source) :
 323         distance(source ? 0 : UINT_MAX),
 324         capacity(source ? UINT_MAX : 0),
 325         free_capacity(source ? INT_MAX : INT_MIN),
 326         flow(0), node(n), origin(source ? n : INVALID_NODE),
 327         num_children(0), parent(nullptr)
 328 {}