--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/yapf/yapf_costcache.hpp Tue Jan 02 19:19:48 2007 +0000
@@ -0,0 +1,196 @@
+/* $Id$ */
+#ifndef YAPF_COSTCACHE_HPP
+#define YAPF_COSTCACHE_HPP
+
+
+/** 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 */