Simple thread-safe Cache template for arbitrary Key-Value pairs. More...

#include <cache.hpp>

Collaboration diagram for dodo::common::Cache< Key, Value >:

[legend]

Data Structures
struct	CacheEntry
	A CachedEntry holds the Value as well as last load and last hit time. More...

Public Member Functions
	Cache (size_t max_size, std::chrono::seconds life_time)
	Construct a cache with at most max_size entries, and a maximum life_time of the cached entry. More...

void	clear ()
	Wipes all cached entries. More...

void	erase (const Key &key)
	Erase the key from the cache. More...

bool	get (const Key &key, Value &value)
	Get a copy of the Value idenified by Key. More...

size_t	getExpiries () const
	Get the number of times a Key was present in the cache (a hit) but expired so implictly calling a load. More...

size_t	getHits () const
	Get the number of cache hits, which may include hits on expired entries - which still cause a load() call. More...

size_t	getMisses () const
	Get the number of cache loads - the number of times a Key was requested but not present in the cache. More...

void	setMaxLifeTime (const std::chrono::seconds &seconds)
	Set the maximum life time, in seconds, of a cached entry. More...

void	setMaxSize (size_t max_size)
	Set the maximum size / number of entries to cache. More...

Protected Types
typedef std::map< Key, CacheEntry >	CacheMap
	typedef for the Cache map More...

typedef CacheMap::const_iterator	CICacheMap
	typedef for a const iterator into the Cache map More...

typedef LRUMap::const_iterator	CILRUMap
	typedef for a const iterator into the LRU map More...

typedef CacheMap::iterator	ICacheMap
	typedef for an iterator into the Cache map More...

typedef LRUMap::iterator	ILRUMap
	typedef for an iterator into the LRU map More...

typedef std::multimap< std::chrono::steady_clock::time_point, Key >	LRUMap
	typedef for the LRU map More...

Protected Member Functions
virtual bool	load (const Key &key, Value &value)=0
	Implement to laod a value from the slow source. More...

Protected Attributes
CacheMap	cache_
	The Cache map. More...

Private Member Functions
void	addLRU (const CICacheMap &iter)
	Add an entry to the lrumap_. More...

void	removeLRU ()
	Remove the oldest CachedEntry from cache_ and lrumap_. More...

void	updateLRU (const CICacheMap &iter, std::chrono::steady_clock::time_point prev_hit_time)
	Update an entry in the lrumap_. More...

Private Attributes
size_t	expired_ = 0
	The number of expiries. More...

size_t	hits_ = 0
	The number of hits. More...

std::chrono::seconds	life_time_s_ = 300s
	The maximum life time of a cached entry. More...

size_t	load_ = 0
	The number of loades. More...

LRUMap	lrumap_
	The least-recently-used map. More...

size_t	max_size_
	The maximum number of cache entries. More...

threads::Mutex	mutex_
	Mutex to synchronize threads. More...

Detailed Description

template<class Key, class Value>
class dodo::common::Cache< Key, Value >

Simple thread-safe Cache template for arbitrary Key-Value pairs.

A Cache is applicable where the get( const Key& key, Value &value ) that finds the key in the cache, is much faster than the load( const Key& key, Value &value ). Each CacheEntry tracks the latest hit and load times. In case of pressure on the max_size, entries with the lowest hit_time are evicted to make room for the new load(). Additionally, if life_time is non-zero and the Value's load time is older then that, load() is invoked even if get() is a cache hit, updating both the load time and the hit time.

The Key class must have equality (==) and ordering (<) operators for the template instantiation to compile.

Template Parameters

Key	The unique Key type to the cached entries.
Value	the cached Value type.

The number of 'loads' is getMisses() + getExpiries().

The time complexity of the get call is O(N log N) where N is the number of cache entries. The cache and lrumap are backed by std::map and std::multimap respectively.

Note that get() receives a copy of the Value in the Cache. If thread A receives Value v1, thread B may cause the Value to get reloaded if its life_time expired , and that Value v2 might differ from v1. So the Cache does not guarentee that two values retrurned by get on the same Key are equal no matter how close they are in wallclock time.

#include <dodo.hpp>
 
 
using namespace dodo;
using namespace std;
 
class TestCache : public common::Cache<int, std::string> {
  public:
    TestCache( size_t max_size, std::chrono::seconds life_time ) : Cache<int, std::string>(max_size,life_time) {}
  protected:
    virtual bool load( const int &key, std::string &value ) {
      std::stringstream ss;
      ss << "retrieving value for key " << key;
      value = ss.str();
      return true;
    }
};
 
