summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorLars Knoll <lars.knoll@qt.io>2020-01-23 14:59:35 +0100
committerLars Knoll <lars.knoll@qt.io>2020-04-09 20:03:03 +0200
commite1e573cee8f0197a1549929dc9e818f8004fb1cb (patch)
tree8e69848165187b7cafd11a0a71b3e05de679d4be
parent5b7c3e31b538376f2b4733bd868b5875b504cdb3 (diff)
new QCache implementation
Make use of the new features available in QHash and do a more performant implementation than the old one. Change-Id: Ie74b3cdcc9871cd241aca205672093dc395d04a7 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
-rw-r--r--src/corelib/tools/qcache.h325
-rw-r--r--src/corelib/tools/qhash.h8
-rw-r--r--src/corelib/tools/qset.h8
-rw-r--r--tests/auto/corelib/tools/qcache/tst_qcache.cpp16
4 files changed, 230 insertions, 127 deletions
diff --git a/src/corelib/tools/qcache.h b/src/corelib/tools/qcache.h
index 4fcde46fbc..f043ea9cff 100644
--- a/src/corelib/tools/qcache.h
+++ b/src/corelib/tools/qcache.h
@@ -48,151 +48,234 @@ 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;
+ int cost = 0;
+ Value() noexcept = default;
+ Value(T *tt, int c) noexcept
+ : t(tt), cost(c)
+ {}
+ Value(Value &&other) noexcept
+ : t(other.t),
+ cost(other.cost)
+ {
+ other.t = nullptr;
+ }
+ Value &operator=(Value &&other) noexcept
+ {
+ qSwap(t, other.t);
+ qSwap(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;
+ struct Chain {
+ Chain() noexcept
+ : prev(this), next(this)
+ {}
+ Chain *prev;
+ Chain *next;
+ };
+
+ struct Node : public Chain {
+ using KeyType = Key;
+ using ValueType = Value;
+
+ Key key;
+ Value value;
+
+ Node(const Key &k, Value &&t) noexcept(std::is_nothrow_move_assignable_v<Key>)
+ : Chain(),
+ key(k),
+ value(std::move(t))
+ {
}
- return n.t;
- }
+ Node(Key &&k, Value &&t) noexcept(std::is_nothrow_move_assignable_v<Key>)
+ : Chain(),
+ key(std::move(k)),
+ value(std::move(t))
+ {
+ }
+ static Node create(Key &&k, Value &&t) noexcept(std::is_nothrow_move_assignable_v<Key> && std::is_nothrow_move_assignable_v<T>)
+ {
+ return Node(std::move(k), std::move(t));
+ }
+ 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>)
+ {
+ 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; }
- Q_DISABLE_COPY(QCache)
+ 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)
+ };
-public:
- inline explicit QCache(int maxCost = 100) noexcept;
- inline ~QCache() { clear(); }
+ using Data = QHashPrivate::Data<Node>;
- inline int maxCost() const { return mx; }
- void setMaxCost(int m);
- inline int totalCost() const { return total; }
+ mutable Chain chain;
+ Data d;
+ int mx = 0;
+ int total = 0;
- 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(); }
+ 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.find(n->key);
+ d.erase(it);
+ }
+ T *relink(const Key &key) const noexcept
+ {
+ Node *n = d.findNode(key);
+ if (!n)
+ return nullptr;
- void clear();
+ 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 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;
+ void trim(int 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);
+ }
+ }
- bool remove(const Key &key);
- T *take(const Key &key);
-private:
- void trim(int m);
-};
+ Q_DISABLE_COPY(QCache)
-template <class Key, class T>
-inline QCache<Key, T>::QCache(int amaxCost) noexcept
- : f(nullptr), l(nullptr), mx(amaxCost), total(0) {}
+public:
+ inline explicit QCache(int maxCost = 100) noexcept
+ : mx(maxCost)
+ {}
+ inline ~QCache() { clear(); }
-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; }
+ inline int maxCost() const noexcept { return mx; }
+ void setMaxCost(int m) noexcept(std::is_nothrow_destructible_v<Node>)
+ {
+ mx = m;
+ trim(mx);
+ }
+ inline int totalCost() const noexcept { return total; }
-template <class Key, class T>
-inline void QCache<Key,T>::setMaxCost(int m)
-{ mx = m; trim(mx); }
+ inline int size() const noexcept { return d.size; }
+ inline int count() const noexcept { return d.size; }
+ inline bool isEmpty() const noexcept { return !d.size; }
+ inline QVector<Key> keys() const
+ {
+ QVector<Key> k;
+ if (d.size) {
+ k.reserve(d.size);
+ for (auto it = d.begin(); it != d.end(); ++it)
+ k << it.node()->key;
+ }
+ Q_ASSERT(k.size() == qsizetype(d.size));
+ return k;
+ }
-template <class Key, class T>
-inline T *QCache<Key,T>::object(const Key &key) const
-{ return const_cast<QCache<Key,T>*>(this)->relink(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 T *QCache<Key,T>::operator[](const Key &key) const
-{ return object(key); }
+ bool insert(const Key &key, T *object, int cost = 1)
+ {
+ remove(key);
-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);
+ if (cost > mx) {
+ delete object;
+ return false;
+ }
+ trim(mx - cost);
+ auto it = d.insert(Node::create(Key(key), Value(object, cost)));
+ total += cost;
+ Node *n = it.node();
+ n->prev = &chain;
+ n->next = chain.next;
+ chain.next->prev = n;
+ chain.next = n;
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 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>)
+ {
+ 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>)
+ {
+ 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
diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h
index cdf5577fcb..09d7ade20f 100644
--- a/src/corelib/tools/qhash.h
+++ b/src/corelib/tools/qhash.h
@@ -491,6 +491,14 @@ struct Data
}
+ void clear()
+ {
+ delete [] spans;
+ spans = nullptr;
+ size = 0;
+ numBuckets = 0;
+ }
+
iterator detachedIterator(iterator other) const noexcept
{
return iterator{this, other.bucket};
diff --git a/src/corelib/tools/qset.h b/src/corelib/tools/qset.h
index 5b7aa8fa28..b631587177 100644
--- a/src/corelib/tools/qset.h
+++ b/src/corelib/tools/qset.h
@@ -165,11 +165,10 @@ public:
inline const_iterator cend() const noexcept { return q_hash.end(); }
inline const_iterator constEnd() const noexcept { return q_hash.constEnd(); }
- iterator erase(iterator i)
- { return erase(m2c(i)); }
iterator erase(const_iterator i)
{
- return q_hash.erase(reinterpret_cast<typename Hash::const_iterator &>(i));
+ Q_ASSERT(i != constEnd());
+ return q_hash.erase(i.i);
}
// more Qt
@@ -221,9 +220,6 @@ public:
private:
Hash q_hash;
-
- static const_iterator m2c(iterator it) noexcept
- { return const_iterator(typename Hash::const_iterator(it.i.i)); }
};
#if defined(__cpp_deduction_guides) && __cpp_deduction_guides >= 201606
diff --git a/tests/auto/corelib/tools/qcache/tst_qcache.cpp b/tests/auto/corelib/tools/qcache/tst_qcache.cpp
index d880953c1c..af74553ab4 100644
--- a/tests/auto/corelib/tools/qcache/tst_qcache.cpp
+++ b/tests/auto/corelib/tools/qcache/tst_qcache.cpp
@@ -47,6 +47,7 @@ private slots:
void remove();
void take();
void axioms_on_key_type();
+ void largeCache();
};
@@ -398,5 +399,20 @@ void tst_QCache::axioms_on_key_type()
QVERIFY(sizeof(QHash<int, int>) == sizeof(void *));
}
+void tst_QCache::largeCache()
+{
+ QCache<int, int> cache;
+ cache.setMaxCost(500);
+ for (int i = 0; i < 1000; ++i) {
+ for (int j = 0; j < qMax(0, i - 500); ++j)
+ QVERIFY(!cache.contains(j));
+ for (int j = qMax(0, i - 500); j < i; ++j)
+ QVERIFY(cache.contains(j));
+ cache.insert(i, new int);
+ }
+ cache.clear();
+ QVERIFY(cache.size() == 0);
+}
+
QTEST_APPLESS_MAIN(tst_QCache)
#include "tst_qcache.moc"