From f242ef892818f8230c8f3b49d155e0e20fe46679 Mon Sep 17 00:00:00 2001 From: Aaron Kennedy Date: Thu, 14 Jul 2011 15:35:39 +1000 Subject: [PATCH] Improve QStringHash We now support reserving nodes, and keys that are ASCII strings. Change-Id: I9cc04438a1e9ceee1081cb1216e0273227551222 Reviewed-on: http://codereview.qt.nokia.com/3745 Reviewed-by: Roberto Raggi --- src/declarative/qml/ftw/qhashedstring.cpp | 7 +- src/declarative/qml/ftw/qhashedstring_p.h | 379 ++++++++++++++++++--- src/declarative/qml/qdeclarativeengine.cpp | 4 +- src/declarative/qml/qdeclarativepropertycache.cpp | 57 +++- src/declarative/qml/qdeclarativepropertycache_p.h | 2 +- 5 files changed, 378 insertions(+), 71 deletions(-) diff --git a/src/declarative/qml/ftw/qhashedstring.cpp b/src/declarative/qml/ftw/qhashedstring.cpp index 2e2af98..2eaa1bd 100644 --- a/src/declarative/qml/ftw/qhashedstring.cpp +++ b/src/declarative/qml/ftw/qhashedstring.cpp @@ -56,6 +56,11 @@ void QHashedStringRef::computeHash() const m_hash = stringHash(m_data, m_length); } +void QHashedCStringRef::computeHash() const +{ + m_hash = v8::String::ComputeHash((char *)m_data, m_length); +} + /* A QHash has initially around pow(2, MinNumBits) buckets. For example, if MinNumBits is 4, it has 17 buckets. @@ -93,7 +98,7 @@ void QStringHashData::rehash() QStringHashNode *nodeList = nodes; while (nodeList) { - int bucket = nodeList->key.hash() % numBuckets; + int bucket = nodeList->hash % numBuckets; nodeList->next = buckets[bucket]; buckets[bucket] = nodeList; diff --git a/src/declarative/qml/ftw/qhashedstring_p.h b/src/declarative/qml/ftw/qhashedstring_p.h index e0ca1d4..fb79df1 100644 --- a/src/declarative/qml/ftw/qhashedstring_p.h +++ b/src/declarative/qml/ftw/qhashedstring_p.h @@ -120,7 +120,7 @@ public: inline quint32 hash() const; inline const QChar *constData() const; - inline quint32 length() const; + inline int length() const; inline bool startsWithUpper() const; private: @@ -129,7 +129,27 @@ private: void computeHash() const; const QChar *m_data; - quint32 m_length; + int m_length; + mutable quint32 m_hash; +}; + +class QHashedCStringRef +{ +public: + inline QHashedCStringRef(); + inline QHashedCStringRef(const char *, int); + inline QHashedCStringRef(const char *, int, quint32); + inline QHashedCStringRef(const QHashedCStringRef &); + + inline quint32 hash() const; + + inline const char *constData() const; + inline int length() const; +private: + void computeHash() const; + + const char *m_data; + int m_length; mutable quint32 m_hash; }; @@ -137,17 +157,71 @@ class QStringHashData; class QStringHashNode { public: + QStringHashNode() + : nlist(0), next(0), length(0), hash(0), pooled(0), ckey(0), symbolId() + { + } + QStringHashNode(const QHashedString &key) - : nlist(0), next(0), key(key), symbolId(0) { + : nlist(0), next(0), length(key.length()), hash(key.hash()), pooled(0), ckey(0), key(key), symbolId(0) { + } + + QStringHashNode(const QHashedCStringRef &key) + : nlist(0), next(0), length(key.length()), hash(key.hash()), pooled(0), ckey(key.constData()), symbolId(0) { + } + + QStringHashNode(const QStringHashNode &o) + : nlist(0), next(0), length(o.length), hash(o.hash), pooled(0), ckey(o.ckey), key(o.key), symbolId(o.symbolId) { } QStringHashNode *nlist; QStringHashNode *next; - QHashedString key; + qint32 length; + quint32 hash; + + quint32 pooled:1; + const char *ckey; + QString key; + quint32 symbolId; inline bool equals(v8::Handle string) { - return string->Equals((uint16_t*)key.constData(), key.length()); + return ckey?string->Equals((char*)ckey, length): + string->Equals((uint16_t*)key.constData(), length); + } + + inline bool symbolEquals(const QHashedV8String &string) { + Q_ASSERT(string.symbolId() != 0); + return length == string.length() && hash == string.hash() && + (string.symbolId() == symbolId || equals(string.string())); + } + + inline bool equals(const QHashedV8String &string) { + return length == string.length() && hash == string.hash() && + equals(string.string()); + } + + 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))); + } + + 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; } }; @@ -172,16 +246,35 @@ class QStringHash private: 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) {} + Node(const Node &o) : QStringHashNode(o), value(o.value) {} + Node() {} T value; }; + struct ReservedNodePool + { + ReservedNodePool() : count(0), used(0), nodes(0) {} + ~ReservedNodePool() { delete [] nodes; } + int count; + int used; + Node *nodes; + }; QStringHashData data; + ReservedNodePool *nodePool; inline Node *findNode(const QHashedStringRef &) const; + inline Node *findNode(const QHashedCStringRef &) const; inline Node *findNode(const QHashedV8String &) const; inline Node *findSymbolNode(const QHashedV8String &) const; - Node *createNode(const QHashedString &, const T &); + inline Node *createNode(const QHashedString &, const T &); + inline Node *createNode(const QHashedCStringRef &, const T &); + + inline Node *takeNode(const QHashedString &key, const T &value); + inline Node *takeNode(const QHashedCStringRef &key, const T &value); + inline Node *takeNode(const Node &o); + inline void copy(const QStringHash &); public: inline QStringHash(); inline QStringHash(const QStringHash &); @@ -189,6 +282,8 @@ public: QStringHash &operator=(const QStringHash &); + void copyAndReserve(const QStringHash &other, int additionalReserve); + inline bool isEmpty() const; inline void clear(); inline int count() const; @@ -196,19 +291,23 @@ public: inline void insert(const QString &, const T &); inline void insert(const QHashedString &, const T &); inline void insert(const QHashedStringRef &, const T &); + inline void insert(const QHashedCStringRef &, const T &); inline T *value(const QString &) const; inline T *value(const QHashedString &) const; inline T *value(const QHashedStringRef &) const; inline T *value(const QHashedV8String &) const; + inline T *value(const QHashedCStringRef &) const; inline bool contains(const QString &) const; inline bool contains(const QHashedString &) const; inline bool contains(const QHashedStringRef &) const; + inline bool contains(const QHashedCStringRef &) const; T &operator[](const QString &); T &operator[](const QHashedString &); T &operator[](const QHashedStringRef &); + T &operator[](const QHashedCStringRef &); class ConstIterator { public: @@ -219,7 +318,13 @@ public: bool operator==(const ConstIterator &o) const { return n == o.n; } bool operator!=(const ConstIterator &o) const { return n != o.n; } - const QHashedString &key() const { return n->key; } + QHashedString key() const { + if (n->ckey) { + return QHashedString(QString::fromLatin1(n->ckey, n->length), n->hash); + } else { + return QHashedString(n->key, n->hash); + } + } const T &value() const { return n->value; } const T &operator*() const { return n->value; } private: @@ -228,30 +333,22 @@ public: ConstIterator begin() const { return ConstIterator((Node *)data.nodes); } ConstIterator end() const { return ConstIterator(); } + + inline void reserve(int); }; template QStringHash::QStringHash() +: nodePool(0) { } template QStringHash::QStringHash(const QStringHash &other) -: data(other.data) +: data(other.data), nodePool(0) { - data.nodes = 0; - data.buckets = 0; - - QStringHashNode *n = other.data.nodes; - while (n) { - Node *o = (Node *)n; - Node *mynode = new Node(o->key, o->value); - mynode->nlist = data.nodes; - data.nodes = mynode; - n = o->nlist; - } - - data.rehash(); + reserve(other.count()); + copy(other); } template @@ -261,22 +358,22 @@ QStringHash &QStringHash::operator=(const QStringHash &other) return *this; clear(); + data = other.data; - data.nodes = 0; - data.buckets = 0; + reserve(other.count()); + copy(other); - QStringHashNode *n = other.data.nodes; - while (n) { - Node *o = (Node *)n; - Node *mynode = new Node(o->key, o->value); - mynode->nlist = data.nodes; - data.nodes = mynode; - n = o->nlist; - } + return *this; +} - data.rehash(); +template +void QStringHash::copyAndReserve(const QStringHash &other, int additionalReserve) +{ + clear(); - return *this; + data = other.data; + reserve(other.count() + additionalReserve); + copy(other); } template @@ -288,16 +385,21 @@ QStringHash::~QStringHash() template void QStringHash::clear() { - QStringHashNode *n = data.nodes; - while (n) { - Node *o = (Node *)n; - n = n->nlist; - delete o; + // If all the nodes were allocated from the node pool, we + // don't need to clean them individually + if (!nodePool || data.size != nodePool->used) { + QStringHashNode *n = data.nodes; + while (n) { + Node *o = (Node *)n; + n = n->nlist; + if (!o->pooled) delete o; + } } - + if (nodePool) delete nodePool; delete [] data.buckets; data = QStringHashData(); + nodePool = 0; } template @@ -313,12 +415,99 @@ int QStringHash::count() const } template +typename QStringHash::Node *QStringHash::takeNode(const QHashedString &key, const T &value) +{ + if (nodePool && nodePool->used != nodePool->count) { + Node *rv = nodePool->nodes + nodePool->used++; + rv->length = key.length(); + rv->hash = key.hash(); + rv->key = key; + rv->pooled = 1; + rv->value = value; + return rv; + } else { + return new Node(key, 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++; + rv->length = key.length(); + rv->hash = key.hash(); + rv->ckey = key.constData(); + rv->pooled = 1; + rv->value = value; + return rv; + } else { + return new Node(key, value); + } +} + +template +typename QStringHash::Node *QStringHash::takeNode(const Node &o) +{ + if (nodePool && nodePool->used != nodePool->count) { + Node *rv = nodePool->nodes + nodePool->used++; + rv->length = o.length; + rv->hash = o.hash; + rv->ckey = o.ckey; + rv->key = o.key; + rv->pooled = 1; + rv->symbolId = o.symbolId; + rv->value = o.value; + return rv; + } else { + return new Node(o); + } +} + +template +void QStringHash::copy(const QStringHash &other) +{ + data.nodes = 0; + data.buckets = 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; + } + + data.rehash(); +} + +template typename QStringHash::Node *QStringHash::createNode(const QHashedString &key, const T &value) { if (data.size == data.numBuckets) data.rehash(); - Node *n = new Node(key, value); + 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; + + data.size++; + + return n; +} + +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; @@ -357,12 +546,33 @@ void QStringHash::insert(const QHashedStringRef &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 { QStringHashNode *node = 0; if (data.numBuckets) { node = data.buckets[string.hash() % data.numBuckets]; - while (node && !(node->key == string)) + while (node && !node->equals(string)) + node = node->next; + } + + return (Node *)node; +} + +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; } @@ -376,8 +586,7 @@ typename QStringHash::Node *QStringHash::findNode(const QHashedV8String &s if (data.numBuckets) { quint32 hash = string.hash(); node = data.buckets[hash % data.numBuckets]; - int length = string.length(); - while (node && (length != node->key.length() || hash != node->key.hash() || !node->equals(string.string()))) + while (node && !node->equals(string)) node = node->next; } @@ -392,14 +601,12 @@ typename QStringHash::Node *QStringHash::findSymbolNode(const QHashedV8Str QStringHashNode *node = 0; if (data.numBuckets) { quint32 hash = string.hash(); - quint32 symbolId = string.symbolId(); node = data.buckets[hash % data.numBuckets]; - int length = string.length(); - while (node && (length != node->key.length() || hash != node->key.hash() || - !(node->symbolId == symbolId || node->equals(string.string())))) + while (node && !node->symbolEquals(string)) node = node->next; + if (node) - node->symbolId = symbolId; + node->symbolId = string.symbolId(); } return (Node *)node; @@ -427,6 +634,13 @@ T *QStringHash::value(const QHashedStringRef &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 { Node *n = string.symbolId()?findSymbolNode(string):findNode(string); @@ -444,6 +658,7 @@ bool QStringHash::contains(const QHashedString &s) const { return 0 != value(s); } + template bool QStringHash::contains(const QHashedStringRef &s) const { @@ -451,6 +666,12 @@ bool QStringHash::contains(const QHashedStringRef &s) const } template +bool QStringHash::contains(const QHashedCStringRef &s) const +{ + return 0 != value(s); +} + +template T &QStringHash::operator[](const QString &key) { QHashedStringRef cs(key); @@ -475,6 +696,25 @@ T &QStringHash::operator[](const QHashedStringRef &key) else return createNode(key, T())->value; } +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) +{ + if (nodePool || 0 == n) + return; + nodePool = new ReservedNodePool; + nodePool->count = n; + nodePool->used = 0; + nodePool->nodes = new Node[n]; +} + inline uint qHash(const QHashedString &string) { return uint(string.hash()); @@ -520,7 +760,7 @@ bool QHashedString::operator==(const QHashedString &string) const bool QHashedString::operator==(const QHashedStringRef &string) const { - return (uint)length() == string.m_length && + 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)); } @@ -625,7 +865,7 @@ QHashedStringRef::QHashedStringRef(const QHashedStringRef &string) bool QHashedStringRef::operator==(const QHashedString &string) const { - return m_length == (uint)string.length() && + 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)); } @@ -642,7 +882,7 @@ const QChar *QHashedStringRef::constData() const return m_data; } -quint32 QHashedStringRef::length() const +int QHashedStringRef::length() const { return m_length; } @@ -659,6 +899,43 @@ quint32 QHashedStringRef::hash() const return m_hash; } +QHashedCStringRef::QHashedCStringRef() +: m_data(0), m_length(0), m_hash(0) +{ +} + +QHashedCStringRef::QHashedCStringRef(const char *data, int length) +: m_data(data), m_length(length), m_hash(0) +{ +} + +QHashedCStringRef::QHashedCStringRef(const char *data, int length, quint32 hash) +: m_data(data), m_length(length), m_hash(hash) +{ +} + +QHashedCStringRef::QHashedCStringRef(const QHashedCStringRef &o) +: m_data(o.m_data), m_length(o.m_length), m_hash(o.m_hash) +{ +} + +quint32 QHashedCStringRef::hash() const +{ + if (!m_hash) computeHash(); + return m_hash; +} + +const char *QHashedCStringRef::constData() const +{ + return m_data; +} + +int QHashedCStringRef::length() const +{ + return m_length; +} + + QT_END_NAMESPACE #endif // QHASHEDSTRING_P_H diff --git a/src/declarative/qml/qdeclarativeengine.cpp b/src/declarative/qml/qdeclarativeengine.cpp index c61849a..f6d4832 100644 --- a/src/declarative/qml/qdeclarativeengine.cpp +++ b/src/declarative/qml/qdeclarativeengine.cpp @@ -1424,7 +1424,9 @@ QDeclarativePropertyCache *QDeclarativeEnginePrivate::createCache(const QMetaObj return rv; } else { QDeclarativePropertyCache *super = cache(mo->superClass()); - QDeclarativePropertyCache *rv = super->copy(); + QDeclarativePropertyCache *rv = super->copy(mo->propertyCount() + mo->methodCount() - + mo->superClass()->propertyCount() - + mo->superClass()->methodCount()); rv->append(q, mo); propertyCache.insert(mo, rv); return rv; diff --git a/src/declarative/qml/qdeclarativepropertycache.cpp b/src/declarative/qml/qdeclarativepropertycache.cpp index d2148ad..0d44b58 100644 --- a/src/declarative/qml/qdeclarativepropertycache.cpp +++ b/src/declarative/qml/qdeclarativepropertycache.cpp @@ -278,14 +278,14 @@ QDeclarativePropertyCache::Data QDeclarativePropertyCache::create(const QMetaObj return rv; } -QDeclarativePropertyCache *QDeclarativePropertyCache::copy() +QDeclarativePropertyCache *QDeclarativePropertyCache::copy(int reserve) { QDeclarativePropertyCache *cache = new QDeclarativePropertyCache(engine); cache->parent = this; cache->parent->addref(); cache->propertyIndexCacheStart = propertyIndexCache.count() + propertyIndexCacheStart; cache->methodIndexCacheStart = methodIndexCache.count() + methodIndexCacheStart; - cache->stringCache = stringCache; + cache->stringCache.copyAndReserve(stringCache, reserve); cache->allowedRevisionCache = allowedRevisionCache; // We specifically do *NOT* copy the constructor @@ -324,10 +324,8 @@ void QDeclarativePropertyCache::append(QDeclarativeEngine *engine, const QMetaOb // Extract method name const char *signature = m.signature(); const char *cptr = signature; - while (*cptr != '(') { Q_ASSERT(*cptr != 0); ++cptr; } - QString str = dynamicMetaObject?QString::fromUtf8(signature, cptr - signature): - QString::fromLatin1(signature, cptr - signature); - QHashedString methodName(str); + bool utf8 = false; + while (*cptr != '(') { Q_ASSERT(*cptr != 0); utf8 |= *cptr & 0x80; ++cptr; } Data *data = &methodIndexCache[ii - methodIndexCacheStart]; @@ -342,15 +340,25 @@ void QDeclarativePropertyCache::append(QDeclarativeEngine *engine, const QMetaOb data->metaObjectOffset = allowedRevisionCache.count() - 1; - if (Data **old = stringCache.value(methodName)) { + Data **old = 0; + + if (utf8) { + QHashedString methodName(QString::fromUtf8(signature, cptr - signature)); + old = stringCache.value(methodName); + stringCache.insert(methodName, data); + } else { + QHashedCStringRef methodName(signature, cptr - signature); + old = stringCache.value(methodName); + stringCache.insert(methodName, data); + } + + if (old) { // We only overload methods in the same class, exactly like C++ if ((*old)->flags & Data::IsFunction && (*old)->coreIndex >= methodOffset) data->relatedIndex = (*old)->coreIndex; data->overrideIndexIsProperty = !bool((*old)->flags & Data::IsFunction); data->overrideIndex = (*old)->coreIndex; } - - stringCache.insert(methodName, data); } int propCount = metaObject->propertyCount(); @@ -362,9 +370,10 @@ void QDeclarativePropertyCache::append(QDeclarativeEngine *engine, const QMetaOb if (!p.isScriptable()) continue; - QString str = dynamicMetaObject?QString::fromUtf8(p.name()): - QString::fromLatin1(p.name()); - QHashedString propName(str); + const char *str = p.name(); + bool utf8 = false; + const char *cptr = str; + while (*cptr != 0) { utf8 |= *cptr & 0x80; ++cptr; } Data *data = &propertyIndexCache[ii - propertyIndexCacheStart]; @@ -376,12 +385,22 @@ void QDeclarativePropertyCache::append(QDeclarativeEngine *engine, const QMetaOb data->metaObjectOffset = allowedRevisionCache.count() - 1; - if (Data **old = stringCache.value(propName)) { + Data **old = 0; + + if (utf8) { + QHashedString propName(QString::fromUtf8(str, cptr - str)); + old = stringCache.value(propName); + stringCache.insert(propName, data); + } else { + QHashedCStringRef propName(str, cptr - str); + old = stringCache.value(propName); + stringCache.insert(propName, data); + } + + if (old) { data->overrideIndexIsProperty = !bool((*old)->flags & Data::IsFunction); data->overrideIndex = (*old)->coreIndex; } - - stringCache.insert(propName, data); } } @@ -417,8 +436,12 @@ void QDeclarativePropertyCache::update(QDeclarativeEngine *engine, const QMetaOb Q_ASSERT(stringCache.isEmpty()); // Optimization to prevent unnecessary reallocation of lists - propertyIndexCache.reserve(metaObject->propertyCount()); - methodIndexCache.reserve(metaObject->methodCount()); + int pc = metaObject->propertyCount(); + int mc = metaObject->methodCount(); + propertyIndexCache.reserve(pc); + methodIndexCache.reserve(mc); + + stringCache.reserve(pc + mc); updateRecur(engine,metaObject); } diff --git a/src/declarative/qml/qdeclarativepropertycache_p.h b/src/declarative/qml/qdeclarativepropertycache_p.h index cdbd493..7e677a5 100644 --- a/src/declarative/qml/qdeclarativepropertycache_p.h +++ b/src/declarative/qml/qdeclarativepropertycache_p.h @@ -172,7 +172,7 @@ public: void update(QDeclarativeEngine *, const QMetaObject *); - QDeclarativePropertyCache *copy(); + QDeclarativePropertyCache *copy(int reserve = 0); void append(QDeclarativeEngine *, const QMetaObject *, Data::Flag propertyFlags = Data::NoFlags, Data::Flag methodFlags = Data::NoFlags, Data::Flag signalFlags = Data::NoFlags); void append(QDeclarativeEngine *, const QMetaObject *, int revision, Data::Flag propertyFlags = Data::NoFlags, -- 1.7.2.5