Split QStringHash and QLinked(Multi)StringHash apart

The plain QStringHash can have a mutable iterator. The linked one can
not. We never use a non-linked MultiStringHash.

Change-Id: I69b66f7952e6e47b79c0995f389e6219744dfc76
Reviewed-by: Lars Knoll <lars.knoll@qt.io>

4 files changed, 301 insertions, 238 deletions

diff --git a/src/qml/qml/ftw/ftw.pri b/src/qml/qml/ftw/ftw.pri
index b1698a7b0e..0bb8cb954e 100644
--- a/src/qml/qml/ftw/ftw.pri
+++ b/src/qml/qml/ftw/ftw.pri
@@ -12,7 +12,8 @@ HEADERS +=  \
     $$PWD/qflagpointer_p.h \
     $$PWD/qlazilyallocated_p.h \
     $$PWD/qqmlnullablevalue_p.h \
-    $$PWD/qstringhash_p.h
+    $$PWD/qstringhash_p.h \
+    $$PWD/qlinkedstringhash_p.h
 
 SOURCES += \
     $$PWD/qintrusivelist.cpp \
diff --git a/src/qml/qml/ftw/qlinkedstringhash_p.h b/src/qml/qml/ftw/qlinkedstringhash_p.h
new file mode 100644
index 0000000000..c5d428119f
--- /dev/null
+++ b/src/qml/qml/ftw/qlinkedstringhash_p.h
@@ -0,0 +1,243 @@
+/****************************************************************************
+**
+** Copyright (C) 2019 The Qt Company Ltd.
+** Contact: https://www.qt.io/licensing/
+**
+** This file is part of the QtQml 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$
+**
+****************************************************************************/
+
+#ifndef QLINKEDSTRINGHASH_P_H
+#define QLINKEDSTRINGHASH_P_H
+
+//
+//  W A R N I N G
+//  -------------
+//
+// This file is not part of the Qt API.  It exists purely as an
+// implementation detail.  This header file may change from version to
+// version without notice, or even be removed.
+//
+// We mean it.
+//
+
+#include <private/qstringhash_p.h>
+
+QT_BEGIN_NAMESPACE
+
+template<class T>
+class QLinkedStringHash : private QStringHash<T>
+{
+public:
+    using typename QStringHash<T>::Node;
+    using typename QStringHash<T>::NewedNode;
+    using typename QStringHash<T>::ReservedNodePool;
+    using typename QStringHash<T>::mapped_type;
+
+    using ConstIteratorData = QStringHashData::IteratorData<const QLinkedStringHash>;
+    using ConstIterator = typename QStringHash<T>::template Iterator<ConstIteratorData>;
+
+    void linkAndReserve(const QLinkedStringHash<T> &other, int additionalReserve)
+    {
+        clear();
+
+        if (other.count()) {
+            data.size = other.data.size;
+            data.rehashToSize(other.count() + additionalReserve);
+
+            if (data.numBuckets == other.data.numBuckets) {
+                nodePool = new ReservedNodePool;
+                nodePool->count = additionalReserve;
+                nodePool->used = 0;
+                nodePool->nodes = new Node[additionalReserve];
+
+#ifdef QSTRINGHASH_LINK_DEBUG
+                data.linkCount++;
+                const_cast<QStringHash<T>&>(other).data.linkCount++;
+#endif
+
+                for (int ii = 0; ii < data.numBuckets; ++ii)
+                    data.buckets[ii] = (Node *)other.data.buckets[ii];
+
+                link = &other;
+                return;
+            }
+
+            data.size = 0;
+        }
+
+        data.numBits = other.data.numBits;
+        reserve(other.count() + additionalReserve);
+        copy(other);
+    }
+
+    inline bool isLinked() const
+    {
+        return link != 0;
+    }
+
+    void clear()
+    {
+        QStringHash<T>::clear();
+        link = nullptr;
+    }
+
+    template<typename K>
+    void insert(const K &key, const T &value)
+    {
+        // If this is a linked hash, we can't rely on owning the node, so we always
+        // create a new one.
+        Node *n = link ? nullptr : QStringHash<T>::findNode(key);
+        if (n)
+            n->value = value;
+        else
+            QStringHash<T>::createNode(key, value);
+    }
+
+    template<typename K>
+    inline ConstIterator find(const K &key) const
+    {
+        return iterator(QStringHash<T>::findNode(key));
+    }
+
+    ConstIterator begin() const
+    {
+        return ConstIterator(
+                QStringHash<T>::template iterateFirst<const QLinkedStringHash<T>,
+                                                      ConstIteratorData>(this));
+    }
+
+    ConstIterator end() const { return ConstIterator(); }
+
+    inline T *value(const ConstIterator &iter) { return value(iter.node()->key()); }
+
+    using QStringHash<T>::value;
+    using QStringHash<T>::reserve;
+    using QStringHash<T>::copy;
+
+protected:
+    friend QStringHash<T>;
+    using QStringHash<T>::data;
+    using QStringHash<T>::nodePool;
+
+    using QStringHash<T>::createNode;
+
+    inline ConstIteratorData iterateFirst() const
+    {
+        const ConstIteratorData rv
+                = QStringHash<T>::template iterateFirst<const QLinkedStringHash<T>,
+                                                        ConstIteratorData>(this);
+        return (rv.n == nullptr && link) ? link->iterateFirst() : rv;
+    }
+
+    static inline ConstIteratorData iterateNext(const ConstIteratorData &d)
+    {
+        const QLinkedStringHash<T> *self = d.p;
+        const ConstIteratorData rv = QStringHash<T>::iterateNext(d);
+        return (rv.n == nullptr && self->link) ? self->link->iterateFirst() : rv;
+    }
+
+    inline ConstIterator iterator(Node *n) const
+    {
+        if (!n)
+            return ConstIterator();
+
+        const QLinkedStringHash<T> *container = this;
+
+        if (link) {
+            // This node could be in the linked hash
+            if ((n >= nodePool->nodes) && (n < (nodePool->nodes + nodePool->used))) {
+                // The node is in this hash
+            } else if ((n >= link->nodePool->nodes)
+                       && (n < (link->nodePool->nodes + link->nodePool->used))) {
+                // The node is in the linked hash
+                container = link;
+            } else {
+                const NewedNode *ln = link->newedNodes;
+                while (ln) {
+                    if (ln == n) {
+                        // This node is in the linked hash's newed list
+                        container = link;
+                        break;
+                    }
+                    ln = ln->nextNewed;
+                }
+            }
+        }
+
+
+        ConstIteratorData rv;
+        rv.n = n;
+        rv.p = container;
+        return ConstIterator(rv);
+    }
+
+    const QLinkedStringHash<T> *link = nullptr;
+};
+
+template<class T>
+class QLinkedStringMultiHash : public QLinkedStringHash<T>
+{
+public:
+    using ConstIterator = typename QLinkedStringHash<T>::ConstIterator;
+
+    template<typename K>
+    inline void insert(const K &key, const T &value)
+    {
+        // Always create a new node
+        QLinkedStringHash<T>::createNode(key, value);
+    }
+
+    inline void insert(const ConstIterator &iter)
+    {
+        // Always create a new node
+        QLinkedStringHash<T>::createNode(iter.key(), iter.value());
+    }
+
+    inline ConstIterator findNext(const ConstIterator &iter) const
+    {
+        if (auto *node = iter.node()) {
+            QHashedString key(node->key());
+            while ((node = static_cast<typename QLinkedStringHash<T>::Node *>(*node->next))) {
+                if (node->equals(key))
+                    return QLinkedStringHash<T>::iterator(node);
+            }
+        }
+
+        return ConstIterator();
+    }
+};
+
+QT_END_NAMESPACE
+
+#endif // QLINKEDSTRINGHASH_P_H
diff --git a/src/qml/qml/ftw/qstringhash_p.h b/src/qml/qml/ftw/qstringhash_p.h
index e5a709b02c..7e1a5dfb4d 100644
--- a/src/qml/qml/ftw/qstringhash_p.h
+++ b/src/qml/qml/ftw/qstringhash_p.h
@@ -167,10 +167,11 @@ public:
     int linkCount = 0;
 #endif
 
