1

/* $Id$ */

     2

#ifndef  YAPF_COSTCACHE_HPP

     3

#define  YAPF_COSTCACHE_HPP

     4

     5

     6

/** CYapfSegmentCostCacheNoneT - the formal only yapf cost cache provider that implements

     7

 * PfNodeCacheFetch() and PfNodeCacheFlush() callbacks. Used when nodes don't have CachedData

     8

 * defined (they don't count with any segment cost caching).

     9

 */

    10

template <class Types>

    11

class CYapfSegmentCostCacheNoneT

    12

{

    13

public:

    14

	typedef typename Types::Tpf Tpf;              ///< the pathfinder class (derived from THIS class)

    15

	typedef typename Types::NodeList::Titem Node; ///< this will be our node type

    16

    17

	/** Called by YAPF to attach cached or local segment cost data to the given node.

    18

	 *  @return true if globally cached data were used or false if local data was used */

    19

	FORCEINLINE bool PfNodeCacheFetch(Node& n)

    20

	{

    21

		return false;

    22

	};

    23

    24

	/** Called by YAPF to flush the cached segment cost data back into cache storage.

    25

	 *  Current cache implementation doesn't use that. */

    26

	FORCEINLINE void PfNodeCacheFlush(Node& n)

    27

	{

    28

	};

    29

};

    30

    31

    32

/** CYapfSegmentCostCacheLocalT - the yapf cost cache provider that implements fake segment

    33

 * cost caching functionality for yapf. Used when node needs caching, but you don't want to

    34

 * cache the segment costs.

    35

 */

    36

template <class Types>

    37

class CYapfSegmentCostCacheLocalT

    38

{

    39

public:

    40

	typedef typename Types::Tpf Tpf;              ///< the pathfinder class (derived from THIS class)

    41

	typedef typename Types::NodeList::Titem Node; ///< this will be our node type

    42

	typedef typename Node::Key Key;               ///< key to hash tables

    43

	typedef typename Node::CachedData CachedData;

    44

	typedef typename CachedData::Key CacheKey;

    45

	typedef CArrayT<CachedData> LocalCache;

    46

    47

protected:

    48

	LocalCache      m_local_cache;

    49

    50

	/// to access inherited path finder

    51

	FORCEINLINE Tpf& Yapf() {return *static_cast<Tpf*>(this);}

    52

    53

public:

    54

	/** Called by YAPF to attach cached or local segment cost data to the given node.

    55

	 *  @return true if globally cached data were used or false if local data was used */

    56

	FORCEINLINE bool PfNodeCacheFetch(Node& n)

    57

	{

    58

		CacheKey key(n.GetKey());

    59

		Yapf().ConnectNodeToCachedData(n, *new (&m_local_cache.AddNC()) CachedData(key));

    60

		return false;

    61

	};

    62

    63

	/** Called by YAPF to flush the cached segment cost data back into cache storage.

    64

	 *  Current cache implementation doesn't use that. */

    65

	FORCEINLINE void PfNodeCacheFlush(Node& n)

    66

	{

    67

	};

    68

};

    69

    70

    71

/** Base class for segment cost cache providers. Contains global counter

    72

 *  of track layout changes and static notification function called whenever

    73

 *  the track layout changes. It is implemented as base class because it needs

    74

 *  to be shared between all rail YAPF types (one shared counter, one notification

    75

 *  function. */

    76

struct CSegmentCostCacheBase

    77

{

    78

	static int   s_rail_change_counter;

    79

    80

	static void NotifyTrackLayoutChange(TileIndex tile, Track track) {s_rail_change_counter++;}

    81

};

    82

    83

    84

/** CSegmentCostCacheT - template class providing hash-map and storage (heap)

    85

 *  of Tsegment structures. Each rail node contains pointer to the segment

    86

 *  that contains cached (or non-cached) segment cost information. Nodes can

    87

 *  differ by key type, but they use the same segment type. Segment key should

    88

 *  be always the same (TileIndex + DiagDirection) that represent the beginning

    89

 *  of the segment (origin tile and exit-dir from this tile).

    90

 *  Different CYapfCachedCostT types can share the same type of CSegmentCostCacheT.

    91

 *  Look at CYapfRailSegment (yapf_node_rail.hpp) for the segment example */

    92

