diff options
Diffstat (limited to 'src/pathfinder/yapf/yapf_costcache.hpp')
-rw-r--r-- | src/pathfinder/yapf/yapf_costcache.hpp | 216 |
1 files changed, 216 insertions, 0 deletions
diff --git a/src/pathfinder/yapf/yapf_costcache.hpp b/src/pathfinder/yapf/yapf_costcache.hpp new file mode 100644 index 000000000..810579120 --- /dev/null +++ b/src/pathfinder/yapf/yapf_costcache.hpp @@ -0,0 +1,216 @@ +/* $Id$ */ + +/* + * 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 <http://www.gnu.org/licenses/>. + */ + +/** @file yapf_costcache.hpp Caching of segment costs. */ + +#ifndef YAPF_COSTCACHE_HPP +#define YAPF_COSTCACHE_HPP + +#include "../../date_func.h" + +/** CYapfSegmentCostCacheNoneT - the formal only yapf cost cache provider that implements + * PfNodeCacheFetch() and PfNodeCacheFlush() callbacks. Used when nodes don't have CachedData + * defined (they don't count with any segment cost caching). + */ +template <class Types> +class CYapfSegmentCostCacheNoneT +{ +public: + typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class) + typedef typename Types::NodeList::Titem Node; ///< this will be our node type + + /** Called by YAPF to attach cached or local segment cost data to the given node. + * @return true if globally cached data were used or false if local data was used */ + FORCEINLINE bool PfNodeCacheFetch(Node& n) + { + return false; + } + + /** Called by YAPF to flush the cached segment cost data back into cache storage. + * Current cache implementation doesn't use that. */ + FORCEINLINE void PfNodeCacheFlush(Node& n) + { + } +}; + + +/** CYapfSegmentCostCacheLocalT - the yapf cost cache provider that implements fake segment + * cost caching functionality for yapf. Used when node needs caching, but you don't want to + * cache the segment costs. + */ +template <class Types> +class CYapfSegmentCostCacheLocalT +{ +public: + typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class) + typedef typename Types::NodeList::Titem Node; ///< this will be our node type + typedef typename Node::Key Key; ///< key to hash tables + typedef typename Node::CachedData CachedData; + typedef typename CachedData::Key CacheKey; + typedef CArrayT<CachedData> LocalCache; + +protected: + LocalCache m_local_cache; + + /** to access inherited path finder */ + FORCEINLINE Tpf& Yapf() + { + return *static_cast<Tpf*>(this); + } + +public: + /** Called by YAPF to attach cached or local segment cost data to the given node. + * @return true if globally cached data were used or false if local data was used */ + FORCEINLINE bool PfNodeCacheFetch(Node& n) + { + CacheKey key(n.GetKey()); + Yapf().ConnectNodeToCachedData(n, *new (&m_local_cache.AddNC()) CachedData(key)); + return false; + } + + /** Called by YAPF to flush the cached segment cost data back into cache storage. + * Current cache implementation doesn't use that. */ + FORCEINLINE void PfNodeCacheFlush(Node& n) + { + } +}; + + +/** Base class for segment cost cache providers. Contains global counter + * of track layout changes and static notification function called whenever + * the track layout changes. It is implemented as base class because it needs + * to be shared between all rail YAPF types (one shared counter, one notification + * function. */ +struct CSegmentCostCacheBase +{ + static int s_rail_change_counter; + + static void NotifyTrackLayoutChange(TileIndex tile, Track track) + { + s_rail_change_counter++; + } +}; + + +/** CSegmentCostCacheT - template class providing hash-map and storage (heap) + * of Tsegment structures. Each rail node contains pointer to the segment + * that contains cached (or non-cached) segment cost information. Nodes can + * differ by key type, but they use the same segment type. Segment key should + * be always the same (TileIndex + DiagDirection) that represent the beginning + * of the segment (origin tile and exit-dir from this tile). + * Different CYapfCachedCostT types can share the same type of CSegmentCostCacheT. + * Look at CYapfRailSegment (yapf_node_rail.hpp) for the segment example */ +template <class Tsegment> +struct CSegmentCostCacheT + : public CSegmentCostCacheBase +{ + enum {c_hash_bits = 14}; + + typedef CHashTableT<Tsegment, c_hash_bits> HashTable; + typedef CArrayT<Tsegment> Heap; + typedef typename Tsegment::Key Key; ///< key to hash table + + HashTable m_map; + Heap m_heap; + + FORCEINLINE CSegmentCostCacheT() {} + + /** flush (clear) the cache */ + FORCEINLINE void Flush() + { + m_map.Clear(); + m_heap.Clear(); + } + + FORCEINLINE Tsegment& Get(Key& key, bool *found) + { + Tsegment *item = m_map.Find(key); + if (item == NULL) { + *found = false; + item = new (&m_heap.AddNC()) Tsegment(key); + m_map.Push(*item); + } else { + *found = true; + } + return *item; + } +}; + +/** CYapfSegmentCostCacheGlobalT - the yapf cost cache provider that adds the segment cost + * caching functionality to yapf. Using this class as base of your will provide the global + * segment cost caching services for your Nodes. + */ +template <class Types> +class CYapfSegmentCostCacheGlobalT + : public CYapfSegmentCostCacheLocalT<Types> +{ +public: + typedef CYapfSegmentCostCacheLocalT<Types> Tlocal; + typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class) + typedef typename Types::NodeList::Titem Node; ///< this will be our node type + typedef typename Node::Key Key; ///< key to hash tables + typedef typename Node::CachedData CachedData; + typedef typename CachedData::Key CacheKey; + typedef CSegmentCostCacheT<CachedData> Cache; + +protected: + Cache& m_global_cache; + + FORCEINLINE CYapfSegmentCostCacheGlobalT() : m_global_cache(stGetGlobalCache()) {}; + + /** to access inherited path finder */ + FORCEINLINE Tpf& Yapf() + { + return *static_cast<Tpf*>(this); + } + + FORCEINLINE static Cache& stGetGlobalCache() + { + static int last_rail_change_counter = 0; + static Date last_date = 0; + static Cache C; + + /* some statistics */ + if (last_date != _date) { + last_date = _date; + DEBUG(yapf, 2, "Pf time today: %5d ms", _total_pf_time_us / 1000); + _total_pf_time_us = 0; + } + + /* delete the cache sometimes... */ + if (last_rail_change_counter != Cache::s_rail_change_counter) { + last_rail_change_counter = Cache::s_rail_change_counter; + C.Flush(); + } + return C; + } + +public: + /** Called by YAPF to attach cached or local segment cost data to the given node. + * @return true if globally cached data were used or false if local data was used */ + FORCEINLINE bool PfNodeCacheFetch(Node& n) + { + if (!Yapf().CanUseGlobalCache(n)) { + return Tlocal::PfNodeCacheFetch(n); + } + CacheKey key(n.GetKey()); + bool found; + CachedData& item = m_global_cache.Get(key, &found); + Yapf().ConnectNodeToCachedData(n, item); + return found; + } + + /** Called by YAPF to flush the cached segment cost data back into cache storage. + * Current cache implementation doesn't use that. */ + FORCEINLINE void PfNodeCacheFlush(Node& n) + { + } +}; + +#endif /* YAPF_COSTCACHE_HPP */ |