From acc54f9c0a6367edddb1fb2bba40b3341f9b384c Mon Sep 17 00:00:00 2001 From: Aaron Kennedy Date: Tue, 7 Feb 2012 13:29:52 +0000 Subject: Reduce the memory used by QStringHash This change reduces the memory consumed by individual QStringHashNodes, and adds support for "linking" one hash to another that allows us to avoid copying all the nodes. Change-Id: Ib5bd151d8ec610a020fd125f46a4e218d959529b Reviewed-by: Martin Jones --- src/declarative/qml/ftw/qhashedstring.cpp | 29 +- src/declarative/qml/ftw/qhashedstring_p.h | 719 +++++++++++++++------- src/declarative/qml/qdeclarativepropertycache.cpp | 5 +- src/declarative/qml/v8/qv8qobjectwrapper.cpp | 12 + 4 files changed, 533 insertions(+), 232 deletions(-) (limited to 'src') diff --git a/src/declarative/qml/ftw/qhashedstring.cpp b/src/declarative/qml/ftw/qhashedstring.cpp index 13b0e55390..f3b5a9ebc9 100644 --- a/src/declarative/qml/ftw/qhashedstring.cpp +++ b/src/declarative/qml/ftw/qhashedstring.cpp @@ -173,16 +173,20 @@ static inline int primeForNumBits(int numBits) return (1 << numBits) + prime_deltas[numBits]; } -void QStringHashData::rehashToSize(int size) +void QStringHashData::rehashToSize(int size, IteratorData first, + IteratorData (*Iterate)(const IteratorData &), + QStringHashNode *skip) { short bits = qMax(MinNumBits, (int)numBits); while (primeForNumBits(bits) < size) bits++; if (bits > numBits) - rehashToBits(bits); + rehashToBits(bits, first, Iterate, skip); } -void QStringHashData::rehashToBits(short bits) +void QStringHashData::rehashToBits(short bits, IteratorData first, + IteratorData (*Iterate)(const IteratorData &), + QStringHashNode *skip) { numBits = qMax(MinNumBits, (int)bits); @@ -192,17 +196,24 @@ void QStringHashData::rehashToBits(short bits) numBuckets = nb; +#ifdef QSTRINGHASH_LINK_DEBUG + if (linkCount) + qFatal("QStringHash: Illegal attempt to rehash a linked hash."); +#endif + delete [] buckets; buckets = new QStringHashNode *[numBuckets]; ::memset(buckets, 0, sizeof(QStringHashNode *) * numBuckets); - QStringHashNode *nodeList = nodes; - while (nodeList) { - int bucket = nodeList->hash % numBuckets; - nodeList->next = buckets[bucket]; - buckets[bucket] = nodeList; + IteratorData nodeList = first; + while (nodeList.n) { + if (nodeList.n != skip) { + int bucket = nodeList.n->hash % numBuckets; + nodeList.n->next = buckets[bucket]; + buckets[bucket] = nodeList.n; + } - nodeList = nodeList->nlist; + nodeList = Iterate(nodeList); } } diff --git a/src/declarative/qml/ftw/qhashedstring_p.h b/src/declarative/qml/ftw/qhashedstring_p.h index 68485999c1..b778dd4df2 100644 --- a/src/declarative/qml/ftw/qhashedstring_p.h +++ b/src/declarative/qml/ftw/qhashedstring_p.h @@ -57,8 +57,13 @@ #include #include +#include + QT_BEGIN_NAMESPACE +// Enable this to debug hash linking assumptions. +// #define QSTRINGHASH_LINK_DEBUG + class QHashedStringRef; class Q_AUTOTEST_EXPORT QHashedString : public QString { @@ -194,40 +199,55 @@ class Q_AUTOTEST_EXPORT QStringHashNode { public: QStringHashNode() - : nlist(0), next(0), length(0), hash(0), pooled(0), ckey(0), ukey(0), symbolId() + : length(0), hash(0), symbolId(0), ckey(0) { } QStringHashNode(const QHashedString &key) - : nlist(0), next(0), length(key.length()), hash(key.hash()), pooled(0), ckey(0), key(key), - ukey(key.constData()), symbolId(0) { + : length(key.length()), hash(key.hash()), symbolId(0) + { + strData = const_cast(key).data_ptr(); + setQString(true); + strData->ref.ref(); } QStringHashNode(const QHashedCStringRef &key) - : nlist(0), next(0), length(key.length()), hash(key.hash()), pooled(0), ckey(key.constData()), - ukey(0), symbolId(0) { + : length(key.length()), hash(key.hash()), symbolId(0), ckey(key.constData()) + { } QStringHashNode(const QStringHashNode &o) - : nlist(0), next(0), length(o.length), hash(o.hash), pooled(0), ckey(o.ckey), key(o.key), - ukey(o.ukey), symbolId(o.symbolId) { + : length(o.length), hash(o.hash), symbolId(o.symbolId), ckey(o.ckey) + { + setQString(o.isQString()); + if (isQString()) { strData->ref.ref(); } } - QStringHashNode *nlist; - QStringHashNode *next; + ~QStringHashNode() + { + if (isQString()) { if (!strData->ref.deref()) free(strData); } + } + + QFlagPointer next; + qint32 length; quint32 hash; - - quint32 pooled:1; - const char *ckey; - QString key; - const QChar *ukey; - quint32 symbolId; + union { + const char *ckey; + QStringData *strData; + }; + + bool isQString() const { return next.flag(); } + void setQString(bool v) { if (v) next.setFlag(); else next.clearFlag(); } + + inline char *cStrData() const { return (char *)ckey; } + inline uint16_t *utf16Data() const { return (uint16_t *)strData->data(); } + inline bool equals(v8::Handle string) { - return ckey?string->Equals((char*)ckey, length): - string->Equals((uint16_t*)ukey, length); + return isQString()?string->Equals(utf16Data(), length): + string->Equals(cStrData(), length); } inline bool symbolEquals(const QHashedV8String &string) { @@ -244,15 +264,15 @@ public: inline bool equals(const QHashedStringRef &string) { return length == string.length() && hash == string.hash() && - (ckey?(QHashedString::compare(string.constData(), ckey, length)): - (QHashedString::compare(string.constData(), ukey, length))); + (isQString()?QHashedString::compare(string.constData(), (QChar *)utf16Data(), length): + QHashedString::compare(string.constData(), cStrData(), length)); } inline bool equals(const QHashedCStringRef &string) { return length == string.length() && hash == string.hash() && - (ckey?(QHashedString::compare(string.constData(), ckey, length)): - (QHashedString::compare(ukey, string.constData(), length))); + (isQString()?QHashedString::compare((QChar *)utf16Data(), string.constData(), length): + QHashedString::compare(string.constData(), cStrData(), length)); } }; @@ -260,23 +280,36 @@ class Q_AUTOTEST_EXPORT QStringHashData { public: QStringHashData() - : nodes(0), buckets(0), numBuckets(0), size(0), numBits(0) {} + : buckets(0), numBuckets(0), size(0), numBits(0) +#ifdef QSTRINGHASH_LINK_DEBUG + , linkCount(0) +#endif + {} - QStringHashNode *nodes; QStringHashNode **buckets; int numBuckets; int size; short numBits; - - void rehashToBits(short); - void rehashToSize(int); +#ifdef QSTRINGHASH_LINK_DEBUG + int linkCount; +#endif + + struct IteratorData { + IteratorData() : n(0), p(0) {} + QStringHashNode *n; + void *p; + }; + void rehashToBits(short, IteratorData, IteratorData (*Iterate)(const IteratorData &), + QStringHashNode *skip = 0); + void rehashToSize(int, IteratorData, IteratorData (*Iterate)(const IteratorData &), + QStringHashNode *skip = 0); private: QStringHashData(const QStringHashData &); QStringHashData &operator=(const QStringHashData &); }; -template +template class QStringHash { public: @@ -287,6 +320,12 @@ public: Node() {} T value; }; + struct NewedNode : public Node { + NewedNode(const QHashedString &key, const T &value) : Node(key, value), nextNewed(0) {} + NewedNode(const QHashedCStringRef &key, const T &value) : Node(key, value), nextNewed(0) {} + NewedNode(const Node &o) : Node(o), nextNewed(0) {} + NewedNode *nextNewed; + }; struct ReservedNodePool { ReservedNodePool() : count(0), used(0), nodes(0) {} @@ -297,7 +336,9 @@ public: }; QStringHashData data; + NewedNode *newedNodes; ReservedNodePool *nodePool; + const QStringHash *link; inline Node *findNode(const QString &) const; inline Node *findNode(const QHashedString &) const; @@ -305,6 +346,7 @@ public: inline Node *findNode(const QHashedCStringRef &) const; inline Node *findNode(const QHashedV8String &) const; inline Node *findSymbolNode(const QHashedV8String &) const; + inline Node *createNode(const Node &o); inline Node *createNode(const QHashedString &, const T &); inline Node *createNode(const QHashedCStringRef &, const T &); @@ -312,78 +354,86 @@ public: 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 &); + + inline QStringHashData::IteratorData iterateFirst() const; + static inline QStringHashData::IteratorData iterateNext(const QStringHashData::IteratorData &); + 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); + void linkAndReserve(const QStringHash &other, int additionalReserve); inline bool isEmpty() const; inline void clear(); inline int count() const; + inline int numBuckets() const; + inline bool isLinked() const; + + class ConstIterator { + public: + inline ConstIterator(); + inline ConstIterator(const QStringHashData::IteratorData &); + + inline ConstIterator &operator++(); + + inline bool operator==(const ConstIterator &o) const; + inline bool operator!=(const ConstIterator &o) const; + + inline QHashedString key() const; + inline const T &value() const; + inline const T &operator*() const; + + inline Node *node() const; + private: + QStringHashData::IteratorData d; + }; + 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 void insert(const ConstIterator &); 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 T *value(const ConstIterator &) 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; + inline bool contains(const ConstIterator &) const; - T &operator[](const QString &); - T &operator[](const QHashedString &); - T &operator[](const QHashedStringRef &); - T &operator[](const QHashedCStringRef &); + inline T &operator[](const QString &); + inline T &operator[](const QHashedString &); + inline T &operator[](const QHashedStringRef &); + inline T &operator[](const QHashedCStringRef &); - class ConstIterator { - public: - ConstIterator() : n(0) {} - ConstIterator(Node *n) : n(n) {} - - ConstIterator &operator++() { n = (Node *)n->nlist; return *this; } - bool operator==(const ConstIterator &o) const { return n == o.n; } - bool operator!=(const ConstIterator &o) const { return n != o.n; } - - 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: - Node *n; - }; - - ConstIterator begin() const { return ConstIterator((Node *)data.nodes); } - ConstIterator end() const { return ConstIterator(); } + inline ConstIterator begin() const; + inline ConstIterator end() const; inline void reserve(int); }; -template -QStringHash::QStringHash() -: nodePool(0) +template +QStringHash::QStringHash() +: newedNodes(0), nodePool(0), link(0) { } -template -QStringHash::QStringHash(const QStringHash &other) -: nodePool(0) +template +QStringHash::QStringHash(const QStringHash &other) +: newedNodes(0), nodePool(0), link(0) { data.numBits = other.data.numBits; data.size = other.data.size; @@ -391,8 +441,8 @@ QStringHash::QStringHash(const QStringHash & copy(other); } -template -QStringHash &QStringHash::operator=(const QStringHash &other) +template +QStringHash &QStringHash::operator=(const QStringHash &other) { if (&other == this) return *this; @@ -407,287 +457,423 @@ QStringHash &QStringHash::operator=(const QS return *this; } -template -void QStringHash::copyAndReserve(const QStringHash &other, int additionalReserve) +template +void QStringHash::copyAndReserve(const QStringHash &other, int additionalReserve) +{ + clear(); + data.numBits = other.data.numBits; + reserve(other.count() + additionalReserve); + copy(other); +} + +template +void QStringHash::linkAndReserve(const QStringHash &other, int additionalReserve) { clear(); + if (other.count()) { + data.size = other.data.size; + data.rehashToSize(other.count() + additionalReserve, iterateFirst(), iterateNext); + + if (data.numBuckets == other.data.numBuckets) { + nodePool = new ReservedNodePool; + nodePool->count = additionalReserve; + nodePool->used = 0; + nodePool->nodes = new Node[additionalReserve]; + +#ifdef QSTRINGHASH_LINK_DEBUG + data.linkCount++; + const_cast&>(other).data.linkCount++; +#endif + + for (int ii = 0; ii < data.numBuckets; ++ii) { + data.buckets[ii] = 0; + Node *n = (Node *)other.data.buckets[ii]; + data.buckets[ii] = n; + } + + link = &other; + return; + } + + data.size = 0; + } + 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 - if (!nodePool || data.size != nodePool->used) { - QStringHashNode *n = data.nodes; - while (n) { - Node *o = (Node *)n; - n = n->nlist; - if (!o->pooled) delete o; - } +#ifdef QSTRINGHASH_LINK_DEBUG + if (link) { + data.linkCount--; + const_cast *>(link)->data.linkCount--; } + + if (data.linkCount) + qFatal("QStringHash: Illegal attempt to clear a linked hash."); +#endif + + // Delete the individually allocated nodes + NewedNode *n = newedNodes; + while (n) { + NewedNode *c = n; + n = c->nextNewed; + delete c; + } + // Delete the pool allocated nodes if (nodePool) delete nodePool; delete [] data.buckets; - data.nodes = 0; data.buckets = 0; data.numBuckets = 0; data.numBits = 0; data.size = 0; + newedNodes = 0; nodePool = 0; + link = 0; } -template -bool QStringHash::isEmpty() const +template +bool QStringHash::isEmpty() const { - return data.nodes == 0; + return data.size== 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 +int QStringHash::numBuckets() const +{ + return data.numBuckets; +} + +template +bool QStringHash::isLinked() const +{ + return link != 0; +} + +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->ukey = rv->key.constData(); - rv->pooled = 1; + rv->strData = const_cast(key).data_ptr(); + rv->strData->ref.ref(); + rv->setQString(true); rv->value = value; return rv; } else { - return new Node(key, value); + NewedNode *rv = new NewedNode(key, value); + rv->nextNewed = newedNodes; + newedNodes = rv; + return rv; } } -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++; 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); + NewedNode *rv = new NewedNode(key, value); + rv->nextNewed = newedNodes; + newedNodes = rv; + return rv; } } -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++; rv->length = o.length; rv->hash = o.hash; - rv->ckey = o.ckey; - rv->key = o.key; - rv->ukey = o.ukey; - rv->pooled = 1; + if (o.isQString()) { + rv->strData = o.strData; + rv->strData->ref.ref(); + rv->setQString(true); + } else { + rv->ckey = o.ckey; + } rv->symbolId = o.symbolId; rv->value = o.value; return rv; } else { - return new Node(o); + NewedNode *rv = new NewedNode(o); + rv->nextNewed = newedNodes; + newedNodes = rv; + return rv; } } -template -void QStringHash::copy(const QStringHash &other) +template +void QStringHash::copy(const QStringHash &other) { - Q_ASSERT(data.nodes == 0); + Q_ASSERT(data.size == 0); - 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; + data.size = other.data.size; - n = o->nlist; + // Ensure buckets array is created + data.rehashToBits(data.numBits, iterateFirst(), iterateNext); + + if (other.link) { + for (ConstIterator iter = other.begin(); iter != other.end(); ++iter) { + Node *o = iter.node(); + Node *n = o->isQString()?findNode(QHashedStringRef((QChar *)o->strData->data(), o->length, o->hash)): + findNode(QHashedCStringRef(o->ckey, o->length, o->hash)); + if (!n) { + Node *mynode = takeNode(*o); + int bucket = mynode->hash % data.numBuckets; + mynode->next = data.buckets[bucket]; + data.buckets[bucket] = mynode; + } } } else { - // Ensure buckets array is created - data.rehashToBits(data.numBits); - - QStringHashNode *n = other.data.nodes; - while (n) { - Node *o = (Node *)n; + for (ConstIterator iter = other.begin(); iter != other.end(); ++iter) { + Node *o = iter.node(); 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 +QStringHashData::IteratorData +QStringHash::iterateNext(const QStringHashData::IteratorData &d) { - Node *n = takeNode(key, value); + QStringHash *This = (QStringHash *)d.p; + Node *node = (Node *)d.n; - if (data.size < SmallThreshold) { + if (This->nodePool && node >= This->nodePool->nodes && + node < (This->nodePool->nodes + This->nodePool->used)) { + node--; + if (node < This->nodePool->nodes) + node = 0; + } else { + NewedNode *nn = (NewedNode *)node; + node = nn->nextNewed; - n->nlist = data.nodes; - n->next = data.nodes; - data.nodes = n; + if (node == 0 && This->nodePool && This->nodePool->used) + node = This->nodePool->nodes + This->nodePool->used - 1; + } - } else { - if (data.size >= data.numBuckets) - data.rehashToBits(data.numBits + 1); + if (node == 0 && This->link) + return This->link->iterateFirst(); - n->nlist = data.nodes; - data.nodes = n; + QStringHashData::IteratorData rv; + rv.n = node; + rv.p = d.p; + return rv; +} - int bucket = key.hash() % data.numBuckets; - n->next = data.buckets[bucket]; - data.buckets[bucket] = n; - } +template +QStringHashData::IteratorData QStringHash::iterateFirst() const +{ + Node *n = 0; + if (newedNodes) + n = newedNodes; + else if (nodePool && nodePool->used) + n = nodePool->nodes + nodePool->used - 1; - data.size++; + if (n == 0 && link) + return link->iterateFirst(); + + QStringHashData::IteratorData rv; + rv.n = n; + rv.p = const_cast *>(this); + return rv; +} + +template +typename QStringHash::Node *QStringHash::createNode(const Node &o) +{ + Node *n = takeNode(o); + + if (data.size >= data.numBuckets) + data.rehashToBits(data.numBits + 1, iterateFirst(), iterateNext, n); + + int bucket = n->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 QHashedString &key, const T &value) { Node *n = takeNode(key, value); - if (data.size < SmallThreshold) { + if (data.size >= data.numBuckets) + data.rehashToBits(data.numBits + 1, iterateFirst(), iterateNext, n); - n->nlist = data.nodes; - n->next = data.nodes; - data.nodes = n; + int bucket = key.hash() % data.numBuckets; + n->next = data.buckets[bucket]; + data.buckets[bucket] = n; - } else { - if (data.size >= data.numBuckets) - data.rehashToBits(data.numBits + 1); + data.size++; - n->nlist = data.nodes; - data.nodes = n; + return n; +} - int bucket = key.hash() % data.numBuckets; - n->next = data.buckets[bucket]; - data.buckets[bucket] = n; - } +template +typename QStringHash::Node *QStringHash::createNode(const QHashedCStringRef &key, const T &value) +{ + Node *n = takeNode(key, value); + + if (data.size >= data.numBuckets) + data.rehashToBits(data.numBits + 1, iterateFirst(), iterateNext, 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); + // If this is a linked hash, we can't rely on owning the node, so we always + // create a new one. + Node *n = link?0:findNode(key); if (n) n->value = 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 this is a linked hash, we can't rely on owning the node, so we always + // create a new one. + Node *n = link?0: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 this is a linked hash, we can't rely on owning the node, so we always + // create a new one. + Node *n = link?0: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 this is a linked hash, we can't rely on owning the node, so we always + // create a new one. + Node *n = link?0:findNode(key); if (n) n->value = value; else createNode(key, value); } -template -typename QStringHash::Node *QStringHash::findNode(const QString &string) const +template +void QStringHash::insert(const ConstIterator &key) +{ + // If this is a linked hash, we can't rely on owning the node, so we always + // create a new one. + if (key.node()->isQString()) { + QHashedStringRef str((QChar *)key.node()->strData->data(), key.node()->length, + key.node()->hash); + + Node *n = link?0:findNode(str); + if (n) n->value = key.node()->value; + else createNode(*key.node()); + } else { + QHashedCStringRef str(key.node()->ckey, key.node()->length, key.node()->hash); + + Node *n = link?0:findNode(str); + if (n) n->value = key.node()->value; + else createNode(str, key.node()->value); + } +} + +template +typename QStringHash::Node *QStringHash::findNode(const QString &string) const { return findNode(QHashedStringRef(string)); } -template -typename QStringHash::Node *QStringHash::findNode(const QHashedString &string) const +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 +template +typename QStringHash::Node *QStringHash::findNode(const QHashedStringRef &string) const { - QStringHashNode *node = (data.size <= SmallThreshold)?data.nodes:data.buckets[string.hash() % data.numBuckets]; + QStringHashNode *node = data.numBuckets?data.buckets[string.hash() % data.numBuckets]:0; while (node && !node->equals(string)) - node = node->next; + 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 = (data.size <= SmallThreshold)?data.nodes:data.buckets[string.hash() % data.numBuckets]; + QStringHashNode *node = data.numBuckets?data.buckets[string.hash() % data.numBuckets]:0; while (node && !node->equals(string)) - node = node->next; + 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 = (data.size <= SmallThreshold)?data.nodes:data.buckets[string.hash() % data.numBuckets]; + QStringHashNode *node = data.numBuckets?data.buckets[string.hash() % data.numBuckets]:0; while (node && !node->equals(string)) - node = node->next; + 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 = (data.size <= SmallThreshold)?data.nodes:data.buckets[string.hash() % data.numBuckets]; + QStringHashNode *node = data.numBuckets?data.buckets[string.hash() % data.numBuckets]:0; while (node && !node->symbolEquals(string)) - node = node->next; + node = (*node->next); if (node) node->symbolId = string.symbolId(); @@ -695,67 +881,83 @@ typename QStringHash::Node *QStringHash::fin 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 ConstIterator &iter) const +{ + Node *n = iter.node(); + if (n->isQString()) + return value(QHashedStringRef((QChar *)n->strData->data(), n->length, n->hash)); + else + return value(QHashedCStringRef(n->ckey, n->length, n->hash)); +} + +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 +bool QStringHash::contains(const ConstIterator &s) const +{ + return 0 != value(s); +} + +template +T &QStringHash::operator[](const QString &key) { QHashedStringRef cs(key); Node *n = findNode(cs); @@ -763,42 +965,115 @@ 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; + nodePool = new ReservedNodePool; nodePool->count = n; nodePool->used = 0; nodePool->nodes = new Node[n]; - if (n > SmallThreshold) - data.rehashToSize(n); + data.rehashToSize(n, iterateFirst(), iterateNext); +} + +template +QStringHash::ConstIterator::ConstIterator() +{ +} + +template +QStringHash::ConstIterator::ConstIterator(const QStringHashData::IteratorData &d) +: d(d) +{ +} + +template +typename QStringHash::ConstIterator &QStringHash::ConstIterator::operator++() +{ + d = QStringHash::iterateNext(d); + return *this; +} + +template +bool QStringHash::ConstIterator::operator==(const ConstIterator &o) const +{ + return d.n == o.d.n; +} + +template +bool QStringHash::ConstIterator::operator!=(const ConstIterator &o) const +{ + return d.n != o.d.n; +} + +template +QHashedString QStringHash::ConstIterator::key() const +{ + Node *n = (Node *)d.n; + if (n->isQString()) { + return QHashedString(QString((QChar *)n->strData->data(), n->length), n->hash); + } else { + return QHashedString(QString::fromLatin1(n->ckey, n->length), n->hash); + } +} +template +const T &QStringHash::ConstIterator::value() const +{ + Node *n = (Node *)d.n; + return n->value; +} + +template +const T &QStringHash::ConstIterator::operator*() const +{ + Node *n = (Node *)d.n; + return n->value; +} + +template +typename QStringHash::Node *QStringHash::ConstIterator::node() const +{ + Node *n = (Node *)d.n; + return n; +} + +template +typename QStringHash::ConstIterator QStringHash::begin() const +{ + return ConstIterator(iterateFirst()); +} + +template +typename QStringHash::ConstIterator QStringHash::end() const +{ + return ConstIterator(); } inline uint qHash(const QHashedString &string) diff --git a/src/declarative/qml/qdeclarativepropertycache.cpp b/src/declarative/qml/qdeclarativepropertycache.cpp index 4418ffad65..fb9beee55a 100644 --- a/src/declarative/qml/qdeclarativepropertycache.cpp +++ b/src/declarative/qml/qdeclarativepropertycache.cpp @@ -259,6 +259,9 @@ QDeclarativePropertyCache::~QDeclarativePropertyCache() args = next; } + // We must clear this prior to releasing the parent incase it is a + // linked hash + stringCache.clear(); if (parent) parent->release(); parent = 0; engine = 0; @@ -289,7 +292,7 @@ QDeclarativePropertyCache *QDeclarativePropertyCache::copy(int reserve) cache->propertyIndexCacheStart = propertyIndexCache.count() + propertyIndexCacheStart; cache->methodIndexCacheStart = methodIndexCache.count() + methodIndexCacheStart; cache->signalHanderIndexCacheStart = signalHandlerIndexCache.count() + signalHanderIndexCacheStart; - cache->stringCache.copyAndReserve(stringCache, reserve); + cache->stringCache.linkAndReserve(stringCache, reserve); cache->allowedRevisionCache = allowedRevisionCache; cache->metaObject = metaObject; diff --git a/src/declarative/qml/v8/qv8qobjectwrapper.cpp b/src/declarative/qml/v8/qv8qobjectwrapper.cpp index 05b5ba2186..11733be5fd 100644 --- a/src/declarative/qml/v8/qv8qobjectwrapper.cpp +++ b/src/declarative/qml/v8/qv8qobjectwrapper.cpp @@ -914,10 +914,22 @@ v8::Local QDeclarativePropertyCache::newQObject(QObject *object, QV8 QString toString = QLatin1String("toString"); QString destroy = QLatin1String("destroy"); + // As we use hash linking, it is possible that iterating over the values can give duplicates. + // To combat this, we must unique'ify our properties. + StringCache uniqueHash; + if (stringCache.isLinked()) + uniqueHash.reserve(stringCache.count()); + // XXX TODO: Enables fast property accessors. These more than double the property access // performance, but the cost of setting up this structure hasn't been measured so // its not guarenteed that this is a win overall. We need to try and measure the cost. for (StringCache::ConstIterator iter = stringCache.begin(); iter != stringCache.end(); ++iter) { + if (stringCache.isLinked()) { + if (uniqueHash.contains(iter)) + continue; + uniqueHash.insert(iter); + } + QDeclarativePropertyData *property = *iter; if (property->notFullyResolved()) resolve(property); -- cgit v1.2.3