linkgraphjob.h

Go to the documentation of this file.

/*
 * This file is part of OpenTTD.
 * 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.
 * 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.
 * 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 <https://www.gnu.org/licenses/old-licenses/gpl-2.0>.
 */

 
#ifndef LINKGRAPHJOB_H
#define LINKGRAPHJOB_H
 
#include "../thread.h"
#include "linkgraph.h"
#include <atomic>
 
class LinkGraphJob;
class Path;
typedef std::list<Path *> PathList;

using LinkGraphJobPool = Pool<LinkGraphJob, LinkGraphJobID, 32>;
extern LinkGraphJobPool _link_graph_job_pool;

class LinkGraphJob : public LinkGraphJobPool::PoolItem<&_link_graph_job_pool> {
public:
  struct DemandAnnotation {
    uint demand = 0; 
    uint unsatisfied_demand = 0; 
  };

  struct EdgeAnnotation {
    const LinkGraph::BaseEdge &base; 
    uint flow = 0; 
 
    EdgeAnnotation(const LinkGraph::BaseEdge &base) : base(base) {}

    uint Flow() const { return this->flow; }

    void AddFlow(uint flow) { this->flow += flow; }

    void RemoveFlow(uint flow)
    {
      assert(flow <= this->flow);
      this->flow -= flow;
    }
 
    friend inline bool operator <(NodeID dest, const EdgeAnnotation &rhs)
    {
      return dest < rhs.base.dest_node;
    }
  };

  struct NodeAnnotation {
    const LinkGraph::BaseNode &base; 
 
    uint undelivered_supply = 0; 
    PathList paths{}; 
    FlowStatMap flows{}; 
 
    std::vector<EdgeAnnotation> edges{}; 
    std::vector<DemandAnnotation> demands{}; 
 
    NodeAnnotation(const LinkGraph::BaseNode &node, size_t size) : base(node), undelivered_supply(node.supply)
    {
      this->edges.reserve(node.edges.size());
      for (auto &e : node.edges) this->edges.emplace_back(e);
      this->demands.resize(size);
    }

    EdgeAnnotation &operator[](NodeID to)
    {
      auto it = std::ranges::find_if(this->edges, [=] (const EdgeAnnotation &e) { return e.base.dest_node == to; });
      assert(it != this->edges.end());
      return *it;
    }

    const EdgeAnnotation &operator[](NodeID to) const
    {
      auto it = std::ranges::find_if(this->edges, [=] (const EdgeAnnotation &e) { return e.base.dest_node == to; });
      assert(it != this->edges.end());
      return *it;
    }

    uint DemandTo(NodeID to) const { return this->demands[to].demand; }

    uint UnsatisfiedDemandTo(NodeID to) const { return this->demands[to].unsatisfied_demand; }

    void SatisfyDemandTo(NodeID to, uint demand)
    {
      assert(demand <= this->demands[to].unsatisfied_demand);
      this->demands[to].unsatisfied_demand -= demand;
    }

    void DeliverSupply(NodeID to, uint amount)
    {
      this->undelivered_supply -= amount;
      this->demands[to].demand += amount;
      this->demands[to].unsatisfied_demand += amount;
    }
  };
 
private:
  typedef std::vector<NodeAnnotation> NodeAnnotationVector;
 
  friend SaveLoadTable GetLinkGraphJobDesc();
  friend class LinkGraphSchedule;
 
protected:
  const LinkGraph link_graph; 
  const LinkGraphSettings settings; 
  std::thread thread{}; 
  TimerGameEconomy::Date join_date = EconomyTime::INVALID_DATE; 
  NodeAnnotationVector nodes{}; 
  std::atomic<bool> job_completed = false; 
  std::atomic<bool> job_aborted = false; 
 
  void EraseFlows(StationID from);
  void JoinThread();
  void SpawnThread();
 
public:
  LinkGraphJob(LinkGraphJobID index) : LinkGraphJobPool::PoolItem<&_link_graph_job_pool>(index), link_graph(LinkGraphID::Invalid()), settings(_settings_game.linkgraph) {}
 
  LinkGraphJob(LinkGraphJobID index, const LinkGraph &orig);
  ~LinkGraphJob();
 
  void Init();

  inline bool IsJobCompleted() const { return this->job_completed.load(std::memory_order_acquire); }

  inline bool IsJobAborted() const { return this->job_aborted.load(std::memory_order_acquire); }

  inline void AbortJob() { this->job_aborted.store(true, std::memory_order_release); }

  inline bool IsScheduledToBeJoined() const { return this->join_date <= TimerGameEconomy::date; }

  inline TimerGameEconomy::Date JoinDate() const { return join_date; }

  inline void ShiftJoinDate(TimerGameEconomy::Date interval) { this->join_date += interval; }

  inline const LinkGraphSettings &Settings() const { return this->settings; }

  inline NodeAnnotation &operator[](NodeID num) { return this->nodes[num]; }

  inline NodeID Size() const { return this->link_graph.Size(); }

  inline CargoType Cargo() const { return this->link_graph.Cargo(); }

  inline TimerGameEconomy::Date LastCompression() const { return this->link_graph.LastCompression(); }

  inline LinkGraphID LinkGraphIndex() const { return this->link_graph.index; }

  inline const LinkGraph &Graph() const { return this->link_graph; }
};

class Path {
public:
  static Path *invalid_path;
 
  Path(NodeID n, bool source = false);
  virtual ~Path() = default;

  inline NodeID GetNode() const { return this->node; }

  inline NodeID GetOrigin() const { return this->origin; }

  inline Path *GetParent() { return this->parent; }

  inline uint GetCapacity() const { return this->capacity; }

  inline int GetFreeCapacity() const { return this->free_capacity; }

  static inline int GetCapacityRatio(int free, uint total)
  {
    return Clamp(free, PATH_CAP_MIN_FREE, PATH_CAP_MAX_FREE) * PATH_CAP_MULTIPLIER / std::max(total, 1U);
  }

  inline int GetCapacityRatio() const
  {
    return Path::GetCapacityRatio(this->free_capacity, this->capacity);
  }

  inline uint GetDistance() const { return this->distance; }

  inline void ReduceFlow(uint f) { this->flow -= f; }

  inline void AddFlow(uint f) { this->flow += f; }

  inline uint GetFlow() const { return this->flow; }

  inline uint GetNumChildren() const { return this->num_children; }

  inline void Detach()
  {
    if (this->parent != nullptr) {
      this->parent->num_children--;
      this->parent = nullptr;
    }
  }
 
  uint AddFlow(uint f, LinkGraphJob &job, uint max_saturation);
  void Fork(Path *base, uint cap, int free_cap, uint dist);
 
protected:
 
  /*
   * Some boundaries to clamp against in order to avoid integer overflows.
   */
  static constexpr int PATH_CAP_MULTIPLIER = 16;
  static constexpr int PATH_CAP_MIN_FREE = (INT_MIN + 1) / PATH_CAP_MULTIPLIER;
  static constexpr int PATH_CAP_MAX_FREE = (INT_MAX - 1) / PATH_CAP_MULTIPLIER;
 
  uint distance = 0; 
  uint capacity = 0; 
  int free_capacity = 0; 
  uint flow = 0; 
  NodeID node = INVALID_NODE; 
  NodeID origin = INVALID_NODE; 
  uint num_children = 0; 
  Path *parent = nullptr; 
};
 
#endif /* LINKGRAPHJOB_H */