From fcb55f3a289f911299f92509287be97723ddbf50 Mon Sep 17 00:00:00 2001 From: Aaron Kennedy Date: Fri, 15 Jul 2011 16:28:40 +1000 Subject: [PATCH] QStringHash improvements Change-Id: I1844460095f4de4980d458dc696c0aab8b504c23 Reviewed-on: http://codereview.qt.nokia.com/3746 Reviewed-by: Roberto Raggi --- src/declarative/qml/ftw/qhashedstring.cpp | 73 ++++++- src/declarative/qml/ftw/qhashedstring_p.h | 387 +++++++++++++++++------------ 2 files changed, 295 insertions(+), 165 deletions(-) diff --git a/src/declarative/qml/ftw/qhashedstring.cpp b/src/declarative/qml/ftw/qhashedstring.cpp index 2eaa1bd..936f818 100644 --- a/src/declarative/qml/ftw/qhashedstring.cpp +++ b/src/declarative/qml/ftw/qhashedstring.cpp @@ -87,10 +87,24 @@ static inline int primeForNumBits(int numBits) return (1 << numBits) + prime_deltas[numBits]; } -void QStringHashData::rehash() +void QStringHashData::rehashToSize(int size) { - numBits = qMax(MinNumBits, numBits + 1); - numBuckets = primeForNumBits(numBits); + 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; + + numBuckets = nb; delete [] buckets; buckets = new QStringHashNode *[numBuckets]; @@ -106,3 +120,56 @@ void QStringHashData::rehash() } } +// 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; + + register 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 + register 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 + register const quint16 *e = sa.w + length; + for ( ; sa.w != e; ++sa.w, ++sb.w) { + if (*sa.w != *sb.w) + return false; + } + } + return true; +} diff --git a/src/declarative/qml/ftw/qhashedstring_p.h b/src/declarative/qml/ftw/qhashedstring_p.h index fb79df1..bfca8da 100644 --- a/src/declarative/qml/ftw/qhashedstring_p.h +++ b/src/declarative/qml/ftw/qhashedstring_p.h @@ -60,7 +60,7 @@ QT_BEGIN_NAMESPACE class QHashedStringRef; -class QHashedString : public QString +class Q_AUTOTEST_EXPORT QHashedString : public QString { public: inline QHashedString(); @@ -78,12 +78,17 @@ public: static inline bool isUpper(const QChar &); private: friend class QHashedStringRef; + friend class QStringHashNode; void computeHash() const; mutable quint32 m_hash; + + static bool compare(const QChar *lhs, const QChar *rhs, int length); + static inline bool compare(const QChar *lhs, const char *rhs, int length); + static inline bool compare(const char *lhs, const char *rhs, int length); }; -class QHashedV8String +class Q_AUTOTEST_EXPORT QHashedV8String { public: inline QHashedV8String(); @@ -104,7 +109,7 @@ private: v8::Handle m_string; }; -class QHashedStringRef +class Q_AUTOTEST_EXPORT QHashedStringRef { public: inline QHashedStringRef(); @@ -133,7 +138,7 @@ private: mutable quint32 m_hash; }; -class QHashedCStringRef +class Q_AUTOTEST_EXPORT QHashedCStringRef { public: inline QHashedCStringRef(); @@ -154,7 +159,7 @@ private: }; class QStringHashData; -class QStringHashNode +class Q_AUTOTEST_EXPORT QStringHashNode { public: QStringHashNode() @@ -203,29 +208,20 @@ public: inline bool equals(const QHashedStringRef &string) { return length == string.length() && - hash == string.hash() && - ckey?(cstrCompare(string.constData(), ckey, length)): - (0 == ::memcmp(string.constData(), key.constData(), length * sizeof(QChar))); + hash == string.hash() && + ckey?(QHashedString::compare(string.constData(), ckey, length)): + (QHashedString::compare(string.constData(), key.constData(), length)); } inline bool equals(const QHashedCStringRef &string) { return length == string.length() && - hash == string.hash() && - ckey?(0 == ::memcmp(string.constData(), ckey, length)): - (cstrCompare(key.constData(), string.constData(), length)); - } - -private: - static inline bool cstrCompare(const QChar *lhsChar, const char *rhs, int length) { - Q_ASSERT(lhsChar && rhs); - const uint16_t *lhs = (const uint16_t*)lhsChar; - while (length--) - if (*lhs++ != *rhs++) return false; - return true; + hash == string.hash() && + ckey?(QHashedString::compare(string.constData(), ckey, length)): + (QHashedString::compare(key.constData(), string.constData(), length)); } }; -struct QStringHashData +struct Q_AUTOTEST_EXPORT QStringHashData { public: QStringHashData() @@ -237,13 +233,18 @@ public: int size; short numBits; - void rehash(); + void rehashToBits(short); + void rehashToSize(int); + +private: + QStringHashData(const QStringHashData &); + QStringHashData &operator=(const QStringHashData &); }; -template -class QStringHash +template +class Q_AUTOTEST_EXPORT QStringHash { -private: +public: 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) {} @@ -263,6 +264,8 @@ private: QStringHashData data; ReservedNodePool *nodePool; + inline Node *findNode(const QString &) const; + inline Node *findNode(const QHashedString &) const; inline Node *findNode(const QHashedStringRef &) const; inline Node *findNode(const QHashedCStringRef &) const; inline Node *findNode(const QHashedV8String &) const; @@ -274,15 +277,15 @@ private: inline Node *takeNode(const QHashedCStringRef &key, const T &value); inline Node *takeNode(const Node &o); - inline void copy(const QStringHash &); + inline void copy(const QStringHash &); public: inline QStringHash(); inline QStringHash(const QStringHash &); inline ~QStringHash(); - QStringHash &operator=(const QStringHash &); + QStringHash &operator=(const QStringHash &); - void copyAndReserve(const QStringHash &other, int additionalReserve); + void copyAndReserve(const QStringHash &other, int additionalReserve); inline bool isEmpty() const; inline void clear(); @@ -337,53 +340,57 @@ public: inline void reserve(int); }; -template -QStringHash::QStringHash() +template +QStringHash::QStringHash() : nodePool(0) { } -template -QStringHash::QStringHash(const QStringHash &other) -: data(other.data), nodePool(0) +template +QStringHash::QStringHash(const QStringHash &other) +: nodePool(0) { + data.numBits = other.data.numBits; + data.size = other.data.size; reserve(other.count()); copy(other); } -template -QStringHash &QStringHash::operator=(const QStringHash &other) +template +QStringHash &QStringHash::operator=(const QStringHash &other) { if (&other == this) return *this; clear(); - data = other.data; + data.numBits = other.data.numBits; + data.size = other.data.size; reserve(other.count()); copy(other); return *this; } -template -void QStringHash::copyAndReserve(const QStringHash &other, int additionalReserve) +template +void QStringHash::copyAndReserve(const QStringHash &other, int additionalReserve) { clear(); - data = other.data; + data.numBits = other.data.numBits; + data.size = other.data.size;; reserve(other.count() + additionalReserve); copy(other); } -template -QStringHash::~QStringHash() +template +QStringHash::~QStringHash() { clear(); } -template -void QStringHash::clear() +template +void QStringHash::clear() { // If all the nodes were allocated from the node pool, we // don't need to clean them individually @@ -398,24 +405,28 @@ void QStringHash::clear() if (nodePool) delete nodePool; delete [] data.buckets; - data = QStringHashData(); + data.nodes = 0; + data.buckets = 0; + data.numBuckets = 0; + data.numBits = 0; + nodePool = 0; } -template -bool QStringHash::isEmpty() const +template +bool QStringHash::isEmpty() const { return data.nodes == 0; } -template -int QStringHash::count() const +template +int QStringHash::count() const { return data.size; } -template -typename QStringHash::Node *QStringHash::takeNode(const QHashedString &key, const T &value) +template +typename QStringHash::Node *QStringHash::takeNode(const QHashedString &key, const T &value) { if (nodePool && nodePool->used != nodePool->count) { Node *rv = nodePool->nodes + nodePool->used++; @@ -430,8 +441,8 @@ typename QStringHash::Node *QStringHash::takeNode(const QHashedString &key } } -template -typename QStringHash::Node *QStringHash::takeNode(const QHashedCStringRef &key, const T &value) +template +typename QStringHash::Node *QStringHash::takeNode(const QHashedCStringRef &key, const T &value) { if (nodePool && nodePool->used != nodePool->count) { Node *rv = nodePool->nodes + nodePool->used++; @@ -446,8 +457,8 @@ typename QStringHash::Node *QStringHash::takeNode(const QHashedCStringRef } } -template -typename QStringHash::Node *QStringHash::takeNode(const Node &o) +template +typename QStringHash::Node *QStringHash::takeNode(const Node &o) { if (nodePool && nodePool->used != nodePool->count) { Node *rv = nodePool->nodes + nodePool->used++; @@ -464,64 +475,101 @@ typename QStringHash::Node *QStringHash::takeNode(const Node &o) } } -template -void QStringHash::copy(const QStringHash &other) +template +void QStringHash::copy(const QStringHash &other) { - data.nodes = 0; - data.buckets = 0; + Q_ASSERT(data.nodes == 0); + Q_ASSERT(data.size == 0); - QStringHashNode *n = other.data.nodes; - while (n) { - Node *o = (Node *)n; - Node *mynode = takeNode(*o); - mynode->nlist = data.nodes; - data.nodes = mynode; - n = o->nlist; - } + if (other.data.size <= SmallThreshold) { + QStringHashNode *n = other.data.nodes; + while (n) { + Node *o = (Node *)n; + Node *mynode = takeNode(*o); + mynode->nlist = data.nodes; + mynode->next = data.nodes; + data.nodes = mynode; + + n = o->nlist; + } + } else { + // Ensure buckets array is created + data.rehashToBits(data.numBits); - data.rehash(); + QStringHashNode *n = other.data.nodes; + while (n) { + Node *o = (Node *)n; + Node *mynode = takeNode(*o); + mynode->nlist = data.nodes; + data.nodes = mynode; + + int bucket = mynode->hash % data.numBuckets; + mynode->next = data.buckets[bucket]; + data.buckets[bucket] = mynode; + + n = o->nlist; + } + } } -template -typename QStringHash::Node *QStringHash::createNode(const QHashedString &key, const T &value) +template +typename QStringHash::Node *QStringHash::createNode(const QHashedString &key, const T &value) { - if (data.size == data.numBuckets) - data.rehash(); - Node *n = takeNode(key, value); - n->nlist = data.nodes; - data.nodes = n; - int bucket = key.hash() % data.numBuckets; - n->next = data.buckets[bucket]; - data.buckets[bucket] = n; + if (data.size < SmallThreshold) { + + n->nlist = data.nodes; + n->next = data.nodes; + data.nodes = n; + + } else { + if (data.size >= data.numBuckets) + data.rehashToBits(data.numBits + 1); + + n->nlist = data.nodes; + data.nodes = n; + + int bucket = key.hash() % data.numBuckets; + n->next = data.buckets[bucket]; + data.buckets[bucket] = n; + } data.size++; return n; } -template -typename QStringHash::Node *QStringHash::createNode(const QHashedCStringRef &key, const T &value) +template +typename QStringHash::Node *QStringHash::createNode(const QHashedCStringRef &key, const T &value) { - if (data.size == data.numBuckets) - data.rehash(); - Node *n = takeNode(key, value); - n->nlist = data.nodes; - data.nodes = n; - int bucket = key.hash() % data.numBuckets; - n->next = data.buckets[bucket]; - data.buckets[bucket] = n; + if (data.size < SmallThreshold) { + + n->nlist = data.nodes; + n->next = data.nodes; + data.nodes = n; + + } else { + if (data.size >= data.numBuckets) + data.rehashToBits(data.numBits + 1); + + n->nlist = data.nodes; + data.nodes = n; + + int bucket = key.hash() % data.numBuckets; + n->next = data.buckets[bucket]; + data.buckets[bucket] = n; + } data.size++; return n; } -template -void QStringHash::insert(const QString &key, const T &value) +template +void QStringHash::insert(const QString &key, const T &value) { QHashedStringRef ch(key); Node *n = findNode(key); @@ -529,150 +577,148 @@ void QStringHash::insert(const QString &key, const T &value) else createNode(QHashedString(key, ch.hash()), value); } -template -void QStringHash::insert(const QHashedString &key, const T &value) +template +void QStringHash::insert(const QHashedString &key, const T &value) { Node *n = findNode(key); if (n) n->value = value; else createNode(key, value); } -template -void QStringHash::insert(const QHashedStringRef &key, const T &value) +template +void QStringHash::insert(const QHashedStringRef &key, const T &value) { Node *n = findNode(key); if (n) n->value = value; else createNode(key, value); } -template -void QStringHash::insert(const QHashedCStringRef &key, const T &value) +template +void QStringHash::insert(const QHashedCStringRef &key, const T &value) { Node *n = findNode(key); if (n) n->value = value; else createNode(key, value); } -template -typename QStringHash::Node *QStringHash::findNode(const QHashedStringRef &string) const +template +typename QStringHash::Node *QStringHash::findNode(const QString &string) const +{ + return findNode(QHashedStringRef(string)); +} + +template +typename QStringHash::Node *QStringHash::findNode(const QHashedString &string) const +{ + return findNode(QHashedStringRef(string.constData(), string.length(), string.hash())); +} + +template +typename QStringHash::Node *QStringHash::findNode(const QHashedStringRef &string) const { - QStringHashNode *node = 0; - if (data.numBuckets) { - node = data.buckets[string.hash() % data.numBuckets]; - while (node && !node->equals(string)) - node = node->next; - } + QStringHashNode *node = (data.size <= SmallThreshold)?data.nodes:data.buckets[string.hash() % data.numBuckets]; + while (node && !node->equals(string)) + node = node->next; return (Node *)node; } -template -typename QStringHash::Node *QStringHash::findNode(const QHashedCStringRef &string) const +template +typename QStringHash::Node *QStringHash::findNode(const QHashedCStringRef &string) const { - QStringHashNode *node = 0; - if (data.numBuckets) { - node = data.buckets[string.hash() % data.numBuckets]; - while (node && !node->equals(string)) - node = node->next; - } + QStringHashNode *node = (data.size <= SmallThreshold)?data.nodes:data.buckets[string.hash() % data.numBuckets]; + while (node && !node->equals(string)) + node = node->next; return (Node *)node; } -template -typename QStringHash::Node *QStringHash::findNode(const QHashedV8String &string) const +template +typename QStringHash::Node *QStringHash::findNode(const QHashedV8String &string) const { - QStringHashNode *node = 0; - if (data.numBuckets) { - quint32 hash = string.hash(); - node = data.buckets[hash % data.numBuckets]; - while (node && !node->equals(string)) - node = node->next; - } + QStringHashNode *node = (data.size <= SmallThreshold)?data.nodes:data.buckets[string.hash() % data.numBuckets]; + while (node && !node->equals(string)) + node = node->next; return (Node *)node; } -template -typename QStringHash::Node *QStringHash::findSymbolNode(const QHashedV8String &string) const +template +typename QStringHash::Node *QStringHash::findSymbolNode(const QHashedV8String &string) const { Q_ASSERT(string.symbolId() != 0); - QStringHashNode *node = 0; - if (data.numBuckets) { - quint32 hash = string.hash(); - node = data.buckets[hash % data.numBuckets]; - while (node && !node->symbolEquals(string)) - node = node->next; + QStringHashNode *node = (data.size <= SmallThreshold)?data.nodes:data.buckets[string.hash() % data.numBuckets]; + while (node && !node->symbolEquals(string)) + node = node->next; - if (node) - node->symbolId = string.symbolId(); - } + if (node) + node->symbolId = string.symbolId(); return (Node *)node; } -template -T *QStringHash::value(const QString &key) const +template +T *QStringHash::value(const QString &key) const { Node *n = findNode(key); return n?&n->value:0; } -template -T *QStringHash::value(const QHashedString &key) const +template +T *QStringHash::value(const QHashedString &key) const { Node *n = findNode(key); return n?&n->value:0; } -template -T *QStringHash::value(const QHashedStringRef &key) const +template +T *QStringHash::value(const QHashedStringRef &key) const { Node *n = findNode(key); return n?&n->value:0; } -template -T *QStringHash::value(const QHashedCStringRef &key) const +template +T *QStringHash::value(const QHashedCStringRef &key) const { Node *n = findNode(key); return n?&n->value:0; } -template -T *QStringHash::value(const QHashedV8String &string) const +template +T *QStringHash::value(const QHashedV8String &string) const { Node *n = string.symbolId()?findSymbolNode(string):findNode(string); return n?&n->value:0; } -template -bool QStringHash::contains(const QString &s) const +template +bool QStringHash::contains(const QString &s) const { return 0 != value(s); } -template -bool QStringHash::contains(const QHashedString &s) const +template +bool QStringHash::contains(const QHashedString &s) const { return 0 != value(s); } -template -bool QStringHash::contains(const QHashedStringRef &s) const +template +bool QStringHash::contains(const QHashedStringRef &s) const { return 0 != value(s); } -template -bool QStringHash::contains(const QHashedCStringRef &s) const +template +bool QStringHash::contains(const QHashedCStringRef &s) const { return 0 != value(s); } -template -T &QStringHash::operator[](const QString &key) +template +T &QStringHash::operator[](const QString &key) { QHashedStringRef cs(key); Node *n = findNode(cs); @@ -680,32 +726,32 @@ T &QStringHash::operator[](const QString &key) else return createNode(QHashedString(key, cs.hash()), T())->value; } -template -T &QStringHash::operator[](const QHashedString &key) +template +T &QStringHash::operator[](const QHashedString &key) { Node *n = findNode(key); if (n) return n->value; else return createNode(key, T())->value; } -template -T &QStringHash::operator[](const QHashedStringRef &key) +template +T &QStringHash::operator[](const QHashedStringRef &key) { Node *n = findNode(key); if (n) return n->value; else return createNode(key, T())->value; } -template -T &QStringHash::operator[](const QHashedCStringRef &key) +template +T &QStringHash::operator[](const QHashedCStringRef &key) { Node *n = findNode(key); if (n) return n->value; else return createNode(key, T())->value; } -template -void QStringHash::reserve(int n) +template +void QStringHash::reserve(int n) { if (nodePool || 0 == n) return; @@ -713,6 +759,9 @@ void QStringHash::reserve(int n) nodePool->count = n; nodePool->used = 0; nodePool->nodes = new Node[n]; + + if (n > SmallThreshold) + data.rehashToSize(n); } inline uint qHash(const QHashedString &string) @@ -762,7 +811,7 @@ bool QHashedString::operator==(const QHashedStringRef &string) const { return length() == string.m_length && (string.m_hash == m_hash || !string.m_hash || !m_hash) && - 0 == ::memcmp(constData(), string.m_data, string.m_length * sizeof(QChar)); + QHashedString::compare(constData(), string.m_data, string.m_length); } quint32 QHashedString::hash() const @@ -867,14 +916,14 @@ bool QHashedStringRef::operator==(const QHashedString &string) const { return m_length == string.length() && (m_hash == string.m_hash || !m_hash || !string.m_hash) && - 0 == ::memcmp(string.constData(), m_data, m_length * sizeof(QChar)); + QHashedString::compare(string.constData(), m_data, m_length); } bool QHashedStringRef::operator==(const QHashedStringRef &string) const { return m_length == string.m_length && (m_hash == string.m_hash || !m_hash || !string.m_hash) && - 0 == ::memcmp(string.m_data, m_data, m_length * sizeof(QChar)); + QHashedString::compare(string.m_data, m_data, m_length); } const QChar *QHashedStringRef::constData() const @@ -935,6 +984,20 @@ int QHashedCStringRef::length() const return m_length; } +bool QHashedString::compare(const QChar *lhs, const char *rhs, int length) +{ + Q_ASSERT(lhs && rhs); + const quint16 *l = (const quint16*)lhs; + while (length--) + if (*l++ != *rhs++) return false; + return true; +} + +bool QHashedString::compare(const char *lhs, const char *rhs, int length) +{ + Q_ASSERT(lhs && rhs); + return 0 == ::memcmp(lhs, rhs, length); +} QT_END_NAMESPACE -- 1.7.2.5