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 "../../timer/timer_game_calendar.h"
  14
  15 /**
  16  * CYapfSegmentCostCacheNoneT - the formal only yapf cost cache provider that implements
  17  * PfNodeCacheFetch(). Used when nodes don't have CachedData
  18  * defined (they don't count with any segment cost caching).
  19  */
  20 template <class Types>
  21 class CYapfSegmentCostCacheNoneT
  22 {
  23 public:
  24         typedef typename Types::Tpf Tpf;              ///< the pathfinder class (derived from THIS class)
  25         typedef typename Types::NodeList::Titem Node; ///< this will be our node type
  26
  27         /**
  28          * Called by YAPF to attach cached or local segment cost data to the given node.
  29          *  @return true if globally cached data were used or false if local data was used
  30          */
  31         inline bool PfNodeCacheFetch(Node &)
  32         {
  33                 return false;
  34         }
  35 };
  36
  37 /**
  38  * Base class for segment cost cache providers. Contains global counter
  39  *  of track layout changes and static notification function called whenever
  40  *  the track layout changes. It is implemented as base class because it needs
  41  *  to be shared between all rail YAPF types (one shared counter, one notification
  42  *  function.
  43  */
  44 struct CSegmentCostCacheBase
  45 {
  46         static int   s_rail_change_counter;
  47
  48         static void NotifyTrackLayoutChange(TileIndex, Track)
  49         {
  50                 s_rail_change_counter++;
  51         }
  52 };
  53
  54
  55 /**
  56  * CSegmentCostCacheT - template class providing hash-map and storage (heap)
  57  *  of Tsegment structures. Each rail node contains pointer to the segment
  58  *  that contains cached (or non-cached) segment cost information. Nodes can
  59  *  differ by key type, but they use the same segment type. Segment key should
  60  *  be always the same (TileIndex + DiagDirection) that represent the beginning
  61  *  of the segment (origin tile and exit-dir from this tile).
  62  *  Different CYapfCachedCostT types can share the same type of CSegmentCostCacheT.
  63  *  Look at CYapfRailSegment (yapf_node_rail.hpp) for the segment example
  64  */
  65 template <class Tsegment>
  66 struct CSegmentCostCacheT : public CSegmentCostCacheBase {
  67         static const int C_HASH_BITS = 14;
  68
  69         typedef CHashTableT<Tsegment, C_HASH_BITS> HashTable;
  70         using Heap = std::deque<Tsegment>;
  71         typedef typename Tsegment::Key Key;    ///< key to hash table
  72
  73         HashTable    m_map;
  74         Heap         m_heap;
  75
  76         inline CSegmentCostCacheT() {}
  77
  78         /** flush (clear) the cache */
  79         inline void Flush()
  80         {
  81                 m_map.Clear();
  82                 m_heap.clear();
  83         }
  84
  85         inline Tsegment &Get(Key &key, bool *found)
  86         {
  87                 Tsegment *item = m_map.Find(key);
  88                 if (item == nullptr) {
  89                         *found = false;
  90                         item = &m_heap.emplace_back(key);
  91                         m_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::Titem 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 &m_global_cache;
 117         LocalCache m_local_cache;
 118
 119         inline CYapfSegmentCostCacheGlobalT() : m_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, m_local_cache.emplace_back(key));
 151                         return false;
 152                 }
 153
 154                 bool found;
 155                 CachedData &item = m_global_cache.Get(key, &found);
 156                 Yapf().ConnectNodeToCachedData(n, item);
 157                 return found;
 158         }
 159 };
 160
 161 #endif /* YAPF_COSTCACHE_HPP */