Qt 4.8
qcache.h
Go to the documentation of this file.
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 
48 
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;
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 
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>
203 {
204  Node *n = l;
205  while (n && total > m) {
206  Node *u = n;
207  n = n->p;
208  unlink(*u);
209  }
210 }
211 
213 
215 
216 #endif // QCACHE_H
The QHash::const_iterator class provides an STL-style const iterator for QHash and QMultiHash...
Definition: qhash.h:395
Node * l
Definition: qcache.h:62
T * object(const Key &key) const
Definition: qcache.h:147
#define QT_END_NAMESPACE
This macro expands to.
Definition: qglobal.h:90
Node * f
Definition: qcache.h:62
#define QT_MODULE(x)
Definition: qglobal.h:2783
int remove(const Key &key)
Removes all the items that have the key from the hash.
Definition: qhash.h:784
#define QT_BEGIN_HEADER
Definition: qglobal.h:136
int maxCost() const
Definition: qcache.h:105
Definition: qcache.h:54
Node * p
Definition: qcache.h:60
void * unused
Definition: qcache.h:64
void unlink(Node &n)
Definition: qcache.h:67
void clear()
Definition: qcache.h:138
#define Q_DISABLE_COPY(Class)
Disables the use of copy constructors and assignment operators for the given Class.
Definition: qglobal.h:2523
quint16 u
T & value() const
Returns a modifiable reference to the current item&#39;s value.
Definition: qhash.h:348
The QHash class is a template class that provides a hash-table-based dictionary.
Definition: qdatastream.h:66
int count() const
Definition: qcache.h:110
T * take(const Key &key)
Definition: qcache.h:167
bool contains(const Key &key) const
Returns true if the hash contains an item with the key; otherwise returns false.
Definition: qhash.h:872
~QCache()
Definition: qcache.h:103
Node(T *data, int cost)
Definition: qcache.h:58
#define QT_BEGIN_NAMESPACE
This macro expands to.
Definition: qglobal.h:89
int size() const
Definition: qcache.h:109
void setMaxCost(int m)
Definition: qcache.h:143
bool isEmpty() const
Returns true if the hash contains no items; otherwise returns false.
Definition: qhash.h:297
const Key * keyPtr
Definition: qcache.h:60
static const char * data(const QByteArray &arr)
QCache(int maxCost=100)
Definition: qcache.h:134
const Key & key() const
Returns the current item&#39;s key as a const reference.
Definition: qhash.h:347
bool insert(const Key &key, T *object, int cost=1)
Definition: qcache.h:181
bool contains(const Key &key) const
Definition: qcache.h:118
int totalCost() const
Definition: qcache.h:107
const_iterator constEnd() const
Returns a const STL-style iterator pointing to the imaginary item after the last item in the hash...
Definition: qhash.h:469
int mx
Definition: qcache.h:65
int size() const
Returns the number of items in the hash.
Definition: qhash.h:295
bool isEmpty() const
Definition: qcache.h:111
Node * n
Definition: qcache.h:60
int key
The QHash::iterator class provides an STL-style non-const iterator for QHash and QMultiHash.
Definition: qhash.h:330
void trim(int m)
Definition: qcache.h:202
int total
Definition: qcache.h:65
QList< Key > keys() const
Definition: qcache.h:112
iterator find(const Key &key)
Returns an iterator pointing to the item with the key in the hash.
Definition: qhash.h:865
#define QT_END_HEADER
Definition: qglobal.h:137
QList< Key > keys() const
Returns a list containing all the keys in the hash, in an arbitrary order.
Definition: qhash.h:648
T * relink(const Key &key)
Definition: qcache.h:77
bool remove(const Key &key)
Definition: qcache.h:155
The QList class is a template class that provides lists.
Definition: qdatastream.h:62
T * operator[](const Key &key) const
Definition: qcache.h:151
QHash< Key, Node > hash
Definition: qcache.h:63