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
45 QT_BEGIN_NAMESPACE
46
47
48 template <class Key, class T>
49 class QCache
50 {
51 struct Node {
NodeNode52 inline Node() : keyPtr(0) {}
NodeNode53 inline Node(T *data, int cost)
54 : keyPtr(nullptr), t(data), c(cost), p(nullptr), n(nullptr) {}
55 const Key *keyPtr; T *t; int c; Node *p,*n;
56 };
57 Node *f, *l;
58 QHash<Key, Node> hash;
59 int mx, total;
60
unlink(Node & n)61 inline void unlink(Node &n) {
62 if (n.p) n.p->n = n.n;
63 if (n.n) n.n->p = n.p;
64 if (l == &n) l = n.p;
65 if (f == &n) f = n.n;
66 total -= n.c;
67 T *obj = n.t;
68 hash.remove(*n.keyPtr);
69 delete obj;
70 }
relink(const Key & key)71 inline T *relink(const Key &key) {
72 typename QHash<Key, Node>::iterator i = hash.find(key);
73 if (typename QHash<Key, Node>::const_iterator(i) == hash.constEnd())
74 return nullptr;
75
76 Node &n = *i;
77 if (f != &n) {
78 if (n.p) n.p->n = n.n;
79 if (n.n) n.n->p = n.p;
80 if (l == &n) l = n.p;
81 n.p = nullptr;
82 n.n = f;
83 f->p = &n;
84 f = &n;
85 }
86 return n.t;
87 }
88
89 Q_DISABLE_COPY(QCache)
90
91 public:
92 inline explicit QCache(int maxCost = 100) noexcept;
~QCache()93 inline ~QCache() { clear(); }
94
maxCost()95 inline int maxCost() const { return mx; }
96 void setMaxCost(int m);
totalCost()97 inline int totalCost() const { return total; }
98
size()99 inline int size() const { return hash.size(); }
count()100 inline int count() const { return hash.size(); }
isEmpty()101 inline bool isEmpty() const { return hash.isEmpty(); }
keys()102 inline QList<Key> keys() const { return hash.keys(); }
103
104 void clear();
105
106 bool insert(const Key &key, T *object, int cost = 1);
107 T *object(const Key &key) const;
contains(const Key & key)108 inline bool contains(const Key &key) const { return hash.contains(key); }
109 T *operator[](const Key &key) const;
110
111 bool remove(const Key &key);
112 T *take(const Key &key);
113
114 private:
115 void trim(int m);
116 };
117
118 template <class Key, class T>
QCache(int amaxCost)119 inline QCache<Key, T>::QCache(int amaxCost) noexcept
120 : f(nullptr), l(nullptr), mx(amaxCost), total(0) {}
121
122 template <class Key, class T>
clear()123 inline void QCache<Key,T>::clear()
124 { while (f) { delete f->t; f = f->n; }
125 hash.clear(); l = nullptr; total = 0; }
126
127 template <class Key, class T>
setMaxCost(int m)128 inline void QCache<Key,T>::setMaxCost(int m)
129 { mx = m; trim(mx); }
130
131 template <class Key, class T>
object(const Key & key)132 inline T *QCache<Key,T>::object(const Key &key) const
133 { return const_cast<QCache<Key,T>*>(this)->relink(key); }
134
135 template <class Key, class T>
136 inline T *QCache<Key,T>::operator[](const Key &key) const
137 { return object(key); }
138
139 template <class Key, class T>
remove(const Key & key)140 inline bool QCache<Key,T>::remove(const Key &key)
141 {
142 typename QHash<Key, Node>::iterator i = hash.find(key);
143 if (typename QHash<Key, Node>::const_iterator(i) == hash.constEnd()) {
144 return false;
145 } else {
146 unlink(*i);
147 return true;
148 }
149 }
150
151 template <class Key, class T>
take(const Key & key)152 inline T *QCache<Key,T>::take(const Key &key)
153 {
154 typename QHash<Key, Node>::iterator i = hash.find(key);
155 if (i == hash.end())
156 return nullptr;
157
158 Node &n = *i;
159 T *t = n.t;
160 n.t = nullptr;
161 unlink(n);
162 return t;
163 }
164
165 template <class Key, class T>
insert(const Key & akey,T * aobject,int acost)166 bool QCache<Key,T>::insert(const Key &akey, T *aobject, int acost)
167 {
168 remove(akey);
169 if (acost > mx) {
170 delete aobject;
171 return false;
172 }
173 trim(mx - acost);
174 Node sn(aobject, acost);
175 typename QHash<Key, Node>::iterator i = hash.insert(akey, sn);
176 total += acost;
177 Node *n = &i.value();
178 n->keyPtr = &i.key();
179 if (f) f->p = n;
180 n->n = f;
181 f = n;
182 if (!l) l = f;
183 return true;
184 }
185
186 template <class Key, class T>
trim(int m)187 void QCache<Key,T>::trim(int m)
188 {
189 Node *n = l;
190 while (n && total > m) {
191 Node *u = n;
192 n = n->p;
193 unlink(*u);
194 }
195 }
196
197 QT_END_NAMESPACE
198
199 #endif // QCACHE_H
200