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 uint32 last_day = 0;

   152

   153

		// some statistics

   154

		if (last_day != _date) {

   155

			last_day = _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 */