Class implementing a generic Most Recently Used cache. More...

#include <MRUCache.h>

Public Types
typedef std::pair< KEY, VALUE >	value_type
	type of elements stored in the cache

typedef boost::multi_index_container< value_type, boost::multi_index::indexed_by< boost::multi_index::sequenced<>, boost::multi_index::hashed_unique< boost::multi_index::member< value_type, KEY, &value_type::first > > > >	container_type
	type of container for the elements

typedef container_type::const_iterator	iterator
	iterator over all cached items, sorted by access: most recent used first

typedef container_type::template nth_index< 1 >::type::const_iterator	hash_iterator
	iterator over the hash index to the items

Public Member Functions
	MRUCache (size_t maxSize)
	Constructor setting the maximum number of cached items.

void	insert (const KEY &key, const VALUE &value)
	Insert a key value pair into the cache.

void	insert (const value_type &item)
	Insert a key value pair into the cache.

bool	retrieve (const KEY &key, VALUE &value)
	Retrieve a value from the cache if it exists.

iterator	begin () const
	Return iterator to the begin of the cache.

iterator	end () const
	Return iterator to the end of the cache.

size_t	size () const
	Return actual size of the cache.

void	clear ()
	Clear cache.

void	setMaxSize (size_t maxSize)
	Set maximum number of cache entries.

size_t	getMaxSize () const
	Get maximum number of cache entries.

unsigned int	getHits () const
	Get number of cache hits since creation/last clear.

unsigned int	getMisses () const
	Get number of cache misses since creation/last clear.

unsigned int	getOverflows () const
	Get number of overflows (dropped items) since creation/last clear.

Protected Member Functions
void	update (const iterator &item)
	Update an item, thus marking it as recently accessed and putting it to the front of the list.

Protected Attributes
container_type	m_container
	Container for the items.

size_t	m_maxSize
	Maximum size of the cache.

unsigned int	m_hits
	Number of hits.

unsigned int	m_misses
	Number of misses.

unsigned int	m_overflows
	Number of overflows.

Detailed Description

template<class KEY, class VALUE>
class Belle2::MRUCache< KEY, VALUE >

Class implementing a generic Most Recently Used cache.

It can be used to cache values which are needed repeatedly. The size is limited so only the N most recently accessed elements will be kept.

Usage: if you have elements of type VALUE which are uniquely identified by something of type KEY and you want to cache the last 100 of them because computation is expensive, than you can define a cache somewhere:

MRUCache<KEY, VALUE> cache(100);

and in your function you can do

