1 | /**************************************************************************** |
2 | ** |
3 | ** Copyright (C) 2014 Digia Plc and/or its subsidiary(-ies). |
4 | ** Contact: http://www.qt-project.org/legal |
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 Digia. For licensing terms and |
14 | ** conditions see http://qt.digia.com/licensing. For further information |
15 | ** use the contact form at http://qt.digia.com/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 2.1 as published by the Free Software |
20 | ** Foundation and appearing in the file LICENSE.LGPL included in the |
21 | ** packaging of this file. Please review the following information to |
22 | ** ensure the GNU Lesser General Public License version 2.1 requirements |
23 | ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. |
24 | ** |
25 | ** In addition, as a special exception, Digia gives you certain additional |
26 | ** rights. These rights are described in the Digia Qt LGPL Exception |
27 | ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. |
28 | ** |
29 | ** GNU General Public License Usage |
30 | ** Alternatively, this file may be used under the terms of the GNU |
31 | ** General Public License version 3.0 as published by the Free Software |
32 | ** Foundation and appearing in the file LICENSE.GPL included in the |
33 | ** packaging of this file. Please review the following information to |
34 | ** ensure the GNU General Public License version 3.0 requirements will be |
35 | ** met: http://www.gnu.org/copyleft/gpl.html. |
36 | ** |
37 | ** |
38 | ** $QT_END_LICENSE$ |
39 | ** |
40 | ****************************************************************************/ |
41 | |
42 | #ifndef QCACHE_H |
43 | #define QCACHE_H |
44 | |
45 | #include <QtCore/qhash.h> |
46 | |
47 | QT_BEGIN_HEADER |
48 | |
49 | QT_BEGIN_NAMESPACE |
50 | |
51 | QT_MODULE(Core) |
52 | |
53 | template <class Key, class T> |
54 | class QCache |
55 | { |
56 | struct Node { |
57 | inline Node() : keyPtr(0) {} |
58 | inline Node(T *data, int cost) |
59 | : keyPtr(0), t(data), c(cost), p(0), n(0) {} |
60 | const Key *keyPtr; T *t; int c; Node *p,*n; |
61 | }; |
62 | Node *f, *l; |
63 | QHash<Key, Node> hash; |
64 | void *unused; // ### Qt5: remove |
65 | int mx, total; |
66 | |
67 | inline void unlink(Node &n) { |
68 | if (n.p) n.p->n = n.n; |
69 | if (n.n) n.n->p = n.p; |
70 | if (l == &n) l = n.p; |
71 | if (f == &n) f = n.n; |
72 | total -= n.c; |
73 | T *obj = n.t; |
74 | hash.remove(*n.keyPtr); |
75 | delete obj; |
76 | } |
77 | inline T *relink(const Key &key) { |
78 | typename QHash<Key, Node>::iterator i = hash.find(key); |
79 | if (typename QHash<Key, Node>::const_iterator(i) == hash.constEnd()) |
80 | return 0; |
81 | |
82 | Node &n = *i; |
83 | if (f != &n) { |
84 | if (n.p) n.p->n = n.n; |
85 | if (n.n) n.n->p = n.p; |
86 | if (l == &n) l = n.p; |
87 | n.p = 0; |
88 | n.n = f; |
89 | f->p = &n; |
90 | f = &n; |
91 | } |
92 | return n.t; |
93 | } |
94 | |
95 | Q_DISABLE_COPY(QCache) |
96 | |
97 | public: |
98 | inline explicit QCache(int maxCost = 100); |
99 | #ifdef QT3_SUPPORT |
100 | inline QT3_SUPPORT_CONSTRUCTOR QCache(int maxCost, int /* dummy */) |
101 | : f(0), l(0), mx(maxCost), total(0) {} |
102 | #endif |
103 | inline ~QCache() { clear(); } |
104 | |
105 | inline int maxCost() const { return mx; } |
106 | void setMaxCost(int m); |
107 | inline int totalCost() const { return total; } |
108 | |
109 | inline int size() const { return hash.size(); } |
110 | inline int count() const { return hash.size(); } |
111 | inline bool isEmpty() const { return hash.isEmpty(); } |
112 | inline QList<Key> keys() const { return hash.keys(); } |
113 | |
114 | void clear(); |
115 | |
116 | bool insert(const Key &key, T *object, int cost = 1); |
117 | T *object(const Key &key) const; |
118 | inline bool contains(const Key &key) const { return hash.contains(key); } |
119 | T *operator[](const Key &key) const; |
120 | |
121 | bool remove(const Key &key); |
122 | T *take(const Key &key); |
123 | |
124 | private: |
125 | void trim(int m); |
126 | |
127 | #ifdef QT3_SUPPORT |
128 | inline QT3_SUPPORT T *find(const Key &key) const { return object(key); } |
129 | #endif |
130 | |
131 | }; |
132 | |
133 | template <class Key, class T> |
134 | inline QCache<Key, T>::QCache(int amaxCost) |
135 | : f(0), l(0), unused(0), mx(amaxCost), total(0) {} |
136 | |
137 | template <class Key, class T> |
138 | inline void QCache<Key,T>::clear() |
139 | { while (f) { delete f->t; f = f->n; } |
140 | hash.clear(); l = 0; total = 0; } |
141 | |
142 | template <class Key, class T> |
143 | inline void QCache<Key,T>::setMaxCost(int m) |
144 | { mx = m; trim(mx); } |
145 | |
146 | template <class Key, class T> |
147 | inline T *QCache<Key,T>::object(const Key &key) const |
148 | { return const_cast<QCache<Key,T>*>(this)->relink(key); } |
149 | |
150 | template <class Key, class T> |
151 | inline T *QCache<Key,T>::operator[](const Key &key) const |
152 | { return object(key); } |
153 | |
154 | template <class Key, class T> |
155 | inline bool QCache<Key,T>::remove(const Key &key) |
156 | { |
157 | typename QHash<Key, Node>::iterator i = hash.find(key); |
158 | if (typename QHash<Key, Node>::const_iterator(i) == hash.constEnd()) { |
159 | return false; |
160 | } else { |
161 | unlink(*i); |
162 | return true; |
163 | } |
164 | } |
165 | |
166 | template <class Key, class T> |
167 | inline T *QCache<Key,T>::take(const Key &key) |
168 | { |
169 | typename QHash<Key, Node>::iterator i = hash.find(key); |
170 | if (i == hash.end()) |
171 | return 0; |
172 | |
173 | Node &n = *i; |
174 | T *t = n.t; |
175 | n.t = 0; |
176 | unlink(n); |
177 | return t; |
178 | } |
179 | |
180 | template <class Key, class T> |
181 | bool QCache<Key,T>::insert(const Key &akey, T *aobject, int acost) |
182 | { |
183 | remove(akey); |
184 | if (acost > mx) { |
185 | delete aobject; |
186 | return false; |
187 | } |
188 | trim(mx - acost); |
189 | Node sn(aobject, acost); |
190 | typename QHash<Key, Node>::iterator i = hash.insert(akey, sn); |
191 | total += acost; |
192 | Node *n = &i.value(); |
193 | n->keyPtr = &i.key(); |
194 | if (f) f->p = n; |
195 | n->n = f; |
196 | f = n; |
197 | if (!l) l = f; |
198 | return true; |
199 | } |
200 | |
201 | template <class Key, class T> |
202 | void QCache<Key,T>::trim(int m) |
203 | { |
204 | Node *n = l; |
205 | while (n && total > m) { |
206 | Node *u = n; |
207 | n = n->p; |
208 | unlink(*u); |
209 | } |
210 | } |
211 | |
212 | QT_END_NAMESPACE |
213 | |
214 | QT_END_HEADER |
215 | |
216 | #endif // QCACHE_H |
217 | |