src/pathfinder/yapf/yapf_costcache.hpp

   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 yapf_costcache.hpp Caching of segment costs. */
   9
  10 #ifndef YAPF_COSTCACHE_HPP
  11 #define YAPF_COSTCACHE_HPP
  12
  13 #include "../../misc/hashtable.hpp"
  14 #include "../../tile_type.h"
  15 #include "../../track_type.h"
  16
  17 /**
  18  * CYapfSegmentCostCacheNoneT - the formal only yapf cost cache provider that implements
  19  * PfNodeCacheFetch(). Used when nodes don't have CachedData
  20  * defined (they don't count with any segment cost caching).
  21  */
  22 template <class Types>
  23 class CYapfSegmentCostCacheNoneT
  24 {
  25 public:
  26         typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class)
  27         typedef typename Types::NodeList::Item Node; ///< this will be our node type
  28
  29         /**
  30          * Called by YAPF to attach cached or local segment cost data to the given node.
  31          *  @return true if globally cached data were used or false if local data was used
  32          */
  33         inline bool PfNodeCacheFetch(Node &)
  34         {
  35                 return false;
  36         }
  37 };
  38
  39 /**
  40  * Base class for segment cost cache providers. Contains global counter
  41  *  of track layout changes and static notification function called whenever
  42  *  the track layout changes. It is implemented as base class because it needs
  43  *  to be shared between all rail YAPF types (one shared counter, one notification
  44  *  function.
  45  */
  46 struct CSegmentCostCacheBase
  47 {
  48         static int   s_rail_change_counter;
  49
  50         static void NotifyTrackLayoutChange(TileIndex, Track)
  51         {
  52                 s_rail_change_counter++;
  53         }
  54 };
  55
  56
  57 /**
  58  * CSegmentCostCacheT - template class providing hash-map and storage (heap)
  59  *  of Tsegment structures. Each rail node contains pointer to the segment
  60  *  that contains cached (or non-cached) segment cost information. Nodes can
  61  *  differ by key type, but they use the same segment type. Segment key should
  62  *  be always the same (TileIndex + DiagDirection) that represent the beginning
  63  *  of the segment (origin tile and exit-dir from this tile).
  64  *  Different CYapfCachedCostT types can share the same type of CSegmentCostCacheT.
  65  *  Look at CYapfRailSegment (yapf_node_rail.hpp) for the segment example
  66  */
  67 template <class Tsegment>
  68 struct CSegmentCostCacheT : public CSegmentCostCacheBase {
  69         static constexpr int HASH_BITS = 14;
  70
  71         using Key = typename Tsegment::Key; ///< key to hash table
  72
  73         HashTable<Tsegment, HASH_BITS> map;
  74         std::deque<Tsegment> heap;
  75
  76         inline CSegmentCostCacheT() {}
  77
  78         /** flush (clear) the cache */
  79         inline void Flush()
  80         {
  81                 this->map.Clear();
  82                 this->heap.clear();
  83         }
  84
  85         inline Tsegment &Get(Key &key, bool *found)
  86         {
  87                 Tsegment *item = this->map.Find(key);
  88                 if (item == nullptr) {
  89                         *found = false;
  90                         item = &this->heap.emplace_back(key);
  91                         this->map.Push(*item);
  92                 } else {
  93                         *found = true;
  94                 }
  95                 return *item;
  96         }
  97 };
  98
  99 /**
 100  * CYapfSegmentCostCacheGlobalT - the yapf cost cache provider that adds the segment cost
 101  *  caching functionality to yapf. Using this class as base of your will provide the global
 102  *  segment cost caching services for your Nodes.
 103  */
 104 template <class Types>
 105 class CYapfSegmentCostCacheGlobalT {
 106 public:
 107         typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class)
 108         typedef typename Types::NodeList::Item Node; ///< this will be our node type
 109         typedef typename Node::Key Key; ///< key to hash tables
 110         typedef typename Node::CachedData CachedData;
 111         typedef typename CachedData::Key CacheKey;
 112         typedef CSegmentCostCacheT<CachedData> Cache;
 113         using LocalCache = std::deque<CachedData>;
 114
 115 protected:
 116         Cache &global_cache;
 117         LocalCache local_cache;
 118
 119         inline CYapfSegmentCostCacheGlobalT() : global_cache(stGetGlobalCache()) {};
 120
 121         /** to access inherited path finder */
 122         inline Tpf &Yapf()
 123         {
 124                 return *static_cast<Tpf *>(this);
 125         }
 126
 127         inline static Cache &stGetGlobalCache()
 128         {
 129                 static int last_rail_change_counter = 0;
 130                 static Cache C;
 131
 132                 /* delete the cache sometimes... */
 133                 if (last_rail_change_counter != Cache::s_rail_change_counter) {
 134                         last_rail_change_counter = Cache::s_rail_change_counter;
 135                         C.Flush();
 136                 }
 137                 return C;
 138         }
 139
 140 public:
 141         /**
 142          * Called by YAPF to attach cached or local segment cost data to the given node.
 143          *  @return true if globally cached data were used or false if local data was used
 144          */
 145         inline bool PfNodeCacheFetch(Node &n)
 146         {
 147                 CacheKey key(n.GetKey());
 148
 149                 if (!Yapf().CanUseGlobalCache(n)) {
 150                         Yapf().ConnectNodeToCachedData(n, this->local_cache.emplace_back(key));
 151                         return false;
 152                 }
 153
 154                 bool found;
 155                 CachedData &item = this->global_cache.Get(key, &found);
 156                 Yapf().ConnectNodeToCachedData(n, item);
 157                 return found;
 158         }
 159 };
 160
 161 #endif /* YAPF_COSTCACHE_HPP */