diff options
author | Ulf Hermann <ulf.hermann@qt.io> | 2019-02-04 12:51:41 +0100 |
---|---|---|
committer | Ulf Hermann <ulf.hermann@qt.io> | 2019-02-06 11:05:42 +0000 |
commit | d7225d67bf0f65f363ff4afb710954aff7698874 (patch) | |
tree | afa4c44d133e5a27eedf9c272c7fc76230d33fa6 /src/qml/qml/ftw | |
parent | 3310f173c1c6208cb0f6541578419196bc29831f (diff) |
Move QStringHash into its own file
QHashedString and QStringHash are different things.
Change-Id: Ifcac58ef41bf15dd6172fa0c42b86eca385c2ce0
Reviewed-by: Lars Knoll <lars.knoll@qt.io>
Diffstat (limited to 'src/qml/qml/ftw')
-rw-r--r-- | src/qml/qml/ftw/ftw.pri | 4 | ||||
-rw-r--r-- | src/qml/qml/ftw/qhashedstring.cpp | 132 | ||||
-rw-r--r-- | src/qml/qml/ftw/qhashedstring_p.h | 848 | ||||
-rw-r--r-- | src/qml/qml/ftw/qstringhash.cpp | 173 | ||||
-rw-r--r-- | src/qml/qml/ftw/qstringhash_p.h | 908 |
5 files changed, 1086 insertions, 979 deletions
diff --git a/src/qml/qml/ftw/ftw.pri b/src/qml/qml/ftw/ftw.pri index ade05a596b..b1698a7b0e 100644 --- a/src/qml/qml/ftw/ftw.pri +++ b/src/qml/qml/ftw/ftw.pri @@ -11,12 +11,14 @@ HEADERS += \ $$PWD/qrecyclepool_p.h \ $$PWD/qflagpointer_p.h \ $$PWD/qlazilyallocated_p.h \ - $$PWD/qqmlnullablevalue_p.h + $$PWD/qqmlnullablevalue_p.h \ + $$PWD/qstringhash_p.h SOURCES += \ $$PWD/qintrusivelist.cpp \ $$PWD/qhashedstring.cpp \ $$PWD/qqmlthread.cpp \ + $$PWD/qstringhash.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 117670dbfc..bb6688599d 100644 --- a/src/qml/qml/ftw/qhashedstring.cpp +++ b/src/qml/qml/ftw/qhashedstring.cpp @@ -39,136 +39,7 @@ #include "qhashedstring_p.h" - - -/* - A QHash has initially around pow(2, MinNumBits) buckets. For - example, if MinNumBits is 4, it has 17 buckets. -*/ -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; - -#ifdef QSTRINGHASH_LINK_DEBUG - if (linkCount) - qFatal("QStringHash: Illegal attempt to rehash a linked hash."); -#endif - - 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_BEGIN_NAMESPACE QHashedStringRef QHashedStringRef::mid(int offset, int length) const { @@ -228,3 +99,4 @@ QString QHashedCStringRef::toUtf16() const return rv; } +QT_END_NAMESPACE diff --git a/src/qml/qml/ftw/qhashedstring_p.h b/src/qml/qml/ftw/qhashedstring_p.h index 2d6c25bdd3..3ed0c109e6 100644 --- a/src/qml/qml/ftw/qhashedstring_p.h +++ b/src/qml/qml/ftw/qhashedstring_p.h @@ -174,854 +174,6 @@ private: mutable quint32 m_hash = 0; }; -class QStringHashData; -class Q_AUTOTEST_EXPORT QStringHashNode -{ -public: - QStringHashNode() - : ckey(nullptr) - { - } - - QStringHashNode(const QHashedString &key) - : length(key.length()), hash(key.hash()), symbolId(0) - { - strData = const_cast<QHashedString &>(key).data_ptr(); - setQString(true); - strData->ref.ref(); - } - - QStringHashNode(const QHashedCStringRef &key) - : length(key.length()), hash(key.hash()), symbolId(0), ckey(key.constData()) - { - } - - QStringHashNode(const QStringHashNode &o) - : length(o.length), hash(o.hash), symbolId(o.symbolId), ckey(o.ckey) - { - setQString(o.isQString()); - if (isQString()) { strData->ref.ref(); } - } - - ~QStringHashNode() - { - if (isQString()) { if (!strData->ref.deref()) free(strData); } - } - - QFlagPointer<QStringHashNode> next; - - qint32 length = 0; - quint32 hash = 0; - quint32 symbolId = 0; - - union { - const char *ckey; - QStringData *strData; - }; - - inline QHashedString key() const - { - if (isQString()) - return QHashedString(QString((QChar *)strData->data(), length), hash); - - return QHashedString(QString::fromLatin1(ckey, length), hash); - } - - 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 quint16 *utf16Data() const { return (quint16 *)strData->data(); } - - inline bool equals(const QV4::Value &string) const { - QString s = string.toQStringNoThrow(); - if (isQString()) { - QStringDataPtr dd; - dd.ptr = strData; - strData->ref.ref(); - return QString(dd) == s; - } else { - return QLatin1String(cStrData(), length) == s; - } - } - - inline bool equals(const QV4::String *string) const { - if (length != string->d()->length() || hash != string->hashValue()) - return false; - if (isQString()) { - QStringDataPtr dd; - dd.ptr = strData; - strData->ref.ref(); - return QString(dd) == string->toQString(); - } else { - return QLatin1String(cStrData(), length) == string->toQString(); - } - } - - inline bool equals(const QHashedStringRef &string) const { - return length == string.length() && - hash == string.hash() && - (isQString()?QHashedString::compare(string.constData(), (const QChar *)utf16Data(), length): - QHashedString::compare(string.constData(), cStrData(), length)); - } - - inline bool equals(const QHashedCStringRef &string) const { - return length == string.length() && - hash == string.hash() && - (isQString()?QHashedString::compare((const QChar *)utf16Data(), string.constData(), length): - QHashedString::compare(string.constData(), cStrData(), length)); - } -}; - -class Q_AUTOTEST_EXPORT QStringHashData -{ -public: - QStringHashData() {} - - QStringHashNode **buckets = nullptr; - int numBuckets = 0; - int size = 0; - short numBits = 0; -#ifdef QSTRINGHASH_LINK_DEBUG - int linkCount = 0; -#endif - - struct IteratorData { - IteratorData() {} - QStringHashNode *n = nullptr; - void *p = nullptr; - }; - void rehashToBits(short); - void rehashToSize(int); - void rehashNode(QStringHashNode **newBuckets, int nb, QStringHashNode *node); - -private: - QStringHashData(const QStringHashData &); - QStringHashData &operator=(const QStringHashData &); -}; - -// For a supplied key type, in what form do we need to keep a hashed version? -template<typename T> -struct HashedForm {}; - -template<> struct HashedForm<QString> { typedef QHashedString Type; }; -template<> struct HashedForm<QStringRef> { typedef QHashedStringRef Type; }; -template<> struct HashedForm<QHashedString> { typedef const QHashedString &Type; }; -template<> struct HashedForm<QV4::String *> { typedef const QV4::String *Type; }; -template<> struct HashedForm<const QV4::String *> { typedef const QV4::String *Type; }; -template<> struct HashedForm<QHashedStringRef> { typedef const QHashedStringRef &Type; }; -template<> struct HashedForm<QLatin1String> { typedef QHashedCStringRef Type; }; -template<> struct HashedForm<QHashedCStringRef> { typedef const QHashedCStringRef &Type; }; - -class QStringHashBase -{ -public: - static HashedForm<QString>::Type hashedString(const QString &s) { return QHashedString(s);} - static HashedForm<QStringRef>::Type hashedString(const QStringRef &s) { return QHashedStringRef(s.constData(), s.size());} - static HashedForm<QHashedString>::Type hashedString(const QHashedString &s) { return s; } - static HashedForm<QV4::String *>::Type hashedString(QV4::String *s) { return s; } - static HashedForm<const QV4::String *>::Type hashedString(const QV4::String *s) { return s; } - static HashedForm<QHashedStringRef>::Type hashedString(const QHashedStringRef &s) { return s; } - - static HashedForm<QLatin1String>::Type hashedString(const QLatin1String &s) { return QHashedCStringRef(s.data(), s.size()); } - static HashedForm<QHashedCStringRef>::Type hashedString(const QHashedCStringRef &s) { return s; } - - static const QString &toQString(const QString &s) { return s; } - static const QString &toQString(const QHashedString &s) { return s; } - static QString toQString(const QV4::String *s) { return s->toQString(); } - static QString toQString(const QHashedStringRef &s) { return s.toString(); } - - static QString toQString(const QLatin1String &s) { return QString(s); } - static QString toQString(const QHashedCStringRef &s) { return s.toUtf16(); } - - static inline quint32 hashOf(const QHashedStringRef &s) { return s.hash(); } - static inline quint32 hashOf(QV4::String *s) { return s->hashValue(); } - static inline quint32 hashOf(const QV4::String *s) { return s->hashValue(); } - - template<typename K> - static inline quint32 hashOf(const K &key) { return hashedString(key).hash(); } -}; - -template<class T> -class QStringHash : public QStringHashBase -{ -public: - typedef QHashedString key_type; - typedef T mapped_type; - - 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 NewedNode : public Node { - NewedNode(const QHashedString &key, const T &value) : Node(key, value), nextNewed(nullptr) {} - NewedNode(const QHashedCStringRef &key, const T &value) : Node(key, value), nextNewed(nullptr) {} - NewedNode(const Node &o) : Node(o), nextNewed(nullptr) {} - NewedNode *nextNewed; - }; - struct ReservedNodePool - { - ReservedNodePool() : nodes(nullptr) {} - ~ReservedNodePool() { delete [] nodes; } - int count = 0; - int used = 0; - Node *nodes; - }; - - QStringHashData data; - NewedNode *newedNodes; - ReservedNodePool *nodePool; - const QStringHash<T> *link; - - template<typename K> - inline Node *findNode(const K &) const; - - inline Node *createNode(const Node &o); - - template<typename K> - inline Node *createNode(const K &, const T &); - - inline Node *insertNode(Node *, quint32); - - inline void initializeNode(Node *, const QHashedString &key); - inline void initializeNode(Node *, const QHashedCStringRef &key); - - template<typename K> - inline Node *takeNode(const K &key, const T &value); - - inline Node *takeNode(const Node &o); - - inline void copy(const QStringHash<T> &); - - void copyNode(const QStringHashNode *otherNode); - - 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<T> &); - - void copyAndReserve(const QStringHash<T> &other, int additionalReserve); - void linkAndReserve(const QStringHash<T> &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; - - template<typename K> - inline bool equals(const K &) const; - - inline QHashedString key() const; - inline const T &value() const; - inline const T &operator*() const; - - inline Node *node() const; - private: - QStringHashData::IteratorData d; - }; - - template<typename K> - inline void insert(const K &, const T &); - - inline void insert(const ConstIterator &); - - template<typename K> - inline T *value(const K &) const; - - inline T *value(const QV4::String *string) const; - inline T *value(const ConstIterator &) const; - - template<typename K> - inline bool contains(const K &) const; - - template<typename K> - inline T &operator[](const K &); - - inline ConstIterator begin() const; - inline ConstIterator end() const; - - inline ConstIterator iterator(Node *n) const; - - template<typename K> - inline ConstIterator find(const K &) const; - - inline void reserve(int); -}; - -template<class T> -QStringHash<T>::QStringHash() -: newedNodes(nullptr), nodePool(nullptr), link(nullptr) -{ -} - -template<class T> -QStringHash<T>::QStringHash(const QStringHash<T> &other) -: newedNodes(nullptr), nodePool(nullptr), link(nullptr) -{ - data.numBits = other.data.numBits; - data.size = other.data.size; - reserve(other.count()); - copy(other); -} - -template<class T> -QStringHash<T> &QStringHash<T>::operator=(const QStringHash<T> &other) -{ - if (&other == this) - return *this; - - clear(); - - data.numBits = other.data.numBits; - data.size = other.data.size; - reserve(other.count()); - copy(other); - - return *this; -} - -template<class T> -void QStringHash<T>::copyAndReserve(const QStringHash<T> &other, int additionalReserve) -{ - clear(); - data.numBits = other.data.numBits; - reserve(other.count() + additionalReserve); - copy(other); -} - -template<class T> -void QStringHash<T>::linkAndReserve(const QStringHash<T> &other, int additionalReserve) -{ - clear(); - - if (other.count()) { - data.size = other.data.size; - data.rehashToSize(other.count() + additionalReserve); - - 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<QStringHash<T>&>(other).data.linkCount++; -#endif - - for (int ii = 0; ii < data.numBuckets; ++ii) - data.buckets[ii] = (Node *)other.data.buckets[ii]; - - link = &other; - return; - } - - data.size = 0; - } - - data.numBits = other.data.numBits; - reserve(other.count() + additionalReserve); - copy(other); -} - -template<class T> -QStringHash<T>::~QStringHash() -{ - clear(); -} - -template<class T> -void QStringHash<T>::clear() -{ -#ifdef QSTRINGHASH_LINK_DEBUG - if (link) { - data.linkCount--; - const_cast<QStringHash<T> *>(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.buckets = nullptr; - data.numBuckets = 0; - data.numBits = 0; - data.size = 0; - - newedNodes = nullptr; - nodePool = nullptr; - link = nullptr; -} - -template<class T> -bool QStringHash<T>::isEmpty() const -{ - return data.size== 0; -} - -template<class T> -int QStringHash<T>::count() const -{ - return data.size; -} - -template<class T> -int QStringHash<T>::numBuckets() const -{ - return data.numBuckets; -} - -template<class T> -bool QStringHash<T>::isLinked() const -{ - return link != 0; -} - -template<class T> -void QStringHash<T>::initializeNode(Node *node, const QHashedString &key) -{ - node->length = key.length(); - node->hash = key.hash(); - node->strData = const_cast<QHashedString &>(key).data_ptr(); - node->strData->ref.ref(); - node->setQString(true); -} - -template<class T> -void QStringHash<T>::initializeNode(Node *node, const QHashedCStringRef &key) -{ - node->length = key.length(); - node->hash = key.hash(); - node->ckey = key.constData(); -} - -template<class T> -template<class K> -typename QStringHash<T>::Node *QStringHash<T>::takeNode(const K &key, const T &value) -{ - if (nodePool && nodePool->used != nodePool->count) { - Node *rv = nodePool->nodes + nodePool->used++; - initializeNode(rv, hashedString(key)); - rv->value = value; - return rv; - } else { - NewedNode *rv = new NewedNode(hashedString(key), value); - rv->nextNewed = newedNodes; - newedNodes = rv; - return rv; - } -} - -template<class T> -typename QStringHash<T>::Node *QStringHash<T>::takeNode(const Node &o) -{ - if (nodePool && nodePool->used != nodePool->count) { - Node *rv = nodePool->nodes + nodePool->used++; - rv->length = o.length; - rv->hash = o.hash; - 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 { - NewedNode *rv = new NewedNode(o); - rv->nextNewed = newedNodes; - newedNodes = rv; - return rv; - } -} - -template<class T> -void QStringHash<T>::copyNode(const QStringHashNode *otherNode) -{ - // Copy the predecessor before the successor - QStringHashNode *next = otherNode->next.data(); - if (next) - copyNode(next); - - Node *mynode = takeNode(*(const Node *)otherNode); - int bucket = mynode->hash % data.numBuckets; - mynode->next = data.buckets[bucket]; - data.buckets[bucket] = mynode; -} - -template<class T> -void QStringHash<T>::copy(const QStringHash<T> &other) -{ - Q_ASSERT(data.size == 0); - - data.size = other.data.size; - - // Ensure buckets array is created - data.rehashToBits(data.numBits); - - // Preserve the existing order within buckets - for (int i = 0; i < other.data.numBuckets; ++i) { - QStringHashNode *bucket = other.data.buckets[i]; - if (bucket) - copyNode(bucket); - } -} - -template<class T> -QStringHashData::IteratorData -QStringHash<T>::iterateNext(const QStringHashData::IteratorData &d) -{ - QStringHash<T> *This = (QStringHash<T> *)d.p; - Node *node = (Node *)d.n; - - if (This->nodePool && node >= This->nodePool->nodes && - node < (This->nodePool->nodes + This->nodePool->used)) { - node--; - if (node < This->nodePool->nodes) - node = nullptr; - } else { - NewedNode *nn = (NewedNode *)node; - node = nn->nextNewed; - - if (node == nullptr && This->nodePool && This->nodePool->used) - node = This->nodePool->nodes + This->nodePool->used - 1; - } - - if (node == nullptr && This->link) - return This->link->iterateFirst(); - - QStringHashData::IteratorData rv; - rv.n = node; - rv.p = d.p; - return rv; -} - -template<class T> -QStringHashData::IteratorData QStringHash<T>::iterateFirst() const -{ - Node *n = nullptr; - if (newedNodes) - n = newedNodes; - else if (nodePool && nodePool->used) - n = nodePool->nodes + nodePool->used - 1; - - if (n == nullptr && link) - return link->iterateFirst(); - - QStringHashData::IteratorData rv; - rv.n = n; - rv.p = const_cast<QStringHash<T> *>(this); - return rv; -} - -template<class T> -typename QStringHash<T>::ConstIterator QStringHash<T>::iterator(Node *n) const -{ - if (!n) - return ConstIterator(); - - const QStringHash<T> *container = this; - - if (link) { - // This node could be in the linked hash - if ((n >= nodePool->nodes) && (n < (nodePool->nodes + nodePool->used))) { - // The node is in this hash - } else if ((n >= link->nodePool->nodes) && (n < (link->nodePool->nodes + link->nodePool->used))) { - // The node is in the linked hash - container = link; - } else { - const NewedNode *ln = link->newedNodes; - while (ln) { - if (ln == n) { - // This node is in the linked hash's newed list - container = link; - break; - } - ln = ln->nextNewed; - } - } - } - - QStringHashData::IteratorData rv; - rv.n = n; - rv.p = const_cast<QStringHash<T> *>(container); - return ConstIterator(rv); -} - -template<class T> -typename QStringHash<T>::Node *QStringHash<T>::createNode(const Node &o) -{ - Node *n = takeNode(o); - return insertNode(n, n->hash); -} - -template<class T> -template<class K> -typename QStringHash<T>::Node *QStringHash<T>::createNode(const K &key, const T &value) -{ - Node *n = takeNode(key, value); - return insertNode(n, hashOf(key)); -} - -template<class T> -typename QStringHash<T>::Node *QStringHash<T>::insertNode(Node *n, quint32 hash) -{ - if (data.size >= data.numBuckets) - data.rehashToBits(data.numBits + 1); - - int bucket = hash % data.numBuckets; - n->next = data.buckets[bucket]; - data.buckets[bucket] = n; - - data.size++; - - return n; -} - -template<class T> -template<class K> -void QStringHash<T>::insert(const K &key, const T &value) -{ - // If this is a linked hash, we can't rely on owning the node, so we always - // create a new one. - Node *n = link?nullptr:findNode(key); - if (n) n->value = value; - else createNode(key, value); -} - -template<class T> -void QStringHash<T>::insert(const ConstIterator &iter) -{ - insert(iter.key(), iter.value()); -} - -template<class T> -template<class K> -typename QStringHash<T>::Node *QStringHash<T>::findNode(const K &key) const -{ - QStringHashNode *node = data.numBuckets?data.buckets[hashOf(key) % data.numBuckets]:nullptr; - - typename HashedForm<K>::Type hashedKey(hashedString(key)); - while (node && !node->equals(hashedKey)) - node = (*node->next); - - return (Node *)node; -} - -template<class T> -template<class K> -T *QStringHash<T>::value(const K &key) const -{ - Node *n = findNode(key); - return n?&n->value:nullptr; -} - -template<class T> -T *QStringHash<T>::value(const ConstIterator &iter) const -{ - Node *n = iter.node(); - return value(n->key()); -} - -template<class T> -T *QStringHash<T>::value(const QV4::String *string) const -{ - Node *n = findNode(string); - return n?&n->value:nullptr; -} - -template<class T> -template<class K> -bool QStringHash<T>::contains(const K &key) const -{ - return nullptr != value(key); -} - -template<class T> -template<class K> -T &QStringHash<T>::operator[](const K &key) -{ - Node *n = findNode(key); - if (n) return n->value; - else return createNode(key, T())->value; -} - -template<class T> -void QStringHash<T>::reserve(int n) -{ - if (nodePool || 0 == n) - return; - - nodePool = new ReservedNodePool; - nodePool->count = n; - nodePool->used = 0; - nodePool->nodes = new Node[n]; - - data.rehashToSize(n); -} - -template<class T> -QStringHash<T>::ConstIterator::ConstIterator() -{ -} - -template<class T> -QStringHash<T>::ConstIterator::ConstIterator(const QStringHashData::IteratorData &d) -: d(d) -{ -} - -template<class T> -typename QStringHash<T>::ConstIterator &QStringHash<T>::ConstIterator::operator++() -{ - d = QStringHash<T>::iterateNext(d); - return *this; -} - -template<class T> -bool QStringHash<T>::ConstIterator::operator==(const ConstIterator &o) const -{ - return d.n == o.d.n; -} - -template<class T> -bool QStringHash<T>::ConstIterator::operator!=(const ConstIterator &o) const -{ - return d.n != o.d.n; -} - -template<class T> -template<typename K> -bool QStringHash<T>::ConstIterator::equals(const K &key) const -{ - return d.n->equals(key); -} - -template<class T> -QHashedString QStringHash<T>::ConstIterator::key() const -{ - Node *n = (Node *)d.n; - return n->key(); -} -template<class T> -const T &QStringHash<T>::ConstIterator::value() const -{ - Node *n = (Node *)d.n; - return n->value; -} - -template<class T> -const T &QStringHash<T>::ConstIterator::operator*() const -{ - Node *n = (Node *)d.n; - return n->value; -} - -template<class T> -typename QStringHash<T>::Node *QStringHash<T>::ConstIterator::node() const -{ - Node *n = (Node *)d.n; - return n; -} - -template<class T> -typename QStringHash<T>::ConstIterator QStringHash<T>::begin() const -{ - return ConstIterator(iterateFirst()); -} - -template<class T> -typename QStringHash<T>::ConstIterator QStringHash<T>::end() const -{ - return ConstIterator(); -} - -template<class T> -template<class K> -typename QStringHash<T>::ConstIterator QStringHash<T>::find(const K &key) const -{ - return iterator(findNode(key)); -} - -template<class T> -class QStringMultiHash : public QStringHash<T> -{ -public: - typedef typename QStringHash<T>::ConstIterator ConstIterator; - - template<typename K> - inline void insert(const K &, const T &); - - inline void insert(const ConstIterator &); - - inline ConstIterator findNext(const ConstIterator &) const; -}; - -template<class T> -template<class K> -void QStringMultiHash<T>::insert(const K &key, const T &value) -{ - // Always create a new node - QStringHash<T>::createNode(key, value); -} - -template<class T> -void QStringMultiHash<T>::insert(const ConstIterator &iter) -{ - // Always create a new node - QStringHash<T>::createNode(iter.key(), iter.value()); -} - -template<class T> -typename QStringHash<T>::ConstIterator QStringMultiHash<T>::findNext(const ConstIterator &iter) const -{ - QStringHashNode *node = iter.node(); - if (node) { - QHashedString key(node->key()); - - while ((node = *node->next)) { - if (node->equals(key)) { - return QStringHash<T>::iterator(static_cast<typename QStringHash<T>::Node *>(node)); - } - } - } - - return ConstIterator(); -} - inline uint qHash(const QHashedString &string) { return uint(string.hash()); diff --git a/src/qml/qml/ftw/qstringhash.cpp b/src/qml/qml/ftw/qstringhash.cpp new file mode 100644 index 0000000000..93963adcde --- /dev/null +++ b/src/qml/qml/ftw/qstringhash.cpp @@ -0,0 +1,173 @@ +/**************************************************************************** +** +** 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; + +#ifdef QSTRINGHASH_LINK_DEBUG + if (linkCount) + qFatal("QStringHash: Illegal attempt to rehash a linked hash."); +#endif + + 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 new file mode 100644 index 0000000000..e5a709b02c --- /dev/null +++ b/src/qml/qml/ftw/qstringhash_p.h @@ -0,0 +1,908 @@ +/**************************************************************************** +** +** 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 QSTRINGHASH_P_H +#define QSTRINGHASH_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/qhashedstring_p.h> + +QT_BEGIN_NAMESPACE + +class QStringHashData; +class Q_AUTOTEST_EXPORT QStringHashNode +{ +public: + QStringHashNode() + : ckey(nullptr) + { + } + + QStringHashNode(const QHashedString &key) + : length(key.length()), hash(key.hash()), symbolId(0) + { + strData = const_cast<QHashedString &>(key).data_ptr(); + setQString(true); + strData->ref.ref(); + } + + QStringHashNode(const QHashedCStringRef &key) + : length(key.length()), hash(key.hash()), symbolId(0), ckey(key.constData()) + { + } + + QStringHashNode(const QStringHashNode &o) + : length(o.length), hash(o.hash), symbolId(o.symbolId), ckey(o.ckey) + { + setQString(o.isQString()); + if (isQString()) { strData->ref.ref(); } + } + + ~QStringHashNode() + { + if (isQString()) { if (!strData->ref.deref()) free(strData); } + } + + QFlagPointer<QStringHashNode> next; + + qint32 length = 0; + quint32 hash = 0; + quint32 symbolId = 0; + + union { + const char *ckey; + QStringData *strData; + }; + + inline QHashedString key() const + { + if (isQString()) + return QHashedString(QString((QChar *)strData->data(), length), hash); + + return QHashedString(QString::fromLatin1(ckey, length), hash); + } + + 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 quint16 *utf16Data() const { return (quint16 *)strData->data(); } + + inline bool equals(const QV4::Value &string) const { + QString s = string.toQStringNoThrow(); + if (isQString()) { + QStringDataPtr dd; + dd.ptr = strData; + strData->ref.ref(); + return QString(dd) == s; + } else { + return QLatin1String(cStrData(), length) == s; + } + } + + inline bool equals(const QV4::String *string) const { + if (length != string->d()->length() || hash != string->hashValue()) + return false; + if (isQString()) { + QStringDataPtr dd; + dd.ptr = strData; + strData->ref.ref(); + return QString(dd) == string->toQString(); + } else { + return QLatin1String(cStrData(), length) == string->toQString(); + } + } + + inline bool equals(const QHashedStringRef &string) const { + return length == string.length() && + hash == string.hash() && + (isQString()?QHashedString::compare(string.constData(), (const QChar *)utf16Data(), length): + QHashedString::compare(string.constData(), cStrData(), length)); + } + + inline bool equals(const QHashedCStringRef &string) const { + return length == string.length() && + hash == string.hash() && + (isQString()?QHashedString::compare((const QChar *)utf16Data(), string.constData(), length): + QHashedString::compare(string.constData(), cStrData(), length)); + } +}; + +class Q_AUTOTEST_EXPORT QStringHashData +{ +public: + QStringHashData() {} + + QStringHashNode **buckets = nullptr; + int numBuckets = 0; + int size = 0; + short numBits = 0; +#ifdef QSTRINGHASH_LINK_DEBUG + int linkCount = 0; +#endif + + struct IteratorData { + IteratorData() {} + QStringHashNode *n = nullptr; + void *p = nullptr; + }; + void rehashToBits(short); + void rehashToSize(int); + void rehashNode(QStringHashNode **newBuckets, int nb, QStringHashNode *node); + +private: + QStringHashData(const QStringHashData &); + QStringHashData &operator=(const QStringHashData &); +}; + +// For a supplied key type, in what form do we need to keep a hashed version? +template<typename T> +struct HashedForm {}; + +template<> struct HashedForm<QString> { typedef QHashedString Type; }; +template<> struct HashedForm<QStringRef> { typedef QHashedStringRef Type; }; +template<> struct HashedForm<QHashedString> { typedef const QHashedString &Type; }; +template<> struct HashedForm<QV4::String *> { typedef const QV4::String *Type; }; +template<> struct HashedForm<const QV4::String *> { typedef const QV4::String *Type; }; +template<> struct HashedForm<QHashedStringRef> { typedef const QHashedStringRef &Type; }; +template<> struct HashedForm<QLatin1String> { typedef QHashedCStringRef Type; }; +template<> struct HashedForm<QHashedCStringRef> { typedef const QHashedCStringRef &Type; }; + +class QStringHashBase +{ +public: + static HashedForm<QString>::Type hashedString(const QString &s) { return QHashedString(s);} + static HashedForm<QStringRef>::Type hashedString(const QStringRef &s) { return QHashedStringRef(s.constData(), s.size());} + static HashedForm<QHashedString>::Type hashedString(const QHashedString &s) { return s; } + static HashedForm<QV4::String *>::Type hashedString(QV4::String *s) { return s; } + static HashedForm<const QV4::String *>::Type hashedString(const QV4::String *s) { return s; } + static HashedForm<QHashedStringRef>::Type hashedString(const QHashedStringRef &s) { return s; } + + static HashedForm<QLatin1String>::Type hashedString(const QLatin1String &s) { return QHashedCStringRef(s.data(), s.size()); } + static HashedForm<QHashedCStringRef>::Type hashedString(const QHashedCStringRef &s) { return s; } + + static const QString &toQString(const QString &s) { return s; } + static const QString &toQString(const QHashedString &s) { return s; } + static QString toQString(const QV4::String *s) { return s->toQString(); } + static QString toQString(const QHashedStringRef &s) { return s.toString(); } + + static QString toQString(const QLatin1String &s) { return QString(s); } + static QString toQString(const QHashedCStringRef &s) { return s.toUtf16(); } + + static inline quint32 hashOf(const QHashedStringRef &s) { return s.hash(); } + static inline quint32 hashOf(QV4::String *s) { return s->hashValue(); } + static inline quint32 hashOf(const QV4::String *s) { return s->hashValue(); } + + template<typename K> + static inline quint32 hashOf(const K &key) { return hashedString(key).hash(); } +}; + +template<class T> +class QStringHash : public QStringHashBase +{ +public: + typedef QHashedString key_type; + typedef T mapped_type; + + 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 NewedNode : public Node { + NewedNode(const QHashedString &key, const T &value) : Node(key, value), nextNewed(nullptr) {} + NewedNode(const QHashedCStringRef &key, const T &value) : Node(key, value), nextNewed(nullptr) {} + NewedNode(const Node &o) : Node(o), nextNewed(nullptr) {} + NewedNode *nextNewed; + }; + struct ReservedNodePool + { + ReservedNodePool() : nodes(nullptr) {} + ~ReservedNodePool() { delete [] nodes; } + int count = 0; + int used = 0; + Node *nodes; + }; + + QStringHashData data; + NewedNode *newedNodes; + ReservedNodePool *nodePool; + const QStringHash<T> *link; + + template<typename K> + inline Node *findNode(const K &) const; + + inline Node *createNode(const Node &o); + + template<typename K> + inline Node *createNode(const K &, const T &); + + inline Node *insertNode(Node *, quint32); + + inline void initializeNode(Node *, const QHashedString &key); + inline void initializeNode(Node *, const QHashedCStringRef &key); + + template<typename K> + inline Node *takeNode(const K &key, const T &value); + + inline Node *takeNode(const Node &o); + + inline void copy(const QStringHash<T> &); + + void copyNode(const QStringHashNode *otherNode); + + 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<T> &); + + void copyAndReserve(const QStringHash<T> &other, int additionalReserve); + void linkAndReserve(const QStringHash<T> &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; + + template<typename K> + inline bool equals(const K &) const; + + inline QHashedString key() const; + inline const T &value() const; + inline const T &operator*() const; + + Node *node() const; + private: + QStringHashData::IteratorData d; + }; + + template<typename K> + inline void insert(const K &, const T &); + + inline void insert(const ConstIterator &); + + template<typename K> + inline T *value(const K &) const; + + inline T *value(const QV4::String *string) const; + inline T *value(const ConstIterator &) const; + + template<typename K> + inline bool contains(const K &) const; + + template<typename K> + inline T &operator[](const K &); + + inline ConstIterator begin() const; + inline ConstIterator end() const; + + inline ConstIterator iterator(Node *n) const; + + template<typename K> + inline ConstIterator find(const K &) const; + + inline void reserve(int); +}; + +template<class T> +QStringHash<T>::QStringHash() +: newedNodes(nullptr), nodePool(nullptr), link(nullptr) +{ +} + +template<class T> +QStringHash<T>::QStringHash(const QStringHash<T> &other) +: newedNodes(nullptr), nodePool(nullptr), link(nullptr) +{ + data.numBits = other.data.numBits; + data.size = other.data.size; + reserve(other.count()); + copy(other); +} + +template<class T> +QStringHash<T> &QStringHash<T>::operator=(const QStringHash<T> &other) +{ + if (&other == this) + return *this; + + clear(); + + data.numBits = other.data.numBits; + data.size = other.data.size; + reserve(other.count()); + copy(other); + + return *this; +} + +template<class T> +void QStringHash<T>::copyAndReserve(const QStringHash<T> &other, int additionalReserve) +{ + clear(); + data.numBits = other.data.numBits; + reserve(other.count() + additionalReserve); + copy(other); +} + +template<class T> +void QStringHash<T>::linkAndReserve(const QStringHash<T> &other, int additionalReserve) +{ + clear(); + + if (other.count()) { + data.size = other.data.size; + data.rehashToSize(other.count() + additionalReserve); + + 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<QStringHash<T>&>(other).data.linkCount++; +#endif + + for (int ii = 0; ii < data.numBuckets; ++ii) + data.buckets[ii] = (Node *)other.data.buckets[ii]; + + link = &other; + return; + } + + data.size = 0; + } + + data.numBits = other.data.numBits; + reserve(other.count() + additionalReserve); + copy(other); +} + +template<class T> +QStringHash<T>::~QStringHash() +{ + clear(); +} + +template<class T> +void QStringHash<T>::clear() +{ +#ifdef QSTRINGHASH_LINK_DEBUG + if (link) { + data.linkCount--; + const_cast<QStringHash<T> *>(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.buckets = nullptr; + data.numBuckets = 0; + data.numBits = 0; + data.size = 0; + + newedNodes = nullptr; + nodePool = nullptr; + link = nullptr; +} + +template<class T> +bool QStringHash<T>::isEmpty() const +{ + return data.size== 0; +} + +template<class T> +int QStringHash<T>::count() const +{ + return data.size; +} + +template<class T> +int QStringHash<T>::numBuckets() const +{ + return data.numBuckets; +} + +template<class T> +bool QStringHash<T>::isLinked() const +{ + return link != 0; +} + +template<class T> +void QStringHash<T>::initializeNode(Node *node, const QHashedString &key) +{ + node->length = key.length(); + node->hash = key.hash(); + node->strData = const_cast<QHashedString &>(key).data_ptr(); + node->strData->ref.ref(); + node->setQString(true); +} + +template<class T> +void QStringHash<T>::initializeNode(Node *node, const QHashedCStringRef &key) +{ + node->length = key.length(); + node->hash = key.hash(); + node->ckey = key.constData(); +} + +template<class T> +template<class K> +typename QStringHash<T>::Node *QStringHash<T>::takeNode(const K &key, const T &value) +{ + if (nodePool && nodePool->used != nodePool->count) { + Node *rv = nodePool->nodes + nodePool->used++; + initializeNode(rv, hashedString(key)); + rv->value = value; + return rv; + } else { + NewedNode *rv = new NewedNode(hashedString(key), value); + rv->nextNewed = newedNodes; + newedNodes = rv; + return rv; + } +} + +template<class T> +typename QStringHash<T>::Node *QStringHash<T>::takeNode(const Node &o) +{ + if (nodePool && nodePool->used != nodePool->count) { + Node *rv = nodePool->nodes + nodePool->used++; + rv->length = o.length; + rv->hash = o.hash; + 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 { + NewedNode *rv = new NewedNode(o); + rv->nextNewed = newedNodes; + newedNodes = rv; + return rv; + } +} + +template<class T> +void QStringHash<T>::copyNode(const QStringHashNode *otherNode) +{ + // Copy the predecessor before the successor + QStringHashNode *next = otherNode->next.data(); + if (next) + copyNode(next); + + Node *mynode = takeNode(*(const Node *)otherNode); + int bucket = mynode->hash % data.numBuckets; + mynode->next = data.buckets[bucket]; + data.buckets[bucket] = mynode; +} + +template<class T> +void QStringHash<T>::copy(const QStringHash<T> &other) +{ + Q_ASSERT(data.size == 0); + + data.size = other.data.size; + + // Ensure buckets array is created + data.rehashToBits(data.numBits); + + // Preserve the existing order within buckets + for (int i = 0; i < other.data.numBuckets; ++i) { + QStringHashNode *bucket = other.data.buckets[i]; + if (bucket) + copyNode(bucket); + } +} + +template<class T> +QStringHashData::IteratorData +QStringHash<T>::iterateNext(const QStringHashData::IteratorData &d) +{ + QStringHash<T> *This = (QStringHash<T> *)d.p; + Node *node = (Node *)d.n; + + if (This->nodePool && node >= This->nodePool->nodes && + node < (This->nodePool->nodes + This->nodePool->used)) { + node--; + if (node < This->nodePool->nodes) + node = nullptr; + } else { + NewedNode *nn = (NewedNode *)node; + node = nn->nextNewed; + + if (node == nullptr && This->nodePool && This->nodePool->used) + node = This->nodePool->nodes + This->nodePool->used - 1; + } + + if (node == nullptr && This->link) + return This->link->iterateFirst(); + + QStringHashData::IteratorData rv; + rv.n = node; + rv.p = d.p; + return rv; +} + +template<class T> +QStringHashData::IteratorData QStringHash<T>::iterateFirst() const +{ + Node *n = nullptr; + if (newedNodes) + n = newedNodes; + else if (nodePool && nodePool->used) + n = nodePool->nodes + nodePool->used - 1; + + if (n == nullptr && link) + return link->iterateFirst(); + + QStringHashData::IteratorData rv; + rv.n = n; + rv.p = const_cast<QStringHash<T> *>(this); + return rv; +} + +template<class T> +typename QStringHash<T>::ConstIterator QStringHash<T>::iterator(Node *n) const +{ + if (!n) + return ConstIterator(); + + const QStringHash<T> *container = this; + + if (link) { + // This node could be in the linked hash + if ((n >= nodePool->nodes) && (n < (nodePool->nodes + nodePool->used))) { + // The node is in this hash + } else if ((n >= link->nodePool->nodes) && (n < (link->nodePool->nodes + link->nodePool->used))) { + // The node is in the linked hash + container = link; + } else { + const NewedNode *ln = link->newedNodes; + while (ln) { + if (ln == n) { + // This node is in the linked hash's newed list + container = link; + break; + } + ln = ln->nextNewed; + } + } + } + + QStringHashData::IteratorData rv; + rv.n = n; + rv.p = const_cast<QStringHash<T> *>(container); + return ConstIterator(rv); +} + +template<class T> +typename QStringHash<T>::Node *QStringHash<T>::createNode(const Node &o) +{ + Node *n = takeNode(o); + return insertNode(n, n->hash); +} + +template<class T> +template<class K> +typename QStringHash<T>::Node *QStringHash<T>::createNode(const K &key, const T &value) +{ + Node *n = takeNode(key, value); + return insertNode(n, hashOf(key)); +} + +template<class T> +typename QStringHash<T>::Node *QStringHash<T>::insertNode(Node *n, quint32 hash) +{ + if (data.size >= data.numBuckets) + data.rehashToBits(data.numBits + 1); + + int bucket = hash % data.numBuckets; + n->next = data.buckets[bucket]; + data.buckets[bucket] = n; + + data.size++; + + return n; +} + +template<class T> +template<class K> +void QStringHash<T>::insert(const K &key, const T &value) +{ + // If this is a linked hash, we can't rely on owning the node, so we always + // create a new one. + Node *n = link?nullptr:findNode(key); + if (n) n->value = value; + else createNode(key, value); +} + +template<class T> +void QStringHash<T>::insert(const ConstIterator &iter) +{ + insert(iter.key(), iter.value()); +} + +template<class T> +template<class K> +typename QStringHash<T>::Node *QStringHash<T>::findNode(const K &key) const +{ + QStringHashNode *node = data.numBuckets?data.buckets[hashOf(key) % data.numBuckets]:nullptr; + + typename HashedForm<K>::Type hashedKey(hashedString(key)); + while (node && !node->equals(hashedKey)) + node = (*node->next); + + return (Node *)node; +} + +template<class T> +template<class K> +T *QStringHash<T>::value(const K &key) const +{ + Node *n = findNode(key); + return n?&n->value:nullptr; +} + +template<class T> +T *QStringHash<T>::value(const ConstIterator &iter) const +{ + Node *n = iter.node(); + return value(n->key()); +} + +template<class T> +T *QStringHash<T>::value(const QV4::String *string) const +{ + Node *n = findNode(string); + return n?&n->value:nullptr; +} + +template<class T> +template<class K> +bool QStringHash<T>::contains(const K &key) const +{ + return nullptr != value(key); +} + +template<class T> +template<class K> +T &QStringHash<T>::operator[](const K &key) +{ + Node *n = findNode(key); + if (n) return n->value; + else return createNode(key, T())->value; +} + +template<class T> +void QStringHash<T>::reserve(int n) +{ + if (nodePool || 0 == n) + return; + + nodePool = new ReservedNodePool; + nodePool->count = n; + nodePool->used = 0; + nodePool->nodes = new Node[n]; + + data.rehashToSize(n); +} + +template<class T> +QStringHash<T>::ConstIterator::ConstIterator() +{ +} + +template<class T> +QStringHash<T>::ConstIterator::ConstIterator(const QStringHashData::IteratorData &d) +: d(d) +{ +} + +template<class T> +typename QStringHash<T>::ConstIterator &QStringHash<T>::ConstIterator::operator++() +{ + d = QStringHash<T>::iterateNext(d); + return *this; +} + +template<class T> +bool QStringHash<T>::ConstIterator::operator==(const ConstIterator &o) const +{ + return d.n == o.d.n; +} + +template<class T> +bool QStringHash<T>::ConstIterator::operator!=(const ConstIterator &o) const +{ + return d.n != o.d.n; +} + +template<class T> +template<typename K> +bool QStringHash<T>::ConstIterator::equals(const K &key) const +{ + return d.n->equals(key); +} + +template<class T> +QHashedString QStringHash<T>::ConstIterator::key() const +{ + Node *n = (Node *)d.n; + return n->key(); +} +template<class T> +const T &QStringHash<T>::ConstIterator::value() const +{ + Node *n = (Node *)d.n; + return n->value; +} + +template<class T> +const T &QStringHash<T>::ConstIterator::operator*() const +{ + Node *n = (Node *)d.n; + return n->value; +} + +template<class T> +typename QStringHash<T>::Node *QStringHash<T>::ConstIterator::node() const +{ + Node *n = (Node *)d.n; + return n; +} + +template<class T> +typename QStringHash<T>::ConstIterator QStringHash<T>::begin() const +{ + return ConstIterator(iterateFirst()); +} + +template<class T> +typename QStringHash<T>::ConstIterator QStringHash<T>::end() const +{ + return ConstIterator(); +} + +template<class T> +template<class K> +typename QStringHash<T>::ConstIterator QStringHash<T>::find(const K &key) const +{ + return iterator(findNode(key)); +} + +template<class T> +class QStringMultiHash : public QStringHash<T> +{ +public: + typedef typename QStringHash<T>::ConstIterator ConstIterator; + + template<typename K> + inline void insert(const K &, const T &); + + inline void insert(const ConstIterator &); + + inline ConstIterator findNext(const ConstIterator &) const; +}; + +template<class T> +template<class K> +void QStringMultiHash<T>::insert(const K &key, const T &value) +{ + // Always create a new node + QStringHash<T>::createNode(key, value); +} + +template<class T> +void QStringMultiHash<T>::insert(const ConstIterator &iter) +{ + // Always create a new node + QStringHash<T>::createNode(iter.key(), iter.value()); +} + +template<class T> +typename QStringHash<T>::ConstIterator QStringMultiHash<T>::findNext(const ConstIterator &iter) const +{ + QStringHashNode *node = iter.node(); + if (node) { + QHashedString key(node->key()); + + while ((node = *node->next)) { + if (node->equals(key)) { + return QStringHash<T>::iterator(static_cast<typename QStringHash<T>::Node *>(node)); + } + } + } + + return ConstIterator(); +} + +QT_END_NAMESPACE + +#endif // QSTRINGHASH_P_H |