diff options
author | Ulf Hermann <ulf.hermann@qt.io> | 2019-04-26 14:23:21 +0200 |
---|---|---|
committer | Ulf Hermann <ulf.hermann@qt.io> | 2019-04-30 08:24:42 +0000 |
commit | a9886b4bf9ee80f9bc29bc5e8fd801705568f4da (patch) | |
tree | 96c21f6f7c4d63cd3d9a9d0d84e8dedfbab734ea /src/qml | |
parent | 11b3bb4cd898c5a837b41258e37a5012ae5ed863 (diff) |
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>
Diffstat (limited to 'src/qml')
-rw-r--r-- | src/qml/jsruntime/qv4identifier.cpp | 16 | ||||
-rw-r--r-- | src/qml/jsruntime/qv4identifiertable.cpp | 16 | ||||
-rw-r--r-- | src/qml/jsruntime/qv4internalclass.cpp | 13 | ||||
-rw-r--r-- | src/qml/qml/ftw/ftw.pri | 4 | ||||
-rw-r--r-- | src/qml/qml/ftw/qhashedstring.cpp | 54 | ||||
-rw-r--r-- | src/qml/qml/ftw/qprimefornumbits_p.h | 80 | ||||
-rw-r--r-- | src/qml/qml/ftw/qstringhash.cpp | 168 | ||||
-rw-r--r-- | src/qml/qml/ftw/qstringhash_p.h | 69 |
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? |