1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
|
/*****************************************************************************
*
* Copyright (C) 1997-2020 by Dimitri van Heesch.
*
* Permission to use, copy, modify, and distribute this software and its
* documentation under the terms of the GNU General Public License is hereby
* granted. No representations are made about the suitability of this software
* for any purpose. It is provided "as is" without express or implied warranty.
* See the GNU General Public License for more details.
*
* Documents produced by Doxygen are derivative works derived from the
* input used in their production; they are not affected by this license.
*
*/
#ifndef CACHE_H
#define CACHE_H
#include <list>
#include <unordered_map>
#include <mutex>
#include <ctype.h>
/*! Fixed size cache for value type V using keys of type K.
*
* When the maximum capacity has reached, the least recently used value is removed from the cache
* (LRU strategy).
*/
template<typename K,typename V>
class Cache
{
public:
using kv_pair = std::pair<K,V>;
using iterator = typename std::list<kv_pair>::iterator;
using const_iterator = typename std::list<kv_pair>::const_iterator;
//! creates a cache that can hold \a capacity elements
Cache(size_t capacity) : m_capacity(capacity)
{
}
//! Inserts \a value under \a key in the cache
V *insert(const K &key,V &&value)
{
// remove item if it already exists
remove(key);
// store new item
m_cacheItemList.push_front(kv_pair(key,std::move(value)));
V *result = &m_cacheItemList.front().second;
m_cacheItemMap[key] = m_cacheItemList.begin();
// remove least recently used item if cache is full
resize();
return result;
}
//! Inserts \a value under \a key in the cache
V *insert(const K &key,const V &value)
{
// remove item if it already exists
remove(key);
// store new item
m_cacheItemList.push_front(kv_pair(key,value));
V *result = &m_cacheItemList.front().second;
m_cacheItemMap[key] = m_cacheItemList.begin();
// remove least recently used item if cache is full
resize();
return result;
}
//! Removes entry \a key from the cache.
//! \note this invalidates any iterators
void remove(const K &key)
{
// remove item if it already exists
auto it = m_cacheItemMap.find(key);
if (it != m_cacheItemMap.end())
{
m_cacheItemList.erase(it->second);
m_cacheItemMap.erase(it);
}
}
//! Finds a value in the cache given the corresponding \a key.
//! @returns a pointer to the value or nullptr if the key is not found in the cache
//! @note The hit and miss counters are updated, see hits() and misses().
V *find(const K &key)
{
auto it = m_cacheItemMap.find(key);
if (it != m_cacheItemMap.end())
{
// move the item to the front of the list
m_cacheItemList.splice(m_cacheItemList.begin(),
m_cacheItemList,
it->second);
m_hits++;
// return the value
return &it->second->second;
}
else
{
m_misses++;
}
return nullptr;
}
//! Returns the number of values stored in the cache.
size_t size() const
{
return m_cacheItemMap.size();
}
//! Returns the maximum number of values that can be stored in the cache.
size_t capacity() const
{
return m_capacity;
}
//! Returns how many of the find() calls did find a value in the cache.
uint64_t hits() const
{
return m_hits;
}
//! Returns how many of the find() calls did not found a value in the cache.
uint64_t misses() const
{
return m_misses;
}
//! Clears all values in the cache.
void clear()
{
m_cacheItemMap.clear();
m_cacheItemList.clear();
}
iterator begin() { return m_cacheItemList.begin(); }
iterator end() { return m_cacheItemList.end(); }
const_iterator begin() const { return m_cacheItemList.cbegin(); }
const_iterator end() const { return m_cacheItemList.cend(); }
private:
void resize()
{
if (m_cacheItemMap.size() > m_capacity)
{
auto last_it = m_cacheItemList.end();
--last_it;
m_cacheItemMap.erase(last_it->first);
m_cacheItemList.pop_back();
}
}
size_t m_capacity;
// list of items in the cache, sorted by most to least recently used.
std::list<kv_pair> m_cacheItemList;
// mapping for each key to a place in the list where item is found
std::unordered_map<K,iterator> m_cacheItemMap;
uint64_t m_hits=0;
uint64_t m_misses=0;
};
#endif
|
