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 "../../date_func.h"
  14
  15 /**
  16  * CYapfSegmentCostCacheNoneT - the formal only yapf cost cache provider that implements
  17  * PfNodeCacheFetch() and PfNodeCacheFlush() callbacks. 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 &n)
  32         {
  33                 return false;
  34         }
  35
  36         /**
  37          * Called by YAPF to flush the cached segment cost data back into cache storage.
  38          *  Current cache implementation doesn't use that.
  39          */
  40         inline void PfNodeCacheFlush(Node &n)
  41         {
  42         }
  43 };
  44
  45
  46 /**
  47  * CYapfSegmentCostCacheLocalT - the yapf cost cache provider that implements fake segment
  48  * cost caching functionality for yapf. Used when node needs caching, but you don't want to
  49  * cache the segment costs.
  50  */
  51 template <class Types>
  52 class CYapfSegmentCostCacheLocalT
  53 {
  54 public:
  55         typedef typename Types::Tpf Tpf;              ///< the pathfinder class (derived from THIS class)
  56         typedef typename Types::NodeList::Titem Node; ///< this will be our node type
  57         typedef typename Node::Key Key;               ///< key to hash tables
  58         typedef typename Node::CachedData CachedData;
  59         typedef typename CachedData::Key CacheKey;
  60         typedef SmallArray<CachedData> LocalCache;
  61
  62 protected:
  63         LocalCache      m_local_cache;
  64
  65         /** to access inherited path finder */
  66         inline Tpf& Yapf()
  67         {
  68                 return *static_cast<Tpf *>(this);
  69         }
  70
  71 public:
  72         /**
  73          * Called by YAPF to attach cached or local segment cost data to the given node.
  74          *  @return true if globally cached data were used or false if local data was used
  75          */
  76         inline bool PfNodeCacheFetch(Node &n)
  77         {
  78                 CacheKey key(n.GetKey());
  79                 Yapf().ConnectNodeToCachedData(n, *new (m_local_cache.Append()) CachedData(key));
  80                 return false;
  81         }
  82
  83         /**
  84          * Called by YAPF to flush the cached segment cost data back into cache storage.
  85          *  Current cache implementation doesn't use that.
  86          */
  87         inline void PfNodeCacheFlush(Node &n)
  88         {
  89         }
  90 };
  91
  92
  93 /**
  94  * Base class for segment cost cache providers. Contains global counter
  95  *  of track layout changes and static notification function called whenever
  96  *  the track layout changes. It is implemented as base class because it needs
  97  *  to be shared between all rail YAPF types (one shared counter, one notification
  98  *  function.
  99  */
 100 struct CSegmentCostCacheBase
 101 {
 102         static int   s_rail_change_counter;
 103
 104         static void NotifyTrackLayoutChange(TileIndex tile, Track track)
 105         {
 106                 s_rail_change_counter++;
 107         }
 108 };
 109
 110
 111 /**
 112  * CSegmentCostCacheT - template class providing hash-map and storage (heap)
 113  *  of Tsegment structures. Each rail node contains pointer to the segment
 114  *  that contains cached (or non-cached) segment cost information. Nodes can
 115  *  differ by key type, but they use the same segment type. Segment key should
 116  *  be always the same (TileIndex + DiagDirection) that represent the beginning
 117  *  of the segment (origin tile and exit-dir from this tile).
 118  *  Different CYapfCachedCostT types can share the same type of CSegmentCostCacheT.
 119  *  Look at CYapfRailSegment (yapf_node_rail.hpp) for the segment example
 120  */
 121 template <class Tsegment>
 122 struct CSegmentCostCacheT : public CSegmentCostCacheBase {
 123         static const int C_HASH_BITS = 14;
 124
 125         typedef CHashTableT<Tsegment, C_HASH_BITS> HashTable;
 126         typedef SmallArray<Tsegment> Heap;
 127         typedef typename Tsegment::Key Key;    ///< key to hash table
 128
 129         HashTable    m_map;
 130         Heap         m_heap;
 131
 132         inline CSegmentCostCacheT() {}
 133
 134         /** flush (clear) the cache */
 135         inline void Flush()
 136         {
 137                 m_map.Clear();
 138                 m_heap.Clear();
 139         }
 140
 141         inline Tsegment& Get(Key &key, bool *found)
 142         {
 143                 Tsegment *item = m_map.Find(key);
 144                 if (item == nullptr) {
 145                         *found = false;
 146                         item = new (m_heap.Append()) Tsegment(key);
 147                         m_map.Push(*item);
 148                 } else {
 149                         *found = true;
 150                 }
 151                 return *item;
 152         }
 153 };
 154
 155 /**
 156  * CYapfSegmentCostCacheGlobalT - the yapf cost cache provider that adds the segment cost
 157  *  caching functionality to yapf. Using this class as base of your will provide the global
 158  *  segment cost caching services for your Nodes.
 159  */
 160 template <class Types>
 161 class CYapfSegmentCostCacheGlobalT : public CYapfSegmentCostCacheLocalT<Types> {
 162 public:
 163         typedef CYapfSegmentCostCacheLocalT<Types> Tlocal;
 164         typedef typename Types::Tpf Tpf;              ///< the pathfinder class (derived from THIS class)
 165         typedef typename Types::NodeList::Titem Node; ///< this will be our node type
 166         typedef typename Node::Key Key;    ///< key to hash tables
 167         typedef typename Node::CachedData CachedData;
 168         typedef typename CachedData::Key CacheKey;
 169         typedef CSegmentCostCacheT<CachedData> Cache;
 170
 171 protected:
 172         Cache &m_global_cache;
 173
 174         inline CYapfSegmentCostCacheGlobalT() : m_global_cache(stGetGlobalCache()) {};
 175
 176         /** to access inherited path finder */
 177         inline Tpf& Yapf()
 178         {
 179                 return *static_cast<Tpf *>(this);
 180         }
 181
 182         inline static Cache& stGetGlobalCache()
 183         {
 184                 static int last_rail_change_counter = 0;
 185                 static Date last_date = 0;
 186                 static Cache C;
 187
 188                 /* some statistics */
 189                 if (last_date != _date) {
 190                         last_date = _date;
 191                         DEBUG(yapf, 2, "Pf time today: %5d ms", _total_pf_time_us / 1000);
 192                         _total_pf_time_us = 0;
 193                 }
 194
 195                 /* delete the cache sometimes... */
 196                 if (last_rail_change_counter != Cache::s_rail_change_counter) {
 197                         last_rail_change_counter = Cache::s_rail_change_counter;
 198                         C.Flush();
 199                 }
 200                 return C;
 201         }
 202
 203 public:
 204         /**
 205          * Called by YAPF to attach cached or local segment cost data to the given node.
 206          *  @return true if globally cached data were used or false if local data was used
 207          */
 208         inline bool PfNodeCacheFetch(Node &n)
 209         {
 210                 if (!Yapf().CanUseGlobalCache(n)) {
 211                         return Tlocal::PfNodeCacheFetch(n);
 212                 }
 213                 CacheKey key(n.GetKey());
 214                 bool found;
 215                 CachedData &item = m_global_cache.Get(key, &found);
 216                 Yapf().ConnectNodeToCachedData(n, item);
 217                 return found;
 218         }
 219
 220         /**
 221          * Called by YAPF to flush the cached segment cost data back into cache storage.
 222          *  Current cache implementation doesn't use that.
 223          */
 224         inline void PfNodeCacheFlush(Node &n)
 225         {
 226         }
 227 };
 228
 229 #endif /* YAPF_COSTCACHE_HPP */