int main() {
  TestCache cache( 38, 40s );
  for ( int i = 0; i < 200; i++ ) {
    std::string value;
    cache.get( rand() % 40, value );
    //cout << value << endl;
    std::this_thread::sleep_for (std::chrono::milliseconds(rand() % 1000));
    std::cout << "." << std::flush;
  }
  std::cout << std::endl;
  cout << "hit     " << cache.getHits() << endl;
  cout << "miss    " << cache.getMisses() << endl;
  cout << "expired " << cache.getExpiries() << endl;
  return 0;
}

Definition at line 60 of file cache.hpp.

Member Typedef Documentation

◆ CacheMap

template<class Key , class Value >

typedef std::map<Key,CacheEntry> dodo::common::Cache< Key, Value >::CacheMap

protected

typedef for the Cache map

Definition at line 77 of file cache.hpp.

◆ CICacheMap

template<class Key , class Value >

typedef CacheMap::const_iterator dodo::common::Cache< Key, Value >::CICacheMap

protected

typedef for a const iterator into the Cache map

Definition at line 81 of file cache.hpp.

◆ CILRUMap

template<class Key , class Value >

typedef LRUMap::const_iterator dodo::common::Cache< Key, Value >::CILRUMap

protected

typedef for a const iterator into the LRU map

Definition at line 87 of file cache.hpp.

◆ ICacheMap

template<class Key , class Value >

typedef CacheMap::iterator dodo::common::Cache< Key, Value >::ICacheMap

protected

typedef for an iterator into the Cache map

Definition at line 79 of file cache.hpp.

◆ ILRUMap

template<class Key , class Value >

typedef LRUMap::iterator dodo::common::Cache< Key, Value >::ILRUMap

protected

typedef for an iterator into the LRU map

Definition at line 85 of file cache.hpp.

◆ LRUMap

template<class Key , class Value >

typedef std::multimap<std::chrono::steady_clock::time_point,Key> dodo::common::Cache< Key, Value >::LRUMap

protected

typedef for the LRU map

Definition at line 83 of file cache.hpp.

Constructor & Destructor Documentation

◆ Cache()

template<class Key , class Value >

dodo::common::Cache< Key, Value >::Cache	(	size_t	max_size,
		std::chrono::seconds	life_time
	)

inline

Construct a cache with at most max_size entries, and a maximum life_time of the cached entry.

Parameters

max_size	The maximum number of entries in the Cache.
life_time	The maximum number of seconds a cached entry may live before a get hit will issue a load. A life_time of 0s will disable the aging of cached entries.

Definition at line 97 of file cache.hpp.

Member Function Documentation

◆ addLRU()

template<class Key , class Value >

void dodo::common::Cache< Key, Value >::addLRU ( const CICacheMap & iter )

inlineprivate

Add an entry to the lrumap_.

Parameters

iter	An iterator to the CacheEntry.

Definition at line 223 of file cache.hpp.

◆ clear()

template<class Key , class Value >

void dodo::common::Cache< Key, Value >::clear ( )

inline

Wipes all cached entries.

Definition at line 105 of file cache.hpp.

◆ erase()

template<class Key , class Value >

void dodo::common::Cache< Key, Value >::erase ( const Key & key )

inline

Erase the key from the cache.

A subsequent get on the same Key will call load. Does nothing if the Key does not exist in the cache.

Parameters

key	The Key to erase.

Definition at line 171 of file cache.hpp.

◆ get()

template<class Key , class Value >

bool dodo::common::Cache< Key, Value >::get	(	const Key &	key,
		Value &	value
	)

inline

Get a copy of the Value idenified by Key.

Parameters

key	The Key to get the Value for.
value	Reference to the Value that will be assigned a copy of the cached entry.

Returns: false when the key is not loadable (load returns false).

See also: load( const Key& key )

Definition at line 119 of file cache.hpp.

◆ getExpiries()

template<class Key , class Value >

size_t dodo::common::Cache< Key, Value >::getExpiries ( ) const

inline

Get the number of times a Key was present in the cache (a hit) but expired so implictly calling a load.

Returns: The number of times a Key was present in the cache, but expired and cuasing a call to load.

Definition at line 164 of file cache.hpp.

◆ getHits()

template<class Key , class Value >

size_t dodo::common::Cache< Key, Value >::getHits ( ) const

inline

Get the number of cache hits, which may include hits on expired entries - which still cause a load() call.

Returns: The number of times a Key was requested and present in the cache.

