1 | /**************************************************************************** |
2 | ** |
3 | ** Copyright (C) 2015 The Qt Company Ltd. |
4 | ** Contact: http://www.qt.io/licensing/ |
5 | ** |
6 | ** This file is part of the QtCore module of the Qt Toolkit. |
7 | ** |
8 | ** $QT_BEGIN_LICENSE:LGPL3$ |
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 http://www.qt.io/terms-conditions. For further |
15 | ** information use the contact form at http://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.LGPLv3 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.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 later as published by the Free |
28 | ** Software Foundation and appearing in the file LICENSE.GPL included in |
29 | ** the packaging of this file. Please review the following information to |
30 | ** ensure the GNU General Public License version 2.0 requirements will be |
31 | ** met: http://www.gnu.org/licenses/gpl-2.0.html. |
32 | ** |
33 | ** $QT_END_LICENSE$ |
34 | ** |
35 | ****************************************************************************/ |
36 | |
37 | #ifndef QCACHE3Q_H |
38 | #define QCACHE3Q_H |
39 | |
40 | // |
41 | // W A R N I N G |
42 | // ------------- |
43 | // |
44 | // This file is not part of the Qt API. It exists purely as an |
45 | // implementation detail. This header file may change from version to |
46 | // version without notice, or even be removed. |
47 | // |
48 | // We mean it. |
49 | |
50 | #include <QtCore/qlinkedlist.h> |
51 | #include <QtCore/qhash.h> |
52 | #include <QtCore/qcache.h> |
53 | #include <QtCore/qsharedpointer.h> |
54 | #include <QDebug> |
55 | |
56 | QT_BEGIN_NAMESPACE |
57 | |
58 | template <class Key, class T> |
59 | class QCache3QDefaultEvictionPolicy |
60 | { |
61 | protected: |
62 | /* called just before a key/value pair is about to be _evicted_ */ |
63 | void aboutToBeEvicted(const Key &key, QSharedPointer<T> obj); |
64 | /* called just before a key/value pair is about to be removed, by |
65 | * clear(), remove() or by the destructor (which calls clear) */ |
66 | void aboutToBeRemoved(const Key &key, QSharedPointer<T> obj); |
67 | }; |
68 | |
69 | template <class Key, class T> |
70 | void QCache3QDefaultEvictionPolicy<Key,T>::aboutToBeEvicted(const Key &key, QSharedPointer<T> obj) |
71 | { |
72 | Q_UNUSED(key); |
73 | Q_UNUSED(obj); |
74 | } |
75 | |
76 | template <class Key, class T> |
77 | void QCache3QDefaultEvictionPolicy<Key,T>::aboutToBeRemoved(const Key &key, QSharedPointer<T> obj) |
78 | { |
79 | Q_UNUSED(key); |
80 | Q_UNUSED(obj); |
81 | } |
82 | |
83 | /* |
84 | * QCache3Q |
85 | * |
86 | * A cache template class for managing QSharedPointers to objects with an |
87 | * associated key. It's a lot like QCache, but uses an alternative algorithm |
88 | * '3Q' -- which is the '2Q' algorithm plus an extra queue for previously popular |
89 | * but evicted nodes, and a 'ghost' list of recent evictions to make a better |
90 | * placement choice if they are requested again. |
91 | * |
92 | * New nodes enter the cache on the "newbies" queue, which is evicted LRA |
93 | * (least-recently-added). If a newbie is popular enough (it has been requested |
94 | * more than promoteAt times), it will be promoted to a "regular". Regulars |
95 | * are evicted LRU (least-recently-used). If a regular is under consideration |
96 | * for eviction, its popularity is compared to the mean popularity of the whole |
97 | * regulars queue. If it is greater, it is instead moved to the "hobos" queue. |
98 | * The "hobos" queue is also evicted LRU, but has a maximum size constraint |
99 | * so eviction from it is less likely than from the regulars. |
100 | * |
101 | * Tweakables: |
102 | * * maxCost = maximum total cost for the whole cache |
103 | * * minRecent = minimum size that q1 ("newbies") has to be before eviction |
104 | * from it takes place |
105 | * * maxOldPopular = maximum size that q3 ("hobos") can reach before eviction |
106 | * from it takes place |
107 | * * promoteAt = minimum popularity necessary to promote a node from |
108 | * "newbie" to "regular" |
109 | */ |
110 | template <class Key, class T, class EvPolicy = QCache3QDefaultEvictionPolicy<Key,T> > |
111 | class QCache3Q : public EvPolicy |
112 | { |
113 | private: |
114 | class Queue; |
115 | class Node |
116 | { |
117 | public: |
118 | inline explicit Node() : q(0), n(0), p(0), pop(0), cost(0) {} |
119 | |
120 | Queue *q; |
121 | Node *n; |
122 | Node *p; |
123 | Key k; |
124 | QSharedPointer<T> v; |
125 | quint64 pop; // popularity, incremented each ping |
126 | int cost; |
127 | }; |
128 | |
129 | class Queue |
130 | { |
131 | public: |
132 | inline explicit Queue() : f(0), l(0), cost(0), pop(0), size(0) {} |
133 | |
134 | Node *f; |
135 | Node *l; |
136 | int cost; // total cost of nodes on the queue |
137 | quint64 pop; // sum of popularity values on the queue |
138 | int size; // size of the queue |
139 | }; |
140 | |
141 | Queue *q1_; // "newbies": seen only once, evicted LRA (least-recently-added) |
142 | Queue *q2_; // regular nodes, promoted from newbies, evicted LRU |
143 | Queue *q3_; // "hobos": evicted from q2 but were very popular (above mean) |
144 | Queue *q1_evicted_; // ghosts of recently evicted newbies and regulars |
145 | QHash<Key, Node *> lookup_; |
146 | |
147 | public: |
148 | explicit QCache3Q(int maxCost = 0, int minRecent = -1, int maxOldPopular = -1); |
149 | inline ~QCache3Q() { clear(); delete q1_; delete q2_; delete q3_; delete q1_evicted_; } |
150 | |
151 | inline int maxCost() const { return maxCost_; } |
152 | void setMaxCost(int maxCost, int minRecent = -1, int maxOldPopular = -1); |
153 | |
154 | inline int promoteAt() const { return promote_; } |
155 | inline void setPromoteAt(int p) { promote_ = p; } |
156 | |
157 | inline int totalCost() const { return q1_->cost + q2_->cost + q3_->cost; } |
158 | |
159 | void clear(); |
160 | bool insert(const Key &key, QSharedPointer<T> object, int cost = 1); |
161 | QSharedPointer<T> object(const Key &key) const; |
162 | QSharedPointer<T> operator[](const Key &key) const; |
163 | |
164 | void remove(const Key &key, bool force = false); |
165 | QList<Key> keys() const; |
166 | void printStats(); |
167 | |
168 | // Copy data directly into a queue. Designed for single use after construction |
169 | void deserializeQueue(int queueNumber, const QList<Key> &keys, |
170 | const QList<QSharedPointer<T> > &values, const QList<int> &costs); |
171 | // Copy data from specific queue into list |
172 | void serializeQueue(int queueNumber, QList<QSharedPointer<T> > &buffer); |
173 | |
174 | private: |
175 | int maxCost_, minRecent_, maxOldPopular_; |
176 | int hitCount_, missCount_, promote_; |
177 | |
178 | void rebalance(); |
179 | void unlink(Node *n); |
180 | void link_front(Node *n, Queue *q); |
181 | |
182 | private: |
183 | // make these private so they can't be used |
184 | inline QCache3Q(const QCache3Q<Key,T,EvPolicy> &) {} |
185 | inline QCache3Q<Key,T,EvPolicy> &operator=(const QCache3Q<Key,T,EvPolicy> &) {} |
186 | }; |
187 | |
188 | template <class Key, class T, class EvPolicy> |
189 | void QCache3Q<Key,T,EvPolicy>::printStats() |
190 | { |
191 | qDebug("\n=== cache %p ===" , this); |
192 | qDebug(msg: "hits: %d (%.2f%%)\tmisses: %d\tfill: %.2f%%" , hitCount_, |
193 | 100.0 * float(hitCount_) / (float(hitCount_ + missCount_)), |
194 | missCount_, |
195 | 100.0 * float(totalCost()) / float(maxCost())); |
196 | qDebug("q1g: size=%d, pop=%llu" , q1_evicted_->size, q1_evicted_->pop); |
197 | qDebug("q1: cost=%d, size=%d, pop=%llu" , q1_->cost, q1_->size, q1_->pop); |
198 | qDebug("q2: cost=%d, size=%d, pop=%llu" , q2_->cost, q2_->size, q2_->pop); |
199 | qDebug("q3: cost=%d, size=%d, pop=%llu" , q3_->cost, q3_->size, q3_->pop); |
200 | } |
201 | |
202 | template <class Key, class T, class EvPolicy> |
203 | QCache3Q<Key,T,EvPolicy>::QCache3Q(int maxCost, int minRecent, int maxOldPopular) |
204 | : q1_(new Queue), q2_(new Queue), q3_(new Queue), q1_evicted_(new Queue), |
205 | maxCost_(maxCost), minRecent_(minRecent), maxOldPopular_(maxOldPopular), |
206 | hitCount_(0), missCount_(0), promote_(0) |
207 | { |
208 | if (minRecent_ < 0) |
209 | minRecent_ = maxCost_ / 3; |
210 | if (maxOldPopular_ < 0) |
211 | maxOldPopular_ = maxCost_ / 5; |
212 | } |
213 | |
214 | template <class Key, class T, class EvPolicy> |
215 | void QCache3Q<Key,T,EvPolicy>::serializeQueue(int queueNumber, QList<QSharedPointer<T> > &buffer) |
216 | { |
217 | Q_ASSERT(queueNumber >= 1 && queueNumber <= 4); |
218 | Queue *queue = queueNumber == 1 ? q1_ : |
219 | queueNumber == 2 ? q2_ : |
220 | queueNumber == 3 ? q3_ : |
221 | q1_evicted_; |
222 | for (Node *node = queue->f; node; node = node->n) |
223 | buffer.append(node->v); |
224 | } |
225 | |
226 | template <class Key, class T, class EvPolicy> |
227 | void QCache3Q<Key,T,EvPolicy>::deserializeQueue(int queueNumber, const QList<Key> &keys, |
228 | const QList<QSharedPointer<T> > &values, const QList<int> &costs) |
229 | { |
230 | Q_ASSERT(queueNumber >= 1 && queueNumber <= 4); |
231 | int bufferSize = keys.size(); |
232 | if (bufferSize == 0) |
233 | return; |
234 | clear(); |
235 | Queue *queue = queueNumber == 1 ? q1_ : |
236 | queueNumber == 2 ? q2_ : |
237 | queueNumber == 3 ? q3_ : |
238 | q1_evicted_; |
239 | for (int i = 0; i<bufferSize; ++i) { |
240 | Node *node = new Node; |
241 | node->v = values[i]; |
242 | node->k = keys[i]; |
243 | node->cost = costs[i]; |
244 | link_front(n: node, q: queue); |
245 | lookup_[keys[i]] = node; |
246 | } |
247 | } |
248 | |
249 | |
250 | template <class Key, class T, class EvPolicy> |
251 | inline void QCache3Q<Key,T,EvPolicy>::setMaxCost(int maxCost, int minRecent, int maxOldPopular) |
252 | { |
253 | maxCost_ = maxCost; |
254 | minRecent_ = minRecent; |
255 | maxOldPopular_ = maxOldPopular; |
256 | if (minRecent_ < 0) |
257 | minRecent_ = maxCost_ / 3; |
258 | if (maxOldPopular_ < 0) |
259 | maxOldPopular_ = maxCost_ / 5; |
260 | rebalance(); |
261 | } |
262 | |
263 | template <class Key, class T, class EvPolicy> |
264 | bool QCache3Q<Key,T,EvPolicy>::insert(const Key &key, QSharedPointer<T> object, int cost) |
265 | { |
266 | if (cost > maxCost_) { |
267 | return false; |
268 | } |
269 | |
270 | if (lookup_.contains(key)) { |
271 | Node *n = lookup_[key]; |
272 | n->v = object; |
273 | n->q->cost -= n->cost; |
274 | n->cost = cost; |
275 | n->q->cost += cost; |
276 | |
277 | if (n->q == q1_evicted_) { |
278 | if (n->pop > (uint)promote_) { |
279 | unlink(n); |
280 | link_front(n, q: q2_); |
281 | rebalance(); |
282 | } |
283 | } else if (n->q != q1_) { |
284 | Queue *q = n->q; |
285 | unlink(n); |
286 | link_front(n, q); |
287 | rebalance(); |
288 | } |
289 | |
290 | return true; |
291 | } |
292 | |
293 | Node *n = new Node; |
294 | n->v = object; |
295 | n->k = key; |
296 | n->cost = cost; |
297 | link_front(n, q: q1_); |
298 | lookup_[key] = n; |
299 | |
300 | rebalance(); |
301 | |
302 | return true; |
303 | } |
304 | |
305 | template <class Key, class T, class EvPolicy> |
306 | void QCache3Q<Key,T,EvPolicy>::clear() |
307 | { |
308 | while (q1_evicted_->f) { |
309 | Node *n = q1_evicted_->f; |
310 | unlink(n); |
311 | delete n; |
312 | } |
313 | |
314 | while (q1_->f) { |
315 | Node *n = q1_->f; |
316 | unlink(n); |
317 | EvPolicy::aboutToBeRemoved(n->k, n->v); |
318 | delete n; |
319 | } |
320 | |
321 | while (q2_->f) { |
322 | Node *n = q2_->f; |
323 | unlink(n); |
324 | EvPolicy::aboutToBeRemoved(n->k, n->v); |
325 | delete n; |
326 | } |
327 | |
328 | while (q3_->f) { |
329 | Node *n = q3_->f; |
330 | unlink(n); |
331 | EvPolicy::aboutToBeRemoved(n->k, n->v); |
332 | delete n; |
333 | } |
334 | |
335 | lookup_.clear(); |
336 | } |
337 | |
338 | template <class Key, class T, class EvPolicy> |
339 | void QCache3Q<Key,T,EvPolicy>::unlink(Node *n) |
340 | { |
341 | if (n->n) |
342 | n->n->p = n->p; |
343 | if (n->p) |
344 | n->p->n = n->n; |
345 | if (n->q->f == n) |
346 | n->q->f = n->n; |
347 | if (n->q->l == n) |
348 | n->q->l = n->p; |
349 | n->n = 0; |
350 | n->p = 0; |
351 | n->q->pop -= n->pop; |
352 | n->q->cost -= n->cost; |
353 | n->q->size--; |
354 | n->q = 0; |
355 | } |
356 | |
357 | template <class Key, class T, class EvPolicy> |
358 | void QCache3Q<Key,T,EvPolicy>::link_front(Node *n, Queue *q) |
359 | { |
360 | n->n = q->f; |
361 | n->p = 0; |
362 | n->q = q; |
363 | if (q->f) |
364 | q->f->p = n; |
365 | q->f = n; |
366 | if (!q->l) |
367 | q->l = n; |
368 | |
369 | q->pop += n->pop; |
370 | q->cost += n->cost; |
371 | q->size++; |
372 | } |
373 | |
374 | template <class Key, class T, class EvPolicy> |
375 | void QCache3Q<Key,T,EvPolicy>::rebalance() |
376 | { |
377 | while (q1_evicted_->size > (q1_->size + q2_->size + q3_->size) * 4) { |
378 | Node *n = q1_evicted_->l; |
379 | unlink(n); |
380 | lookup_.remove(n->k); |
381 | delete n; |
382 | } |
383 | |
384 | while ((q1_->cost + q2_->cost + q3_->cost) > maxCost_) { |
385 | if (q3_->cost > maxOldPopular_) { |
386 | Node *n = q3_->l; |
387 | unlink(n); |
388 | EvPolicy::aboutToBeEvicted(n->k, n->v); |
389 | lookup_.remove(n->k); |
390 | delete n; |
391 | } else if (q1_->cost > minRecent_) { |
392 | Node *n = q1_->l; |
393 | unlink(n); |
394 | EvPolicy::aboutToBeEvicted(n->k, n->v); |
395 | n->v.clear(); |
396 | n->cost = 0; |
397 | link_front(n, q: q1_evicted_); |
398 | } else { |
399 | Node *n = q2_->l; |
400 | unlink(n); |
401 | if (q2_->size && n->pop > (q2_->pop / q2_->size)) { |
402 | link_front(n, q: q3_); |
403 | } else { |
404 | EvPolicy::aboutToBeEvicted(n->k, n->v); |
405 | n->v.clear(); |
406 | n->cost = 0; |
407 | link_front(n, q: q1_evicted_); |
408 | } |
409 | } |
410 | } |
411 | } |
412 | |
413 | template <class Key, class T, class EvPolicy> |
414 | void QCache3Q<Key,T,EvPolicy>::remove(const Key &key, bool force) |
415 | { |
416 | if (!lookup_.contains(key)) { |
417 | return; |
418 | } |
419 | Node *n = lookup_[key]; |
420 | unlink(n); |
421 | if (n->q != q1_evicted_ && !force) |
422 | EvPolicy::aboutToBeRemoved(n->k, n->v); |
423 | lookup_.remove(key); |
424 | delete n; |
425 | } |
426 | |
427 | template <class Key, class T, class EvPolicy> |
428 | QList<Key> QCache3Q<Key,T,EvPolicy>::keys() const |
429 | { |
430 | return lookup_.keys(); |
431 | } |
432 | |
433 | template <class Key, class T, class EvPolicy> |
434 | QSharedPointer<T> QCache3Q<Key,T,EvPolicy>::object(const Key &key) const |
435 | { |
436 | if (!lookup_.contains(key)) { |
437 | const_cast<QCache3Q<Key,T,EvPolicy> *>(this)->missCount_++; |
438 | return QSharedPointer<T>(0); |
439 | } |
440 | |
441 | QCache3Q<Key,T,EvPolicy> *me = const_cast<QCache3Q<Key,T,EvPolicy> *>(this); |
442 | |
443 | Node *n = me->lookup_[key]; |
444 | n->pop++; |
445 | n->q->pop++; |
446 | |
447 | if (n->q == q1_) { |
448 | me->hitCount_++; |
449 | |
450 | if (n->pop > (quint64)promote_) { |
451 | me->unlink(n); |
452 | me->link_front(n, q2_); |
453 | me->rebalance(); |
454 | } |
455 | } else if (n->q != q1_evicted_) { |
456 | me->hitCount_++; |
457 | |
458 | Queue *q = n->q; |
459 | me->unlink(n); |
460 | me->link_front(n, q); |
461 | me->rebalance(); |
462 | } else { |
463 | me->missCount_++; |
464 | } |
465 | |
466 | return n->v; |
467 | } |
468 | |
469 | template <class Key, class T, class EvPolicy> |
470 | inline QSharedPointer<T> QCache3Q<Key,T,EvPolicy>::operator[](const Key &key) const |
471 | { |
472 | return object(key); |
473 | } |
474 | |
475 | QT_END_NAMESPACE |
476 | |
477 | #endif // QCACHE3Q_H |
478 | |