+    template<typename StringHash>
     struct IteratorData {
-        IteratorData() {}
-        QStringHashNode *n = nullptr;
-        void *p = nullptr;
+        IteratorData(QStringHashNode *n = nullptr, StringHash *p = nullptr) : n(n), p(p) {}
+        QStringHashNode *n;
+        StringHash *p;
     };
     void rehashToBits(short);
     void rehashToSize(int);
@@ -230,6 +231,9 @@ public:
     typedef QHashedString key_type;
     typedef T mapped_type;
 
+    using MutableIteratorData = QStringHashData::IteratorData<QStringHash<T>>;
+    using ConstIteratorData = QStringHashData::IteratorData<const QStringHash<T>>;
+
     struct Node : public QStringHashNode {
         Node(const QHashedString &key, const T &value) : QStringHashNode(key), value(value) {}
         Node(const QHashedCStringRef &key, const T &value) : QStringHashNode(key), value(value) {}
@@ -255,7 +259,6 @@ public:
     QStringHashData data;
     NewedNode *newedNodes;
     ReservedNodePool *nodePool;
-    const QStringHash<T> *link;
 
     template<typename K>
     inline Node *findNode(const K &) const;
@@ -279,8 +282,11 @@ public:
 
     void copyNode(const QStringHashNode *otherNode);
 
-    inline QStringHashData::IteratorData iterateFirst() const;
-    static inline QStringHashData::IteratorData iterateNext(const QStringHashData::IteratorData &);
+    template<typename StringHash, typename Data>
+    static inline Data iterateFirst(StringHash *self);
+
+    template<typename Data>
+    static inline Data iterateNext(const Data &);
 
 public:
     inline QStringHash();
@@ -290,37 +296,42 @@ public:
     QStringHash &operator=(const QStringHash<T> &);
 
     void copyAndReserve(const QStringHash<T> &other, int additionalReserve);
-    void linkAndReserve(const QStringHash<T> &other, int additionalReserve);
 
     inline bool isEmpty() const;
     inline void clear();
     inline int count() const;
 
     inline int numBuckets() const;
-    inline bool isLinked() const;
 
-    class ConstIterator {
+    template<typename Data>
+    class Iterator {
     public:
-        inline ConstIterator();
-        inline ConstIterator(const QStringHashData::IteratorData &);
+        inline Iterator() = default;
+        inline Iterator(const Data &d) : d(d) {}
 
-        inline ConstIterator &operator++();
+        inline Iterator &operator++()
+        {
+            d = QStringHash<T>::iterateNext(d);
+            return *this;
+        }
 
-        inline bool operator==(const ConstIterator &o) const;
-        inline bool operator!=(const ConstIterator &o) const;
+        inline bool operator==(const Iterator &o) const { return d.n == o.d.n; }
+        inline bool operator!=(const Iterator &o) const { return d.n != o.d.n; }
 
         template<typename K>
-        inline bool equals(const K &) const;
+        inline bool equals(const K &key) const { return d.n->equals(key); }
 
-        inline QHashedString key() const;
-        inline const T &value() const;
-        inline const T &operator*() const;
+        inline QHashedString key() const { return static_cast<Node *>(d.n)->key(); }
+        inline const T &value() const { return static_cast<Node *>(d.n)->value; }
+        inline const T &operator*() const { return static_cast<Node *>(d.n)->value; }
 
-        Node *node() const;
+        Node *node() const { return static_cast<Node *>(d.n); }
     private:
-        QStringHashData::IteratorData d;
+        Data d;
     };
 
+    using ConstIterator = Iterator<ConstIteratorData>;
+
     template<typename K>
     inline void insert(const K &, const T &);
 
@@ -341,8 +352,6 @@ public:
     inline ConstIterator begin() const;
     inline ConstIterator end() const;
 
-    inline ConstIterator iterator(Node *n) const;
-
     template<typename K>
     inline ConstIterator find(const K &) const;
 
@@ -351,13 +360,13 @@ public:
 
 template<class T>
 QStringHash<T>::QStringHash()
-: newedNodes(nullptr), nodePool(nullptr), link(nullptr)
+: newedNodes(nullptr), nodePool(nullptr)
 {
 }
 
 template<class T>
 QStringHash<T>::QStringHash(const QStringHash<T> &other)
-: newedNodes(nullptr), nodePool(nullptr), link(nullptr)
+: newedNodes(nullptr), nodePool(nullptr)
 {
     data.numBits = other.data.numBits;
     data.size = other.data.size;
@@ -391,41 +400,6 @@ void QStringHash<T>::copyAndReserve(const QStringHash<T> &other, int additionalR
 }
 
 template<class T>
-void QStringHash<T>::linkAndReserve(const QStringHash<T> &other, int additionalReserve)
-{
-    clear();
-
-    if (other.count()) {
-        data.size = other.data.size;
-        data.rehashToSize(other.count() + additionalReserve);
-
-        if (data.numBuckets == other.data.numBuckets) {
-            nodePool = new ReservedNodePool;
-            nodePool->count = additionalReserve;
-            nodePool->used = 0;
-            nodePool->nodes = new Node[additionalReserve];
-
-#ifdef QSTRINGHASH_LINK_DEBUG
-            data.linkCount++;
-            const_cast<QStringHash<T>&>(other).data.linkCount++;
-#endif
-
-            for (int ii = 0; ii < data.numBuckets; ++ii)
-                data.buckets[ii] = (Node *)other.data.buckets[ii];
-
-            link = &other;
-            return;
-        }
-
-        data.size = 0;
-    }
-
-    data.numBits = other.data.numBits;
-    reserve(other.count() + additionalReserve);
-    copy(other);
-}
-
-template<class T>
 QStringHash<T>::~QStringHash()
 {
     clear();
@@ -462,7 +436,6 @@ void QStringHash<T>::clear()
 
     newedNodes = nullptr;
     nodePool = nullptr;
-    link = nullptr;
 }
 
 template<class T>
@@ -484,12 +457,6 @@ int QStringHash<T>::numBuckets() const
 }
 
 template<class T>
-bool QStringHash<T>::isLinked() const
-{
-    return link != 0;
-}
-
-template<class T>
 void QStringHash<T>::initializeNode(Node *node, const QHashedString &key)
 {
     node->length = key.length();
@@ -582,10 +549,10 @@ void QStringHash<T>::copy(const QStringHash<T> &other)
 }
 
 template<class T>
-QStringHashData::IteratorData
-QStringHash<T>::iterateNext(const QStringHashData::IteratorData &d)
+template<typename Data>
+Data QStringHash<T>::iterateNext(const Data &d)
 {
-    QStringHash<T> *This = (QStringHash<T> *)d.p;
+    auto *This = d.p;
     Node *node = (Node *)d.n;
 
     if (This->nodePool && node >= This->nodePool->nodes &&
@@ -601,68 +568,29 @@ QStringHash<T>::iterateNext(const QStringHashData::IteratorData &d)
             node = This->nodePool->nodes + This->nodePool->used - 1;
     }
 
-    if (node == nullptr && This->link)
-        return This->link->iterateFirst();
-
-    QStringHashData::IteratorData rv;
+    Data rv;
     rv.n = node;
     rv.p = d.p;
     return rv;
 }
 
 template<class T>
-QStringHashData::IteratorData QStringHash<T>::iterateFirst() const
+template<typename StringHash, typename Data>
+Data QStringHash<T>::iterateFirst(StringHash *self)
 {
-    Node *n = nullptr;
-    if (newedNodes)
-        n = newedNodes;
-    else if (nodePool && nodePool->used)
-        n = nodePool->nodes + nodePool->used - 1;
+    typename StringHash::Node *n = nullptr;
+    if (self->newedNodes)
+        n = self->newedNodes;
+    else if (self->nodePool && self->nodePool->used)
+        n = self->nodePool->nodes + self->nodePool->used - 1;
 
-    if (n == nullptr && link)
-        return link->iterateFirst();
-
-    QStringHashData::IteratorData rv;
+    Data rv;
     rv.n = n;
-    rv.p = const_cast<QStringHash<T> *>(this);
+    rv.p = self;
     return rv;
 }
 
 template<class T>
-typename QStringHash<T>::ConstIterator QStringHash<T>::iterator(Node *n) const
-{
-    if (!n)
-        return ConstIterator();
-
-    const QStringHash<T> *container = this;
-
-    if (link) {
-        // This node could be in the linked hash
-        if ((n >= nodePool->nodes) && (n < (nodePool->nodes + nodePool->used))) {
-            // The node is in this hash
-        } else if ((n >= link->nodePool->nodes) && (n < (link->nodePool->nodes + link->nodePool->used))) {
-            // The node is in the linked hash
-            container = link;
-        } else {
-            const NewedNode *ln = link->newedNodes;
-            while (ln) {
-                if (ln == n) {
-                    // This node is in the linked hash's newed list
-                    container = link;
-                    break;
-                }
-                ln = ln->nextNewed;
-            }
-        }
-    }
-
-    QStringHashData::IteratorData rv;
-    rv.n = n;
-    rv.p = const_cast<QStringHash<T> *>(container);
-    return ConstIterator(rv);
-}
-
-template<class T>
 typename QStringHash<T>::Node *QStringHash<T>::createNode(const Node &o)
 {
     Node *n = takeNode(o);
@@ -696,11 +624,11 @@ template<class T>
 template<class K>
 void QStringHash<T>::insert(const K &key, const T &value)
 {
-    // If this is a linked hash, we can't rely on owning the node, so we always
-    // create a new one.
-    Node *n = link?nullptr:findNode(key);
-    if (n) n->value = value;
-    else createNode(key, value);
+    Node *n = findNode(key);
+    if (n)
+        n->value = value;
+    else
+        createNode(key, value);
 }
 
 template<class T>
@@ -775,73 +703,9 @@ void QStringHash<T>::reserve(int n)
 }
 
 template<class T>
-QStringHash<T>::ConstIterator::ConstIterator()
-{
-}
-
-template<class T>
-QStringHash<T>::ConstIterator::ConstIterator(const QStringHashData::IteratorData &d)
-: d(d)
-{
-}
-
-template<class T>
-typename QStringHash<T>::ConstIterator &QStringHash<T>::ConstIterator::operator++()
-{
-    d = QStringHash<T>::iterateNext(d);
-    return *this;
-}
-
-template<class T>
-bool QStringHash<T>::ConstIterator::operator==(const ConstIterator &o) const
-{
-    return d.n == o.d.n;
-}
-
-template<class T>
-bool QStringHash<T>::ConstIterator::operator!=(const ConstIterator &o) const
-{
-    return d.n != o.d.n;
-}
-
-template<class T>
-template<typename K>
-bool QStringHash<T>::ConstIterator::equals(const K &key) const
-{
-    return d.n->equals(key);
-}
-
-template<class T>
-QHashedString QStringHash<T>::ConstIterator::key() const
-{
-    Node *n = (Node *)d.n;
-    return n->key();
-}
-template<class T>
-const T &QStringHash<T>::ConstIterator::value() const
-{
-    Node *n = (Node *)d.n;
-    return n->value;
-}
-
-template<class T>
-const T &QStringHash<T>::ConstIterator::operator*() const
-{
-    Node *n = (Node *)d.n;
-    return n->value;
-}
-
-template<class T>
-typename QStringHash<T>::Node *QStringHash<T>::ConstIterator::node() const
-{
-    Node *n = (Node *)d.n;
-    return n;
-}
-
-template<class T>
 typename QStringHash<T>::ConstIterator QStringHash<T>::begin() const
 {
-    return ConstIterator(iterateFirst());
+    return ConstIterator(iterateFirst<const QStringHash<T>, ConstIteratorData>(this));
 }
 
 template<class T>
@@ -854,53 +718,8 @@ template<class T>
 template<class K>
 typename QStringHash<T>::ConstIterator QStringHash<T>::find(const K &key) const
 {
-    return iterator(findNode(key));
-}
-
-template<class T>
-class QStringMultiHash : public QStringHash<T>
-{
-public:
-    typedef typename QStringHash<T>::ConstIterator ConstIterator;
-
-    template<typename K>
-    inline void insert(const K &, const T &);
-
-    inline void insert(const ConstIterator &);
-
-    inline ConstIterator findNext(const ConstIterator &) const;
-};
-
-template<class T>
-template<class K>
-void QStringMultiHash<T>::insert(const K &key, const T &value)
-{
-    // Always create a new node
-    QStringHash<T>::createNode(key, value);
-}
-
-template<class T>
-void QStringMultiHash<T>::insert(const ConstIterator &iter)
-{
-    // Always create a new node
-    QStringHash<T>::createNode(iter.key(), iter.value());
-}
-
-template<class T>
-typename QStringHash<T>::ConstIterator QStringMultiHash<T>::findNext(const ConstIterator &iter) const
-{
-    QStringHashNode *node = iter.node();
-    if (node) {
-        QHashedString key(node->key());
-
-        while ((node = *node->next)) {
-            if (node->equals(key)) {
-                return QStringHash<T>::iterator(static_cast<typename QStringHash<T>::Node *>(node));
-            }
-        }
-    }
-
-    return ConstIterator();
+    Node *n = findNode(key);
+    return n ? ConstIterator(ConstIteratorData(n, this)) : ConstIterator();
 }
 
 QT_END_NAMESPACE
diff --git a/src/qml/qml/qqmlpropertycache_p.h b/src/qml/qml/qqmlpropertycache_p.h
index 7a74579699..7369714f70 100644
--- a/src/qml/qml/qqmlpropertycache_p.h
+++ b/src/qml/qml/qqmlpropertycache_p.h
@@ -57,7 +57,7 @@
 #include "qqmlnotifier_p.h"
 #include <private/qqmlpropertyindex_p.h>
 
-#include <private/qstringhash_p.h>
+#include <private/qlinkedstringhash_p.h>
 #include <QtCore/qvarlengtharray.h>
 #include <QtCore/qvector.h>
 
@@ -191,7 +191,7 @@ private:
     QQmlPropertyCacheMethodArguments *createArgumentsObject(int count, const QList<QByteArray> &names);
 
     typedef QVector<QQmlPropertyData> IndexCache;
-    typedef QStringMultiHash<QPair<int, QQmlPropertyData *> > StringCache;
+    typedef QLinkedStringMultiHash<QPair<int, QQmlPropertyData *> > StringCache;
     typedef QVector<int> AllowedRevisionCache;
 
     QQmlPropertyData *findProperty(StringCache::ConstIterator it, QObject *, QQmlContextData *) const;