Clean up QStringHash

Make it completely inline, move the (4 times duplicated) primeForNumBits
function into its own file, address some warnings, move
QHashedString::compare into qhashedstring.cpp.

Change-Id: I778bb3d3e176cfec45eda9be9d7e5982585e6474
Reviewed-by: Simon Hausmann <simon.hausmann@qt.io>

8 files changed, 203 insertions, 217 deletions

diff --git a/src/qml/jsruntime/qv4identifier.cpp b/src/qml/jsruntime/qv4identifier.cpp
index 5db5bd46ec..f9bc7b68c6 100644
--- a/src/qml/jsruntime/qv4identifier.cpp
+++ b/src/qml/jsruntime/qv4identifier.cpp
@@ -39,29 +39,19 @@
 #include "qv4identifier_p.h"
 #include "qv4identifiertable_p.h"
 #include "qv4string_p.h"
+#include <private/qprimefornumbits_p.h>
 
 QT_BEGIN_NAMESPACE
 
 namespace QV4 {
 
-static const uchar prime_deltas[] = {
-    0,  0,  1,  3,  1,  5,  3,  3,  1,  9,  7,  5,  3,  9, 25,  3,
-    1, 21,  3, 21,  7, 15,  9,  5,  3, 29, 15,  0,  0,  0,  0,  0
-};
-
-static inline int primeForNumBits(int numBits)
-{
-    return (1 << numBits) + prime_deltas[numBits];
-}
-
-
 IdentifierHashData::IdentifierHashData(IdentifierTable *table, int numBits)
     : size(0)
     , numBits(numBits)
     , identifierTable(table)
 {
     refCount.store(1);
-    alloc = primeForNumBits(numBits);
+    alloc = qPrimeForNumBits(numBits);
     entries = (IdentifierHashEntry *)malloc(alloc*sizeof(IdentifierHashEntry));
     memset(entries, 0, alloc*sizeof(IdentifierHashEntry));
     identifierTable->addIdentifierHash(this);
@@ -110,7 +100,7 @@ IdentifierHashEntry *IdentifierHash::addEntry(PropertyKey identifier)
 
     if (grow) {
         ++d->numBits;
-        int newAlloc = primeForNumBits(d->numBits);
+        int newAlloc = qPrimeForNumBits(d->numBits);
         IdentifierHashEntry *newEntries = (IdentifierHashEntry *)malloc(newAlloc * sizeof(IdentifierHashEntry));
         memset(newEntries, 0, newAlloc*sizeof(IdentifierHashEntry));
         for (int i = 0; i < d->alloc; ++i) {
diff --git a/src/qml/jsruntime/qv4identifiertable.cpp b/src/qml/jsruntime/qv4identifiertable.cpp
index ae937b2889..21b47c3909 100644
--- a/src/qml/jsruntime/qv4identifiertable.cpp
+++ b/src/qml/jsruntime/qv4identifiertable.cpp
@@ -38,28 +38,18 @@
 ****************************************************************************/
 #include "qv4identifiertable_p.h"
 #include "qv4symbol_p.h"
+#include <private/qprimefornumbits_p.h>
 
 QT_BEGIN_NAMESPACE
 
 namespace QV4 {
 
-static const uchar prime_deltas[] = {
-    0,  0,  1,  3,  1,  5,  3,  3,  1,  9,  7,  5,  3,  9, 25,  3,
-    1, 21,  3, 21,  7, 15,  9,  5,  3, 29, 15,  0,  0,  0,  0,  0
-};
-
-static inline int primeForNumBits(int numBits)
-{
-    return (1 << numBits) + prime_deltas[numBits];
-}
-
-
 IdentifierTable::IdentifierTable(ExecutionEngine *engine, int numBits)
     : engine(engine)
     , size(0)
     , numBits(numBits)
 {
-    alloc = primeForNumBits(numBits);
+    alloc = qPrimeForNumBits(numBits);
     entriesByHash = (Heap::StringOrSymbol **)malloc(alloc*sizeof(Heap::StringOrSymbol *));
     entriesById = (Heap::StringOrSymbol **)malloc(alloc*sizeof(Heap::StringOrSymbol *));
     memset(entriesByHash, 0, alloc*sizeof(Heap::String *));
@@ -87,7 +77,7 @@ void IdentifierTable::addEntry(Heap::StringOrSymbol *str)
 
     if (grow) {
         ++numBits;
-        int newAlloc = primeForNumBits(numBits);
+        int newAlloc = qPrimeForNumBits(numBits);
         Heap::StringOrSymbol **newEntries = (Heap::StringOrSymbol **)malloc(newAlloc*sizeof(Heap::String *));
         memset(newEntries, 0, newAlloc*sizeof(Heap::StringOrSymbol *));
         for (uint i = 0; i < alloc; ++i) {
diff --git a/src/qml/jsruntime/qv4internalclass.cpp b/src/qml/jsruntime/qv4internalclass.cpp
index a10fda79f2..d597335031 100644
--- a/src/qml/jsruntime/qv4internalclass.cpp
+++ b/src/qml/jsruntime/qv4internalclass.cpp
@@ -45,27 +45,18 @@
 #include "qv4identifiertable_p.h"
 #include "qv4value_p.h"
 #include "qv4mm_p.h"
+#include <private/qprimefornumbits_p.h>
 
 QT_BEGIN_NAMESPACE
 
 namespace QV4 {
 
-static const uchar prime_deltas[] = {
-    0,  0,  1,  3,  1,  5,  3,  3,  1,  9,  7,  5,  3,  9, 25,  3,
-    1, 21,  3, 21,  7, 15,  9,  5,  3, 29, 15,  0,  0,  0,  0,  0
-};
-
-static inline int primeForNumBits(int numBits)
-{
-    return (1 << numBits) + prime_deltas[numBits];
-}
-
 PropertyHashData::PropertyHashData(int numBits)
     : refCount(1)
     , size(0)
     , numBits(numBits)
 {
-    alloc = primeForNumBits(numBits);
+    alloc = qPrimeForNumBits(numBits);
     entries = (PropertyHash::Entry *)malloc(alloc*sizeof(PropertyHash::Entry));
     memset(entries, 0, alloc*sizeof(PropertyHash::Entry));
 }
diff --git a/src/qml/qml/ftw/ftw.pri b/src/qml/qml/ftw/ftw.pri
index 0bb8cb954e..eadba394b4 100644
--- a/src/qml/qml/ftw/ftw.pri
+++ b/src/qml/qml/ftw/ftw.pri
@@ -3,6 +3,7 @@ HEADERS +=  \
     $$PWD/qintrusivelist_p.h \
     $$PWD/qpodvector_p.h \
     $$PWD/qhashedstring_p.h \
+    $$PWD/qprimefornumbits_p.h \
     $$PWD/qqmlrefcount_p.h \
     $$PWD/qfieldlist_p.h \
     $$PWD/qqmlthread_p.h \
@@ -18,8 +19,7 @@ HEADERS +=  \
 SOURCES += \
     $$PWD/qintrusivelist.cpp \
     $$PWD/qhashedstring.cpp \
-    $$PWD/qqmlthread.cpp \
-    $$PWD/qstringhash.cpp
+    $$PWD/qqmlthread.cpp
 
 # mirrors logic in $$QT_SOURCE_TREE/config.tests/unix/clock-gettime/clock-gettime.pri
 # clock_gettime() is implemented in librt on these systems
diff --git a/src/qml/qml/ftw/qhashedstring.cpp b/src/qml/qml/ftw/qhashedstring.cpp
index bb6688599d..7a8fdd0a14 100644
--- a/src/qml/qml/ftw/qhashedstring.cpp
+++ b/src/qml/qml/ftw/qhashedstring.cpp
@@ -41,6 +41,60 @@
 
 QT_BEGIN_NAMESPACE
 
+// Copy of QString's qMemCompare
+bool QHashedString::compare(const QChar *lhs, const QChar *rhs, int length)
+{
+    Q_ASSERT(lhs && rhs);
+    const quint16 *a = (const quint16 *)lhs;
+    const quint16 *b = (const quint16 *)rhs;
+
+    if (a == b || !length)
+        return true;
+
+    union {
+        const quint16 *w;
+        const quint32 *d;
+        quintptr value;
+    } sa, sb;
+    sa.w = a;
+    sb.w = b;
+
+    // check alignment
+    if ((sa.value & 2) == (sb.value & 2)) {
+        // both addresses have the same alignment
+        if (sa.value & 2) {
+            // both addresses are not aligned to 4-bytes boundaries
+            // compare the first character
+            if (*sa.w != *sb.w)
+                return false;
+            --length;
+            ++sa.w;
+            ++sb.w;
+
+            // now both addresses are 4-bytes aligned
+        }
+
+        // both addresses are 4-bytes aligned
+        // do a fast 32-bit comparison
+        const quint32 *e = sa.d + (length >> 1);
+        for ( ; sa.d != e; ++sa.d, ++sb.d) {
+            if (*sa.d != *sb.d)
+                return false;
+        }
+
+        // do we have a tail?
+        return (length & 1) ? *sa.w == *sb.w : true;
+    } else {
+        // one of the addresses isn't 4-byte aligned but the other is
+        const quint16 *e = sa.w + length;
+        for ( ; sa.w != e; ++sa.w, ++sb.w) {
+            if (*sa.w != *sb.w)
+                return false;
+        }
+    }
+    return true;
+}
+
 QHashedStringRef QHashedStringRef::mid(int offset, int length) const
 {
     Q_ASSERT(offset < m_length);
diff --git a/src/qml/qml/ftw/qprimefornumbits_p.h b/src/qml/qml/ftw/qprimefornumbits_p.h
new file mode 100644
index 0000000000..6e9acbf7fd
--- /dev/null
+++ b/src/qml/qml/ftw/qprimefornumbits_p.h
@@ -0,0 +1,80 @@
+/****************************************************************************
+**
+** 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 QPRIMEFORNUMBITS_P_H
+#define QPRIMEFORNUMBITS_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/qtqmlglobal_p.h>
+
+QT_BEGIN_NAMESPACE
+
+/*
+    The prime_deltas array is a table of selected prime values, even
+    though it doesn't look like one. The primes we are using are 1,
+    2, 5, 11, 17, 37, 67, 131, 257, ..., i.e. primes in the immediate
+    surrounding of a power of two.
+
+    The qPrimeForNumBits() function returns the prime associated to a
+    power of two. For example, qPrimeForNumBits(8) returns 257.
+*/
+
+inline int qPrimeForNumBits(int numBits)
+{
+    static constexpr const uchar prime_deltas[] = {
+        0,  0,  1,  3,  1,  5,  3,  3,  1,  9,  7,  5,  3,  9, 25,  3,
+        1, 21,  3, 21,  7, 15,  9,  5,  3, 29, 15,  0,  0,  0,  0,  0
+    };
+
+    return (1 << numBits) + prime_deltas[numBits];
+}
+
+QT_END_NAMESPACE
+
+#endif // QPRIMEFORNUMBITS_P_H
diff --git a/src/qml/qml/ftw/qstringhash.cpp b/src/qml/qml/ftw/qstringhash.cpp
deleted file mode 100644
index a483dcb810..0000000000
--- a/src/qml/qml/ftw/qstringhash.cpp
+++ /dev/null
@@ -1,168 +0,0 @@
-/****************************************************************************
-**
-** 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$
-**
-****************************************************************************/
-
-#include "qstringhash_p.h"
-
-QT_BEGIN_NAMESPACE
-
-/*
-    A QHash has initially around pow(2, MinNumBits) buckets. For
-    example, if MinNumBits is 4, it has 17 buckets.
-*/
-static const int MinNumBits = 4;
-
-/*
-    The prime_deltas array is a table of selected prime values, even
-    though it doesn't look like one. The primes we are using are 1,
-    2, 5, 11, 17, 37, 67, 131, 257, ..., i.e. primes in the immediate
-    surrounding of a power of two.
-
-    The primeForNumBits() function returns the prime associated to a
-    power of two. For example, primeForNumBits(8) returns 257.
-*/
-
-static const uchar prime_deltas[] = {
-    0,  0,  1,  3,  1,  5,  3,  3,  1,  9,  7,  5,  3,  9, 25,  3,
-    1, 21,  3, 21,  7, 15,  9,  5,  3, 29, 15,  0,  0,  0,  0,  0
-};
-
-static inline int primeForNumBits(int numBits)
-{
-    return (1 << numBits) + prime_deltas[numBits];
-}
-
-void QStringHashData::rehashToSize(int size)
-{
-    short bits = qMax(MinNumBits, (int)numBits);
-    while (primeForNumBits(bits) < size) bits++;
-
-    if (bits > numBits)
-        rehashToBits(bits);
-}
-
-void QStringHashData::rehashToBits(short bits)
-{
-    numBits = qMax(MinNumBits, (int)bits);
-
-    int nb = primeForNumBits(numBits);
-    if (nb == numBuckets && buckets)
-        return;
-
-    QStringHashNode **newBuckets = new QStringHashNode *[nb];
-    ::memset(newBuckets, 0, sizeof(QStringHashNode *) * nb);
-
-    // Preserve the existing order within buckets so that items with the
-    // same key will retain the same find/findNext order
-    for (int i = 0; i < numBuckets; ++i) {
-        QStringHashNode *bucket = buckets[i];
-        if (bucket)
-            rehashNode(newBuckets, nb, bucket);
-    }
-
-    delete [] buckets;
-    buckets = newBuckets;
-    numBuckets = nb;
-}
-
-void QStringHashData::rehashNode(QStringHashNode **newBuckets, int nb, QStringHashNode *node)
-{
-    QStringHashNode *next = node->next.data();
-    if (next)
-        rehashNode(newBuckets, nb, next);
-
-    int bucket = node->hash % nb;
-    node->next = newBuckets[bucket];
-    newBuckets[bucket] = node;
-}
-
-// Copy of QString's qMemCompare
-bool QHashedString::compare(const QChar *lhs, const QChar *rhs, int length)
-{
-    Q_ASSERT(lhs && rhs);
-    const quint16 *a = (const quint16 *)lhs;
-    const quint16 *b = (const quint16 *)rhs;
-
-    if (a == b || !length)
-        return true;
-
-    union {
-        const quint16 *w;
-        const quint32 *d;
-        quintptr value;
-    } sa, sb;
-    sa.w = a;
-    sb.w = b;
-
-    // check alignment
-    if ((sa.value & 2) == (sb.value & 2)) {
-        // both addresses have the same alignment
-        if (sa.value & 2) {
-            // both addresses are not aligned to 4-bytes boundaries
-            // compare the first character
-            if (*sa.w != *sb.w)
-                return false;
-            --length;
-            ++sa.w;
-            ++sb.w;
-
-            // now both addresses are 4-bytes aligned
-        }
-
-        // both addresses are 4-bytes aligned
-        // do a fast 32-bit comparison
-        const quint32 *e = sa.d + (length >> 1);
-        for ( ; sa.d != e; ++sa.d, ++sb.d) {
-            if (*sa.d != *sb.d)
-                return false;
-        }
-
-        // do we have a tail?
-        return (length & 1) ? *sa.w == *sb.w : true;
-    } else {
-        // one of the addresses isn't 4-byte aligned but the other is
-        const quint16 *e = sa.w + length;
-        for ( ; sa.w != e; ++sa.w, ++sb.w) {
-            if (*sa.w != *sb.w)
-                return false;
-        }
-    }
-    return true;
-}
-
-QT_END_NAMESPACE
diff --git a/src/qml/qml/ftw/qstringhash_p.h b/src/qml/qml/ftw/qstringhash_p.h
index c7251e8837..f9435b4919 100644
--- a/src/qml/qml/ftw/qstringhash_p.h
+++ b/src/qml/qml/ftw/qstringhash_p.h
@@ -52,11 +52,14 @@
 //
 
 #include <private/qhashedstring_p.h>
+#include <private/qprimefornumbits_p.h>
+
+#include <QtCore/qglobal.h>
 
 QT_BEGIN_NAMESPACE
 
 class QStringHashData;
-class Q_AUTOTEST_EXPORT QStringHashNode
+class QStringHashNode
 {
 public:
     QStringHashNode()
@@ -154,12 +157,20 @@ public:
     }
 };
 
-class Q_AUTOTEST_EXPORT QStringHashData
+class QStringHashData
 {
+    Q_DISABLE_COPY_MOVE(QStringHashData)
 public:
-    QStringHashData() {}
+    QStringHashData() = default;
+    ~QStringHashData() = default;
+
+    /*
+        A QHash has initially around pow(2, MinNumBits) buckets. For
+        example, if MinNumBits is 4, it has 17 buckets.
+    */
+    enum { MinNumBits = 4 };
 
-    QStringHashNode **buckets = nullptr;
+    QStringHashNode **buckets = nullptr; // life cycle managed by QStringHash
     int numBuckets = 0;
     int size = 0;
     short numBits = 0;
@@ -174,13 +185,51 @@ public:
         QStringHashNode *n;
         StringHash *p;
     };
-    void rehashToBits(short);
-    void rehashToSize(int);
-    void rehashNode(QStringHashNode **newBuckets, int nb, QStringHashNode *node);
 
-private:
-    QStringHashData(const QStringHashData &);
-    QStringHashData &operator=(const QStringHashData &);
+    void rehashToBits(short bits)
+    {
+        numBits = qMax(short(MinNumBits), bits);
+
+        int nb = qPrimeForNumBits(numBits);
+        if (nb == numBuckets && buckets)
+            return;
+
+        QStringHashNode **newBuckets = new QStringHashNode *[nb];
+        ::memset(newBuckets, 0, sizeof(QStringHashNode *) * nb);
+
+        // Preserve the existing order within buckets so that items with the
+        // same key will retain the same find/findNext order
+        for (int i = 0; i < numBuckets; ++i) {
+            QStringHashNode *bucket = buckets[i];
+            if (bucket)
+                rehashNode(newBuckets, nb, bucket);
+        }
+
+        delete [] buckets;
+        buckets = newBuckets;
+        numBuckets = nb;
+    }
+
+    void rehashToSize(int size)
+    {
+        short bits = qMax(short(MinNumBits), numBits);
+        while (qPrimeForNumBits(bits) < size)
+            bits++;
+
+        if (bits > numBits)
+            rehashToBits(bits);
+    }
+
+    void rehashNode(QStringHashNode **newBuckets, int nb, QStringHashNode *node)
+    {
+        QStringHashNode *next = node->next.data();
+        if (next)
+            rehashNode(newBuckets, nb, next);
+
+        int bucket = node->hash % nb;
+        node->next = newBuckets[bucket];
+        newBuckets[bucket] = node;
+    }
 };
 
 // For a supplied key type, in what form do we need to keep a hashed version?