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
47QT_BEGIN_HEADER
48
49QT_BEGIN_NAMESPACE
50
51QT_MODULE(Core)
52
53template <class Key, class T>
54class 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
97public:
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
124private:
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
133template <class Key, class T>
134inline QCache<Key, T>::QCache(int amaxCost)
135 : f(0), l(0), unused(0), mx(amaxCost), total(0) {}
136
137template <class Key, class T>
138inline void QCache<Key,T>::clear()
139{ while (f) { delete f->t; f = f->n; }
140 hash.clear(); l = 0; total = 0; }
141
142template <class Key, class T>
143inline void QCache<Key,T>::setMaxCost(int m)
144{ mx = m; trim(mx); }
145
146template <class Key, class T>
147inline T *QCache<Key,T>::object(const Key &key) const
148{ return const_cast<QCache<Key,T>*>(this)->relink(key); }
149
150template <class Key, class T>
151inline T *QCache<Key,T>::operator[](const Key &key) const
152{ return object(key); }
153
154template <class Key, class T>
155inline 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
166template <class Key, class T>
167inline 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
180template <class Key, class T>
181bool 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
201template <class Key, class T>
202void 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
212QT_END_NAMESPACE
213
214QT_END_HEADER
215
216#endif // QCACHE_H
217