libquentier  0.5.0
The library for rich desktop clients of Evernote service
LRUCache.hpp
1 /*
2  * Copyright 2016-2020 Dmitry Ivanov
3  *
4  * This file is part of libquentier
5  *
6  * libquentier is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU Lesser General Public License as published by
8  * the Free Software Foundation, version 3 of the License.
9  *
10  * libquentier is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  * GNU Lesser General Public License for more details.
14  *
15  * You should have received a copy of the GNU Lesser General Public License
16  * along with libquentier. If not, see <http://www.gnu.org/licenses/>.
17  */
18 
19 #ifndef LIB_QUENTIER_UTILITY_LRU_CACHE_HPP
20 #define LIB_QUENTIER_UTILITY_LRU_CACHE_HPP
21 
22 #include <quentier/utility/Macros.h>
23 
24 #include <QHash>
25 
26 #include <cstddef>
27 #include <list>
28 
29 namespace quentier {
30 
31 template<
32  class Key,
33  class Value,
34  class Allocator = std::allocator<std::pair<Key, Value>>>
35 class LRUCache
36 {
37 public:
38  LRUCache(const size_t maxSize = 100) :
39  m_container(),
40  m_currentSize(0),
41  m_maxSize(maxSize),
42  m_mapper()
43  {}
44 
45  using key_type = Key;
46  using mapped_type = Value;
47  using allocator_type = Allocator;
48  using value_type = std::pair<key_type, mapped_type>;
49  using container_type = std::list<value_type, allocator_type>;
50  using size_type = typename container_type::size_type;
51  using difference_type = typename container_type::difference_type;
52  using iterator = typename container_type::iterator;
53  using const_iterator = typename container_type::const_iterator;
54  using reverse_iterator = std::reverse_iterator<iterator>;
55  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
56 
57  using reference = value_type&;
58  using const_reference = const value_type&;
59  using pointer = typename std::allocator_traits<allocator_type>::pointer;
60 
61  using const_pointer =
62  typename std::allocator_traits<allocator_type>::const_pointer;
63 
64  iterator begin() { return m_container.begin(); }
65  const_iterator begin() const { return m_container.begin(); }
66 
67  reverse_iterator rbegin() { return m_container.rbegin(); }
68  const_reverse_iterator rbegin() const { return m_container.rbegin(); }
69 
70  iterator end() { return m_container.end(); }
71  const_iterator end() const { return m_container.end(); }
72 
73  reverse_iterator rend() { return m_container.rend(); }
74  const_reverse_iterator rend() const { return m_container.rend(); }
75 
76  bool empty() const { return m_container.empty(); }
77  size_t size() const { return m_currentSize; }
78  size_t max_size() const { return m_maxSize; }
79 
80  void clear() { m_container.clear(); m_mapper.clear(); m_currentSize = 0; }
81 
82  void put(const key_type & key, const mapped_type & value)
83  {
84  Q_UNUSED(remove(key))
85 
86  m_container.push_front(value_type(key, value));
87  m_mapper[key] = m_container.begin();
88  ++m_currentSize;
89 
90  fixupSize();
91  }
92 
93  const mapped_type * get(const key_type & key) const
94  {
95  auto mapperIt = m_mapper.find(key);
96  if (mapperIt == m_mapper.end()) {
97  return nullptr;
98  }
99 
100  auto it = mapperIt.value();
101  if (it == m_container.end()) {
102  return nullptr;
103  }
104 
105  m_container.splice(m_container.begin(), m_container, it);
106  mapperIt.value() = m_container.begin();
107  return &(mapperIt.value()->second);
108  }
109 
110  bool exists(const key_type & key)
111  {
112  auto mapperIt = m_mapper.find(key);
113  if (mapperIt == m_mapper.end()) {
114  return false;
115  }
116 
117  auto it = mapperIt.value();
118  return (it != m_container.end());
119  }
120 
121  bool remove(const key_type & key)
122  {
123  auto mapperIt = m_mapper.find(key);
124  if (mapperIt == m_mapper.end()) {
125  return false;
126  }
127 
128  auto it = mapperIt.value();
129  Q_UNUSED(m_container.erase(it))
130  Q_UNUSED(m_mapper.erase(mapperIt))
131 
132  if (m_currentSize != 0) {
133  --m_currentSize;
134  }
135 
136  return true;
137  }
138 
139  void setMaxSize(const size_t maxSize)
140  {
141  if (maxSize >= m_maxSize) {
142  m_maxSize = maxSize;
143  return;
144  }
145 
146  size_t diff = m_maxSize - maxSize;
147  for(size_t i = 0; (i < diff) && !m_container.empty(); ++i)
148  {
149  auto lastIt = m_container.end();
150  --lastIt;
151 
152  const key_type & lastElementKey = lastIt->first;
153  Q_UNUSED(m_mapper.remove(lastElementKey))
154  Q_UNUSED(m_container.erase(lastIt))
155 
156  if (m_currentSize != 0) {
157  --m_currentSize;
158  }
159  }
160  }
161 
162 private:
163  void fixupSize()
164  {
165  if (m_currentSize <= m_maxSize) {
166  return;
167  }
168 
169  if (Q_UNLIKELY(m_container.empty())) {
170  return;
171  }
172 
173  auto lastIt = m_container.end();
174  --lastIt;
175 
176  const key_type & lastElementKey = lastIt->first;
177 
178  Q_UNUSED(m_mapper.remove(lastElementKey))
179  Q_UNUSED(m_container.erase(lastIt))
180 
181  if (m_currentSize != 0) {
182  --m_currentSize;
183  }
184  }
185 
186 private:
187  mutable container_type m_container;
188  size_t m_currentSize;
189  size_t m_maxSize;
190 
191  mutable QHash<Key, iterator> m_mapper;
192 };
193 
194 } // namespace quentier
195 
196 #endif // LIB_QUENTIER_UTILITY_LRU_CACHE_HPP
Definition: LRUCache.hpp:35