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 <QHash>
23 
24 #include <cstddef>
25 #include <list>
26 
27 namespace quentier {
28 
29 template <
30  class Key, class Value,
31  class Allocator = std::allocator<std::pair<Key, Value>>>
32 class LRUCache
33 {
34 public:
35  LRUCache(const size_t maxSize = 100) :
36  m_container(), m_currentSize(0), m_maxSize(maxSize), m_mapper()
37  {}
38 
39  using key_type = Key;
40  using mapped_type = Value;
41  using allocator_type = Allocator;
42  using value_type = std::pair<key_type, mapped_type>;
43  using container_type = std::list<value_type, allocator_type>;
44  using size_type = typename container_type::size_type;
45  using difference_type = typename container_type::difference_type;
46  using iterator = typename container_type::iterator;
47  using const_iterator = typename container_type::const_iterator;
48  using reverse_iterator = std::reverse_iterator<iterator>;
49  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
50 
51  using reference = value_type &;
52  using const_reference = const value_type &;
53  using pointer = typename std::allocator_traits<allocator_type>::pointer;
54 
55  using const_pointer =
56  typename std::allocator_traits<allocator_type>::const_pointer;
57 
58  iterator begin()
59  {
60  return m_container.begin();
61  }
62  const_iterator begin() const
63  {
64  return m_container.begin();
65  }
66 
67  reverse_iterator rbegin()
68  {
69  return m_container.rbegin();
70  }
71  const_reverse_iterator rbegin() const
72  {
73  return m_container.rbegin();
74  }
75 
76  iterator end()
77  {
78  return m_container.end();
79  }
80  const_iterator end() const
81  {
82  return m_container.end();
83  }
84 
85  reverse_iterator rend()
86  {
87  return m_container.rend();
88  }
89  const_reverse_iterator rend() const
90  {
91  return m_container.rend();
92  }
93 
94  bool empty() const
95  {
96  return m_container.empty();
97  }
98  size_t size() const
99  {
100  return m_currentSize;
101  }
102  size_t max_size() const
103  {
104  return m_maxSize;
105  }
106 
107  void clear()
108  {
109  m_container.clear();
110  m_mapper.clear();
111  m_currentSize = 0;
112  }
113 
114  void put(const key_type & key, const mapped_type & value)
115  {
116  Q_UNUSED(remove(key))
117 
118  m_container.push_front(value_type(key, value));
119  m_mapper[key] = m_container.begin();
120  ++m_currentSize;
121 
122  fixupSize();
123  }
124 
125  const mapped_type * get(const key_type & key) const
126  {
127  auto mapperIt = m_mapper.find(key);
128  if (mapperIt == m_mapper.end()) {
129  return nullptr;
130  }
131 
132  auto it = mapperIt.value();
133  if (it == m_container.end()) {
134  return nullptr;
135  }
136 
137  m_container.splice(m_container.begin(), m_container, it);
138  mapperIt.value() = m_container.begin();
139  return &(mapperIt.value()->second);
140  }
141 
142  bool exists(const key_type & key)
143  {
144  auto mapperIt = m_mapper.find(key);
145  if (mapperIt == m_mapper.end()) {
146  return false;
147  }
148 
149  auto it = mapperIt.value();
150  return (it != m_container.end());
151  }
152 
153  bool remove(const key_type & key)
154  {
155  auto mapperIt = m_mapper.find(key);
156  if (mapperIt == m_mapper.end()) {
157  return false;
158  }
159 
160  auto it = mapperIt.value();
161  Q_UNUSED(m_container.erase(it))
162  Q_UNUSED(m_mapper.erase(mapperIt))
163 
164  if (m_currentSize != 0) {
165  --m_currentSize;
166  }
167 
168  return true;
169  }
170 
171  void setMaxSize(const size_t maxSize)
172  {
173  if (maxSize >= m_maxSize) {
174  m_maxSize = maxSize;
175  return;
176  }
177 
178  size_t diff = m_maxSize - maxSize;
179  for (size_t i = 0; (i < diff) && !m_container.empty(); ++i) {
180  auto lastIt = m_container.end();
181  --lastIt;
182 
183  const key_type & lastElementKey = lastIt->first;
184  Q_UNUSED(m_mapper.remove(lastElementKey))
185  Q_UNUSED(m_container.erase(lastIt))
186 
187  if (m_currentSize != 0) {
188  --m_currentSize;
189  }
190  }
191  }
192 
193 private:
194  void fixupSize()
195  {
196  if (m_currentSize <= m_maxSize) {
197  return;
198  }
199 
200  if (Q_UNLIKELY(m_container.empty())) {
201  return;
202  }
203 
204  auto lastIt = m_container.end();
205  --lastIt;
206 
207  const key_type & lastElementKey = lastIt->first;
208 
209  Q_UNUSED(m_mapper.remove(lastElementKey))
210  Q_UNUSED(m_container.erase(lastIt))
211 
212  if (m_currentSize != 0) {
213  --m_currentSize;
214  }
215  }
216 
217 private:
218  mutable container_type m_container;
219  size_t m_currentSize;
220  size_t m_maxSize;
221 
222  mutable QHash<Key, iterator> m_mapper;
223 };
224 
225 } // namespace quentier
226 
227 #endif // LIB_QUENTIER_UTILITY_LRU_CACHE_HPP
Definition: DecryptedTextManager.h:26
Definition: LRUCache.hpp:32