1 /****************************************************************************

     2 **

     3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

     4 ** All rights reserved.

     5 ** Contact: Nokia Corporation (qt-info@nokia.com)

     6 **

     7 ** This file is part of the QtCore module of the Qt Toolkit.

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

    11 ** This file contains pre-release code and may not be distributed.

    12 ** You may use this file in accordance with the terms and conditions

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    15 **

    16 ** GNU Lesser General Public License Usage

    17 ** Alternatively, this file may be used under the terms of the GNU Lesser

    18 ** General Public License version 2.1 as published by the Free Software

    19 ** Foundation and appearing in the file LICENSE.LGPL included in the

    20 ** packaging of this file.  Please review the following information to

    21 ** ensure the GNU Lesser General Public License version 2.1 requirements

    22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

    23 **

    24 ** In addition, as a special exception, Nokia gives you certain additional

    25 ** rights.  These rights are described in the Nokia Qt LGPL Exception

    26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

    27 **

    28 ** If you have questions regarding the use of this file, please contact

    29 ** Nokia at qt-info@nokia.com.

    30 **

    31 **

    32 **

    33 **

    34 **

    35 **

    36 **

    37 **

    38 ** $QT_END_LICENSE$

    39 **

    40 ****************************************************************************/

    41 

    42 #include "qhash.h"

    43 

    44 #ifdef truncate

    45 #undef truncate

    46 #endif

    47 

    48 #include <qbitarray.h>

    49 #include <qstring.h>

    50 #include <stdlib.h>

    51 #ifdef QT_QHASH_DEBUG

    52 #include <qstring.h>

    53 #endif

    54 

    55 QT_BEGIN_NAMESPACE

    56 

    57 /*

    58     These functions are based on Peter J. Weinberger's hash function

    59     (from the Dragon Book). The constant 24 in the original function

    60     was replaced with 23 to produce fewer collisions on input such as

    61     "a", "aa", "aaa", "aaaa", ...

    62 */

    63 

    64 static uint hash(const uchar *p, int n)

    65 {

    66     uint h = 0;

    67     uint g;

    68 

    69     while (n--) {

    70         h = (h << 4) + *p++;

    71         if ((g = (h & 0xf0000000)) != 0)

    72             h ^= g >> 23;

    73         h &= ~g;

    74     }

    75     return h;

    76 }

    77 

    78 static uint hash(const QChar *p, int n)

    79 {

    80     uint h = 0;

    81     uint g;

    82 

    83     while (n--) {

    84         h = (h << 4) + (*p++).unicode();

    85         if ((g = (h & 0xf0000000)) != 0)

    86             h ^= g >> 23;

    87         h &= ~g;

    88     }

    89     return h;

    90 }

    91 

    92 uint qHash(const QByteArray &key)

    93 {

    94     return hash(reinterpret_cast<const uchar *>(key.constData()), key.size());

    95 }

    96 

    97 uint qHash(const QString &key)

    98 {

    99     return hash(key.unicode(), key.size());

   100 }

   101 

   102 uint qHash(const QStringRef &key)

   103 {

   104     return hash(key.unicode(), key.size());

   105 }

   106 

   107 uint qHash(const QBitArray &bitArray)

   108 {

   109     int m = bitArray.d.size() - 1;

   110     uint result = hash(reinterpret_cast<const uchar *>(bitArray.d.constData()), qMax(0, m));

   111 

   112     // deal with the last 0 to 7 bits manually, because we can't trust that

   113     // the padding is initialized to 0 in bitArray.d

   114     int n = bitArray.size();

   115     if (n & 0x7)

   116         result = ((result << 4) + bitArray.d.at(m)) & ((1 << n) - 1);

   117     return result;

   118 }

   119 

   120 /*

   121     The prime_deltas array is a table of selected prime values, even

   122     though it doesn't look like one. The primes we are using are 1,

   123     2, 5, 11, 17, 37, 67, 131, 257, ..., i.e. primes in the immediate

   124     surrounding of a power of two.

   125 

   126     The primeForNumBits() function returns the prime associated to a

   127     power of two. For example, primeForNumBits(8) returns 257.

   128 */

   129 

   130 static const uchar prime_deltas[] = {

   131     0,  0,  1,  3,  1,  5,  3,  3,  1,  9,  7,  5,  3,  9, 25,  3,

   132     1, 21,  3, 21,  7, 15,  9,  5,  3, 29, 15,  0,  0,  0,  0,  0

   133 };

   134 

   135 static inline int primeForNumBits(int numBits)

   136 {

   137     return (1 << numBits) + prime_deltas[numBits];

   138 }

   139 

   140 /*

   141     Returns the smallest integer n such that

   142     primeForNumBits(n) >= hint.

   143 */

   144 static int countBits(int hint)

   145 {

   146     int numBits = 0;

   147     int bits = hint;

   148 

   149     while (bits > 1) {

   150         bits >>= 1;

   151         numBits++;

   152     }

   153 

   154     if (numBits >= (int)sizeof(prime_deltas)) {

   155         numBits = sizeof(prime_deltas) - 1;

   156     } else if (primeForNumBits(numBits) < hint) {

   157         ++numBits;

   158     }

   159     return numBits;

   160 }

   161 

   162 /*

   163     A QHash has initially around pow(2, MinNumBits) buckets. For

   164     example, if MinNumBits is 4, it has 17 buckets.

   165 */

   166 const int MinNumBits = 4;

   167 

   168 QHashData QHashData::shared_null = {

   169     0, 0, Q_BASIC_ATOMIC_INITIALIZER(1), 0, 0, MinNumBits, 0, 0, true

   170 };

   171 

   172 void *QHashData::allocateNode()

   173 {

   174     void *ptr = qMalloc(nodeSize);

   175     Q_CHECK_PTR(ptr);

   176     return ptr;

   177 }

   178 

   179 void QHashData::freeNode(void *node)

   180 {

   181     qFree(node);

   182 }

   183 

   184 QHashData *QHashData::detach_helper(void (*node_duplicate)(Node *, void *), int nodeSize)

   185 {

   186     return detach_helper( node_duplicate, 0, nodeSize );

   187 }

   188 

   189 QHashData *QHashData::detach_helper(void (*node_duplicate)(Node *, void *),

   190         void (*node_delete)(Node *),

   191         int nodeSize)

   192 {

   193     union {

   194         QHashData *d;

   195         Node *e;

   196     };

   197     d = new QHashData;

   198     d->fakeNext = 0;

   199     d->buckets = 0;

   200     d->ref = 1;

   201     d->size = size;

   202     d->nodeSize = nodeSize;

   203     d->userNumBits = userNumBits;

   204     d->numBits = numBits;

   205     d->numBuckets = numBuckets;

   206     d->sharable = true;

   207 

   208     if (numBuckets) {

   209         QT_TRY {

   210             d->buckets = new Node *[numBuckets];

   211         } QT_CATCH(...) {

   212             // restore a consistent state for d

   213             d->numBuckets = 0;

   214             // roll back

   215             d->free_helper(node_delete);

   216             QT_RETHROW;

   217         }

   218 

   219         Node *this_e = reinterpret_cast<Node *>(this);

   220         for (int i = 0; i < numBuckets; ++i) {

   221             Node **nextNode = &d->buckets[i];

   222             Node *oldNode = buckets[i];

   223             while (oldNode != this_e) {

   224                 QT_TRY {

   225                     Node *dup = static_cast<Node *>(allocateNode());

   226 

   227                     QT_TRY {

   228                         node_duplicate(oldNode, dup);

   229                     } QT_CATCH(...) {

   230                         freeNode( dup );

   231                         QT_RETHROW;

   232                     }

   233 

   234                     dup->h = oldNode->h;

   235                     *nextNode = dup;

   236                     nextNode = &dup->next;

   237                     oldNode = oldNode->next;

   238                 } QT_CATCH(...) {

   239                     // restore a consistent state for d

   240                     *nextNode = e;

   241                     d->numBuckets = i+1;

   242                     // roll back

   243                     d->free_helper(node_delete);

   244                     QT_RETHROW;

   245                 }

   246             }

   247             *nextNode = e;

   248         }

   249     }

   250     return d;

   251 }

   252 

   253 void QHashData::free_helper(void (*node_delete)(Node *))

   254 {

   255     if (node_delete) {

   256         Node *this_e = reinterpret_cast<Node *>(this);

   257         Node **bucket = reinterpret_cast<Node **>(this->buckets);

   258 

   259         int n = numBuckets;

   260         while (n--) {

   261             Node *cur = *bucket++;

   262             while (cur != this_e) {

   263                 Node *next = cur->next;

   264                 node_delete(cur);

   265                 cur = next;

   266             }

   267         }

   268     }

   269     delete [] buckets;

   270     delete this;

   271 }

   272 

   273 QHashData::Node *QHashData::nextNode(Node *node)

   274 {

   275     union {

   276         Node *next;

   277         Node *e;

   278         QHashData *d;

   279     };

   280     next = node->next;

   281     Q_ASSERT_X(next, "QHash", "Iterating beyond end()");

   282     if (next->next)

   283         return next;

   284 

   285     int start = (node->h % d->numBuckets) + 1;

   286     Node **bucket = d->buckets + start;

   287     int n = d->numBuckets - start;

   288     while (n--) {

   289         if (*bucket != e)

   290             return *bucket;

   291         ++bucket;

   292     }

   293     return e;

   294 }

   295 

   296 QHashData::Node *QHashData::previousNode(Node *node)

   297 {

   298     union {

   299         Node *e;

   300         QHashData *d;

   301     };

   302 

   303     e = node;

   304     while (e->next)

   305         e = e->next;

   306 

   307     int start;

   308     if (node == e)

   309         start = d->numBuckets - 1;

   310     else

   311         start = node->h % d->numBuckets;

   312 

   313     Node *sentinel = node;

   314     Node **bucket = d->buckets + start;

   315     while (start >= 0) {

   316         if (*bucket != sentinel) {

   317             Node *prev = *bucket;

   318             while (prev->next != sentinel)

   319                 prev = prev->next;

   320             return prev;

   321         }

   322 

   323         sentinel = e;

   324         --bucket;

   325         --start;

   326     }

   327     Q_ASSERT_X(start >= 0, "QHash", "Iterating backward beyond begin()");

   328     return e;

   329 }

   330 

   331 /*

   332     If hint is negative, -hint gives the approximate number of

   333     buckets that should be used for the hash table. If hint is

   334     nonnegative, (1 << hint) gives the approximate number

   335     of buckets that should be used.

   336 */

   337 void QHashData::rehash(int hint)

   338 {

   339     if (hint < 0) {

   340         hint = countBits(-hint);

   341         if (hint < MinNumBits)

   342             hint = MinNumBits;

   343         userNumBits = hint;

   344         while (primeForNumBits(hint) < (size >> 1))

   345             ++hint;

   346     } else if (hint < MinNumBits) {

   347         hint = MinNumBits;

   348     }

   349 

   350     if (numBits != hint) {

   351         Node *e = reinterpret_cast<Node *>(this);

   352         Node **oldBuckets = buckets;

   353         int oldNumBuckets = numBuckets;

   354 

   355         int nb = primeForNumBits(hint);

   356         buckets = new Node *[nb];

   357         numBits = hint;

   358         numBuckets = nb;

   359         for (int i = 0; i < numBuckets; ++i)

   360             buckets[i] = e;

   361 

   362         for (int i = 0; i < oldNumBuckets; ++i) {

   363             Node *firstNode = oldBuckets[i];

   364             while (firstNode != e) {

   365                 uint h = firstNode->h;

   366                 Node *lastNode = firstNode;

   367                 while (lastNode->next != e && lastNode->next->h == h)

   368                     lastNode = lastNode->next;

   369 

   370                 Node *afterLastNode = lastNode->next;

   371                 Node **beforeFirstNode = &buckets[h % numBuckets];

   372                 while (*beforeFirstNode != e)

   373                     beforeFirstNode = &(*beforeFirstNode)->next;

   374                 lastNode->next = *beforeFirstNode;

   375                 *beforeFirstNode = firstNode;

   376                 firstNode = afterLastNode;

   377             }

   378         }

   379         delete [] oldBuckets;

   380     }

   381 }

   382 

   383 void QHashData::destroyAndFree()

   384 {

   385     free_helper(0);

   386 }

   387 

   388 #ifdef QT_QHASH_DEBUG

   389 

   390 void QHashData::dump()

   391 {

   392     qDebug("Hash data (ref = %d, size = %d, nodeSize = %d, userNumBits = %d, numBits = %d, numBuckets = %d)",

   393             int(ref), size, nodeSize, userNumBits, numBits,

   394             numBuckets);

   395     qDebug("    %p (fakeNode = %p)", this, fakeNext);

   396     for (int i = 0; i < numBuckets; ++i) {

   397         QString line;

   398         Node *n = buckets[i];

   399         if (n != reinterpret_cast<Node *>(this)) {

   400             line.sprintf("%d:", i);

   401             while (n != reinterpret_cast<Node *>(this)) {

   402                 line += QString().sprintf(" -> [%p]", n);

   403                 if (!n) {

   404                     line += " (CORRUPT)";

   405                     break;

   406                 }

   407                 n = n->next;

   408             }

   409             qDebug(qPrintable(line));

   410         }

   411     }

   412 }

   413 

   414 void QHashData::checkSanity()

   415 {

   416     if (fakeNext)

   417         qFatal("Fake next isn't 0");

   418 

   419     for (int i = 0; i < numBuckets; ++i) {

   420         Node *n = buckets[i];

   421         Node *p = n;

   422         if (!n)

   423             qFatal("%d: Bucket entry is 0", i);

   424         if (n != reinterpret_cast<Node *>(this)) {

   425             while (n != reinterpret_cast<Node *>(this)) {

   426                 if (!n->next)

   427                     qFatal("%d: Next of %p is 0, should be %p", i, n, this);

   428                 n = n->next;

   429             }

   430         }

   431     }

   432 }

   433 #endif

   434 

   435 /*!

   436     \fn uint qHash(const QPair<T1, T2> &key)

   437     \since 4.3

   438     \relates QHash

   439     

   440     Returns the hash value for the \a key.

   441 

   442     Types \c T1 and \c T2 must be supported by qHash().

   443 */

   444 

   445 /*! \fn uint qHash(char key)

   446     \relates QHash

   447 

   448     Returns the hash value for the \a key.

   449 */

   450 

   451 /*! \fn uint qHash(uchar key)

   452     \relates QHash

   453 

   454     Returns the hash value for the \a key.

   455 */

   456 

   457 /*! \fn uint qHash(signed char key)

   458     \relates QHash

   459 

   460     Returns the hash value for the \a key.

   461 */

   462 

   463 /*! \fn uint qHash(ushort key)

   464     \relates QHash

   465 

   466     Returns the hash value for the \a key.

   467 */

   468 

   469 /*! \fn uint qHash(short key)

   470     \relates QHash

   471 

   472     Returns the hash value for the \a key.

   473 */

   474 

   475 /*! \fn uint qHash(uint key)

   476     \relates QHash

   477 

   478     Returns the hash value for the \a key.

   479 */

   480 

   481 /*! \fn uint qHash(int key)

   482     \relates QHash

   483 

   484     Returns the hash value for the \a key.

   485 */

   486 

   487 /*! \fn uint qHash(ulong key)

   488     \relates QHash

   489 

   490     Returns the hash value for the \a key.

   491 */

   492 

   493 /*! \fn uint qHash(long key)

   494     \relates QHash

   495 

   496     Returns the hash value for the \a key.

   497 */

   498 

   499 /*! \fn uint qHash(quint64 key)

   500     \relates QHash

   501 

   502     Returns the hash value for the \a key.

   503 */

   504 

   505 /*! \fn uint qHash(qint64 key)

   506     \relates QHash

   507 

   508     Returns the hash value for the \a key.

   509 */

   510 

   511 /*! \fn uint qHash(QChar key)

   512     \relates QHash

   513 

   514     Returns the hash value for the \a key.

   515 */

   516 

   517 /*! \fn uint qHash(const QByteArray &key)

   518     \fn uint qHash(const QBitArray &key)

   519     \relates QHash

   520 

   521     Returns the hash value for the \a key.

   522 */

   523 

   524 /*! \fn uint qHash(const QString &key)

   525     \relates QHash

   526 

   527     Returns the hash value for the \a key.

   528 */

   529 

   530 /*! \fn uint qHash(const T *key)

   531     \relates QHash

   532 

   533     Returns the hash value for the \a key.

   534 */

   535 

   536 /*!

   537     \class QHash

   538     \brief The QHash class is a template class that provides a hash-table-based dictionary.

   539 

   540     \ingroup tools

   541     \ingroup shared

   542 

   543     \reentrant

   544 

   545     QHash\<Key, T\> is one of Qt's generic \l{container classes}. It

   546     stores (key, value) pairs and provides very fast lookup of the

   547     value associated with a key.

   548 

   549     QHash provides very similar functionality to QMap. The

   550     differences are:

   551 

   552     \list

   553     \i QHash provides faster lookups than QMap. (See \l{Algorithmic

   554        Complexity} for details.)

   555     \i When iterating over a QMap, the items are always sorted by

   556        key. With QHash, the items are arbitrarily ordered.

   557     \i The key type of a QMap must provide operator<(). The key

   558        type of a QHash must provide operator==() and a global

   559        hash function called qHash() (see the related non-member

   560        functions).

   561     \endlist

   562 

   563     Here's an example QHash with QString keys and \c int values:

   564     \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 0

   565 

   566     To insert a (key, value) pair into the hash, you can use operator[]():

   567 

   568     \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 1

   569 

   570     This inserts the following three (key, value) pairs into the

   571     QHash: ("one", 1), ("three", 3), and ("seven", 7). Another way to

   572     insert items into the hash is to use insert():

   573 

   574     \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 2

   575 

   576     To look up a value, use operator[]() or value():

   577 

   578     \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 3

   579 

   580     If there is no item with the specified key in the hash, these

   581     functions return a \l{default-constructed value}.

   582 

   583     If you want to check whether the hash contains a particular key,

   584     use contains():

   585 

   586     \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 4

   587 

   588     There is also a value() overload that uses its second argument as

   589     a default value if there is no item with the specified key:

   590 

   591     \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 5

   592 

   593     In general, we recommend that you use contains() and value()

   594     rather than operator[]() for looking up a key in a hash. The

   595     reason is that operator[]() silently inserts an item into the

   596     hash if no item exists with the same key (unless the hash is

   597     const). For example, the following code snippet will create 1000

   598     items in memory:

   599 

   600     \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 6

   601 

   602     To avoid this problem, replace \c hash[i] with \c hash.value(i)

   603     in the code above.

   604 

   605     If you want to navigate through all the (key, value) pairs stored

   606     in a QHash, you can use an iterator. QHash provides both

   607     \l{Java-style iterators} (QHashIterator and QMutableHashIterator)

   608     and \l{STL-style iterators} (QHash::const_iterator and

   609     QHash::iterator). Here's how to iterate over a QHash<QString,

   610     int> using a Java-style iterator:

   611 

   612     \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 7

   613 

   614     Here's the same code, but using an STL-style iterator:

   615 

   616     \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 8

   617 

   618     QHash is unordered, so an iterator's sequence cannot be assumed

   619     to be predictable. If ordering by key is required, use a QMap.

   620 

   621     Normally, a QHash allows only one value per key. If you call

   622     insert() with a key that already exists in the QHash, the

   623     previous value is erased. For example:

   624 

   625     \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 9

   626 

   627     However, you can store multiple values per key by using

   628     insertMulti() instead of insert() (or using the convenience

   629     subclass QMultiHash). If you want to retrieve all

   630     the values for a single key, you can use values(const Key &key),

   631     which returns a QList<T>:

   632 

   633     \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 10

   634 

   635     The items that share the same key are available from most

   636     recently to least recently inserted. A more efficient approach is

   637     to call find() to get the iterator for the first item with a key

   638     and iterate from there:

   639 

   640     \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 11

   641 

   642     If you only need to extract the values from a hash (not the keys),

   643     you can also use \l{foreach}:

   644 

   645     \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 12

   646 

   647     Items can be removed from the hash in several ways. One way is to

   648     call remove(); this will remove any item with the given key.

   649     Another way is to use QMutableHashIterator::remove(). In addition,

   650     you can clear the entire hash using clear().

   651 

   652     QHash's key and value data types must be \l{assignable data

   653     types}. You cannot, for example, store a QWidget as a value;

   654     instead, store a QWidget *. In addition, QHash's key type must

   655     provide operator==(), and there must also be a global qHash()

   656     function that returns a hash value for an argument of the key's

   657     type.

   658 

   659     Here's a list of the C++ and Qt types that can serve as keys in a

   660     QHash: any integer type (char, unsigned long, etc.), any pointer

   661     type, QChar, QString, and QByteArray. For all of these, the \c

   662     <QHash> header defines a qHash() function that computes an

   663     adequate hash value. If you want to use other types as the key,

   664     make sure that you provide operator==() and a qHash()

   665     implementation.

   666 

   667     Example:

   668     \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 13

   669 

   670     The qHash() function computes a numeric value based on a key. It

   671     can use any algorithm imaginable, as long as it always returns

   672     the same value if given the same argument. In other words, if

   673     \c{e1 == e2}, then \c{qHash(e1) == qHash(e2)} must hold as well.

   674     However, to obtain good performance, the qHash() function should

   675     attempt to return different hash values for different keys to the

   676     largest extent possible.

   677 

   678     In the example above, we've relied on Qt's global qHash(const

   679     QString &) to give us a hash value for the employee's name, and

   680     XOR'ed this with the day they were born to help produce unique

   681     hashes for people with the same name.

   682 

   683     Internally, QHash uses a hash table to perform lookups. Unlike Qt

   684     3's \c QDict class, which needed to be initialized with a prime

   685     number, QHash's hash table automatically grows and shrinks to

   686     provide fast lookups without wasting too much memory. You can

   687     still control the size of the hash table by calling reserve() if

   688     you already know approximately how many items the QHash will

   689     contain, but this isn't necessary to obtain good performance. You

   690     can also call capacity() to retrieve the hash table's size.

   691 

   692     \sa QHashIterator, QMutableHashIterator, QMap, QSet

   693 */

   694 

   695 /*! \fn QHash::QHash()

   696 

   697     Constructs an empty hash.

   698 

   699     \sa clear()

   700 */

   701 

   702 /*! \fn QHash::QHash(const QHash<Key, T> &other)

   703 

   704     Constructs a copy of \a other.

   705 

   706     This operation occurs in \l{constant time}, because QHash is

   707     \l{implicitly shared}. This makes returning a QHash from a

   708     function very fast. If a shared instance is modified, it will be

   709     copied (copy-on-write), and this takes \l{linear time}.

   710 

   711     \sa operator=()

   712 */

   713 

   714 /*! \fn QHash::~QHash()

   715 

   716     Destroys the hash. References to the values in the hash and all

   717     iterators of this hash become invalid.

   718 */

   719 

   720 /*! \fn QHash<Key, T> &QHash::operator=(const QHash<Key, T> &other)

   721 

   722     Assigns \a other to this hash and returns a reference to this hash.

   723 */

   724 

   725 /*! \fn bool QHash::operator==(const QHash<Key, T> &other) const

   726 

   727     Returns true if \a other is equal to this hash; otherwise returns

   728     false.

   729 

   730     Two hashes are considered equal if they contain the same (key,

   731     value) pairs.

   732 

   733     This function requires the value type to implement \c operator==().

   734 

   735     \sa operator!=()

   736 */

   737 

   738 /*! \fn bool QHash::operator!=(const QHash<Key, T> &other) const

   739 

   740     Returns true if \a other is not equal to this hash; otherwise

   741     returns false.

   742 

   743     Two hashes are considered equal if they contain the same (key,

   744     value) pairs.

   745 

   746     This function requires the value type to implement \c operator==().

   747 

   748     \sa operator==()

   749 */

   750 

   751 /*! \fn int QHash::size() const

   752 

   753     Returns the number of items in the hash.

   754 

   755     \sa isEmpty(), count()

   756 */

   757 

   758 /*! \fn bool QHash::isEmpty() const

   759 

   760     Returns true if the hash contains no items; otherwise returns

   761     false.

   762 

   763     \sa size()

   764 */

   765 

   766 /*! \fn int QHash::capacity() const

   767 

   768     Returns the number of buckets in the QHash's internal hash table.

   769 

   770     The sole purpose of this function is to provide a means of fine

   771     tuning QHash's memory usage. In general, you will rarely ever

   772     need to call this function. If you want to know how many items are

   773     in the hash, call size().

   774 

   775     \sa reserve(), squeeze()

   776 */

   777 

   778 /*! \fn void QHash::reserve(int size)

   779 

   780     Ensures that the QHash's internal hash table consists of at least

   781     \a size buckets.

   782 

   783     This function is useful for code that needs to build a huge hash

   784     and wants to avoid repeated reallocation. For example:

   785 

   786     \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 14

   787 

   788     Ideally, \a size should be slightly more than the maximum number

   789     of items expected in the hash. \a size doesn't have to be prime,

   790     because QHash will use a prime number internally anyway. If \a size

   791     is an underestimate, the worst that will happen is that the QHash

   792     will be a bit slower.

   793 

   794     In general, you will rarely ever need to call this function.

   795     QHash's internal hash table automatically shrinks or grows to

   796     provide good performance without wasting too much memory.

   797 

   798     \sa squeeze(), capacity()

   799 */

   800 

   801 /*! \fn void QHash::squeeze()

   802 

   803     Reduces the size of the QHash's internal hash table to save

   804     memory.

   805 

   806     The sole purpose of this function is to provide a means of fine

   807     tuning QHash's memory usage. In general, you will rarely ever

   808     need to call this function.

   809 

   810     \sa reserve(), capacity()

   811 */

   812 

   813 /*! \fn void QHash::detach()

   814 

   815     \internal

   816 

   817     Detaches this hash from any other hashes with which it may share

   818     data.

   819 

   820     \sa isDetached()

   821 */

   822 

   823 /*! \fn bool QHash::isDetached() const

   824 

   825     \internal

   826 

   827     Returns true if the hash's internal data isn't shared with any

   828     other hash object; otherwise returns false.

   829 

   830     \sa detach()

   831 */

   832 

   833 /*! \fn void QHash::setSharable(bool sharable)

   834 

   835     \internal

   836 */

   837 

   838 /*! \fn void QHash::clear()

   839 

   840     Removes all items from the hash.

   841 

   842     \sa remove()

   843 */

   844 

   845 /*! \fn int QHash::remove(const Key &key)

   846 

   847     Removes all the items that have the \a key from the hash.

   848     Returns the number of items removed which is usually 1 but will

   849     be 0 if the key isn't in the hash, or greater than 1 if

   850     insertMulti() has been used with the \a key.

   851 

   852     \sa clear(), take(), QMultiHash::remove()

   853 */

   854 

   855 /*! \fn T QHash::take(const Key &key)

   856 

   857     Removes the item with the \a key from the hash and returns

   858     the value associated with it.

   859 

   860     If the item does not exist in the hash, the function simply

   861     returns a \l{default-constructed value}. If there are multiple

   862     items for \a key in the hash, only the most recently inserted one

   863     is removed.

   864 

   865     If you don't use the return value, remove() is more efficient.

   866 

   867     \sa remove()

   868 */

   869 

   870 /*! \fn bool QHash::contains(const Key &key) const

   871 

   872     Returns true if the hash contains an item with the \a key;

   873     otherwise returns false.

   874 

   875     \sa count(), QMultiHash::contains()

   876 */

   877 

   878 /*! \fn const T QHash::value(const Key &key) const

   879 

   880     Returns the value associated with the \a key.

   881 

   882     If the hash contains no item with the \a key, the function

   883     returns a \l{default-constructed value}. If there are multiple

   884     items for the \a key in the hash, the value of the most recently

   885     inserted one is returned.

   886 

   887     \sa key(), values(), contains(), operator[]()

   888 */

   889 

   890 /*! \fn const T QHash::value(const Key &key, const T &defaultValue) const

   891     \overload

   892 

   893     If the hash contains no item with the given \a key, the function returns

   894     \a defaultValue.

   895 */

   896 

   897 /*! \fn T &QHash::operator[](const Key &key)

   898 

   899     Returns the value associated with the \a key as a modifiable

   900     reference.

   901 

   902     If the hash contains no item with the \a key, the function inserts

   903     a \l{default-constructed value} into the hash with the \a key, and

   904     returns a reference to it. If the hash contains multiple items

   905     with the \a key, this function returns a reference to the most

   906     recently inserted value.

   907 

   908     \sa insert(), value()

   909 */

   910 

   911 /*! \fn const T QHash::operator[](const Key &key) const

   912 

   913     \overload

   914 

   915     Same as value().

   916 */

   917 

   918 /*! \fn QList<Key> QHash::uniqueKeys() const

   919     \since 4.2

   920 

   921     Returns a list containing all the keys in the map. Keys that occur multiple

   922     times in the map (because items were inserted with insertMulti(), or

   923     unite() was used) occur only once in the returned list.

   924 

   925     \sa keys(), values()

   926 */

   927 

   928 /*! \fn QList<Key> QHash::keys() const

   929 

   930     Returns a list containing all the keys in the hash, in an

   931     arbitrary order. Keys that occur multiple times in the hash

   932     (because items were inserted with insertMulti(), or unite() was

   933     used) also occur multiple times in the list.

   934 

   935     To obtain a list of unique keys, where each key from the map only

   936     occurs once, use uniqueKeys().

   937 

   938     The order is guaranteed to be the same as that used by values().

   939 

   940     \sa uniqueKeys(), values(), key()

   941 */

   942 

   943 /*! \fn QList<Key> QHash::keys(const T &value) const

   944 

   945     \overload

   946 

   947     Returns a list containing all the keys associated with value \a

   948     value, in an arbitrary order.

   949 

   950     This function can be slow (\l{linear time}), because QHash's

   951     internal data structure is optimized for fast lookup by key, not

   952     by value.

   953 */

   954 

   955 /*! \fn QList<T> QHash::values() const

   956 

   957     Returns a list containing all the values in the hash, in an

   958     arbitrary order. If a key is associated multiple values, all of

   959     its values will be in the list, and not just the most recently

   960     inserted one.

   961 

   962     The order is guaranteed to be the same as that used by keys().

   963 

   964     \sa keys(), value()

   965 */

   966 

   967 /*! \fn QList<T> QHash::values(const Key &key) const

   968 

   969     \overload

   970 

   971     Returns a list of all the values associated with the \a key,

   972     from the most recently inserted to the least recently inserted.

   973 

   974     \sa count(), insertMulti()

   975 */

   976 

   977 /*! \fn Key QHash::key(const T &value) const

   978 

   979     Returns the first key mapped to \a value.

   980 

   981     If the hash contains no item with the \a value, the function

   982     returns a \link {default-constructed value} default-constructed

   983     key \endlink.

   984 

   985     This function can be slow (\l{linear time}), because QHash's

   986     internal data structure is optimized for fast lookup by key, not

   987     by value.

   988 

   989     \sa value(), keys()

   990 */

   991 

   992 /*!

   993     \fn Key QHash::key(const T &value, const Key &defaultKey) const

   994     \since 4.3

   995     \overload

   996 

   997     Returns the first key mapped to \a value, or \a defaultKey if the

   998     hash contains no item mapped to \a value.

   999 

  1000     This function can be slow (\l{linear time}), because QHash's

  1001     internal data structure is optimized for fast lookup by key, not

  1002     by value.

  1003 */

  1004 

  1005 /*! \fn int QHash::count(const Key &key) const

  1006 

  1007     Returns the number of items associated with the \a key.

  1008 

  1009     \sa contains(), insertMulti()

  1010 */

  1011 

  1012 /*! \fn int QHash::count() const

  1013 

  1014     \overload

  1015 

  1016     Same as size().

  1017 */

  1018 

  1019 /*! \fn QHash::iterator QHash::begin()

  1020 

  1021     Returns an \l{STL-style iterator} pointing to the first item in

  1022     the hash.

  1023 

  1024     \sa constBegin(), end()

  1025 */

  1026 

  1027 /*! \fn QHash::const_iterator QHash::begin() const

  1028 

  1029     \overload

  1030 */

  1031 

  1032 /*! \fn QHash::const_iterator QHash::constBegin() const

  1033 

  1034     Returns a const \l{STL-style iterator} pointing to the first item

  1035     in the hash.

  1036 

  1037     \sa begin(), constEnd()

  1038 */

  1039 

  1040 /*! \fn QHash::iterator QHash::end()

  1041 

  1042     Returns an \l{STL-style iterator} pointing to the imaginary item

  1043     after the last item in the hash.

  1044 

  1045     \sa begin(), constEnd()

  1046 */

  1047 

  1048 /*! \fn QHash::const_iterator QHash::end() const

  1049 

  1050     \overload

  1051 */

  1052 

  1053 /*! \fn QHash::const_iterator QHash::constEnd() const

  1054 

  1055     Returns a const \l{STL-style iterator} pointing to the imaginary

  1056     item after the last item in the hash.

  1057 

  1058     \sa constBegin(), end()

  1059 */

  1060 

  1061 /*! \fn QHash::iterator QHash::erase(iterator pos)

  1062 

  1063     Removes the (key, value) pair associated with the iterator \a pos

  1064     from the hash, and returns an iterator to the next item in the

  1065     hash.

  1066 

  1067     Unlike remove() and take(), this function never causes QHash to

  1068     rehash its internal data structure. This means that it can safely

  1069     be called while iterating, and won't affect the order of items in

  1070     the hash. For example:

  1071 

  1072     \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 15

  1073 

  1074     \sa remove(), take(), find()

  1075 */

  1076 

  1077 /*! \fn QHash::iterator QHash::find(const Key &key)

  1078 

  1079     Returns an iterator pointing to the item with the \a key in the

  1080     hash.

  1081 

  1082     If the hash contains no item with the \a key, the function

  1083     returns end().

  1084 

  1085     If the hash contains multiple items with the \a key, this

  1086     function returns an iterator that points to the most recently

  1087     inserted value. The other values are accessible by incrementing

  1088     the iterator. For example, here's some code that iterates over all

  1089     the items with the same key:

  1090 

  1091     \snippet doc/src/snippets/code/src_corelib_tools_qhash.cpp 16

  1092 

  1093     \sa value(), values(), QMultiHash::find()

  1094 */

  1095 

  1096 /*! \fn QHash::const_iterator QHash::find(const Key &key) const

  1097 

  1098     \overload

  1099 */

  1100 

  1101 /*! \fn QHash::iterator QHash::constFind(const Key &key) const

  1102     \since 4.1

  1103 

  1104     Returns an iterator pointing to the item with the \a key in the

  1105     hash.

  1106 

  1107     If the hash contains no item with the \a key, the function

  1108     returns constEnd().

  1109 

  1110     \sa find(), QMultiHash::constFind()

  1111 */

  1112 

  1113 /*! \fn QHash::iterator QHash::insert(const Key &key, const T &value)

  1114 

  1115     Inserts a new item with the \a key and a value of \a value.

  1116 

  1117     If there is already an item with the \a key, that item's value

  1118     is replaced with \a value.

  1119 

  1120     If there are multiple items with the \a key, the most

  1121     recently inserted item's value is replaced with \a value.

  1122 

  1123     \sa insertMulti()

  1124 */

  1125 

  1126 /*! \fn QHash::iterator QHash::insertMulti(const Key &key, const T &value)

  1127 

  1128     Inserts a new item with the \a key and a value of \a value.

  1129 

  1130     If there is already an item with the same key in the hash, this

  1131     function will simply create a new one. (This behavior is

  1132     different from insert(), which overwrites the value of an

  1133     existing item.)

  1134