libquentier 0.5.0
The library for rich desktop clients of Evernote service
Loading...
Searching...
No Matches
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
27namespace quentier {
28
29template <
30 class Key, class Value,
31 class Allocator = std::allocator<std::pair<Key, Value>>>
33{
34public:
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
193private:
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
217private:
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 LRUCache.hpp:33