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 }
198 inline ~QCache()
199 {
200 static_assert(std::is_nothrow_destructible_v<Key>, "Types with throwing destructors are not supported in Qt containers.");
201 static_assert(std::is_nothrow_destructible_v<T>, "Types with throwing destructors are not supported in Qt containers.");
202
203 clear();
204 }
205
206 inline qsizetype maxCost() const noexcept { return mx; }
207 void setMaxCost(qsizetype m) noexcept(std::is_nothrow_destructible_v<Node>)
208 {
209 mx = m;
210 trim(mx);
211 }
212 inline qsizetype totalCost() const noexcept { return total; }
213
214 inline qsizetype size() const noexcept { return qsizetype(d.size); }
215 inline qsizetype count() const noexcept { return qsizetype(d.size); }
216 inline bool isEmpty() const noexcept { return !d.size; }
217 inline QList<Key> keys() const
218 {
219 QList<Key> k;
220 if (size()) {
221 k.reserve(size());
222 for (auto it = d.begin(); it != d.end(); ++it)
223 k << it.node()->key;
224 }
225 Q_ASSERT(k.size() == size());
226 return k;
227 }
228
229 void clear() noexcept(std::is_nothrow_destructible_v<Node>)
230 {
231 d.clear();
232 total = 0;
233 chain.next = &chain;
234 chain.prev = &chain;
235 }
236
237 bool insert(const Key &key, T *object, qsizetype cost = 1)
238 {
239 if (cost > mx) {
240 remove(key);
241 delete object;
242 return false;
243 }
244 trim(mx - cost);
245 auto result = d.findOrInsert(key);
246 Node *n = result.it.node();
247 if (result.initialized) {
248 auto prevCost = n->value.cost;
249 result.it.node()->emplace(object, cost);
250 cost -= prevCost;
251 relink(key);
252 } else {
253 Node::createInPlace(n, key, object, cost);
254 n->prev = &chain;
255 n->next = chain.next;
256 chain.next->prev = n;
257 chain.next = n;
258 }
259 total += cost;
260 return true;
261 }
262 T *object(const Key &key) const noexcept
263 {
264 return relink(key);
265 }
266 T *operator[](const Key &key) const noexcept
267 {
268 return relink(key);
269 }
270 inline bool contains(const Key &key) const noexcept
271 {
272 return d.findNode(key) != nullptr;
273 }
274
275 bool remove(const Key &key) noexcept(std::is_nothrow_destructible_v<Node>)
276 {
277 Node *n = d.findNode(key);
278 if (!n) {
279 return false;
280 } else {
281 unlink(n);
282 return true;
283 }
284 }
285
286 T *take(const Key &key) noexcept(std::is_nothrow_destructible_v<Key>)
287 {
288 Node *n = d.findNode(key);
289 if (!n)
290 return nullptr;
291
292 T *t = n->value.t;
293 n->value.t = nullptr;
294 unlink(n);
295 return t;
296 }
297
298};
299
300QT_END_NAMESPACE
301
302#endif // QCACHE_H
303

source code of qtbase/src/corelib/tools/qcache.h