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

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

   108

	{

   109

		Tsegment* item = &m_map.Find(key);

   110

		if (item == NULL) {

   111

			*found = false;

   112

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

   113

			m_map.Push(*item);

   114

		} else {

   115

			*found = true;

   116

		}

   117

		return *item;

   118

	}

   119

};

   120

   121

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

   122

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

   123

 *  segment cost caching services for your Nodes.

   124

*/

   125

template <class Types>

   126

class CYapfSegmentCostCacheGlobalT

   127

	: public CYapfSegmentCostCacheLocalT<Types>

   128

{

   129

public:

   130

	typedef CYapfSegmentCostCacheLocalT<Types> Tlocal;

   131

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

   132

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

   133

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

   134

	typedef typename Node::CachedData CachedData;

   135

	typedef typename CachedData::Key CacheKey;

   136

	typedef CSegmentCostCacheT<CachedData> Cache;

   137

   138

protected:

   139

	Cache&      m_global_cache;

   140

   141

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

   142

   143

	/// to access inherited path finder

   144

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

   145

   146

	FORCEINLINE static Cache*& stGlobalCachePtr() {static Cache* pC = NULL; return pC;}

   147

   148

	FORCEINLINE static Cache& stGetGlobalCache()

   149

	{

   150

		static int last_rail_change_counter = 0;

   151

		static Date last_date = 0;

   152

   153

		// some statistics

   154

		if (last_date != _date) {

   155

			last_date = _date;

   156

			DEBUG(yapf, 1)("pf time today:%5d ms\n", _total_pf_time_us / 1000);

   157

			_total_pf_time_us = 0;

   158

		}

   159

   160

		Cache*& pC = stGlobalCachePtr();

   161

   162

		// delete the cache sometimes...

   163

		if (pC != NULL && last_rail_change_counter != Cache::s_rail_change_counter) {

   164

			last_rail_change_counter = Cache::s_rail_change_counter;

   165

			delete pC;

   166

			pC = NULL;

   167

		}

   168

   169

		if (pC == NULL)

   170

			pC = new Cache();

   171

		return *pC;

   172

	}

   173

   174

public:

   175

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

   176

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

   177

	FORCEINLINE bool PfNodeCacheFetch(Node& n)

   178

	{

   179

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

   180

			return Tlocal::PfNodeCacheFetch(n);

   181

		}

   182

		CacheKey key(n.GetKey());

   183

		bool found;

   184

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

   185

		Yapf().ConnectNodeToCachedData(n, item);

   186

		return found;

   187

	};

   188

   189

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

   190

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

   191

	FORCEINLINE void PfNodeCacheFlush(Node& n)

   192

	{

   193

	};

   194

   195

};

   196

   197

   198

   199

   200

#endif /* YAPF_COSTCACHE_HPP */