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
45QT_BEGIN_NAMESPACE
46
47
48template <class Key, class T>
49class 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
91public:
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
114private:
115 void trim(int m);
116};
117
118template <class Key, class T>
119inline QCache<Key, T>::QCache(int amaxCost) noexcept
120 : f(nullptr), l(nullptr), mx(amaxCost), total(0) {}
121
122template <class Key, class T>
123inline void QCache<Key,T>::clear()
124{ while (f) { delete f->t; f = f->n; }
125 hash.clear(); l = nullptr; total = 0; }
126
127template <class Key, class T>
128inline void QCache<Key,T>::setMaxCost(int m)
129{ mx = m; trim(mx); }
130
131template <class Key, class T>
132inline T *QCache<Key,T>::object(const Key &key) const
133{ return const_cast<QCache<Key,T>*>(this)->relink(key); }
134
135template <class Key, class T>
136inline T *QCache<Key,T>::operator[](const Key &key) const
137{ return object(key); }
138
139template <class Key, class T>
140inline 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
151template <class Key, class T>
152inline 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
165template <class Key, class T>
166bool 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
186template <class Key, class T>
187void 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
197QT_END_NAMESPACE
198
199#endif // QCACHE_H
200