diff options
Diffstat (limited to 'src/corelib/tools/qhash.cpp')
| -rw-r--r-- | src/corelib/tools/qhash.cpp | 1843 |
1 files changed, 1843 insertions, 0 deletions
diff --git a/src/corelib/tools/qhash.cpp b/src/corelib/tools/qhash.cpp new file mode 100644 index 0000000..540f43d --- /dev/null +++ b/src/corelib/tools/qhash.cpp @@ -0,0 +1,1843 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the QtCore module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain +** additional rights. These rights are described in the Nokia Qt LGPL +** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this +** package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include "qhash.h" + +#ifdef truncate +#undef truncate +#endif + +#include <qbitarray.h> +#include <qstring.h> +#include <stdlib.h> +#ifdef QT_QHASH_DEBUG +#include <qstring.h> +#endif + +QT_BEGIN_NAMESPACE + +/* + These functions are based on Peter J. Weinberger's hash function + (from the Dragon Book). The constant 24 in the original function + was replaced with 23 to produce fewer collisions on input such as + "a", "aa", "aaa", "aaaa", ... +*/ + +static uint hash(const uchar *p, int n) +{ + uint h = 0; + uint g; + + while (n--) { + h = (h << 4) + *p++; + if ((g = (h & 0xf0000000)) != 0) + h ^= g >> 23; + h &= ~g; + } + return h; +} + +static uint hash(const QChar *p, int n) +{ + uint h = 0; + uint g; + + while (n--) { + h = (h << 4) + (*p++).unicode(); + if ((g = (h & 0xf0000000)) != 0) + h ^= g >> 23; + h &= ~g; + } + return h; +} + +uint qHash(const QByteArray &key) +{ + return hash(reinterpret_cast<const uchar *>(key.data()), key.size()); +} + +uint qHash(const QString &key) +{ + return hash(key.unicode(), key.size()); +} + +uint qHash(const QStringRef &key) +{ + return hash(key.unicode(), key.size()); +} + +uint qHash(const QBitArray &bitArray) +{ + int m = bitArray.d.size() - 1; + uint result = hash(reinterpret_cast<const uchar *>(bitArray.d.data()), qMax(0, m)); + + // deal with the last 0 to 7 bits manually, because we can't trust that + // the padding is initialized to 0 in bitArray.d + int n = bitArray.size(); + if (n & 0x7) + result = ((result << 4) + bitArray.d.at(m)) & ((1 << n) - 1); + return result; +} + +/* + 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]; +} + +/* + Returns the smallest integer n such that + primeForNumBits(n) >= hint. +*/ +static int countBits(int hint) +{ + int numBits = 0; + int bits = hint; + + while (bits > 1) { + bits >>= 1; + numBits++; + } + + if (numBits >= (int)sizeof(prime_deltas)) { + numBits = sizeof(prime_deltas) - 1; + } else if (primeForNumBits(numBits) < hint) { + ++numBits; + } + return numBits; +} + +/* + A QHash has initially around pow(2, MinNumBits) buckets. For + example, if MinNumBits is 4, it has 17 buckets. +*/ +const int MinNumBits = 4; + +QHashData QHashData::shared_null = { + 0, 0, Q_BASIC_ATOMIC_INITIALIZER(1), 0, 0, MinNumBits, 0, 0, true +}; + +void *QHashData::allocateNode() +{ + return qMalloc(nodeSize); +} + +void QHashData::freeNode(void *node) +{ + qFree(node); +} + +QHashData *QHashData::detach_helper(void (*node_duplicate)(Node *, void *), int nodeSize) +{ + union { + QHashData *d; + Node *e; + }; + d = new QHashData; + d->fakeNext = 0; + d->buckets = 0; + d->ref = 1; + d->size = size; + d->nodeSize = nodeSize; + d->userNumBits = userNumBits; + d->numBits = numBits; + d->numBuckets = numBuckets; + d->sharable = true; + + if (numBuckets) { + d->buckets = new Node *[numBuckets]; + Node *this_e = reinterpret_cast<Node *>(this); + for (int i = 0; i < numBuckets; ++i) { + Node **nextNode = &d->buckets[i]; + Node *oldNode = buckets[i]; + while (oldNode != this_e) { + Node *dup = static_cast<Node *>(allocateNode()); + node_duplicate(oldNode, dup); + dup->h = oldNode->h; + *nextNode = dup; + nextNode = &dup->next; + oldNode = oldNode->next; + } + *nextNode = e; + } + } + return d; +} + +QHashData::Node *QHashData::nextNode(Node *node) +{ + union { + Node *next; + Node *e; + QHashData *d; + }; + next = node->next; + Q_ASSERT_X(next, "QHash", "Iterating beyond end()"); + if (next->next) + return next; + + int start = (node->h % d->numBuckets) + 1; + Node **bucket = d->buckets + start; + int n = d->numBuckets - start; + while (n--) { + if (*bucket != e) + return *bucket; + ++bucket; + } + return e; +} + +QHashData::Node *QHashData::previousNode(Node *node) +{ + union { + Node *e; + QHashData *d; + }; + + e = node; + while (e->next) + e = e->next; + + int start; + if (node == e) + start = d->numBuckets - 1; + else + start = node->h % d->numBuckets; + + Node *sentinel = node; + Node **bucket = d->buckets + start; + while (start >= 0) { + if (*bucket != sentinel) { + Node *prev = *bucket; + while (prev->next != sentinel) + prev = prev->next; + return prev; + } + + sentinel = e; + --bucket; + --start; + } + Q_ASSERT_X(start >= 0, "QHash", "Iterating backward beyond begin()"); + return e; +} + +/* + If hint is negative, -hint gives the approximate number of + buckets that should be used for the hash table. If hint is + nonnegative, (1 << hint) gives the approximate number + of buckets that should be used. +*/ +void QHashData::rehash(int hint) +{ + if (hint < 0) { + hint = countBits(-hint); + if (hint < MinNumBits) + hint = MinNumBits; + userNumBits = hint; + while (primeForNumBits(hint) < (size >> 1)) + ++hint; + } else if (hint < MinNumBits) { + hint = MinNumBits; + } + + if (numBits != hint) { + Node *e = reinterpret_cast<Node *>(this); + Node **oldBuckets = buckets; + int oldNumBuckets = numBuckets; + + numBits = hint; + numBuckets = primeForNumBits(hint); + buckets = new Node *[numBuckets]; + for (int i = 0; i < numBuckets; ++i) + buckets[i] = e; + + for (int i = 0; i < oldNumBuckets; ++i) { + Node *firstNode = oldBuckets[i]; + while (firstNode != e) { + uint h = firstNode->h; + Node *lastNode = firstNode; + while (lastNode->next != e && lastNode->next->h == h) + lastNode = lastNode->next; + + Node *afterLastNode = lastNode->next; + Node **beforeFirstNode = &buckets[h % numBuckets]; + while (*beforeFirstNode != e) + beforeFirstNode = &(*beforeFirstNode)->next; + lastNode->next = *beforeFirstNode; + *beforeFirstNode = firstNode; + firstNode = afterLastNode; + } + } + delete [] oldBuckets; + } +} + +void QHashData::destroyAndFree() +{ + delete [] buckets; + delete this; +} + +#ifdef QT_QHASH_DEBUG + +void QHashData::dump() +{ + qDebug("Hash data (ref = %d, size = %d, nodeSize = %d, userNumBits = %d, numBits = %d, numBuckets = %d)", + int(ref), size, nodeSize, userNumBits, numBits, + numBuckets); + qDebug(" %p (fakeNode = %p)", this, fakeNext); + for (int i = 0; i < numBuckets; ++i) { + QString line; + Node *n = buckets[i]; + if (n != reinterpret_cast<Node *>(this)) { + line.sprintf("%d:", i); + while (n != reinterpret_cast<Node *>(this)) { + line += QString().sprintf(" -> [%p]", n); + if (!n) { + line += " (CORRUPT)"; + break; + } + n = n->next; + } + qDebug(qPrintable(line)); + } + } +} + +void QHashData::checkSanity() +{ + if (fakeNext) + qFatal("Fake next isn't 0"); + + for (int i = 0; i < numBuckets; ++i) { + Node *n = buckets[i]; + Node *p = n; + if (!n) + qFatal("%d: Bucket entry is 0", i); + if (n != reinterpret_cast<Node *>(this)) { + while (n != reinterpret_cast<Node *>(this)) { + if (!n->next) + qFatal("%d: Next of %p is 0, should be %p", i, n, this); + n = n->next; + } + } + } +} +#endif + +/*! + \class QHash + \brief The QHash class is a template class that provides a hash-table-based dictionary. + + \ingroup tools + \ingroup shared + \mainclass + \reentrant + + QHash\<Key, T\> is one of Qt's generic \l{container classes}. It + stores (key, value) pairs and provides very fast lookup of the + value associated with a key. + + QHash provides very similar functionality to QMap. The + differences are: + + \list + \i QHash provides faster lookups than QMap. (See \l{Algorithmic + Complexity} for details.) + \i When iterating over a QMap, the items are always sorted by + key. With QHash, the items are arbitrarily ordered. + \i The key type of a QMap must provide operator<(). The key + type of a QHash must provide operator==() and a global + \l{qHash()}{qHash}(Key) function. + \endlist + + Here's an example QHash with QString keys and \c int values: + \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 0 + + To insert a (key, value) pair into the hash, you can use operator[](): + + \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 1 + + This inserts the following three (key, value) pairs into the + QHash: ("one", 1), ("three", 3), and ("seven", 7). Another way to + insert items into the hash is to use insert(): + + \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 2 + + To look up a value, use operator[]() or value(): + + \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 3 + + If there is no item with the specified key in the hash, these + functions return a \l{default-constructed value}. + + If you want to check whether the hash contains a particular key, + use contains(): + + \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 4 + + There is also a value() overload that uses its second argument as + a default value if there is no item with the specified key: + + \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 5 + + In general, we recommend that you use contains() and value() + rather than operator[]() for looking up a key in a hash. The + reason is that operator[]() silently inserts an item into the + hash if no item exists with the same key (unless the hash is + const). For example, the following code snippet will create 1000 + items in memory: + + \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 6 + + To avoid this problem, replace \c hash[i] with \c hash.value(i) + in the code above. + + If you want to navigate through all the (key, value) pairs stored + in a QHash, you can use an iterator. QHash provides both + \l{Java-style iterators} (QHashIterator and QMutableHashIterator) + and \l{STL-style iterators} (QHash::const_iterator and + QHash::iterator). Here's how to iterate over a QHash<QString, + int> using a Java-style iterator: + + \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 7 + + Here's the same code, but using an STL-style iterator: + + \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 8 + + QHash is unordered, so an iterator's sequence cannot be assumed + to be predictable. If ordering by key is required, use a QMap. + + Normally, a QHash allows only one value per key. If you call + insert() with a key that already exists in the QHash, the + previous value is erased. For example: + + \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 9 + + However, you can store multiple values per key by using + insertMulti() instead of insert() (or using the convenience + subclass QMultiHash). If you want to retrieve all + the values for a single key, you can use values(const Key &key), + which returns a QList<T>: + + \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 10 + + The items that share the same key are available from most + recently to least recently inserted. A more efficient approach is + to call find() to get the iterator for the first item with a key + and iterate from there: + + \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 11 + + If you only need to extract the values from a hash (not the keys), + you can also use \l{foreach}: + + \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 12 + + Items can be removed from the hash in several ways. One way is to + call remove(); this will remove any item with the given key. + Another way is to use QMutableHashIterator::remove(). In addition, + you can clear the entire hash using clear(). + + QHash's key and value data types must be \l{assignable data + types}. You cannot, for example, store a QWidget as a value; + instead, store a QWidget *. In addition, QHash's key type must + provide operator==(), and there must also be a global qHash() + function that returns a hash value for an argument of the key's + type. + + Here's a list of the C++ and Qt types that can serve as keys in a + QHash: any integer type (char, unsigned long, etc.), any pointer + type, QChar, QString, and QByteArray. For all of these, the \c + <QHash> header defines a qHash() function that computes an + adequate hash value. If you want to use other types as the key, + make sure that you provide operator==() and a qHash() + implementation. + + Example: + \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 13 + + The qHash() function computes a numeric value based on a key. It + can use any algorithm imaginable, as long as it always returns + the same value if given the same argument. In other words, if + \c{e1 == e2}, then \c{qHash(e1) == qHash(e2)} must hold as well. + However, to obtain good performance, the qHash() function should + attempt to return different hash values for different keys to the + largest extent possible. + + In the example above, we've relied on Qt's global qHash(const + QString &) to give us a hash value for the employee's name, and + XOR'ed this with the day they were born to help produce unique + hashes for people with the same name. + + Internally, QHash uses a hash table to perform lookups. Unlike Qt + 3's \c QDict class, which needed to be initialized with a prime + number, QHash's hash table automatically grows and shrinks to + provide fast lookups without wasting too much memory. You can + still control the size of the hash table by calling reserve() if + you already know approximately how many items the QHash will + contain, but this isn't necessary to obtain good performance. You + can also call capacity() to retrieve the hash table's size. + + \sa QHashIterator, QMutableHashIterator, QMap, QSet +*/ + +/*! \fn QHash::QHash() + + Constructs an empty hash. + + \sa clear() +*/ + +/*! \fn QHash::QHash(const QHash<Key, T> &other) + + Constructs a copy of \a other. + + This operation occurs in \l{constant time}, because QHash is + \l{implicitly shared}. This makes returning a QHash from a + function very fast. If a shared instance is modified, it will be + copied (copy-on-write), and this takes \l{linear time}. + + \sa operator=() +*/ + +/*! \fn QHash::~QHash() + + Destroys the hash. References to the values in the hash and all + iterators of this hash become invalid. +*/ + +/*! \fn QHash<Key, T> &QHash::operator=(const QHash<Key, T> &other) + + Assigns \a other to this hash and returns a reference to this hash. +*/ + +/*! \fn bool QHash::operator==(const QHash<Key, T> &other) const + + Returns true if \a other is equal to this hash; otherwise returns + false. + + Two hashes are considered equal if they contain the same (key, + value) pairs. + + This function requires the value type to implement \c operator==(). + + \sa operator!=() +*/ + +/*! \fn bool QHash::operator!=(const QHash<Key, T> &other) const + + Returns true if \a other is not equal to this hash; otherwise + returns false. + + Two hashes are considered equal if they contain the same (key, + value) pairs. + + This function requires the value type to implement \c operator==(). + + \sa operator==() +*/ + +/*! \fn int QHash::size() const + + Returns the number of items in the hash. + + \sa isEmpty(), count() +*/ + +/*! \fn bool QHash::isEmpty() const + + Returns true if the hash contains no items; otherwise returns + false. + + \sa size() +*/ + +/*! \fn int QHash::capacity() const + + Returns the number of buckets in the QHash's internal hash table. + + The sole purpose of this function is to provide a means of fine + tuning QHash's memory usage. In general, you will rarely ever + need to call this function. If you want to know how many items are + in the hash, call size(). + + \sa reserve(), squeeze() +*/ + +/*! \fn void QHash::reserve(int size) + + Ensures that the QHash's internal hash table consists of at least + \a size buckets. + + This function is useful for code that needs to build a huge hash + and wants to avoid repeated reallocation. For example: + + \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 14 + + Ideally, \a size should be slightly more than the maximum number + of items expected in the hash. \a size doesn't have to be prime, + because QHash will use a prime number internally anyway. If \a size + is an underestimate, the worst that will happen is that the QHash + will be a bit slower. + + In general, you will rarely ever need to call this function. + QHash's internal hash table automatically shrinks or grows to + provide good performance without wasting too much memory. + + \sa squeeze(), capacity() +*/ + +/*! \fn void QHash::squeeze() + + Reduces the size of the QHash's internal hash table to save + memory. + + The sole purpose of this function is to provide a means of fine + tuning QHash's memory usage. In general, you will rarely ever + need to call this function. + + \sa reserve(), capacity() +*/ + +/*! \fn void QHash::detach() + + \internal + + Detaches this hash from any other hashes with which it may share + data. + + \sa isDetached() +*/ + +/*! \fn bool QHash::isDetached() const + + \internal + + Returns true if the hash's internal data isn't shared with any + other hash object; otherwise returns false. + + \sa detach() +*/ + +/*! \fn void QHash::setSharable(bool sharable) + + \internal +*/ + +/*! \fn void QHash::clear() + + Removes all items from the hash. + + \sa remove() +*/ + +/*! \fn int QHash::remove(const Key &key) + + Removes all the items that have the \a key from the hash. + Returns the number of items removed which is usually 1 but will + be 0 if the key isn't in the hash, or greater than 1 if + insertMulti() has been used with the \a key. + + \sa clear(), take(), QMultiHash::remove() +*/ + +/*! \fn T QHash::take(const Key &key) + + Removes the item with the \a key from the hash and returns + the value associated with it. + + If the item does not exist in the hash, the function simply + returns a \l{default-constructed value}. If there are multiple + items for \a key in the hash, only the most recently inserted one + is removed. + + If you don't use the return value, remove() is more efficient. + + \sa remove() +*/ + +/*! \fn bool QHash::contains(const Key &key) const + + Returns true if the hash contains an item with the \a key; + otherwise returns false. + + \sa count(), QMultiHash::contains() +*/ + +/*! \fn const T QHash::value(const Key &key) const + + Returns the value associated with the \a key. + + If the hash contains no item with the \a key, the function + returns a \l{default-constructed value}. If there are multiple + items for the \a key in the hash, the value of the most recently + inserted one is returned. + + \sa key(), values(), contains(), operator[]() +*/ + +/*! \fn const T QHash::value(const Key &key, const T &defaultValue) const + + \overload + + If the hash contains no item with the given \a key, the function returns + \a defaultValue. +*/ + +/*! \fn T &QHash::operator[](const Key &key) + + Returns the value associated with the \a key as a modifiable + reference. + + If the hash contains no item with the \a key, the function inserts + a \l{default-constructed value} into the hash with the \a key, and + returns a reference to it. If the hash contains multiple items + with the \a key, this function returns a reference to the most + recently inserted value. + + \sa insert(), value() +*/ + +/*! \fn const T QHash::operator[](const Key &key) const + + \overload + + Same as value(). +*/ + +/*! \fn QList<Key> QHash::uniqueKeys() const + \since 4.2 + + Returns a list containing all the keys in the map. Keys that occur multiple + times in the map (because items were inserted with insertMulti(), or + unite() was used) occur only once in the returned list. + + \sa keys(), values() +*/ + +/*! \fn QList<Key> QHash::keys() const + + Returns a list containing all the keys in the hash, in an + arbitrary order. Keys that occur multiple times in the hash + (because items were inserted with insertMulti(), or unite() was + used) also occur multiple times in the list. + + To obtain a list of unique keys, where each key from the map only + occurs once, use uniqueKeys(). + + The order is guaranteed to be the same as that used by values(). + + \sa uniqueKeys(), values(), key() +*/ + +/*! \fn QList<Key> QHash::keys(const T &value) const + + \overload + + Returns a list containing all the keys associated with value \a + value, in an arbitrary order. + + This function can be slow (\l{linear time}), because QHash's + internal data structure is optimized for fast lookup by key, not + by value. +*/ + +/*! \fn QList<T> QHash::values() const + + Returns a list containing all the values in the hash, in an + arbitrary order. If a key is associated multiple values, all of + its values will be in the list, and not just the most recently + inserted one. + + The order is guaranteed to be the same as that used by keys(). + + \sa keys(), value() +*/ + +/*! \fn QList<T> QHash::values(const Key &key) const + + \overload + + Returns a list of all the values associated with the \a key, + from the most recently inserted to the least recently inserted. + + \sa count(), insertMulti() +*/ + +/*! \fn Key QHash::key(const T &value) const + + Returns the first key mapped to \a value. + + If the hash contains no item with the \a value, the function + returns a \link {default-constructed value} default-constructed + key \endlink. + + This function can be slow (\l{linear time}), because QHash's + internal data structure is optimized for fast lookup by key, not + by value. + + \sa value(), keys() +*/ + +/*! + \fn Key QHash::key(const T &value, const Key &defaultKey) const + \since 4.3 + \overload + + Returns the first key mapped to \a value, or \a defaultKey if the + hash contains no item mapped to \a value. + + This function can be slow (\l{linear time}), because QHash's + internal data structure is optimized for fast lookup by key, not + by value. +*/ + +/*! \fn int QHash::count(const Key &key) const + + Returns the number of items associated with the \a key. + + \sa contains(), insertMulti() +*/ + +/*! \fn int QHash::count() const + + \overload + + Same as size(). +*/ + +/*! \fn QHash::iterator QHash::begin() + + Returns an \l{STL-style iterator} pointing to the first item in + the hash. + + \sa constBegin(), end() +*/ + +/*! \fn QHash::const_iterator QHash::begin() const + + \overload +*/ + +/*! \fn QHash::const_iterator QHash::constBegin() const + + Returns a const \l{STL-style iterator} pointing to the first item + in the hash. + + \sa begin(), constEnd() +*/ + +/*! \fn QHash::iterator QHash::end() + + Returns an \l{STL-style iterator} pointing to the imaginary item + after the last item in the hash. + + \sa begin(), constEnd() +*/ + +/*! \fn QHash::const_iterator QHash::end() const + + \overload +*/ + +/*! \fn QHash::const_iterator QHash::constEnd() const + + Returns a const \l{STL-style iterator} pointing to the imaginary + item after the last item in the hash. + + \sa constBegin(), end() +*/ + +/*! \fn QHash::iterator QHash::erase(iterator pos) + + Removes the (key, value) pair associated with the iterator \a pos + from the hash, and returns an iterator to the next item in the + hash. + + Unlike remove() and take(), this function never causes QHash to + rehash its internal data structure. This means that it can safely + be called while iterating, and won't affect the order of items in + the hash. For example: + + \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 15 + + \sa remove(), take(), find() +*/ + +/*! \fn QHash::iterator QHash::find(const Key &key) + + Returns an iterator pointing to the item with the \a key in the + hash. + + If the hash contains no item with the \a key, the function + returns end(). + + If the hash contains multiple items with the \a key, this + function returns an iterator that points to the most recently + inserted value. The other values are accessible by incrementing + the iterator. For example, here's some code that iterates over all + the items with the same key: + + \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 16 + + \sa value(), values(), QMultiHash::find() +*/ + +/*! \fn QHash::const_iterator QHash::find(const Key &key) const + + \overload +*/ + +/*! \fn QHash::iterator QHash::constFind(const Key &key) const + \since 4.1 + + Returns an iterator pointing to the item with the \a key in the + hash. + + If the hash contains no item with the \a key, the function + returns constEnd(). + + \sa find(), QMultiHash::constFind() +*/ + +/*! \fn QHash::iterator QHash::insert(const Key &key, const T &value) + + Inserts a new item with the \a key and a value of \a value. + + If there is already an item with the \a key, that item's value + is replaced with \a value. + + If there are multiple items with the \a key, the most + recently inserted item's value is replaced with \a value. + + \sa insertMulti() +*/ + +/*! \fn QHash::iterator QHash::insertMulti(const Key &key, const T &value) + + Inserts a new item with the \a key and a value of \a value. + + If there is already an item with the same key in the hash, this + function will simply create a new one. (This behavior is + different from insert(), which overwrites the value of an + existing item.) + + \sa insert(), values() +*/ + +/*! \fn QHash<Key, T> &QHash::unite(const QHash<Key, T> &other) + + Inserts all the items in the \a other hash into this hash. If a + key is common to both hashes, the resulting hash will contain the + key multiple times. + + \sa insertMulti() +*/ + +/*! \fn bool QHash::empty() const + + This function is provided for STL compatibility. It is equivalent + to isEmpty(), returning true if the hash is empty; otherwise + returns false. +*/ + +/*! \typedef QHash::ConstIterator + + Qt-style synonym for QHash::const_iterator. +*/ + +/*! \typedef QHash::Iterator + + Qt-style synonym for QHash::iterator. +*/ + +/*! \typedef QHash::difference_type + + Typedef for ptrdiff_t. Provided for STL compatibility. +*/ + +/*! \typedef QHash::key_type + + Typedef for Key. Provided for STL compatibility. +*/ + +/*! \typedef QHash::mapped_type + + Typedef for T. Provided for STL compatibility. +*/ + +/*! \typedef QHash::size_type + + Typedef for int. Provided for STL compatibility. +*/ + +/*! \typedef QHash::iterator::difference_type + \internal +*/ + +/*! \typedef QHash::iterator::iterator_category + \internal +*/ + +/*! \typedef QHash::iterator::pointer + \internal +*/ + +/*! \typedef QHash::iterator::reference + \internal +*/ + +/*! \typedef QHash::iterator::value_type + \internal +*/ + +/*! \typedef QHash::const_iterator::difference_type + \internal +*/ + +/*! \typedef QHash::const_iterator::iterator_category + \internal +*/ + +/*! \typedef QHash::const_iterator::pointer + \internal +*/ + +/*! \typedef QHash::const_iterator::reference + \internal +*/ + +/*! \typedef QHash::const_iterator::value_type + \internal +*/ + +/*! \class QHash::iterator + \brief The QHash::iterator class provides an STL-style non-const iterator for QHash and QMultiHash. + + QHash features both \l{STL-style iterators} and \l{Java-style + iterators}. The STL-style iterators are more low-level and more + cumbersome to use; on the other hand, they are slightly faster + and, for developers who already know STL, have the advantage of + familiarity. + + QHash\<Key, T\>::iterator allows you to iterate over a QHash (or + QMultiHash) and to modify the value (but not the key) associated + with a particular key. If you want to iterate over a const QHash, + you should use QHash::const_iterator. It is generally good + practice to use QHash::const_iterator on a non-const QHash as + well, unless you need to change the QHash through the iterator. + Const iterators are slightly faster, and can improve code + readability. + + The default QHash::iterator constructor creates an uninitialized + iterator. You must initialize it using a QHash function like + QHash::begin(), QHash::end(), or QHash::find() before you can + start iterating. Here's a typical loop that prints all the (key, + value) pairs stored in a hash: + + \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 17 + + Unlike QMap, which orders its items by key, QHash stores its + items in an arbitrary order. The only guarantee is that items that + share the same key (because they were inserted using + QHash::insertMulti()) will appear consecutively, from the most + recently to the least recently inserted value. + + Let's see a few examples of things we can do with a + QHash::iterator that we cannot do with a QHash::const_iterator. + Here's an example that increments every value stored in the QHash + by 2: + + \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 18 + + Here's an example that removes all the items whose key is a + string that starts with an underscore character: + + \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 19 + + The call to QHash::erase() removes the item pointed to by the + iterator from the hash, and returns an iterator to the next item. + Here's another way of removing an item while iterating: + + \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 20 + + It might be tempting to write code like this: + + \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 21 + + However, this will potentially crash in \c{++i}, because \c i is + a dangling iterator after the call to erase(). + + Multiple iterators can be used on the same hash. However, be + aware that any modification performed directly on the QHash has + the potential of dramatically changing the order in which the + items are stored in the hash, as they might cause QHash to rehash + its internal data structure. There is one notable exception: + QHash::erase(). This function can safely be called while + iterating, and won't affect the order of items in the hash. If you + need to keep iterators over a long period of time, we recommend + that you use QMap rather than QHash. + + \sa QHash::const_iterator, QMutableHashIterator +*/ + +/*! \fn QHash::iterator::operator Node *() const + + \internal +*/ + +/*! \fn QHash::iterator::iterator() + + Constructs an uninitialized iterator. + + Functions like key(), value(), and operator++() must not be + called on an uninitialized iterator. Use operator=() to assign a + value to it before using it. + + \sa QHash::begin() QHash::end() +*/ + +/*! \fn QHash::iterator::iterator(void *node) + + \internal +*/ + +/*! \fn const Key &QHash::iterator::key() const + + Returns the current item's key as a const reference. + + There is no direct way of changing an item's key through an + iterator, although it can be done by calling QHash::erase() + followed by QHash::insert() or QHash::insertMulti(). + + \sa value() +*/ + +/*! \fn T &QHash::iterator::value() const + + Returns a modifiable reference to the current item's value. + + You can change the value of an item by using value() on + the left side of an assignment, for example: + + \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 22 + + \sa key(), operator*() +*/ + +/*! \fn T &QHash::iterator::operator*() const + + Returns a modifiable reference to the current item's value. + + Same as value(). + + \sa key() +*/ + +/*! \fn T *QHash::iterator::operator->() const + + Returns a pointer to the current item's value. + + \sa value() +*/ + +/*! + \fn bool QHash::iterator::operator==(const iterator &other) const + \fn bool QHash::iterator::operator==(const const_iterator &other) const + + Returns true if \a other points to the same item as this + iterator; otherwise returns false. + + \sa operator!=() +*/ + +/*! + \fn bool QHash::iterator::operator!=(const iterator &other) const + \fn bool QHash::iterator::operator!=(const const_iterator &other) const + + Returns true if \a other points to a different item than this + iterator; otherwise returns false. + + \sa operator==() +*/ + +/*! + \fn QHash::iterator &QHash::iterator::operator++() + + The prefix ++ operator (\c{++i}) advances the iterator to the + next item in the hash and returns an iterator to the new current + item. + + Calling this function on QHash::end() leads to undefined results. + + \sa operator--() +*/ + +/*! \fn QHash::iterator QHash::iterator::operator++(int) + + \overload + + The postfix ++ operator (\c{i++}) advances the iterator to the + next item in the hash and returns an iterator to the previously + current item. +*/ + +/*! + \fn QHash::iterator &QHash::iterator::operator--() + + The prefix -- operator (\c{--i}) makes the preceding item + current and returns an iterator pointing to the new current item. + + Calling this function on QHash::begin() leads to undefined + results. + + \sa operator++() +*/ + +/*! + \fn QHash::iterator QHash::iterator::operator--(int) + + \overload + + The postfix -- operator (\c{i--}) makes the preceding item + current and returns an iterator pointing to the previously + current item. +*/ + +/*! \fn QHash::iterator QHash::iterator::operator+(int j) const + + Returns an iterator to the item at \a j positions forward from + this iterator. (If \a j is negative, the iterator goes backward.) + + This operation can be slow for large \a j values. + + \sa operator-() + +*/ + +/*! \fn QHash::iterator QHash::iterator::operator-(int j) const + + Returns an iterator to the item at \a j positions backward from + this iterator. (If \a j is negative, the iterator goes forward.) + + This operation can be slow for large \a j values. + + \sa operator+() +*/ + +/*! \fn QHash::iterator &QHash::iterator::operator+=(int j) + + Advances the iterator by \a j items. (If \a j is negative, the + iterator goes backward.) + + \sa operator-=(), operator+() +*/ + +/*! \fn QHash::iterator &QHash::iterator::operator-=(int j) + + Makes the iterator go back by \a j items. (If \a j is negative, + the iterator goes forward.) + + \sa operator+=(), operator-() +*/ + +/*! \class QHash::const_iterator + \brief The QHash::const_iterator class provides an STL-style const iterator for QHash and QMultiHash. + + QHash features both \l{STL-style iterators} and \l{Java-style + iterators}. The STL-style iterators are more low-level and more + cumbersome to use; on the other hand, they are slightly faster + and, for developers who already know STL, have the advantage of + familiarity. + + QHash\<Key, T\>::const_iterator allows you to iterate over a + QHash (or a QMultiHash). If you want to modify the QHash as you + iterate over it, you must use QHash::iterator instead. It is + generally good practice to use QHash::const_iterator on a + non-const QHash as well, unless you need to change the QHash + through the iterator. Const iterators are slightly faster, and + can improve code readability. + + The default QHash::const_iterator constructor creates an + uninitialized iterator. You must initialize it using a QHash + function like QHash::constBegin(), QHash::constEnd(), or + QHash::find() before you can start iterating. Here's a typical + loop that prints all the (key, value) pairs stored in a hash: + + \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 23 + + Unlike QMap, which orders its items by key, QHash stores its + items in an arbitrary order. The only guarantee is that items that + share the same key (because they were inserted using + QHash::insertMulti()) will appear consecutively, from the most + recently to the least recently inserted value. + + Multiple iterators can be used on the same hash. However, be aware + that any modification performed directly on the QHash has the + potential of dramatically changing the order in which the items + are stored in the hash, as they might cause QHash to rehash its + internal data structure. If you need to keep iterators over a long + period of time, we recommend that you use QMap rather than QHash. + + \sa QHash::iterator, QHashIterator +*/ + +/*! \fn QHash::const_iterator::operator Node *() const + + \internal +*/ + +/*! \fn QHash::const_iterator::const_iterator() + + Constructs an uninitialized iterator. + + Functions like key(), value(), and operator++() must not be + called on an uninitialized iterator. Use operator=() to assign a + value to it before using it. + + \sa QHash::constBegin() QHash::constEnd() +*/ + +/*! \fn QHash::const_iterator::const_iterator(void *node) + + \internal +*/ + +/*! \fn QHash::const_iterator::const_iterator(const iterator &other) + + Constructs a copy of \a other. +*/ + +/*! \fn const Key &QHash::const_iterator::key() const + + Returns the current item's key. + + \sa value() +*/ + +/*! \fn const T &QHash::const_iterator::value() const + + Returns the current item's value. + + \sa key(), operator*() +*/ + +/*! \fn const T &QHash::const_iterator::operator*() const + + Returns the current item's value. + + Same as value(). + + \sa key() +*/ + +/*! \fn const T *QHash::const_iterator::operator->() const + + Returns a pointer to the current item's value. + + \sa value() +*/ + +/*! \fn bool QHash::const_iterator::operator==(const const_iterator &other) const + + Returns true if \a other points to the same item as this + iterator; otherwise returns false. + + \sa operator!=() +*/ + +/*! \fn bool QHash::const_iterator::operator!=(const const_iterator &other) const + + Returns true if \a other points to a different item than this + iterator; otherwise returns false. + + \sa operator==() +*/ + +/*! + \fn QHash::const_iterator &QHash::const_iterator::operator++() + + The prefix ++ operator (\c{++i}) advances the iterator to the + next item in the hash and returns an iterator to the new current + item. + + Calling this function on QHash::end() leads to undefined results. + + \sa operator--() +*/ + +/*! \fn QHash::const_iterator QHash::const_iterator::operator++(int) + + \overload + + The postfix ++ operator (\c{i++}) advances the iterator to the + next item in the hash and returns an iterator to the previously + current item. +*/ + +/*! \fn QHash::const_iterator &QHash::const_iterator::operator--() + + The prefix -- operator (\c{--i}) makes the preceding item + current and returns an iterator pointing to the new current item. + + Calling this function on QHash::begin() leads to undefined + results. + + \sa operator++() +*/ + +/*! \fn QHash::const_iterator QHash::const_iterator::operator--(int) + + \overload + + The postfix -- operator (\c{i--}) makes the preceding item + current and returns an iterator pointing to the previously + current item. +*/ + +/*! \fn QHash::const_iterator QHash::const_iterator::operator+(int j) const + + Returns an iterator to the item at \a j positions forward from + this iterator. (If \a j is negative, the iterator goes backward.) + + This operation can be slow for large \a j values. + + \sa operator-() +*/ + +/*! \fn QHash::const_iterator QHash::const_iterator::operator-(int j) const + + Returns an iterator to the item at \a j positions backward from + this iterator. (If \a j is negative, the iterator goes forward.) + + This operation can be slow for large \a j values. + + \sa operator+() +*/ + +/*! \fn QHash::const_iterator &QHash::const_iterator::operator+=(int j) + + Advances the iterator by \a j items. (If \a j is negative, the + iterator goes backward.) + + This operation can be slow for large \a j values. + + \sa operator-=(), operator+() +*/ + +/*! \fn QHash::const_iterator &QHash::const_iterator::operator-=(int j) + + Makes the iterator go back by \a j items. (If \a j is negative, + the iterator goes forward.) + + This operation can be slow for large \a j values. + + \sa operator+=(), operator-() +*/ + +/*! \fn uint qHash(char key) + \relates QHash + + Returns the hash value for the \a key. +*/ + +/*! \fn uint qHash(uchar key) + \relates QHash + \overload + + Returns the hash value for the \a key. +*/ + +/*! \fn uint qHash(signed char key) + \relates QHash + \overload + + Returns the hash value for the \a key. +*/ + +/*! \fn uint qHash(ushort key) + \relates QHash + \overload + + Returns the hash value for the \a key. +*/ + +/*! \fn uint qHash(short key) + \relates QHash + \overload + + Returns the hash value for the \a key. +*/ + +/*! \fn uint qHash(uint key) + \relates QHash + \overload + + Returns the hash value for the \a key. +*/ + +/*! \fn uint qHash(int key) + \relates QHash + \overload + + Returns the hash value for the \a key. +*/ + +/*! \fn uint qHash(ulong key) + \relates QHash + \overload + + Returns the hash value for the \a key. +*/ + +/*! \fn uint qHash(long key) + \relates QHash + \overload + + Returns the hash value for the \a key. +*/ + +/*! \fn uint qHash(quint64 key) + \relates QHash + \overload + + Returns the hash value for the \a key. +*/ + +/*! \fn uint qHash(qint64 key) + \relates QHash + \overload + + Returns the hash value for the \a key. +*/ + +/*! \fn uint qHash(QChar key) + \relates QHash + \overload + + Returns the hash value for the \a key. +*/ + +/*! \fn uint qHash(const QByteArray &key) + \fn uint qHash(const QBitArray &key) + \relates QHash + \overload + + Returns the hash value for the \a key. +*/ + +/*! \fn uint qHash(const QString &key) + \relates QHash + \overload + + Returns the hash value for the \a key. +*/ + +/*! \fn uint qHash(const T *key) + \relates QHash + \overload + + Returns the hash value for the \a key. +*/ + +/*! + \fn uint qHash(const QPair<T1, T2> &key) + \relates QHash + \since 4.3 + + Returns the hash value for the \a key. + + Types \c T1 and \c T2 must be supported by qHash(). +*/ + +/*! \fn QDataStream &operator<<(QDataStream &out, const QHash<Key, T>& hash) + \relates QHash + + Writes the hash \a hash to stream \a out. + + This function requires the key and value types to implement \c + operator<<(). + + \sa {Format of the QDataStream operators} +*/ + +/*! \fn QDataStream &operator>>(QDataStream &in, QHash<Key, T> &hash) + \relates QHash + + Reads a hash from stream \a in into \a hash. + + This function requires the key and value types to implement \c + operator>>(). + + \sa {Format of the QDataStream operators} +*/ + +/*! \class QMultiHash + \brief The QMultiHash class is a convenience QHash subclass that provides multi-valued hashes. + + \ingroup tools + \ingroup shared + \mainclass + \reentrant + + QMultiHash\<Key, T\> is one of Qt's generic \l{container classes}. + It inherits QHash and extends it with a few convenience functions + that make it more suitable than QHash for storing multi-valued + hashes. A multi-valued hash is a hash that allows multiple values + with the same key; QHash normally doesn't allow that, unless you + call QHash::insertMulti(). + + Because QMultiHash inherits QHash, all of QHash's functionality also + applies to QMultiHash. For example, you can use isEmpty() to test + whether the hash is empty, and you can traverse a QMultiHash using + QHash's iterator classes (for example, QHashIterator). But in + addition, it provides an insert() function that corresponds to + QHash::insertMulti(), and a replace() function that corresponds to + QHash::insert(). It also provides convenient operator+() and + operator+=(). + + Example: + \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 24 + + Unlike QHash, QMultiHash provides no operator[]. Use value() or + replace() if you want to access the most recently inserted item + with a certain key. + + If you want to retrieve all the values for a single key, you can + use values(const Key &key), which returns a QList<T>: + + \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 25 + + The items that share the same key are available from most + recently to least recently inserted. + + A more efficient approach is to call find() to get + the STL-style iterator for the first item with a key and iterate from + there: + + \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 26 + + QMultiHash's key and value data types must be \l{assignable data + types}. You cannot, for example, store a QWidget as a value; + instead, store a QWidget *. In addition, QMultiHash's key type + must provide operator==(), and there must also be a global + qHash() function that returns a hash value for an argument of the + key's type. See the QHash documentation for details. + + \sa QHash, QHashIterator, QMutableHashIterator, QMultiMap +*/ + +/*! \fn QMultiHash::QMultiHash() + + Constructs an empty hash. +*/ + +/*! \fn QMultiHash::QMultiHash(const QHash<Key, T> &other) + + Constructs a copy of \a other (which can be a QHash or a + QMultiHash). + + \sa operator=() +*/ + +/*! \fn QMultiHash::iterator QMultiHash::replace(const Key &key, const T &value) + + Inserts a new item with the \a key and a value of \a value. + + If there is already an item with the \a key, that item's value + is replaced with \a value. + + If there are multiple items with the \a key, the most + recently inserted item's value is replaced with \a value. + + \sa insert() +*/ + +/*! \fn QMultiHash::iterator QMultiHash::insert(const Key &key, const T &value) + + Inserts a new item with the \a key and a value of \a value. + + If there is already an item with the same key in the hash, this + function will simply create a new one. (This behavior is + different from replace(), which overwrites the value of an + existing item.) + + \sa replace() +*/ + +/*! \fn QMultiHash &QMultiHash::operator+=(const QMultiHash &other) + + Inserts all the items in the \a other hash into this hash + and returns a reference to this hash. + + \sa insert() +*/ + +/*! \fn QMultiHash QMultiHash::operator+(const QMultiHash &other) const + + Returns a hash that contains all the items in this hash in + addition to all the items in \a other. If a key is common to both + hashes, the resulting hash will contain the key multiple times. + + \sa operator+=() +*/ + +/*! + \fn bool QMultiHash::contains(const Key &key, const T &value) const + \since 4.3 + + Returns true if the hash contains an item with the \a key and + \a value; otherwise returns false. + + \sa QHash::contains() +*/ + +/*! + \fn bool QMultiHash::contains(const Key &key) const + \overload + \sa QHash::contains() +*/ + +/*! + \fn int QMultiHash::remove(const Key &key, const T &value) + \since 4.3 + + Removes all the items that have the \a key and the value \a + value from the hash. Returns the number of items removed. + + \sa QHash::remove() +*/ + +/*! + \fn int QMultiHash::remove(const Key &key) + \overload + \sa QHash::remove() +*/ + +/*! + \fn int QMultiHash::count(const Key &key, const T &value) const + \since 4.3 + + Returns the number of items with the \a key and \a value. + + \sa QHash::count() +*/ + +/*! + \fn int QMultiHash::count(const Key &key) const + \overload + \sa QHash::count() +*/ + +/*! + \fn int QMultiHash::count() const + \overload + \sa QHash::count() +*/ + +/*! + \fn typename QHash<Key, T>::iterator QMultiHash::find(const Key &key, const T &value) + \since 4.3 + + Returns an iterator pointing to the item with the \a key and \a value. + If the hash contains no such item, the function returns end(). + + If the hash contains multiple items with the \a key and \a value, the + iterator returned points to the most recently inserted item. + + \sa QHash::find() +*/ + +/*! + \fn typename QHash<Key, T>::iterator QMultiHash::find(const Key &key) + \overload + \sa QHash::find() +*/ + +/*! + \fn typename QHash<Key, T>::const_iterator QMultiHash::find(const Key &key, const T &value) const + \since 4.3 + \overload +*/ + +/*! + \fn typename QHash<Key, T>::const_iterator QMultiHash::find(const Key &key) const + \overload + \sa QHash::find() +*/ + +/*! + \fn typename QHash<Key, T>::const_iterator QMultiHash::constFind(const Key &key, const T &value) const + \since 4.3 + + Returns an iterator pointing to the item with the \a key and the + \a value in the hash. + + If the hash contains no such item, the function returns + constEnd(). + + \sa QHash::constFind() +*/ + +/*! + \fn typename QHash<Key, T>::const_iterator QMultiHash::constFind(const Key &key) const + \overload + \sa QHash::constFind() +*/ + +QT_END_NAMESPACE |