diff options
Diffstat (limited to 'src/corelib/tools/qcache.h')
-rw-r--r-- | src/corelib/tools/qcache.h | 374 |
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 |