From e1e573cee8f0197a1549929dc9e818f8004fb1cb Mon Sep 17 00:00:00 2001
From: Lars Knoll <lars.knoll@qt.io>
Date: Thu, 23 Jan 2020 14:59:35 +0100
Subject: 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>
---
 src/corelib/tools/qcache.h                     | 325 ++++++++++++++++---------
 src/corelib/tools/qhash.h                      |   8 +
 src/corelib/tools/qset.h                       |   8 +-
 tests/auto/corelib/tools/qcache/tst_qcache.cpp |  16 ++
 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"
-- 
cgit v1.2.3