Belle II Software light-2406-ragdoll
MRUCache< KEY, VALUE > Class Template Reference

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
KEYKey type to identify entries of the cache
VALUEValue 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
maxSizeMaximum 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) {}
unsigned int m_hits
Number of hits.
Definition: MRUCache.h:160
size_t m_maxSize
Maximum size of the cache.
Definition: MRUCache.h:158
unsigned int m_misses
Number of misses.
Definition: MRUCache.h:162
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(); }
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.

126 {
127 m_container.clear();
128 m_hits = 0;
129 m_misses = 0;
130 m_overflows = 0;
131 }

◆ 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
keykey to the new item
valueto the new item

Definition at line 79 of file MRUCache.h.

79{ insert(value_type(key, value)); }
void insert(const KEY &key, const VALUE &value)
Insert a key value pair into the cache.
Definition: MRUCache.h:79
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
itemstd::pair containing key and value of the new item

Definition at line 86 of file MRUCache.h.

87 {
88 std::pair<iterator, bool> p = m_container.push_front(item);
89 if (!p.second) { /* duplicate item, put existing in front */
90 m_container.replace(p.first, item);
91 update(p.first);
92 } else if (m_container.size() > m_maxSize) { /* keep the length <= maxSize */
94 m_container.pop_back();
95 }
96 }
void update(const iterator &item)
Update an item, thus marking it as recently accessed and putting it to the front of the list.
Definition: MRUCache.h:150

◆ retrieve()

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

Retrieve a value from the cache if it exists.

Parameters
[in]keykey for the value to retrieve
[out]valuereference 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.

105 {
106 hash_iterator it = m_container.template get<1>().find(key);
107 if (it == m_container.template get<1>().end()) {
108 ++m_misses;
109 return false;
110 }
111 update(m_container.template project<0>(it));
112 value = it->second;
113 ++m_hits;
114 return true;
115 }
container_type::template nth_index< 1 >::type::const_iterator hash_iterator
iterator over the hash index to the items
Definition: MRUCache.h:65

◆ 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
itemiterator to the item to update

Definition at line 150 of file MRUCache.h.

151 {
152 m_container.relocate(m_container.begin(), item);
153 }

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: