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