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