src/corelib/tools/qcache.h

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