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>
aboutToBeEvicted(const Key & key,QSharedPointer<T> obj)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>
aboutToBeRemoved(const Key & key,QSharedPointer<T> obj)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:
Node()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:
Queue()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);
~QCache3Q()149 inline ~QCache3Q() { clear(); delete q1_; delete q2_; delete q3_; delete q1_evicted_; }
150
maxCost()151 inline int maxCost() const { return maxCost_; }
152 void setMaxCost(int maxCost, int minRecent = -1, int maxOldPopular = -1);
153
promoteAt()154 inline int promoteAt() const { return promote_; }
setPromoteAt(int p)155 inline void setPromoteAt(int p) { promote_ = p; }
156
totalCost()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
QCache3Q(const QCache3Q<Key,T,EvPolicy> &)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>
printStats()189 void QCache3Q<Key,T,EvPolicy>::printStats()
190 {
191 qDebug("\n=== cache %p ===", this);
192 qDebug("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>
QCache3Q(int maxCost,int minRecent,int maxOldPopular)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>
serializeQueue(int queueNumber,QList<QSharedPointer<T>> & buffer)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>
deserializeQueue(int queueNumber,const QList<Key> & keys,const QList<QSharedPointer<T>> & values,const QList<int> & costs)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(node, queue);
245 lookup_[keys[i]] = node;
246 }
247 }
248
249
250 template <class Key, class T, class EvPolicy>
setMaxCost(int maxCost,int minRecent,int maxOldPopular)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>
insert(const Key & key,QSharedPointer<T> object,int cost)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, 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, q1_);
298 lookup_[key] = n;
299
300 rebalance();
301
302 return true;
303 }
304
305 template <class Key, class T, class EvPolicy>
clear()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>
unlink(Node * n)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>
link_front(Node * n,Queue * q)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>
rebalance()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, 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, q3_);
403 } else {
404 EvPolicy::aboutToBeEvicted(n->k, n->v);
405 n->v.clear();
406 n->cost = 0;
407 link_front(n, q1_evicted_);
408 }
409 }
410 }
411 }
412
413 template <class Key, class T, class EvPolicy>
remove(const Key & key,bool force)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>
keys()428 QList<Key> QCache3Q<Key,T,EvPolicy>::keys() const
429 {
430 return lookup_.keys();
431 }
432
433 template <class Key, class T, class EvPolicy>
object(const Key & key)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