Belle II Software light-2406-ragdoll
MRUCache.h
1/**************************************************************************
2 * basf2 (Belle II Analysis Software Framework) *
3 * Author: The Belle II Collaboration *
4 * *
5 * See git log for contributors and copyright holders. *
6 * This file is licensed under LGPL-3.0, see LICENSE.md. *
7 **************************************************************************/
8
9#pragma once
10
11#include <boost/multi_index_container.hpp>
12#include <boost/multi_index/sequenced_index.hpp>
13#include <boost/multi_index/hashed_index.hpp>
14#include <boost/multi_index/member.hpp>
15
16namespace Belle2 {
48 template <class KEY, class VALUE> class MRUCache {
49 public:
51 typedef std::pair<KEY, VALUE> value_type;
53 typedef boost::multi_index_container <
55 boost::multi_index::indexed_by <
56 boost::multi_index::sequenced<>,
57 boost::multi_index::hashed_unique <
58 boost::multi_index::member<value_type, KEY, &value_type::first>
59 >
60 >
63 typedef typename container_type::const_iterator iterator;
65 typedef typename container_type::template nth_index<1>::type::const_iterator hash_iterator;
66
71 explicit MRUCache(size_t maxSize): m_maxSize(maxSize), m_hits(0), m_misses(0), m_overflows(0) {}
72
79 void insert(const KEY& key, const VALUE& value) { insert(value_type(key, value)); }
80
86 void insert(const value_type& item)
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 }
97
104 bool retrieve(const KEY& key, VALUE& value)
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 }
116
118 iterator begin() const { return m_container.begin(); }
120 iterator end() const { return m_container.end(); }
121
123 size_t size() const { return m_container.size(); }
125 void clear()
126 {
127 m_container.clear();
128 m_hits = 0;
129 m_misses = 0;
130 m_overflows = 0;
131 }
132
134 void setMaxSize(size_t maxSize) { m_maxSize = maxSize; }
136 size_t getMaxSize() const { return m_maxSize; }
138 unsigned int getHits() const { return m_hits; }
140 unsigned int getMisses() const { return m_misses; }
142 unsigned int getOverflows() const { return m_overflows; }
143
144 protected:
150 void update(const iterator& item)
151 {
152 m_container.relocate(m_container.begin(), item);
153 }
154
158 size_t m_maxSize;
160 unsigned int m_hits;
162 unsigned int m_misses;
164 unsigned int m_overflows;
165 };
167}
Class implementing a generic Most Recently Used cache.
Definition: MRUCache.h:48
iterator begin() const
Return iterator to the begin of the cache.
Definition: MRUCache.h:118
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
void insert(const value_type &item)
Insert a key value pair into the cache.
Definition: MRUCache.h:86
size_t size() const
Return actual size of the cache.
Definition: MRUCache.h:123
size_t getMaxSize() const
Get maximum number of cache entries.
Definition: MRUCache.h:136
unsigned int getHits() const
Get number of cache hits since creation/last clear.
Definition: MRUCache.h:138
void insert(const KEY &key, const VALUE &value)
Insert a key value pair into the cache.
Definition: MRUCache.h:79
container_type m_container
Container for the items.
Definition: MRUCache.h:156
unsigned int getOverflows() const
Get number of overflows (dropped items) since creation/last clear.
Definition: MRUCache.h:142
unsigned int getMisses() const
Get number of cache misses since creation/last clear.
Definition: MRUCache.h:140
iterator end() const
Return iterator to the end of the cache.
Definition: MRUCache.h:120
container_type::template nth_index< 1 >::type::const_iterator hash_iterator
iterator over the hash index to the items
Definition: MRUCache.h:65
container_type::const_iterator iterator
iterator over all cached items, sorted by access: most recent used first
Definition: MRUCache.h:63
unsigned int m_hits
Number of hits.
Definition: MRUCache.h:160
void clear()
Clear cache.
Definition: MRUCache.h:125
size_t m_maxSize
Maximum size of the cache.
Definition: MRUCache.h:158
unsigned int m_misses
Number of misses.
Definition: MRUCache.h:162
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: MRUCache.h:61
bool retrieve(const KEY &key, VALUE &value)
Retrieve a value from the cache if it exists.
Definition: MRUCache.h:104
std::pair< KEY, VALUE > value_type
type of elements stored in the cache
Definition: MRUCache.h:51
void setMaxSize(size_t maxSize)
Set maximum number of cache entries.
Definition: MRUCache.h:134
unsigned int m_overflows
Number of overflows.
Definition: MRUCache.h:164
MRUCache(size_t maxSize)
Constructor setting the maximum number of cached items.
Definition: MRUCache.h:71
Abstract base class for different kinds of events.
Definition: ClusterUtils.h:24