1/****************************************************************************
2**
3** Copyright (C) 2016 The Qt Company Ltd.
4** Contact: https://www.qt.io/licensing/
5**
6** This file is part of the QtCore module of the Qt Toolkit.
7**
8** $QT_BEGIN_LICENSE:LGPL$
9** Commercial License Usage
10** Licensees holding valid commercial Qt licenses may use this file in
11** accordance with the commercial license agreement provided with the
12** Software or, alternatively, in accordance with the terms contained in
13** a written agreement between you and The Qt Company. For licensing terms
14** and conditions see https://www.qt.io/terms-conditions. For further
15** information use the contact form at https://www.qt.io/contact-us.
16**
17** GNU Lesser General Public License Usage
18** Alternatively, this file may be used under the terms of the GNU Lesser
19** General Public License version 3 as published by the Free Software
20** Foundation and appearing in the file LICENSE.LGPL3 included in the
21** packaging of this file. Please review the following information to
22** ensure the GNU Lesser General Public License version 3 requirements
23** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24**
25** GNU General Public License Usage
26** Alternatively, this file may be used under the terms of the GNU
27** General Public License version 2.0 or (at your option) the GNU General
28** Public license version 3 or any later version approved by the KDE Free
29** Qt Foundation. The licenses are as published by the Free Software
30** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31** included in the packaging of this file. Please review the following
32** information to ensure the GNU General Public License requirements will
33** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34** https://www.gnu.org/licenses/gpl-3.0.html.
35**
36** $QT_END_LICENSE$
37**
38****************************************************************************/
39
40#ifndef QCACHE_H
41#define QCACHE_H
42
43#include <QtCore/qhash.h>
44
45QT_BEGIN_NAMESPACE
46
47
48template <class Key, class T>
49class QCache
50{
51 struct Value
52 {
53 T *t = nullptr;
54 qsizetype cost = 0;
55 Value() noexcept = default;
56 Value(T *tt, qsizetype c) noexcept
57 : t(tt), cost(c)
58 {}
59 Value(Value &&other) noexcept
60 : t(other.t),
61 cost(other.cost)
62 {
63 other.t = nullptr;
64 }
65 Value &operator=(Value &&other) noexcept
66 {
67 qSwap(t, other.t);
68 qSwap(cost, other.cost);
69 return *this;
70 }
71 ~Value() { delete t; }
72
73 private:
74 Q_DISABLE_COPY(Value)
75 };
76
77 struct Chain
78 {
79 Chain() noexcept : prev(this), next(this) { }
80 Chain *prev;
81 Chain *next;
82 };
83
84 struct Node : public Chain
85 {
86 using KeyType = Key;
87 using ValueType = Value;
88
89 Key key;
90 Value value;
91
92 Node(const Key &k, Value &&t) noexcept(std::is_nothrow_move_assignable_v<Key>)
93 : Chain(),
94 key(k),
95 value(std::move(t))
96 {
97 }
98 Node(Key &&k, Value &&t) noexcept(std::is_nothrow_move_assignable_v<Key>)
99 : Chain(),
100 key(std::move(k)),
101 value(std::move(t))
102 {
103 }
104 static void createInPlace(Node *n, const Key &k, T *o, qsizetype cost)
105 {
106 new (n) Node{ Key(k), Value(o, cost) };
107 }
108 void emplace(T *o, qsizetype cost)
109 {
110 value = Value(o, cost);
111 }
112 static Node create(const Key &k, Value &&t) noexcept(std::is_nothrow_move_assignable_v<Key> && std::is_nothrow_move_assignable_v<T>)
113 {
114 return Node(k, std::move(t));
115 }
116 void replace(const Value &t) noexcept(std::is_nothrow_assignable_v<T, T>)
117 {
118 value = t;
119 }
120 void replace(Value &&t) noexcept(std::is_nothrow_move_assignable_v<T>)
121 {
122 value = std::move(t);
123 }
124 Value takeValue() noexcept(std::is_nothrow_move_constructible_v<T>)
125 {
126 return std::move(value);
127 }
128 bool valuesEqual(const Node *other) const { return value == other->value; }
129
130 Node(Node &&other)
131 : Chain(other),
132 key(std::move(other.key)),
133 value(std::move(other.value))
134 {
135 Q_ASSERT(this->prev);
136 Q_ASSERT(this->next);
137 this->prev->next = this;
138 this->next->prev = this;
139 }
140 private:
141 Q_DISABLE_COPY(Node)
142 };
143
144 using Data = QHashPrivate::Data<Node>;
145
146 mutable Chain chain;
147 Data d;
148 qsizetype mx = 0;
149 qsizetype total = 0;
150
151 void unlink(Node *n) noexcept(std::is_nothrow_destructible_v<Node>)
152 {
153 Q_ASSERT(n->prev);
154 Q_ASSERT(n->next);
155 n->prev->next = n->next;
156 n->next->prev = n->prev;
157 total -= n->value.cost;
158 auto it = d.find(n->key);
159 d.erase(it);
160 }
161 T *relink(const Key &key) const noexcept
162 {
163 Node *n = d.findNode(key);
164 if (!n)
165 return nullptr;
166
167 if (chain.next != n) {
168 Q_ASSERT(n->prev);
169 Q_ASSERT(n->next);
170 n->prev->next = n->next;
171 n->next->prev = n->prev;
172 n->next = chain.next;
173 chain.next->prev = n;
174 n->prev = &chain;
175 chain.next = n;
176 }
177 return n->value.t;
178 }
179
180 void trim(qsizetype m) noexcept(std::is_nothrow_destructible_v<Node>)
181 {
182 Chain *n = chain.prev;
183 while (n != &chain && total > m) {
184 Node *u = static_cast<Node *>(n);
185 n = n->prev;
186 unlink(u);
187 }
188 }
189
190
191 Q_DISABLE_COPY(QCache)
192
193public:
194 inline explicit QCache(qsizetype maxCost = 100) noexcept
195 : mx(maxCost)
196 {}
197 inline ~QCache() { clear(); }
198
199 inline qsizetype maxCost() const noexcept { return mx; }
200 void setMaxCost(qsizetype m) noexcept(std::is_nothrow_destructible_v<Node>)
201 {
202 mx = m;
203 trim(mx);
204 }
205 inline qsizetype totalCost() const noexcept { return total; }
206
207 inline qsizetype size() const noexcept { return qsizetype(d.size); }
208 inline qsizetype count() const noexcept { return qsizetype(d.size); }
209 inline bool isEmpty() const noexcept { return !d.size; }
210 inline QList<Key> keys() const
211 {
212 QList<Key> k;
213 if (size()) {
214 k.reserve(size());
215 for (auto it = d.begin(); it != d.end(); ++it)
216 k << it.node()->key;
217 }
218 Q_ASSERT(k.size() == size());
219 return k;
220 }
221
222 void clear() noexcept(std::is_nothrow_destructible_v<Node>)
223 {
224 d.clear();
225 total = 0;
226 chain.next = &chain;
227 chain.prev = &chain;
228 }
229
230 bool insert(const Key &key, T *object, qsizetype cost = 1)
231 {
232 remove(key);
233
234 if (cost > mx) {
235 delete object;
236 return false;
237 }
238 trim(mx - cost);
239 auto result = d.findOrInsert(key);
240 Node *n = result.it.node();
241 if (result.initialized) {
242 cost -= n->value.cost;
243 result.it.node()->emplace(object, cost);
244 } else {
245 Node::createInPlace(n, key, object, cost);
246 }
247 total += cost;
248 n->prev = &chain;
249 n->next = chain.next;
250 chain.next->prev = n;
251 chain.next = n;
252 return true;
253 }
254 T *object(const Key &key) const noexcept
255 {
256 return relink(key);
257 }
258 T *operator[](const Key &key) const noexcept
259 {
260 return relink(key);
261 }
262 inline bool contains(const Key &key) const noexcept
263 {
264 return d.findNode(key) != nullptr;
265 }
266
267 bool remove(const Key &key) noexcept(std::is_nothrow_destructible_v<Node>)
268 {
269 Node *n = d.findNode(key);
270 if (!n) {
271 return false;
272 } else {
273 unlink(n);
274 return true;
275 }
276 }
277
278 T *take(const Key &key) noexcept(std::is_nothrow_destructible_v<Key>)
279 {
280 Node *n = d.findNode(key);
281 if (!n)
282 return nullptr;
283
284 T *t = n->value.t;
285 n->value.t = nullptr;
286 unlink(n);
287 return t;
288 }
289
290};
291
292QT_END_NAMESPACE
293
294#endif // QCACHE_H
295