Definition at line 152 of file cache.hpp.

◆ getMisses()

template<class Key , class Value >

size_t dodo::common::Cache< Key, Value >::getMisses ( ) const

inline

Get the number of cache loads - the number of times a Key was requested but not present in the cache.

Returns: The number of cache loades.

Definition at line 158 of file cache.hpp.

◆ load()

template<class Key , class Value >

virtual bool dodo::common::Cache< Key, Value >::load	(	const Key &	key,
		Value &	value
	)

protectedpure virtual

Implement to laod a value from the slow source.

If the key is not loadable, return false.

Parameters

key	The Key to load.
value	To receive the value.

Returns: False if the key could not be loaded.

◆ removeLRU()

template<class Key , class Value >

void dodo::common::Cache< Key, Value >::removeLRU ( )

inlineprivate

Remove the oldest CachedEntry from cache_ and lrumap_.

Definition at line 230 of file cache.hpp.

◆ setMaxLifeTime()

template<class Key , class Value >

void dodo::common::Cache< Key, Value >::setMaxLifeTime ( const std::chrono::seconds & seconds )

inline

Set the maximum life time, in seconds, of a cached entry.

Parameters

max_size The maximum size to set.

Definition at line 200 of file cache.hpp.

◆ setMaxSize()

template<class Key , class Value >

void dodo::common::Cache< Key, Value >::setMaxSize ( size_t max_size )

inline

Set the maximum size / number of entries to cache.

Parameters

max_size The maximum size to set.

Definition at line 194 of file cache.hpp.

◆ updateLRU()

template<class Key , class Value >

void dodo::common::Cache< Key, Value >::updateLRU	(	const CICacheMap &	iter,
		std::chrono::steady_clock::time_point	prev_hit_time
	)

inlineprivate

Update an entry in the lrumap_.

Parameters

iter	An iterator to the CacheEntry.
prev_hit_time	The previous hit time (the current key into the lrumap_)

Definition at line 242 of file cache.hpp.

Field Documentation

◆ cache_

template<class Key , class Value >

CacheMap dodo::common::Cache< Key, Value >::cache_

protected

The Cache map.

Definition at line 215 of file cache.hpp.

◆ expired_

template<class Key , class Value >

size_t dodo::common::Cache< Key, Value >::expired_ = 0

private

The number of expiries.

Definition at line 290 of file cache.hpp.

◆ hits_

template<class Key , class Value >

size_t dodo::common::Cache< Key, Value >::hits_ = 0

private

The number of hits.

Definition at line 280 of file cache.hpp.

◆ life_time_s_

template<class Key , class Value >

std::chrono::seconds dodo::common::Cache< Key, Value >::life_time_s_ = 300s

private

The maximum life time of a cached entry.

Definition at line 270 of file cache.hpp.

◆ load_

template<class Key , class Value >

size_t dodo::common::Cache< Key, Value >::load_ = 0

private

The number of loades.

Definition at line 285 of file cache.hpp.

◆ lrumap_

template<class Key , class Value >

LRUMap dodo::common::Cache< Key, Value >::lrumap_

private

The least-recently-used map.

Definition at line 260 of file cache.hpp.

◆ max_size_

template<class Key , class Value >

size_t dodo::common::Cache< Key, Value >::max_size_

private

The maximum number of cache entries.

Definition at line 265 of file cache.hpp.

◆ mutex_

template<class Key , class Value >

threads::Mutex dodo::common::Cache< Key, Value >::mutex_

private

Mutex to synchronize threads.

Definition at line 275 of file cache.hpp.

The documentation for this class was generated from the following file:

src/include/common/cache.hpp

Data Structures

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Private Member Functions

Private Attributes

Detailed Description

template<class Key, class Value> class dodo::common::Cache< Key, Value >

Member Typedef Documentation

◆ CacheMap

◆ CICacheMap

◆ CILRUMap

◆ ICacheMap

◆ ILRUMap

◆ LRUMap

Constructor & Destructor Documentation

◆ Cache()

Member Function Documentation

◆ addLRU()

◆ clear()

◆ erase()

◆ get()

◆ getExpiries()

◆ getHits()

◆ getMisses()

◆ load()

◆ removeLRU()

◆ setMaxLifeTime()

◆ setMaxSize()

◆ updateLRU()

Field Documentation

◆ cache_

◆ expired_

◆ hits_

◆ life_time_s_

◆ load_

◆ lrumap_

◆ max_size_

◆ mutex_

template<class Key, class Value>
class dodo::common::Cache< Key, Value >