1// Copyright (C) 2016 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
3
4#ifndef QCACHE_H
5#define QCACHE_H
6
7#include <QtCore/qhash.h>
8
9QT_BEGIN_NAMESPACE
10
11
12template <class Key, class T>
13class QCache
14{
15 struct Value
16 {
17 T *t = nullptr;
18 qsizetype cost = 0;
19 Value() noexcept = default;
20 Value(T *tt, qsizetype c) noexcept
21 : t(tt), cost(c)
22 {}
23 Value(Value &&other) noexcept
24 : t(other.t),
25 cost(other.cost)
26 {
27 other.t = nullptr;
28 }
29 Value &operator=(Value &&other) noexcept
30 {
31 qt_ptr_swap(t, other.t);
32 std::swap(cost, other.cost);
33 return *this;
34 }
35 ~Value() { delete t; }
36
37 private:
38 Q_DISABLE_COPY(Value)
39 };
40
41 struct Chain
42 {
43 Chain() noexcept : prev(this), next(this) { }
44 Chain *prev;
45 Chain *next;
46 };
47
48 struct Node : public Chain
49 {
50 using KeyType = Key;
51 using ValueType = Value;
52
53 Key key;
54 Value value;
55
56 Node(const Key &k, Value &&t) noexcept(std::is_nothrow_move_assignable_v<Key>)
57 : Chain(),
58 key(k),
59 value(std::move(t))
60 {
61 }
62 Node(Key &&k, Value &&t) noexcept(std::is_nothrow_move_assignable_v<Key>)
63 : Chain(),
64 key(std::move(k)),
65 value(std::move(t))
66 {
67 }
68 static void createInPlace(Node *n, const Key &k, T *o, qsizetype cost)
69 {
70 new (n) Node{ Key(k), Value(o, cost) };
71 }
72 void emplace(T *o, qsizetype cost)
73 {
74 value = Value(o, cost);
75 }
76
77 Node(Node &&other)
78 : Chain(other),
79 key(std::move(other.key)),
80 value(std::move(other.value))
81 {
82 Q_ASSERT(this->prev);
83 Q_ASSERT(this->next);
84 this->prev->next = this;
85 this->next->prev = this;
86 }
87 private:
88 Q_DISABLE_COPY(Node)
89 };
90
91 using Data = QHashPrivate::Data<Node>;
92
93 mutable Chain chain;
94 Data d;
95 qsizetype mx = 0;
96 qsizetype total = 0;
97
98 void unlink(Node *n) noexcept(std::is_nothrow_destructible_v<Node>)
99 {
100 Q_ASSERT(n->prev);
101 Q_ASSERT(n->next);
102 n->prev->next = n->next;
103 n->next->prev = n->prev;
104 total -= n->value.cost;
105 auto it = d.findBucket(n->key);
106 d.erase(it);
107 }
108 T *relink(const Key &key) const noexcept
109 {
110 if (isEmpty())
111 return nullptr;
112 Node *n = d.findNode(key);
113 if (!n)
114 return nullptr;
115
116 if (chain.next != n) {
117 Q_ASSERT(n->prev);
118 Q_ASSERT(n->next);
119 n->prev->next = n->next;
120 n->next->prev = n->prev;
121 n->next = chain.next;
122 chain.next->prev = n;
123 n->prev = &chain;
124 chain.next = n;
125 }
126 return n->value.t;
127 }
128
129 void trim(qsizetype m) noexcept(std::is_nothrow_destructible_v<Node>)
130 {
131 while (chain.prev != &chain && total > m) {
132 Node *n = static_cast<Node *>(chain.prev);
133 unlink(n);
134 }
135 }
136
137
138 Q_DISABLE_COPY(QCache)
139
140public:
141 inline explicit QCache(qsizetype maxCost = 100) noexcept
142 : mx(maxCost)
143 {
144 }
145 inline ~QCache()
146 {
147 static_assert(std::is_nothrow_destructible_v<Key>, "Types with throwing destructors are not supported in Qt containers.");
148 static_assert(std::is_nothrow_destructible_v<T>, "Types with throwing destructors are not supported in Qt containers.");
149
150 clear();
151 }
152
153 inline qsizetype maxCost() const noexcept { return mx; }
154 void setMaxCost(qsizetype m) noexcept(std::is_nothrow_destructible_v<Node>)
155 {
156 mx = m;
157 trim(m: mx);
158 }
159 inline qsizetype totalCost() const noexcept { return total; }
160
161 inline qsizetype size() const noexcept { return qsizetype(d.size); }
162 inline qsizetype count() const noexcept { return qsizetype(d.size); }
163 inline bool isEmpty() const noexcept { return !d.size; }
164 inline QList<Key> keys() const
165 {
166 QList<Key> k;
167 if (size()) {
168 k.reserve(size());
169 for (auto it = d.begin(); it != d.end(); ++it)
170 k << it.node()->key;
171 }
172 Q_ASSERT(k.size() == size());
173 return k;
174 }
175
176 void clear() noexcept(std::is_nothrow_destructible_v<Node>)
177 {
178 d.clear();
179 total = 0;
180 chain.next = &chain;
181 chain.prev = &chain;
182 }
183
184 bool insert(const Key &key, T *object, qsizetype cost = 1)
185 {
186 if (cost > mx) {
187 remove(key);
188 delete object;
189 return false;
190 }
191 trim(m: mx - cost);
192 auto result = d.findOrInsert(key);
193 Node *n = result.it.node();
194 if (result.initialized) {
195 auto prevCost = n->value.cost;
196 result.it.node()->emplace(object, cost);
197 cost -= prevCost;
198 relink(key);
199 } else {
200 Node::createInPlace(n, key, object, cost);
201 n->prev = &chain;
202 n->next = chain.next;
203 chain.next->prev = n;
204 chain.next = n;
205 }
206 total += cost;
207 return true;
208 }
209 T *object(const Key &key) const noexcept
210 {
211 return relink(key);
212 }
213 T *operator[](const Key &key) const noexcept
214 {
215 return relink(key);
216 }
217 inline bool contains(const Key &key) const noexcept
218 {
219 return !isEmpty() && d.findNode(key) != nullptr;
220 }
221
222 bool remove(const Key &key) noexcept(std::is_nothrow_destructible_v<Node>)
223 {
224 if (isEmpty())
225 return false;
226 Node *n = d.findNode(key);
227 if (!n) {
228 return false;
229 } else {
230 unlink(n);
231 return true;
232 }
233 }
234
235 T *take(const Key &key) noexcept(std::is_nothrow_destructible_v<Key>)
236 {
237 if (isEmpty())
238 return nullptr;
239 Node *n = d.findNode(key);
240 if (!n)
241 return nullptr;
242
243 T *t = n->value.t;
244 n->value.t = nullptr;
245 unlink(n);
246 return t;
247 }
248
249};
250
251QT_END_NAMESPACE
252
253#endif // QCACHE_H
254

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