VALUE calculate(const KEY &key){ VALUE value; if(!cache.retrieve(key,value)){ //calculate value here //and finally add to cache cache.insert(key,value); } return value; }

Template Parameters

KEY	Key type to identify entries of the cache
VALUE	Value type of the cache entries

Definition at line 48 of file MRUCache.h.

Member Typedef Documentation

◆ container_type

typedef boost::multi_index_container< value_type, boost::multi_index::indexed_by < boost::multi_index::sequenced<>, boost::multi_index::hashed_unique < boost::multi_index::member<value_type, KEY, &value_type::first> > > > container_type

type of container for the elements

Definition at line 61 of file MRUCache.h.

◆ hash_iterator

typedef container_type::template nth_index<1>::type::const_iterator hash_iterator

iterator over the hash index to the items

Definition at line 65 of file MRUCache.h.

◆ iterator

typedef container_type::const_iterator iterator

iterator over all cached items, sorted by access: most recent used first

Definition at line 63 of file MRUCache.h.

◆ value_type

typedef std::pair<KEY, VALUE> value_type

type of elements stored in the cache

Definition at line 51 of file MRUCache.h.

Constructor & Destructor Documentation

◆ MRUCache()

MRUCache ( size_t maxSize )

inlineexplicit

Constructor setting the maximum number of cached items.

Parameters

maxSize Maximum number of cached Items

Definition at line 71 of file MRUCache.h.

71: m_maxSize(maxSize), m_hits(0), m_misses(0), m_overflows(0) {}

Belle2::MRUCache::m_hits

unsigned int m_hits

Number of hits.

Definition: MRUCache.h:160

Belle2::MRUCache::m_maxSize

size_t m_maxSize

Maximum size of the cache.

Definition: MRUCache.h:158

Belle2::MRUCache::m_misses

unsigned int m_misses

Number of misses.

Definition: MRUCache.h:162

Belle2::MRUCache::m_overflows

unsigned int m_overflows

Number of overflows.

Definition: MRUCache.h:164

Member Function Documentation

◆ begin()

iterator begin ( ) const

inline

Return iterator to the begin of the cache.

Items are sorted by access: most recently inserted

Definition at line 118 of file MRUCache.h.

118{ return m_container.begin(); }

Belle2::MRUCache::m_container

container_type m_container

Container for the items.

Definition: MRUCache.h:156

◆ clear()

void clear ( )

inline

Clear cache.

Definition at line 125 of file MRUCache.h.

    {
      m_container.clear();
      m_hits = 0;
      m_misses = 0;
      m_overflows = 0;
    }

◆ end()

iterator end ( ) const

inline

Return iterator to the end of the cache.

Definition at line 120 of file MRUCache.h.

120{ return m_container.end(); }

◆ getHits()

unsigned int getHits ( ) const

inline

Get number of cache hits since creation/last clear.

Definition at line 138 of file MRUCache.h.

138{ return m_hits; }

◆ getMaxSize()

size_t getMaxSize ( ) const

inline

Get maximum number of cache entries.

Definition at line 136 of file MRUCache.h.

136{ return m_maxSize; }

◆ getMisses()

unsigned int getMisses ( ) const

inline

Get number of cache misses since creation/last clear.

Definition at line 140 of file MRUCache.h.

140{ return m_misses; }

◆ getOverflows()

unsigned int getOverflows ( ) const

inline

Get number of overflows (dropped items) since creation/last clear.

Definition at line 142 of file MRUCache.h.

142{ return m_overflows; }

◆ insert() [1/2]

void insert	(	const KEY &	key,
		const VALUE &	value
	)

inline

Insert a key value pair into the cache.

If the maximum size is reached, the least recently used item is dropped

Parameters

key	key to the new item
value	to the new item

Definition at line 79 of file MRUCache.h.

79{ insert(value_type(key, value)); }

Belle2::MRUCache::insert

void insert(const KEY &key, const VALUE &value)

Insert a key value pair into the cache.

Definition: MRUCache.h:79

Belle2::MRUCache::value_type

std::pair< KEY, VALUE > value_type

type of elements stored in the cache

Definition: MRUCache.h:51

◆ insert() [2/2]

void insert ( const value_type & item )

inline

Insert a key value pair into the cache.

If the maximum size is reached, the least recently used item is dropped

Parameters

item	std::pair containing key and value of the new item

Definition at line 86 of file MRUCache.h.

    {
      std::pair<iterator, bool> p = m_container.push_front(item);
      if (!p.second) {  /* duplicate item, put existing in front */
        m_container.replace(p.first, item);
        update(p.first);
      } else if (m_container.size() > m_maxSize) {  /* keep the length <= maxSize */
        ++m_overflows;
        m_container.pop_back();
      }
    }

◆ retrieve()

bool retrieve	(	const KEY &	key,
		VALUE &	value
	)

inline

Retrieve a value from the cache if it exists.

Parameters

[in]	key	key for the value to retrieve
[out]	value	reference to the value. Will only be modified if an item is found

Returns: true if value could be found, false otherwise

Definition at line 104 of file MRUCache.h.

    {
      hash_iterator it = m_container.template get<1>().find(key);
      if (it == m_container.template get<1>().end()) {
        ++m_misses;
        return false;
      }
      update(m_container.template project<0>(it));
      value = it->second;
      ++m_hits;
      return true;
    }

◆ setMaxSize()

void setMaxSize ( size_t maxSize )

inline

Set maximum number of cache entries.

Definition at line 134 of file MRUCache.h.

134{ m_maxSize = maxSize; }

◆ size()

size_t size ( ) const

inline

Return actual size of the cache.

Definition at line 123 of file MRUCache.h.

123{ return m_container.size(); }

◆ update()

void update ( const iterator & item )

inlineprotected

Update an item, thus marking it as recently accessed and putting it to the front of the list.

Parameters

item	iterator to the item to update

Definition at line 150 of file MRUCache.h.

    {
      m_container.relocate(m_container.begin(), item);
    }

Member Data Documentation

◆ m_container

container_type m_container

protected

Container for the items.

Definition at line 156 of file MRUCache.h.

◆ m_hits

unsigned int m_hits

protected

Number of hits.

Definition at line 160 of file MRUCache.h.

◆ m_maxSize

size_t m_maxSize

protected

Maximum size of the cache.

Definition at line 158 of file MRUCache.h.

◆ m_misses

unsigned int m_misses

protected

Number of misses.

Definition at line 162 of file MRUCache.h.

◆ m_overflows

unsigned int m_overflows

protected

Number of overflows.

Definition at line 164 of file MRUCache.h.

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

framework/core/include/MRUCache.h

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ container_type

◆ hash_iterator

◆ iterator

◆ value_type

Constructor & Destructor Documentation

◆ MRUCache()

Member Function Documentation

◆ begin()

◆ clear()

◆ end()

◆ getHits()

◆ getMaxSize()

◆ getMisses()

◆ getOverflows()

◆ insert() [1/2]

◆ insert() [2/2]

◆ retrieve()

◆ setMaxSize()

◆ size()

◆ update()

Member Data Documentation

◆ m_container

◆ m_hits

◆ m_maxSize

◆ m_misses

◆ m_overflows