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
56QT_BEGIN_NAMESPACE
57
58template <class Key, class T>
59class QCache3QDefaultEvictionPolicy
60{
61protected:
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
69template <class Key, class T>
70void QCache3QDefaultEvictionPolicy<Key,T>::aboutToBeEvicted(const Key &key, QSharedPointer<T> obj)
71{
72 Q_UNUSED(key);
73 Q_UNUSED(obj);
74}
75
76template <class Key, class T>
77void 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 */
110template <class Key, class T, class EvPolicy = QCache3QDefaultEvictionPolicy<Key,T> >
111class QCache3Q : public EvPolicy
112{
113private:
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
147public:
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
174private:
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
182private:
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
188template <class Key, class T, class EvPolicy>
189void 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
202template <class Key, class T, class EvPolicy>
203QCache3Q<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
214template <class Key, class T, class EvPolicy>
215void 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
226template <class Key, class T, class EvPolicy>
227void 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
250template <class Key, class T, class EvPolicy>
251inline 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
263template <class Key, class T, class EvPolicy>
264bool 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
305template <class Key, class T, class EvPolicy>
306void 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
338template <class Key, class T, class EvPolicy>
339void 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
357template <class Key, class T, class EvPolicy>
358void 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
374template <class Key, class T, class EvPolicy>
375void 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
413template <class Key, class T, class EvPolicy>
414void 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
427template <class Key, class T, class EvPolicy>
428QList<Key> QCache3Q<Key,T,EvPolicy>::keys() const
429{
430 return lookup_.keys();
431}
432
433template <class Key, class T, class EvPolicy>
434QSharedPointer<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
469template <class Key, class T, class EvPolicy>
470inline QSharedPointer<T> QCache3Q<Key,T,EvPolicy>::operator[](const Key &key) const
471{
472 return object(key);
473}
474
475QT_END_NAMESPACE
476
477#endif // QCACHE3Q_H
478

source code of qtlocation/src/location/maps/qcache3q_p.h