diff options
Diffstat (limited to 'src/corelib/tools/qcache.h')
-rw-r--r-- | src/corelib/tools/qcache.h | 153 |
1 files changed, 57 insertions, 96 deletions
diff --git a/src/corelib/tools/qcache.h b/src/corelib/tools/qcache.h index fbfa2ab997..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,11 +12,12 @@ QT_BEGIN_NAMESPACE template <class Key, class T> class QCache { - struct Value { + struct Value + { T *t = nullptr; - int cost = 0; + qsizetype cost = 0; Value() noexcept = default; - Value(T *tt, int c) noexcept + Value(T *tt, qsizetype c) noexcept : t(tt), cost(c) {} Value(Value &&other) noexcept @@ -63,24 +28,25 @@ class QCache } Value &operator=(Value &&other) noexcept { - qSwap(t, other.t); - qSwap(cost, other.cost); + qt_ptr_swap(t, other.t); + std::swap(cost, other.cost); return *this; } ~Value() { delete t; } + private: Q_DISABLE_COPY(Value) }; - struct Chain { - Chain() noexcept - : prev(this), next(this) - {} + struct Chain + { + Chain() noexcept : prev(this), next(this) { } Chain *prev; Chain *next; }; - struct Node : public Chain { + struct Node : public Chain + { using KeyType = Key; using ValueType = Value; @@ -99,31 +65,14 @@ class QCache value(std::move(t)) { } - static void createInPlace(Node *n, const Key &k, T *o, int cost) + static void createInPlace(Node *n, const Key &k, T *o, qsizetype cost) { new (n) Node{ Key(k), Value(o, cost) }; } - void emplace(T *o, int cost) + void emplace(T *o, qsizetype cost) { value = Value(o, cost); } - static Node create(const Key &k, Value &&t) noexcept(std::is_nothrow_move_assignable_v<Key> && std::is_nothrow_move_assignable_v<T>) - { - return Node(k, std::move(t)); - } - void replace(const Value &t) noexcept(std::is_nothrow_assignable_v<T, T>) - { - value = t; - } - void replace(Value &&t) noexcept(std::is_nothrow_move_assignable_v<T>) - { - value = std::move(t); - } - Value takeValue() noexcept(std::is_nothrow_move_constructible_v<T>) - { - return std::move(value); - } - bool valuesEqual(const Node *other) const { return value == other->value; } Node(Node &&other) : Chain(other), @@ -143,8 +92,8 @@ class QCache mutable Chain chain; Data d; - int mx = 0; - int total = 0; + qsizetype mx = 0; + qsizetype total = 0; void unlink(Node *n) noexcept(std::is_nothrow_destructible_v<Node>) { @@ -153,11 +102,13 @@ class QCache n->prev->next = n->next; n->next->prev = n->prev; total -= n->value.cost; - auto it = d.find(n->key); + 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; @@ -175,13 +126,11 @@ class QCache return n->value.t; } - void trim(int m) noexcept(std::is_nothrow_destructible_v<Node>) + void trim(qsizetype m) noexcept(std::is_nothrow_destructible_v<Node>) { - Chain *n = chain.prev; - while (n != &chain && total > m) { - Node *u = static_cast<Node *>(n); - n = n->prev; - unlink(u); + while (chain.prev != &chain && total > m) { + Node *n = static_cast<Node *>(chain.prev); + unlink(n); } } @@ -189,31 +138,38 @@ class QCache Q_DISABLE_COPY(QCache) public: - inline explicit QCache(int maxCost = 100) noexcept + inline explicit QCache(qsizetype maxCost = 100) noexcept : mx(maxCost) - {} - inline ~QCache() { clear(); } + { + } + 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."); - inline int maxCost() const noexcept { return mx; } - void setMaxCost(int m) noexcept(std::is_nothrow_destructible_v<Node>) + clear(); + } + + inline qsizetype maxCost() const noexcept { return mx; } + void setMaxCost(qsizetype m) noexcept(std::is_nothrow_destructible_v<Node>) { mx = m; trim(mx); } - inline int totalCost() const noexcept { return total; } + inline qsizetype totalCost() const noexcept { return total; } - inline qsizetype size() const noexcept { return d.size; } - inline qsizetype count() const noexcept { return d.size; } + 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 (d.size) { - k.reserve(typename QList<Key>::size_type(d.size)); + if (size()) { + k.reserve(size()); for (auto it = d.begin(); it != d.end(); ++it) k << it.node()->key; } - Q_ASSERT(k.size() == qsizetype(d.size)); + Q_ASSERT(k.size() == size()); return k; } @@ -225,11 +181,10 @@ public: chain.prev = &chain; } - bool insert(const Key &key, T *object, int cost = 1) + bool insert(const Key &key, T *object, qsizetype cost = 1) { - remove(key); - if (cost > mx) { + remove(key); delete object; return false; } @@ -237,16 +192,18 @@ public: auto result = d.findOrInsert(key); Node *n = result.it.node(); if (result.initialized) { - cost -= n->value.cost; + 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; - n->prev = &chain; - n->next = chain.next; - chain.next->prev = n; - chain.next = n; return true; } T *object(const Key &key) const noexcept @@ -259,11 +216,13 @@ public: } inline bool contains(const Key &key) const noexcept { - return d.findNode(key) != nullptr; + return !isEmpty() && d.findNode(key) != 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; @@ -275,6 +234,8 @@ public: 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; |