diff options
author | Aaron Kennedy <aaron.kennedy@nokia.com> | 2011-07-21 20:01:07 +1000 |
---|---|---|
committer | Qt by Nokia <qt-info@nokia.com> | 2011-08-30 13:18:28 +0200 |
commit | a8cbaf353842779bf79491bf54a6b5b0018d9774 (patch) | |
tree | 8450043b1d531c71b6007c9857f190e1b2ee2d76 | |
parent | a257441a420d850205a5910bc2d3c1aa67bfc3e8 (diff) |
Calculate the hash inside QHashedString
This avoids calling into V8 to calculate the hash. This improves
performance and removes the dependency on V8.
Change-Id: I8ccb405cba15c7eda51a1d56652784164789de7f
Reviewed-on: http://codereview.qt.nokia.com/3765
Reviewed-by: Roberto Raggi <roberto.raggi@nokia.com>
-rw-r--r-- | src/declarative/qml/ftw/qhashedstring.cpp | 92 |
1 files changed, 89 insertions, 3 deletions
diff --git a/src/declarative/qml/ftw/qhashedstring.cpp b/src/declarative/qml/ftw/qhashedstring.cpp index 296d0c4709..41adc26ccf 100644 --- a/src/declarative/qml/ftw/qhashedstring.cpp +++ b/src/declarative/qml/ftw/qhashedstring.cpp @@ -41,9 +41,95 @@ #include "qhashedstring_p.h" -inline unsigned stringHash(const QChar* data, unsigned length) +// This is a reimplementation of V8's string hash algorithm. It is significantly +// faster to do it here than call into V8, but it adds the maintainence burden of +// ensuring that the two hashes are identical. We Q_ASSERT() that the two return +// the same value. If these asserts start to fail, the hash code needs to be +// synced with V8. +namespace String { + static const int kMaxArrayIndexSize = 10; + static const int kMaxHashCalcLength = 16383; + static const int kNofHashBitFields = 2; + static const int kHashShift = kNofHashBitFields; + static const int kIsNotArrayIndexMask = 1 << 1; + static const int kArrayIndexValueBits = 24; + static const int kArrayIndexHashLengthShift = kArrayIndexValueBits + kNofHashBitFields; + static const int kMaxCachedArrayIndexLength = 7; +}; + +template <typename schar> +uint32_t calculateHash(const schar* chars, int length) { + if (length > String::kMaxHashCalcLength) { + // V8 trivial hash + return (length << String::kHashShift) | String::kIsNotArrayIndexMask; + } + + uint32_t raw_running_hash = 0; + uint32_t array_index = 0; + bool is_array_index = (0 < length && length <= String::kMaxArrayIndexSize); + bool is_first_char = true; + + int ii = 0; + for (;is_array_index && ii < length; ++ii) { + quint32 c = *chars++; + + raw_running_hash += c; + raw_running_hash += (raw_running_hash << 10); + raw_running_hash ^= (raw_running_hash >> 6); + + if (c < '0' || c > '9') { + is_array_index = false; + } else { + int d = c - '0'; + if (is_first_char) { + is_first_char = false; + if (c = '0' && length > 1) { + is_array_index = false; + continue; + } + } + if (array_index > 429496729U - ((d + 2) >> 3)) { + is_array_index = false; + } else { + array_index = array_index * 10 + d; + } + } + } + + for (;ii < length; ++ii) { + raw_running_hash += *chars++; + raw_running_hash += (raw_running_hash << 10); + raw_running_hash ^= (raw_running_hash >> 6); + } + + if (is_array_index) { + array_index <<= String::kHashShift; + array_index |= length << String::kArrayIndexHashLengthShift; + return array_index; + } else { + raw_running_hash += (raw_running_hash << 3); + raw_running_hash ^= (raw_running_hash >> 11); + raw_running_hash += (raw_running_hash << 15); + if (raw_running_hash == 0) { + raw_running_hash = 27; + } + + return (raw_running_hash << String::kHashShift) | String::kIsNotArrayIndexMask; + } +} + +inline quint32 stringHash(const QChar* data, int length) { - return v8::String::ComputeHash((uint16_t *)data, length); + quint32 rv = calculateHash<quint16>((quint16*)data, length) >> String::kHashShift; + Q_ASSERT(rv == v8::String::ComputeHash((uint16_t*)data, length)); + return rv; +} + +inline quint32 stringHash(const char *data, int length) +{ + quint32 rv = calculateHash<quint8>((quint8*)data, length) >> String::kHashShift; + Q_ASSERT(rv == v8::String::ComputeHash((char *)data, length)); + return rv; } void QHashedString::computeHash() const @@ -58,7 +144,7 @@ void QHashedStringRef::computeHash() const void QHashedCStringRef::computeHash() const { - m_hash = v8::String::ComputeHash((char *)m_data, m_length); + m_hash = stringHash(m_data, m_length); } /* |