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 { |
52 | inline Node() : keyPtr(0) {} |
53 | 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 | |
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 | } |
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; |
93 | inline ~QCache() { clear(); } |
94 | |
95 | inline int maxCost() const { return mx; } |
96 | void setMaxCost(int m); |
97 | inline int totalCost() const { return total; } |
98 | |
99 | inline int size() const { return hash.size(); } |
100 | inline int count() const { return hash.size(); } |
101 | inline bool isEmpty() const { return hash.isEmpty(); } |
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; |
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> |
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> |
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> |
128 | inline void QCache<Key,T>::setMaxCost(int m) |
129 | { mx = m; trim(mx); } |
130 | |
131 | template <class Key, class T> |
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> |
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> |
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> |
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> |
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 | |