summaryrefslogtreecommitdiffstats
path: root/src/corelib/tools/qcache.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/corelib/tools/qcache.h')
-rw-r--r--src/corelib/tools/qcache.h374
1 files changed, 214 insertions, 160 deletions
diff --git a/src/corelib/tools/qcache.h b/src/corelib/tools/qcache.h
index 4fcde46fbc..952b88bafb 100644
--- a/src/corelib/tools/qcache.h
+++ b/src/corelib/tools/qcache.h
@@ -1,41 +1,5 @@
-/****************************************************************************
-**
-** Copyright (C) 2016 The Qt Company Ltd.
-** Contact: https://www.qt.io/licensing/
-**
-** This file is part of the QtCore module of the Qt Toolkit.
-**
-** $QT_BEGIN_LICENSE:LGPL$
-** Commercial License Usage
-** Licensees holding valid commercial Qt licenses may use this file in
-** accordance with the commercial license agreement provided with the
-** Software or, alternatively, in accordance with the terms contained in
-** a written agreement between you and The Qt Company. For licensing terms
-** and conditions see https://www.qt.io/terms-conditions. For further
-** information use the contact form at https://www.qt.io/contact-us.
-**
-** GNU Lesser General Public License Usage
-** Alternatively, this file may be used under the terms of the GNU Lesser
-** General Public License version 3 as published by the Free Software
-** Foundation and appearing in the file LICENSE.LGPL3 included in the
-** packaging of this file. Please review the following information to
-** ensure the GNU Lesser General Public License version 3 requirements
-** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
-**
-** GNU General Public License Usage
-** Alternatively, this file may be used under the terms of the GNU
-** General Public License version 2.0 or (at your option) the GNU General
-** Public license version 3 or any later version approved by the KDE Free
-** Qt Foundation. The licenses are as published by the Free Software
-** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
-** included in the packaging of this file. Please review the following
-** information to ensure the GNU General Public License requirements will
-** be met: https://www.gnu.org/licenses/gpl-2.0.html and
-** https://www.gnu.org/licenses/gpl-3.0.html.
-**
-** $QT_END_LICENSE$
-**
-****************************************************************************/
+// Copyright (C) 2016 The Qt Company Ltd.
+// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
#ifndef QCACHE_H
#define QCACHE_H
@@ -48,151 +12,241 @@ QT_BEGIN_NAMESPACE
template <class Key, class T>
class QCache
{
- struct Node {
- inline Node() : keyPtr(0) {}
- inline Node(T *data, int cost)
- : keyPtr(nullptr), t(data), c(cost), p(nullptr), n(nullptr) {}
- const Key *keyPtr; T *t; int c; Node *p,*n;
+ struct Value
+ {
+ T *t = nullptr;
+ qsizetype cost = 0;
+ Value() noexcept = default;
+ Value(T *tt, qsizetype c) noexcept
+ : t(tt), cost(c)
+ {}
+ Value(Value &&other) noexcept
+ : t(other.t),
+ cost(other.cost)
+ {
+ other.t = nullptr;
+ }
+ Value &operator=(Value &&other) noexcept
+ {
+ qt_ptr_swap(t, other.t);
+ std::swap(cost, other.cost);
+ return *this;
+ }
+ ~Value() { delete t; }
+
+ private:
+ Q_DISABLE_COPY(Value)
};
- Node *f, *l;
- QHash<Key, Node> hash;
- int mx, total;
-
- inline void unlink(Node &n) {
- if (n.p) n.p->n = n.n;
- if (n.n) n.n->p = n.p;
- if (l == &n) l = n.p;
- if (f == &n) f = n.n;
- total -= n.c;
- T *obj = n.t;
- hash.remove(*n.keyPtr);
- delete obj;
- }
- inline T *relink(const Key &key) {
- typename QHash<Key, Node>::iterator i = hash.find(key);
- if (typename QHash<Key, Node>::const_iterator(i) == hash.constEnd())
- return nullptr;
- Node &n = *i;
- if (f != &n) {
- if (n.p) n.p->n = n.n;
- if (n.n) n.n->p = n.p;
- if (l == &n) l = n.p;
- n.p = nullptr;
- n.n = f;
- f->p = &n;
- f = &n;
- }
- return n.t;
- }
+ struct Chain
+ {
+ Chain() noexcept : prev(this), next(this) { }
+ Chain *prev;
+ Chain *next;
+ };
- Q_DISABLE_COPY(QCache)
+ struct Node : public Chain
+ {
+ using KeyType = Key;
+ using ValueType = Value;
-public:
- inline explicit QCache(int maxCost = 100) noexcept;
- inline ~QCache() { clear(); }
+ Key key;
+ Value value;
- inline int maxCost() const { return mx; }
- void setMaxCost(int m);
- inline int totalCost() const { return total; }
+ Node(const Key &k, Value &&t) noexcept(std::is_nothrow_move_assignable_v<Key>)
+ : Chain(),
+ key(k),
+ value(std::move(t))
+ {
+ }
+ Node(Key &&k, Value &&t) noexcept(std::is_nothrow_move_assignable_v<Key>)
+ : Chain(),
+ key(std::move(k)),
+ value(std::move(t))
+ {
+ }
+ static void createInPlace(Node *n, const Key &k, T *o, qsizetype cost)
+ {
+ new (n) Node{ Key(k), Value(o, cost) };
+ }
+ void emplace(T *o, qsizetype cost)
+ {
+ value = Value(o, cost);
+ }
- inline int size() const { return hash.size(); }
- inline int count() const { return hash.size(); }
- inline bool isEmpty() const { return hash.isEmpty(); }
- inline QList<Key> keys() const { return hash.keys(); }
+ Node(Node &&other)
+ : Chain(other),
+ key(std::move(other.key)),
+ value(std::move(other.value))
+ {
+ Q_ASSERT(this->prev);
+ Q_ASSERT(this->next);
+ this->prev->next = this;
+ this->next->prev = this;
+ }
+ private:
+ Q_DISABLE_COPY(Node)
+ };
- void clear();
+ using Data = QHashPrivate::Data<Node>;
+
+ mutable Chain chain;
+ Data d;
+ qsizetype mx = 0;
+ qsizetype total = 0;
+
+ void unlink(Node *n) noexcept(std::is_nothrow_destructible_v<Node>)
+ {
+ Q_ASSERT(n->prev);
+ Q_ASSERT(n->next);
+ n->prev->next = n->next;
+ n->next->prev = n->prev;
+ total -= n->value.cost;
+ auto it = d.findBucket(n->key);
+ d.erase(it);
+ }
+ T *relink(const Key &key) const noexcept
+ {
+ if (isEmpty())
+ return nullptr;
+ Node *n = d.findNode(key);
+ if (!n)
+ return nullptr;
- bool insert(const Key &key, T *object, int cost = 1);
- T *object(const Key &key) const;
- inline bool contains(const Key &key) const { return hash.contains(key); }
- T *operator[](const Key &key) const;
+ if (chain.next != n) {
+ Q_ASSERT(n->prev);
+ Q_ASSERT(n->next);
+ n->prev->next = n->next;
+ n->next->prev = n->prev;
+ n->next = chain.next;
+ chain.next->prev = n;
+ n->prev = &chain;
+ chain.next = n;
+ }
+ return n->value.t;
+ }
- bool remove(const Key &key);
- T *take(const Key &key);
+ void trim(qsizetype m) noexcept(std::is_nothrow_destructible_v<Node>)
+ {
+ while (chain.prev != &chain && total > m) {
+ Node *n = static_cast<Node *>(chain.prev);
+ unlink(n);
+ }
+ }
-private:
- void trim(int m);
-};
-template <class Key, class T>
-inline QCache<Key, T>::QCache(int amaxCost) noexcept
- : f(nullptr), l(nullptr), mx(amaxCost), total(0) {}
+ Q_DISABLE_COPY(QCache)
-template <class Key, class T>
-inline void QCache<Key,T>::clear()
-{ while (f) { delete f->t; f = f->n; }
- hash.clear(); l = nullptr; total = 0; }
+public:
+ inline explicit QCache(qsizetype maxCost = 100) noexcept
+ : mx(maxCost)
+ {
+ }
+ inline ~QCache()
+ {
+ static_assert(std::is_nothrow_destructible_v<Key>, "Types with throwing destructors are not supported in Qt containers.");
+ static_assert(std::is_nothrow_destructible_v<T>, "Types with throwing destructors are not supported in Qt containers.");
-template <class Key, class T>
-inline void QCache<Key,T>::setMaxCost(int m)
-{ mx = m; trim(mx); }
+ clear();
+ }
-template <class Key, class T>
-inline T *QCache<Key,T>::object(const Key &key) const
-{ return const_cast<QCache<Key,T>*>(this)->relink(key); }
+ inline qsizetype maxCost() const noexcept { return mx; }
+ void setMaxCost(qsizetype m) noexcept(std::is_nothrow_destructible_v<Node>)
+ {
+ mx = m;
+ trim(mx);
+ }
+ inline qsizetype totalCost() const noexcept { return total; }
+
+ inline qsizetype size() const noexcept { return qsizetype(d.size); }
+ inline qsizetype count() const noexcept { return qsizetype(d.size); }
+ inline bool isEmpty() const noexcept { return !d.size; }
+ inline QList<Key> keys() const
+ {
+ QList<Key> k;
+ if (size()) {
+ k.reserve(size());
+ for (auto it = d.begin(); it != d.end(); ++it)
+ k << it.node()->key;
+ }
+ Q_ASSERT(k.size() == size());
+ return k;
+ }
-template <class Key, class T>
-inline T *QCache<Key,T>::operator[](const Key &key) const
-{ return object(key); }
+ void clear() noexcept(std::is_nothrow_destructible_v<Node>)
+ {
+ d.clear();
+ total = 0;
+ chain.next = &chain;
+ chain.prev = &chain;
+ }
-template <class Key, class T>
-inline bool QCache<Key,T>::remove(const Key &key)
-{
- typename QHash<Key, Node>::iterator i = hash.find(key);
- if (typename QHash<Key, Node>::const_iterator(i) == hash.constEnd()) {
- return false;
- } else {
- unlink(*i);
+ bool insert(const Key &key, T *object, qsizetype cost = 1)
+ {
+ if (cost > mx) {
+ remove(key);
+ delete object;
+ return false;
+ }
+ trim(mx - cost);
+ auto result = d.findOrInsert(key);
+ Node *n = result.it.node();
+ if (result.initialized) {
+ auto prevCost = n->value.cost;
+ result.it.node()->emplace(object, cost);
+ cost -= prevCost;
+ relink(key);
+ } else {
+ Node::createInPlace(n, key, object, cost);
+ n->prev = &chain;
+ n->next = chain.next;
+ chain.next->prev = n;
+ chain.next = n;
+ }
+ total += cost;
return true;
}
-}
+ T *object(const Key &key) const noexcept
+ {
+ return relink(key);
+ }
+ T *operator[](const Key &key) const noexcept
+ {
+ return relink(key);
+ }
+ inline bool contains(const Key &key) const noexcept
+ {
+ return !isEmpty() && d.findNode(key) != nullptr;
+ }
-template <class Key, class T>
-inline T *QCache<Key,T>::take(const Key &key)
-{
- typename QHash<Key, Node>::iterator i = hash.find(key);
- if (i == hash.end())
- return nullptr;
+ bool remove(const Key &key) noexcept(std::is_nothrow_destructible_v<Node>)
+ {
+ if (isEmpty())
+ return false;
+ Node *n = d.findNode(key);
+ if (!n) {
+ return false;
+ } else {
+ unlink(n);
+ return true;
+ }
+ }
- Node &n = *i;
- T *t = n.t;
- n.t = nullptr;
- unlink(n);
- return t;
-}
+ T *take(const Key &key) noexcept(std::is_nothrow_destructible_v<Key>)
+ {
+ if (isEmpty())
+ return nullptr;
+ Node *n = d.findNode(key);
+ if (!n)
+ return nullptr;
-template <class Key, class T>
-bool QCache<Key,T>::insert(const Key &akey, T *aobject, int acost)
-{
- remove(akey);
- if (acost > mx) {
- delete aobject;
- return false;
+ T *t = n->value.t;
+ n->value.t = nullptr;
+ unlink(n);
+ return t;
}
- trim(mx - acost);
- Node sn(aobject, acost);
- typename QHash<Key, Node>::iterator i = hash.insert(akey, sn);
- total += acost;
- Node *n = &i.value();
- n->keyPtr = &i.key();
- if (f) f->p = n;
- n->n = f;
- f = n;
- if (!l) l = f;
- return true;
-}
-template <class Key, class T>
-void QCache<Key,T>::trim(int m)
-{
- Node *n = l;
- while (n && total > m) {
- Node *u = n;
- n = n->p;
- unlink(*u);
- }
-}
+};
QT_END_NAMESPACE
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-25 22:34:49 +0000