template <class Tsegment>

    93

struct CSegmentCostCacheT

    94

	: public CSegmentCostCacheBase

    95

{

    96

	enum {c_hash_bits = 14};

    97

    98

	typedef CHashTableT<Tsegment, c_hash_bits> HashTable;

    99

	typedef CArrayT<Tsegment> Heap;

   100

	typedef typename Tsegment::Key Key;    ///< key to hash table

   101

   102

	HashTable    m_map;

   103

	Heap         m_heap;

   104

   105

	FORCEINLINE CSegmentCostCacheT() {}

   106

   107

	/** flush (clear) the cache */

   108

	FORCEINLINE void Flush() {m_map.Clear(); m_heap.Clear();};

   109

   110

	FORCEINLINE Tsegment& Get(Key& key, bool *found)

   111

	{

   112

		Tsegment* item = m_map.Find(key);

   113

		if (item == NULL) {

   114

			*found = false;

   115

			item = new (&m_heap.AddNC()) Tsegment(key);

   116

			m_map.Push(*item);

   117

		} else {

   118

			*found = true;

   119

		}

   120

		return *item;

   121

	}

   122

};

   123

   124

/** CYapfSegmentCostCacheGlobalT - the yapf cost cache provider that adds the segment cost

   125

 *  caching functionality to yapf. Using this class as base of your will provide the global

   126

 *  segment cost caching services for your Nodes.

   127

*/

   128

template <class Types>

   129

class CYapfSegmentCostCacheGlobalT

   130

	: public CYapfSegmentCostCacheLocalT<Types>

   131

{

   132

public:

   133

	typedef CYapfSegmentCostCacheLocalT<Types> Tlocal;

   134

	typedef typename Types::Tpf Tpf;              ///< the pathfinder class (derived from THIS class)

   135

	typedef typename Types::NodeList::Titem Node; ///< this will be our node type

   136

	typedef typename Node::Key Key;    ///< key to hash tables

   137

	typedef typename Node::CachedData CachedData;

   138

	typedef typename CachedData::Key CacheKey;

   139

	typedef CSegmentCostCacheT<CachedData> Cache;

   140

   141

protected:

   142

	Cache&      m_global_cache;

   143

   144

	FORCEINLINE CYapfSegmentCostCacheGlobalT() : m_global_cache(stGetGlobalCache()) {};

   145

   146

	/// to access inherited path finder

   147

	FORCEINLINE Tpf& Yapf() {return *static_cast<Tpf*>(this);}

   148

   149

	FORCEINLINE static Cache& stGetGlobalCache()

   150

	{

   151

		static int last_rail_change_counter = 0;

   152

		static Date last_date = 0;

   153

		static Cache C;

   154

   155

		// some statistics

   156

		if (last_date != _date) {

   157

			last_date = _date;

   159

			_total_pf_time_us = 0;

   160

		}

   161

   162

		// delete the cache sometimes...

   163

		if (last_rail_change_counter != Cache::s_rail_change_counter) {

   164

			last_rail_change_counter = Cache::s_rail_change_counter;

   165

			C.Flush();

   166

		}

   167

		return C;

   168

	}

   169

   170

public:

   171

	/** Called by YAPF to attach cached or local segment cost data to the given node.

   172

	 *  @return true if globally cached data were used or false if local data was used */

   173

	FORCEINLINE bool PfNodeCacheFetch(Node& n)

   174

	{

   175

		if (!Yapf().CanUseGlobalCache(n)) {

   176

			return Tlocal::PfNodeCacheFetch(n);

   177

		}

   178

		CacheKey key(n.GetKey());

   179

		bool found;

   180

		CachedData& item = m_global_cache.Get(key, &found);

   181

		Yapf().ConnectNodeToCachedData(n, item);

   182

		return found;

   183

	};

   184

   185

	/** Called by YAPF to flush the cached segment cost data back into cache storage.

   186

	 *  Current cache implementation doesn't use that. */

   187

	FORCEINLINE void PfNodeCacheFlush(Node& n)

   188

	{

   189

	};

   190

   191

};

   192

   193

   194

   195

   196

#endif /* YAPF_COSTCACHE_HPP */