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 */