src/pathfinder/yapf/yapf_costcache.hpp

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