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 #ifndef QHASH_H

    43 #define QHASH_H

    44 

    45 #include <QtCore/qatomic.h>

    46 #include <QtCore/qchar.h>

    47 #include <QtCore/qiterator.h>

    48 #include <QtCore/qlist.h>

    49 #include <QtCore/qpair.h>

    50 

    51 QT_BEGIN_HEADER

    52 

    53 QT_BEGIN_NAMESPACE

    54 

    55 QT_MODULE(Core)

    56 

    57 class QBitArray;

    58 class QByteArray;

    59 class QString;

    60 class QStringRef;

    61 

    62 inline uint qHash(char key) { return uint(key); }

    63 inline uint qHash(uchar key) { return uint(key); }

    64 inline uint qHash(signed char key) { return uint(key); }

    65 inline uint qHash(ushort key) { return uint(key); }

    66 inline uint qHash(short key) { return uint(key); }

    67 inline uint qHash(uint key) { return key; }

    68 inline uint qHash(int key) { return uint(key); }

    69 inline uint qHash(ulong key)

    70 {

    71     if (sizeof(ulong) > sizeof(uint)) {

    72         return uint((key >> (8 * sizeof(uint) - 1)) ^ key);

    73     } else {

    74         return uint(key);

    75     }

    76 }

    77 inline uint qHash(long key) { return qHash(ulong(key)); }

    78 inline uint qHash(quint64 key)

    79 {

    80     if (sizeof(quint64) > sizeof(uint)) {

    81         return uint((key >> (8 * sizeof(uint) - 1)) ^ key);

    82     } else {

    83         return uint(key);

    84     }

    85 }

    86 inline uint qHash(qint64 key) { return qHash(quint64(key)); }

    87 inline uint qHash(QChar key) { return qHash(key.unicode()); }

    88 Q_CORE_EXPORT uint qHash(const QByteArray &key);

    89 Q_CORE_EXPORT uint qHash(const QString &key);

    90 Q_CORE_EXPORT uint qHash(const QStringRef &key);

    91 Q_CORE_EXPORT uint qHash(const QBitArray &key);

    92 

    93 #if defined(Q_CC_MSVC)

    94 #pragma warning( push )

    95 #pragma warning( disable : 4311 ) // disable pointer truncation warning

    96 #endif

    97 template <class T> inline uint qHash(const T *key)

    98 {

    99     return qHash(reinterpret_cast<quintptr>(key));

   100 }

   101 #if defined(Q_CC_MSVC)

   102 #pragma warning( pop )

   103 #endif

   104 

   105 template <typename T1, typename T2> inline uint qHash(const QPair<T1, T2> &key)

   106 {

   107     uint h1 = qHash(key.first);

   108     uint h2 = qHash(key.second);

   109     return ((h1 << 16) | (h1 >> 16)) ^ h2;

   110 }

   111 

   112 struct Q_CORE_EXPORT QHashData

   113 {

   114     struct Node {

   115         Node *next;

   116         uint h;

   117     };

   118 

   119     Node *fakeNext;

   120     Node **buckets;

   121     QBasicAtomicInt ref;

   122     int size;

   123     int nodeSize;

   124     short userNumBits;

   125     short numBits;

   126     int numBuckets;

   127     uint sharable : 1;

   128 

   129     void *allocateNode();

   130     void freeNode(void *node);

   131     QHashData *detach_helper(void (*node_duplicate)(Node *, void *), int nodeSize); // ### Qt5 remove me

   132     QHashData *detach_helper(void (*node_duplicate)(Node *, void *), void (*node_delete)(Node *),

   133             int nodeSize);

   134     void mightGrow();

   135     bool willGrow();

   136     void hasShrunk();

   137     void rehash(int hint);

   138     void free_helper(void (*node_delete)(Node *));

   139     void destroyAndFree(); // ### Qt5 remove me

   140     Node *firstNode();

   141 #ifdef QT_QHASH_DEBUG

   142     void dump();

   143     void checkSanity();

   144 #endif

   145     static Node *nextNode(Node *node);

   146     static Node *previousNode(Node *node);

   147 

   148     static QHashData shared_null;

   149 };

   150 

   151 inline void QHashData::mightGrow() // ### Qt 5: eliminate

   152 {

   153     if (size >= numBuckets)

   154         rehash(numBits + 1);

   155 }

   156 

   157 inline bool QHashData::willGrow()

   158 {

   159     if (size >= numBuckets) {

   160         rehash(numBits + 1);

   161         return true;

   162     } else {

   163         return false;

   164     }

   165 }

   166 

   167 inline void QHashData::hasShrunk()

   168 {

   169     if (size <= (numBuckets >> 3) && numBits > userNumBits) {

   170         QT_TRY {

   171             rehash(qMax(int(numBits) - 2, int(userNumBits)));

   172         } QT_CATCH(const std::bad_alloc &) {

   173             // ignore bad allocs - shrinking shouldn't throw. rehash is exception safe.

   174         }

   175     }

   176 }

   177 

   178 inline QHashData::Node *QHashData::firstNode()

   179 {

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

   181     Node **bucket = buckets;

   182     int n = numBuckets;

   183     while (n--) {

   184         if (*bucket != e)

   185             return *bucket;

   186         ++bucket;

   187     }

   188     return e;

   189 }

   190 

   191 struct QHashDummyValue

   192 {

   193 };

   194 

   195 inline bool operator==(const QHashDummyValue & /* v1 */, const QHashDummyValue & /* v2 */)

   196 {

   197     return true;

   198 }

   199 

   200 Q_DECLARE_TYPEINFO(QHashDummyValue, Q_MOVABLE_TYPE | Q_DUMMY_TYPE);

   201 

   202 template <class Key, class T>

   203 struct QHashDummyNode

   204 {

   205     QHashDummyNode *next;

   206     uint h;

   207     Key key;

   208 

   209     inline QHashDummyNode(const Key &key0) : key(key0) {}

   210 };

   211 

   212 template <class Key, class T>

   213 struct QHashNode

   214 {

   215     QHashNode *next;

   216     uint h;

   217     Key key;

   218     T value;

   219 

   220     inline QHashNode(const Key &key0) : key(key0) {} // ### remove in 5.0

   221     inline QHashNode(const Key &key0, const T &value0) : key(key0), value(value0) {}

   222     inline bool same_key(uint h0, const Key &key0) { return h0 == h && key0 == key; }

   223 };

   224 

   225 #ifndef QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION

   226 #define Q_HASH_DECLARE_INT_NODES(key_type) \

   227     template <class T> \

   228     struct QHashDummyNode<key_type, T> { \

   229         QHashDummyNode *next; \

   230         union { uint h; key_type key; }; \

   231 \

   232         inline QHashDummyNode(key_type /* key0 */) {} \

   233     }; \

   234 \

   235     template <class T> \

   236     struct QHashNode<key_type, T> { \

   237         QHashNode *next; \

   238         union { uint h; key_type key; }; \

   239         T value; \

   240 \

   241         inline QHashNode(key_type /* key0 */) {} \

   242         inline QHashNode(key_type /* key0 */, const T &value0) : value(value0) {} \

   243         inline bool same_key(uint h0, key_type) { return h0 == h; } \

   244     }

   245 

   246 #if defined(Q_BYTE_ORDER) && Q_BYTE_ORDER == Q_LITTLE_ENDIAN

   247 Q_HASH_DECLARE_INT_NODES(short);

   248 Q_HASH_DECLARE_INT_NODES(ushort);

   249 #endif

   250 Q_HASH_DECLARE_INT_NODES(int);

   251 Q_HASH_DECLARE_INT_NODES(uint);

   252 #undef Q_HASH_DECLARE_INT_NODES

   253 #endif // QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION

   254 

   255 template <class Key, class T>

   256 class QHash

   257 {

   258     typedef QHashDummyNode<Key, T> DummyNode;

   259     typedef QHashNode<Key, T> Node;

   260 

   261     union {

   262         QHashData *d;

   263         QHashNode<Key, T> *e;

   264     };

   265 

   266     static inline Node *concrete(QHashData::Node *node) {

   267         return reinterpret_cast<Node *>(node);

   268     }

   269 

   270 public:

   271     inline QHash() : d(&QHashData::shared_null) { d->ref.ref(); }

   272     inline QHash(const QHash<Key, T> &other) : d(other.d) { d->ref.ref(); if (!d->sharable) detach(); }

   273     inline ~QHash() { if (!d->ref.deref()) freeData(d); }

   274 

   275     QHash<Key, T> &operator=(const QHash<Key, T> &other);

   276 

   277     bool operator==(const QHash<Key, T> &other) const;

   278     inline bool operator!=(const QHash<Key, T> &other) const { return !(*this == other); }

   279 

   280     inline int size() const { return d->size; }

   281 

   282     inline bool isEmpty() const { return d->size == 0; }

   283 

   284     inline int capacity() const { return d->numBuckets; }

   285     void reserve(int size);

   286     inline void squeeze() { reserve(1); }

   287 

   288     inline void detach() { if (d->ref != 1) detach_helper(); }

   289     inline bool isDetached() const { return d->ref == 1; }

   290     inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }

   291 

   292     void clear();

   293 

   294     int remove(const Key &key);

   295     T take(const Key &key);

   296 

   297     bool contains(const Key &key) const;

   298     const Key key(const T &value) const;

   299     const Key key(const T &value, const Key &defaultKey) const;

   300     const T value(const Key &key) const;

   301     const T value(const Key &key, const T &defaultValue) const;

   302     T &operator[](const Key &key);

   303     const T operator[](const Key &key) const;

   304 

   305     QList<Key> uniqueKeys() const;

   306     QList<Key> keys() const;

   307     QList<Key> keys(const T &value) const;

   308     QList<T> values() const;

   309     QList<T> values(const Key &key) const;

   310     int count(const Key &key) const;

   311 

   312     class const_iterator;

   313 

   314     class iterator

   315     {

   316         friend class const_iterator;

   317         QHashData::Node *i;

   318 

   319     public:

   320         typedef std::bidirectional_iterator_tag iterator_category;

   321         typedef ptrdiff_t difference_type;

   322         typedef T value_type;

   323         typedef T *pointer;

   324         typedef T &reference;

   325 

   326         // ### Qt 5: get rid of 'operator Node *'

   327         inline operator Node *() const { return concrete(i); }

   328         inline iterator() : i(0) { }

   329         explicit inline iterator(void *node) : i(reinterpret_cast<QHashData::Node *>(node)) { }

   330 

   331         inline const Key &key() const { return concrete(i)->key; }

   332         inline T &value() const { return concrete(i)->value; }

   333         inline T &operator*() const { return concrete(i)->value; }

   334         inline T *operator->() const { return &concrete(i)->value; }

   335         inline bool operator==(const iterator &o) const { return i == o.i; }

   336         inline bool operator!=(const iterator &o) const { return i != o.i; }

   337 

   338         inline iterator &operator++() {

   339             i = QHashData::nextNode(i);

   340             return *this;

   341         }

   342         inline iterator operator++(int) {

   343             iterator r = *this;

   344             i = QHashData::nextNode(i);

   345             return r;

   346         }

   347         inline iterator &operator--() {

   348             i = QHashData::previousNode(i);

   349             return *this;

   350         }

   351         inline iterator operator--(int) {

   352             iterator r = *this;

   353             i = QHashData::previousNode(i);

   354             return r;

   355         }

   356         inline iterator operator+(int j) const

   357         { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }

   358         inline iterator operator-(int j) const { return operator+(-j); }

   359         inline iterator &operator+=(int j) { return *this = *this + j; }

   360         inline iterator &operator-=(int j) { return *this = *this - j; }

   361 

   362         // ### Qt 5: not sure this is necessary anymore

   363 #ifdef QT_STRICT_ITERATORS

   364     private:

   365 #else

   366     public:

   367 #endif

   368         inline bool operator==(const const_iterator &o) const

   369             { return i == o.i; }

   370         inline bool operator!=(const const_iterator &o) const

   371             { return i != o.i; }

   372 

   373     private:

   374         // ### Qt 5: remove

   375         inline operator bool() const { return false; }

   376     };

   377     friend class iterator;

   378 

   379     class const_iterator

   380     {

   381         friend class iterator;

   382         QHashData::Node *i;

   383 

   384     public:

   385         typedef std::bidirectional_iterator_tag iterator_category;

   386         typedef ptrdiff_t difference_type;

   387         typedef T value_type;

   388         typedef const T *pointer;

   389         typedef const T &reference;

   390 

   391         // ### Qt 5: get rid of 'operator Node *'

   392         inline operator Node *() const { return concrete(i); }

   393         inline const_iterator() : i(0) { }

   394         explicit inline const_iterator(void *node)

   395             : i(reinterpret_cast<QHashData::Node *>(node)) { }

   396 #ifdef QT_STRICT_ITERATORS

   397         explicit inline const_iterator(const iterator &o)

   398 #else

   399         inline const_iterator(const iterator &o)

   400 #endif

   401         { i = o.i; }

   402 

   403         inline const Key &key() const { return concrete(i)->key; }

   404         inline const T &value() const { return concrete(i)->value; }

   405         inline const T &operator*() const { return concrete(i)->value; }

   406         inline const T *operator->() const { return &concrete(i)->value; }

   407         inline bool operator==(const const_iterator &o) const { return i == o.i; }

   408         inline bool operator!=(const const_iterator &o) const { return i != o.i; }

   409 

   410         inline const_iterator &operator++() {

   411             i = QHashData::nextNode(i);

   412             return *this;

   413         }

   414         inline const_iterator operator++(int) {

   415             const_iterator r = *this;

   416             i = QHashData::nextNode(i);

   417             return r;

   418         }

   419         inline const_iterator &operator--() {

   420             i = QHashData::previousNode(i);

   421             return *this;

   422         }

   423         inline const_iterator operator--(int) {

   424             const_iterator r = *this;

   425             i = QHashData::previousNode(i);

   426             return r;

   427         }

   428         inline const_iterator operator+(int j) const

   429         { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }

   430         inline const_iterator operator-(int j) const { return operator+(-j); }

   431         inline const_iterator &operator+=(int j) { return *this = *this + j; }

   432         inline const_iterator &operator-=(int j) { return *this = *this - j; }

   433 

   434         // ### Qt 5: not sure this is necessary anymore

   435 #ifdef QT_STRICT_ITERATORS

   436     private:

   437         inline bool operator==(const iterator &o) const { return operator==(const_iterator(o)); }

   438         inline bool operator!=(const iterator &o) const { return operator!=(const_iterator(o)); }

   439 #endif

   440 

   441     private:

   442         // ### Qt 5: remove

   443         inline operator bool() const { return false; }

   444     };

   445     friend class const_iterator;

   446 

   447     // STL style

   448     inline iterator begin() { detach(); return iterator(d->firstNode()); }

   449     inline const_iterator begin() const { return const_iterator(d->firstNode()); }

   450     inline const_iterator constBegin() const { return const_iterator(d->firstNode()); }

   451     inline iterator end() { detach(); return iterator(e); }

   452     inline const_iterator end() const { return const_iterator(e); }

   453     inline const_iterator constEnd() const { return const_iterator(e); }

   454     iterator erase(iterator it);

   455 

   456     // more Qt

   457     typedef iterator Iterator;

   458     typedef const_iterator ConstIterator;

   459     inline int count() const { return d->size; }

   460     iterator find(const Key &key);

   461     const_iterator find(const Key &key) const;

   462     const_iterator constFind(const Key &key) const;

   463     iterator insert(const Key &key, const T &value);

   464     iterator insertMulti(const Key &key, const T &value);

   465     QHash<Key, T> &unite(const QHash<Key, T> &other);

   466 

   467     // STL compatibility

   468     typedef T mapped_type;

   469     typedef Key key_type;

   470     typedef ptrdiff_t difference_type;

   471     typedef int size_type;

   472 

   473     inline bool empty() const { return isEmpty(); }

   474 

   475 #ifdef QT_QHASH_DEBUG

   476     inline void dump() const { d->dump(); }

   477     inline void checkSanity() const { d->checkSanity(); }

   478 #endif

   479 

   480 private:

   481     void detach_helper();

   482     void freeData(QHashData *d);

   483     Node **findNode(const Key &key, uint *hp = 0) const;

   484     Node *createNode(uint h, const Key &key, const T &value, Node **nextNode);

   485     void deleteNode(Node *node);

   486     static void deleteNode(QHashData::Node *node);

   487 

   488     static void duplicateNode(QHashData::Node *originalNode, void *newNode);

   489 };

   490 

   491 

   492 template <class Key, class T>

   493 Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode(Node *node)

   494 {

   495     deleteNode(reinterpret_cast<QHashData::Node*>(node));

   496 }

   497 

   498 

   499 template <class Key, class T>

   500 Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode(QHashData::Node *node)

   501 {

   502 #ifdef Q_CC_BOR

   503     concrete(node)->~QHashNode<Key, T>();

   504 #elif defined(QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION)

   505     concrete(node)->~QHashNode();

   506 #else

   507     concrete(node)->~Node();

   508 #endif

   509     qFree(node);

   510 }

   511 

   512 template <class Key, class T>

   513 Q_INLINE_TEMPLATE void QHash<Key, T>::duplicateNode(QHashData::Node *node, void *newNode)

   514 {

   515     Node *concreteNode = concrete(node);

   516     if (QTypeInfo<T>::isDummy) {

   517         (void) new (newNode) DummyNode(concreteNode->key);

   518     } else {

   519         (void) new (newNode) Node(concreteNode->key, concreteNode->value);

   520     }

   521 }

   522 

   523 template <class Key, class T>

   524 Q_INLINE_TEMPLATE typename QHash<Key, T>::Node *

   525 QHash<Key, T>::createNode(uint ah, const Key &akey, const T &avalue, Node **anextNode)

   526 {

   527     Node *node;

   528 

   529     if (QTypeInfo<T>::isDummy) {

   530         node = reinterpret_cast<Node *>(new (d->allocateNode()) DummyNode(akey));

   531     } else {

   532         node = new (d->allocateNode()) Node(akey, avalue);

   533     }

   534 

   535     node->h = ah;

   536     node->next = *anextNode;

   537     *anextNode = node;

   538     ++d->size;

   539     return node;

   540 }

   541 

   542 template <class Key, class T>

   543 Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::unite(const QHash<Key, T> &other)

   544 {

   545     QHash<Key, T> copy(other);

   546     const_iterator it = copy.constEnd();

   547     while (it != copy.constBegin()) {

   548         --it;

   549         insertMulti(it.key(), it.value());

   550     }

   551     return *this;

   552 }

   553 

   554 template <class Key, class T>

   555 Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::freeData(QHashData *x)

   556 {

   557     x->free_helper(deleteNode);

   558 }

   559 

   560 template <class Key, class T>

   561 Q_INLINE_TEMPLATE void QHash<Key, T>::clear()

   562 {

   563     *this = QHash<Key,T>();

   564 }

   565 

   566 template <class Key, class T>

   567 Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::detach_helper()

   568 {

   569     QHashData *x = d->detach_helper(duplicateNode, deleteNode,

   570         QTypeInfo<T>::isDummy ? sizeof(DummyNode) : sizeof(Node));

   571     if (!d->ref.deref())

   572         freeData(d);

   573     d = x;

   574 }

   575 

   576 template <class Key, class T>

   577 Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::operator=(const QHash<Key, T> &other)

   578 {

   579     if (d != other.d) {

   580         other.d->ref.ref();

   581         if (!d->ref.deref())

   582             freeData(d);

   583         d = other.d;

   584         if (!d->sharable)

   585             detach_helper();

   586     }

   587     return *this;

   588 }

   589 

   590 template <class Key, class T>

   591 Q_INLINE_TEMPLATE const T QHash<Key, T>::value(const Key &akey) const

   592 {

   593     Node *node;

   594     if (d->size == 0 || (node = *findNode(akey)) == e) {

   595         return T();

   596     } else {

   597         return node->value;

   598     }

   599 }

   600 

   601 template <class Key, class T>

   602 Q_INLINE_TEMPLATE const T QHash<Key, T>::value(const Key &akey, const T &adefaultValue) const

   603 {

   604     Node *node;

   605     if (d->size == 0 || (node = *findNode(akey)) == e) {

   606         return adefaultValue;

   607     } else {

   608         return node->value;

   609     }

   610 }

   611 

   612 template <class Key, class T>

   613 Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::uniqueKeys() const

   614 {

   615     QList<Key> res;

   616     const_iterator i = begin();

   617     if (i != end()) {

   618         for (;;) {

   619             const Key &aKey = i.key();

   620             res.append(aKey);

   621             do {

   622                 if (++i == end())

   623                     goto break_out_of_outer_loop;

   624             } while (aKey == i.key());

   625         }

   626     }

   627 break_out_of_outer_loop:

   628     return res;

   629 }

   630 

   631 template <class Key, class T>

   632 Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys() const

   633 {

   634     QList<Key> res;

   635     const_iterator i = begin();

   636     while (i != end()) {

   637         res.append(i.key());

   638         ++i;

   639     }

   640     return res;

   641 }

   642 

   643 template <class Key, class T>

   644 Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys(const T &avalue) const

   645 {

   646     QList<Key> res;

   647     const_iterator i = begin();

   648     while (i != end()) {

   649         if (i.value() == avalue)

   650             res.append(i.key());

   651         ++i;

   652     }

   653     return res;

   654 }

   655 

   656 template <class Key, class T>

   657 Q_OUTOFLINE_TEMPLATE const Key QHash<Key, T>::key(const T &avalue) const

   658 {

   659     return key(avalue, Key());

   660 }

   661 

   662 template <class Key, class T>

   663 Q_OUTOFLINE_TEMPLATE const Key QHash<Key, T>::key(const T &avalue, const Key &defaultValue) const

   664 {

   665     const_iterator i = begin();

   666     while (i != end()) {

   667         if (i.value() == avalue)

   668             return i.key();

   669         ++i;

   670     }

   671 

   672     return defaultValue;

   673 }

   674 

   675 template <class Key, class T>

   676 Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values() const

   677 {

   678     QList<T> res;

   679     const_iterator i = begin();

   680     while (i != end()) {

   681         res.append(i.value());

   682         ++i;

   683     }

   684     return res;

   685 }

   686 

   687 template <class Key, class T>

   688 Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values(const Key &akey) const

   689 {

   690     QList<T> res;

   691     Node *node = *findNode(akey);

   692     if (node != e) {

   693         do {

   694             res.append(node->value);

   695         } while ((node = node->next) != e && node->key == akey);

   696     }

   697     return res;

   698 }

   699 

   700 template <class Key, class T>

   701 Q_OUTOFLINE_TEMPLATE int QHash<Key, T>::count(const Key &akey) const

   702 {

   703     int cnt = 0;

   704     Node *node = *findNode(akey);

   705     if (node != e) {

   706         do {

   707             ++cnt;

   708         } while ((node = node->next) != e && node->key == akey);

   709     }

   710     return cnt;

   711 }

   712 

   713 template <class Key, class T>

   714 Q_INLINE_TEMPLATE const T QHash<Key, T>::operator[](const Key &akey) const

   715 {

   716     return value(akey);

   717 }

   718 

   719 template <class Key, class T>

   720 Q_INLINE_TEMPLATE T &QHash<Key, T>::operator[](const Key &akey)

   721 {

   722     detach();

   723 

   724     uint h;

   725     Node **node = findNode(akey, &h);

   726     if (*node == e) {

   727         if (d->willGrow())

   728             node = findNode(akey, &h);

   729         return createNode(h, akey, T(), node)->value;

   730     }

   731     return (*node)->value;

   732 }

   733 

   734 template <class Key, class T>

   735 Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insert(const Key &akey,

   736                                                                          const T &avalue)

   737 {

   738     detach();

   739 

   740     uint h;

   741     Node **node = findNode(akey, &h);

   742     if (*node == e) {

   743         if (d->willGrow())

   744             node = findNode(akey, &h);

   745         return iterator(createNode(h, akey, avalue, node));

   746     }

   747 

   748     if (!QTypeInfo<T>::isDummy)

   749         (*node)->value = avalue;

   750     return iterator(*node);

   751 }

   752 

   753 template <class Key, class T>

   754 Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insertMulti(const Key &akey,

   755                                                                               const T &avalue)

   756 {

   757     detach();

   758     d->willGrow();

   759 

   760     uint h;

   761     Node **nextNode = findNode(akey, &h);

   762     return iterator(createNode(h, akey, avalue, nextNode));

   763 }

   764 

   765 template <class Key, class T>

   766 Q_OUTOFLINE_TEMPLATE int QHash<Key, T>::remove(const Key &akey)

   767 {

   768     if (isEmpty()) // prevents detaching shared null

   769         return 0;

   770     detach();

   771 

   772     int oldSize = d->size;

   773     Node **node = findNode(akey);

   774     if (*node != e) {

   775         bool deleteNext = true;

   776         do {

   777             Node *next = (*node)->next;

   778             deleteNext = (next != e && next->key == (*node)->key);

   779             deleteNode(*node);

   780             *node = next;

   781             --d->size;

   782         } while (deleteNext);

   783         d->hasShrunk();

   784     }

   785     return oldSize - d->size;

   786 }

   787 

   788 template <class Key, class T>

   789 Q_OUTOFLINE_TEMPLATE T QHash<Key, T>::take(const Key &akey)

   790 {

   791     if (isEmpty()) // prevents detaching shared null

   792         return T();

   793     detach();

   794 

   795     Node **node = findNode(akey);

   796     if (*node != e) {

   797         T t = (*node)->value;

   798         Node *next = (*node)->next;

   799         deleteNode(*node);

   800         *node = next;

   801         --d->size;

   802         d->hasShrunk();

   803         return t;

   804     }

   805     return T();

   806 }

   807 

   808 template <class Key, class T>

   809 Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::erase(iterator it)

   810 {

   811     if (it == iterator(e))

   812         return it;

   813 

   814     iterator ret = it;

   815     ++ret;

   816 

   817     Node *node = it;

   818     Node **node_ptr = reinterpret_cast<Node **>(&d->buckets[node->h % d->numBuckets]);

   819     while (*node_ptr != node)

   820         node_ptr = &(*node_ptr)->next;

   821     *node_ptr = node->next;

   822     deleteNode(node);

   823     --d->size;

   824     return ret;

   825 }

   826 

   827 template <class Key, class T>

   828 Q_INLINE_TEMPLATE void QHash<Key, T>::reserve(int asize)

   829 {

   830     detach();

   831     d->rehash(-qMax(asize, 1));

   832 }

   833 

   834 template <class Key, class T>

   835 Q_INLINE_TEMPLATE typename QHash<Key, T>::const_iterator QHash<Key, T>::find(const Key &akey) const

   836 {

   837     return const_iterator(*findNode(akey));

   838 }

   839 

   840 template <class Key, class T>

   841 Q_INLINE_TEMPLATE typename QHash<Key, T>::const_iterator QHash<Key, T>::constFind(const Key &akey) const

   842 {

   843     return const_iterator(*findNode(akey));

   844 }

   845 

   846 template <class Key, class T>

   847 Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::find(const Key &akey)

   848 {

   849     detach();

   850     return iterator(*findNode(akey));

   851 }

   852 

   853 template <class Key, class T>

   854 Q_INLINE_TEMPLATE bool QHash<Key, T>::contains(const Key &akey) const

   855 {

   856     return *findNode(akey) != e;

   857 }

   858 

   859 template <class Key, class T>

   860 Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::Node **QHash<Key, T>::findNode(const Key &akey,

   861                                                                             uint *ahp) const

   862 {

   863     Node **node;

   864     uint h = qHash(akey);

   865 

   866     if (d->numBuckets) {

   867         node = reinterpret_cast<Node **>(&d->buckets[h % d->numBuckets]);

   868         Q_ASSERT(*node == e || (*node)->next);

   869         while (*node != e && !(*node)->same_key(h, akey))

   870             node = &(*node)->next;

   871     } else {

   872         node = const_cast<Node **>(reinterpret_cast<const Node * const *>(&e));

   873     }

   874     if (ahp)

   875         *ahp = h;

   876     return node;

   877 }

   878 

   879 template <class Key, class T>

   880 Q_OUTOFLINE_TEMPLATE bool QHash<Key, T>::operator==(const QHash<Key, T> &other) const

   881 {

   882     if (size() != other.size())

   883         return false;

   884     if (d == other.d)

   885         return true;

   886 

   887     const_iterator it = begin();

   888 

   889     while (it != end()) {

   890         const Key &akey = it.key();

   891 

   892         const_iterator it2 = other.find(akey);

   893         do {

   894             if (it2 == other.end() || !(it2.key() == akey))

   895                 return false;

   896             if (!QTypeInfo<T>::isDummy && !(it.value() == it2.value()))

   897                 return false;

   898             ++it;

   899             ++it2;

   900         } while (it != end() && it.key() == akey);

   901     }

   902     return true;

   903 }

   904 

   905 template <class Key, class T>

   906 class QMultiHash : public QHash<Key, T>

   907 {

   908 public:

   909     QMultiHash() {}

   910     QMultiHash(const QHash<Key, T> &other) : QHash<Key, T>(other) {}

   911 

   912     inline typename QHash<Key, T>::iterator replace(const Key &key, const T &value)

   913     { return QHash<Key, T>::insert(key, value); }

   914 

   915     inline typename QHash<Key, T>::iterator insert(const Key &key, const T &value)

   916     { return QHash<Key, T>::insertMulti(key, value); }

   917 

   918     inline QMultiHash &operator+=(const QMultiHash &other)

   919     { unite(other); return *this; }

   920     inline QMultiHash operator+(const QMultiHash &other) const

   921     { QMultiHash result = *this; result += other; return result; }

   922 

   923 #if !defined(Q_NO_USING_KEYWORD) && !defined(Q_CC_RVCT)

   924     // RVCT compiler doesn't handle using-keyword right when used functions are overloaded in child class

   925     using QHash<Key, T>::contains;

   926     using QHash<Key, T>::remove;

   927     using QHash<Key, T>::count;

   928     using QHash<Key, T>::find;

   929     using QHash<Key, T>::constFind;

   930 #else

   931     inline bool contains(const Key &key) const

   932     { return QHash<Key, T>::contains(key); }

   933     inline int remove(const Key &key)

   934     { return QHash<Key, T>::remove(key); }

   935     inline int count(const Key &key) const

   936     { return QHash<Key, T>::count(key); }

   937     inline int count() const

   938     { return QHash<Key, T>::count(); }

   939     inline typename QHash<Key, T>::iterator find(const Key &key)

   940     { return QHash<Key, T>::find(key); }

   941     inline typename QHash<Key, T>::const_iterator find(const Key &key) const

   942     { return QHash<Key, T>::find(key); }

   943     inline typename QHash<Key, T>::const_iterator constFind(const Key &key) const

   944     { return QHash<Key, T>::constFind(key); }

   945 #endif

   946 

   947     bool contains(const Key &key, const T &value) const;

   948 

   949     int remove(const Key &key, const T &value);

   950 

   951     int count(const Key &key, const T &value) const;

   952 

   953     typename QHash<Key, T>::iterator find(const Key &key, const T &value) {

   954         typename QHash<Key, T>::iterator i(find(key));

   955         typename QHash<Key, T>::iterator end(this->end());

   956         while (i != end && i.key() == key) {

   957             if (i.value() == value)

   958                 return i;

   959             ++i;

   960         }

   961         return end;

   962     }

   963     typename QHash<Key, T>::const_iterator find(const Key &key, const T &value) const {

   964         typename QHash<Key, T>::const_iterator i(constFind(key));

   965         typename QHash<Key, T>::const_iterator end(QHash<Key, T>::constEnd());

   966         while (i != end && i.key() == key) {

   967             if (i.value() == value)

   968                 return i;

   969             ++i;

   970         }

   971         return end;

   972     }

   973     typename QHash<Key, T>::const_iterator constFind(const Key &key, const T &value) const

   974         { return find(key, value); }

   975 private:

   976     T &operator[](const Key &key);

   977     const T operator[](const Key &key) const;

   978 };

   979 

   980 template <class Key, class T>

   981 Q_INLINE_TEMPLATE bool QMultiHash<Key, T>::contains(const Key &key, const T &value) const

   982 {

   983     return constFind(key, value) != QHash<Key, T>::constEnd();

   984 }

   985 

   986 template <class Key, class T>

   987 Q_INLINE_TEMPLATE int QMultiHash<Key, T>::remove(const Key &key, const T &value)

   988 {

   989     int n = 0;

   990     typename QHash<Key, T>::iterator i(find(key));

   991     typename QHash<Key, T>::iterator end(QHash<Key, T>::end());

   992     while (i != end && i.key() == key) {

   993         if (i.value() == value) {

   994 #if defined(Q_CC_RVCT)

   995             // RVCT has problems with scoping, apparently.

   996             i = QHash<Key, T>::erase(i);

   997 #else

   998             i = erase(i);

   999 #endif

  1000             ++n;

  1001         } else {

  1002             ++i;

  1003         }

  1004     }

  1005     return n;

  1006 }

  1007 

  1008 template <class Key, class T>

  1009 Q_INLINE_TEMPLATE int QMultiHash<Key, T>::count(const Key &key, const T &value) const

  1010 {

  1011     int n = 0;

  1012     typename QHash<Key, T>::const_iterator i(constFind(key));

  1013     typename QHash<Key, T>::const_iterator end(QHash<Key, T>::constEnd());

  1014     while (i != end && i.key() == key) {

  1015         if (i.value() == value)

  1016             ++n;

  1017         ++i;

  1018     }

  1019     return n;

  1020 }

  1021 

  1022 Q_DECLARE_ASSOCIATIVE_ITERATOR(Hash)

  1023 Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Hash)

  1024 

  1025 QT_END_NAMESPACE

  1026 

  1027 QT_END_HEADER

  1028 

  1029 #endif // QHASH_H