1

/* $Id$ */

     2

     3

/** @file yapf_costcache.hpp */

     4

     5

#ifndef  YAPF_COSTCACHE_HPP

     6

#define  YAPF_COSTCACHE_HPP

     7

     8

     9

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

    10

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

    11

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

    12

 */

    13

template <class Types>

    14

class CYapfSegmentCostCacheNoneT

    15

{

    16

public:

    17

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

    18

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

    19

    20

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

    21

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

    22

	FORCEINLINE bool PfNodeCacheFetch(Node& n)

    23

	{

    24

		return false;

    25

	};

    26

    27

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

    28

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

    29

	FORCEINLINE void PfNodeCacheFlush(Node& n)

    30

	{

    31

	};

    32

};

    33

    34

    35

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

    36

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

    37

 * cache the segment costs.

    38

 */

    39

template <class Types>

    40

class CYapfSegmentCostCacheLocalT

    41

{

    42

public:

    43

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

    44

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

    45

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

    46

	typedef typename Node::CachedData CachedData;

    47

	typedef typename CachedData::Key CacheKey;

    48

	typedef CArrayT<CachedData> LocalCache;

    49

    50

protected:

    51

	LocalCache      m_local_cache;

    52

    53

	/// to access inherited path finder

    54

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

    55

    56

public:

    57

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

    58

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

    59

	FORCEINLINE bool PfNodeCacheFetch(Node& n)

    60

	{

    61

		CacheKey key(n.GetKey());

    62

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

    63

		return false;

    64

	};

    65

    66

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

    67

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

    68

	FORCEINLINE void PfNodeCacheFlush(Node& n)

    69

	{

    70

	};

    71

};

    72

    73

    74

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

    75

 *  of track layout changes and static notification function called whenever

    76

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

    77

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

    78

 *  function. */

    79

struct CSegmentCostCacheBase

    80

{

    81

	static int   s_rail_change_counter;

    82

    83

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

    84

};

    85

    86

    87

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

    88

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

    89

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

    90

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

    91

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

    92

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

    93

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

    94

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

    95

template <class Tsegment>

    96

struct CSegmentCostCacheT

    97

	: public CSegmentCostCacheBase

    98

{

    99

	enum {c_hash_bits = 14};

   100

   101

	typedef CHashTableT<Tsegment, c_hash_bits> HashTable;

   102

	typedef CArrayT<Tsegment> Heap;

   103

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

   104

   105

	HashTable    m_map;

   106

	Heap         m_heap;

   107

   108

	FORCEINLINE CSegmentCostCacheT() {}

   109

   110

	/** flush (clear) the cache */

   111

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

   112

   113

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

   114

	{

   115

		Tsegment* item = m_map.Find(key);

   116

		if (item == NULL) {

   117

			*found = false;

   118

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

   119

			m_map.Push(*item);

   120

		} else {

   121

			*found = true;

   122

		}

   123

		return *item;

   124

	}

   125

};

   126

   127

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

   128

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

   129

 *  segment cost caching services for your Nodes.

   130

*/

   131

template <class Types>

   132

class CYapfSegmentCostCacheGlobalT

   133

	: public CYapfSegmentCostCacheLocalT<Types>

   134

{

   135

public:

   136

	typedef CYapfSegmentCostCacheLocalT<Types> Tlocal;

   137

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

   138

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

   139

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

   140

	typedef typename Node::CachedData CachedData;

   141

	typedef typename CachedData::Key CacheKey;

   142

	typedef CSegmentCostCacheT<CachedData> Cache;

   143

   144

protected:

   145

	Cache&      m_global_cache;

   146

   147

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

   148

   149

	/// to access inherited path finder

   150

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

   151

   152

	FORCEINLINE static Cache& stGetGlobalCache()

   153

	{

   154

		static int last_rail_change_counter = 0;

   155

		static Date last_date = 0;

   156

		static Cache C;

   157

   158

		// some statistics

   159

		if (last_date != _date) {

   160

			last_date = _date;

   161

			DEBUG(yapf, 2, "Pf time today: %5d ms", _total_pf_time_us / 1000);

   162

			_total_pf_time_us = 0;

   163

		}

   164

   165

		// delete the cache sometimes...

   166

		if (last_rail_change_counter != Cache::s_rail_change_counter) {

   167

			last_rail_change_counter = Cache::s_rail_change_counter;

   168

			C.Flush();

   169

		}

   170

		return C;

   171

	}

   172

   173

public:

   174

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

   175

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

   176

	FORCEINLINE bool PfNodeCacheFetch(Node& n)

   177

	{

   178

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

   179

			return Tlocal::PfNodeCacheFetch(n);

   180

		}

   181

		CacheKey key(n.GetKey());

   182

		bool found;

   183

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

   184

		Yapf().ConnectNodeToCachedData(n, item);

   185

		return found;

   186

	};

   187

   188

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

   189

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

   190

	FORCEINLINE void PfNodeCacheFlush(Node& n)

   191

	{

   192

	};

   193

   194

};

   195

   196

   197

   198

   199

#endif /* YAPF_COSTCACHE_HPP */