src/corelib/tools/qhash.h

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
   4 ** Contact: http://www.qt-project.org/
   5 **
   6 ** This file is part of the QtCore module of the Qt Toolkit.
   7 **
   8 ** $QT_BEGIN_LICENSE:LGPL$
   9 ** GNU Lesser General Public License Usage
  10 ** This file may be used under the terms of the GNU Lesser General Public
  11 ** License version 2.1 as published by the Free Software Foundation and
  12 ** appearing in the file LICENSE.LGPL included in the packaging of this
  13 ** file. Please review the following information to ensure the GNU Lesser
  14 ** General Public License version 2.1 requirements will be met:
  15 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  16 **
  17 ** In addition, as a special exception, Nokia gives you certain additional
  18 ** rights. These rights are described in the Nokia Qt LGPL Exception
  19 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  20 **
  21 ** GNU General Public License Usage
  22 ** Alternatively, this file may be used under the terms of the GNU General
  23 ** Public License version 3.0 as published by the Free Software Foundation
  24 ** and appearing in the file LICENSE.GPL included in the packaging of this
  25 ** file. Please review the following information to ensure the GNU General
  26 ** Public License version 3.0 requirements will be met:
  27 ** http://www.gnu.org/copyleft/gpl.html.
  28 **
  29 ** Other Usage
  30 ** Alternatively, this file may be used in accordance with the terms and
  31 ** conditions contained in a signed written agreement between you and Nokia.
  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/qchar.h>
  46 #include <QtCore/qiterator.h>
  47 #include <QtCore/qlist.h>
  48 #include <QtCore/qpair.h>
  49 #include <QtCore/qrefcount.h>
  50
  51 QT_BEGIN_HEADER
  52
  53 QT_BEGIN_NAMESPACE
  54
  55
  56 class QBitArray;
  57 class QByteArray;
  58 class QString;
  59 class QStringRef;
  60
  61 inline uint qHash(char key) { return uint(key); }
  62 inline uint qHash(uchar key) { return uint(key); }
  63 inline uint qHash(signed char key) { return uint(key); }
  64 inline uint qHash(ushort key) { return uint(key); }
  65 inline uint qHash(short key) { return uint(key); }
  66 inline uint qHash(uint key) { return key; }
  67 inline uint qHash(int key) { return uint(key); }
  68 inline uint qHash(ulong key)
  69 {
  70     if (sizeof(ulong) > sizeof(uint)) {
  71         return uint(((key >> (8 * sizeof(uint) - 1)) ^ key) & (~0U));
  72     } else {
  73         return uint(key & (~0U));
  74     }
  75 }
  76 inline uint qHash(long key) { return qHash(ulong(key)); }
  77 inline uint qHash(quint64 key)
  78 {
  79     if (sizeof(quint64) > sizeof(uint)) {
  80         return uint(((key >> (8 * sizeof(uint) - 1)) ^ key) & (~0U));
  81     } else {
  82         return uint(key & (~0U));
  83     }
  84 }
  85 inline uint qHash(qint64 key) { return qHash(quint64(key)); }
  86 inline uint qHash(QChar key) { return qHash(key.unicode()); }
  87 Q_CORE_EXPORT uint qHash(const QByteArray &key, uint seed = 0);
  88 Q_CORE_EXPORT uint qHash(const QString &key, uint seed = 0);
  89 Q_CORE_EXPORT uint qHash(const QStringRef &key, uint seed = 0);
  90 Q_CORE_EXPORT uint qHash(const QBitArray &key, uint seed = 0);
  91 Q_CORE_EXPORT uint qHash(const QLatin1String &key, uint seed = 0);
  92 Q_CORE_EXPORT uint qt_hash(const QString &key);
  93
  94 #if defined(Q_CC_MSVC)
  95 #pragma warning( push )
  96 #pragma warning( disable : 4311 ) // disable pointer truncation warning
  97 #endif
  98 template <class T> inline uint qHash(const T *key)
  99 {
 100     return qHash(reinterpret_cast<quintptr>(key));
 101 }
 102 #if defined(Q_CC_MSVC)
 103 #pragma warning( pop )
 104 #endif
 105
 106 template <typename T1, typename T2> inline uint qHash(const QPair<T1, T2> &key)
 107 {
 108     uint h1 = qHash(key.first);
 109     uint h2 = qHash(key.second);
 110     return ((h1 << 16) | (h1 >> 16)) ^ h2;
 111 }
 112
 113 template<typename T> inline uint qHash(const T &t, uint seed) { return (qHash(t) ^ seed); }
 114
 115 struct Q_CORE_EXPORT QHashData
 116 {
 117     struct Node {
 118         Node *next;
 119         uint h;
 120     };
 121
 122     Node *fakeNext;
 123     Node **buckets;
 124     QtPrivate::RefCount ref;
 125     int size;
 126     int nodeSize;
 127     short userNumBits;
 128     short numBits;
 129     int numBuckets;
 130     uint seed;
 131     uint sharable : 1;
 132     uint strictAlignment : 1;
 133     uint reserved : 30;
 134
 135     void *allocateNode(int nodeAlign);
 136     void freeNode(void *node);
 137     QHashData *detach_helper(void (*node_duplicate)(Node *, void *), void (*node_delete)(Node *),
 138                              int nodeSize, int nodeAlign);
 139     bool willGrow();
 140     void hasShrunk();
 141     void rehash(int hint);
 142     void free_helper(void (*node_delete)(Node *));
 143     Node *firstNode();
 144 #ifdef QT_QHASH_DEBUG
 145     void dump();
 146     void checkSanity();
 147 #endif
 148     static Node *nextNode(Node *node);
 149     static Node *previousNode(Node *node);
 150
 151     static const QHashData shared_null;
 152 };
 153
 154 inline bool QHashData::willGrow()
 155 {
 156     if (size >= numBuckets) {
 157         rehash(numBits + 1);
 158         return true;
 159     } else {
 160         return false;
 161     }
 162 }
 163
 164 inline void QHashData::hasShrunk()
 165 {
 166     if (size <= (numBuckets >> 3) && numBits > userNumBits) {
 167         QT_TRY {
 168             rehash(qMax(int(numBits) - 2, int(userNumBits)));
 169         } QT_CATCH(const std::bad_alloc &) {
 170             // ignore bad allocs - shrinking shouldn't throw. rehash is exception safe.
 171         }
 172     }
 173 }
 174
 175 inline QHashData::Node *QHashData::firstNode()
 176 {
 177     Node *e = reinterpret_cast<Node *>(this);
 178     Node **bucket = buckets;
 179     int n = numBuckets;
 180     while (n--) {
 181         if (*bucket != e)
 182             return *bucket;
 183         ++bucket;
 184     }
 185     return e;
 186 }
 187
 188 struct QHashDummyValue
 189 {
 190 };
 191
 192 inline bool operator==(const QHashDummyValue & /* v1 */, const QHashDummyValue & /* v2 */)
 193 {
 194     return true;
 195 }
 196
 197 Q_DECLARE_TYPEINFO(QHashDummyValue, Q_MOVABLE_TYPE | Q_DUMMY_TYPE);
 198
 199 template <class Key, class T>
 200 struct QHashDummyNode
 201 {
 202     QHashDummyNode *next;
 203     uint h;
 204     Key key;
 205
 206     inline QHashDummyNode(const Key &key0) : key(key0) {}
 207 };
 208
 209 template <class Key, class T>
 210 struct QHashNode
 211 {
 212     QHashNode *next;
 213     uint h;
 214     Key key;
 215     T value;
 216
 217     inline QHashNode(const Key &key0, const T &value0) : key(key0), value(value0) {}
 218     inline bool same_key(uint h0, const Key &key0) { return h0 == h && key0 == key; }
 219 };
 220
 221
 222 #define Q_HASH_DECLARE_INT_NODES(key_type) \
 223     template <class T> \
 224     struct QHashDummyNode<key_type, T> { \
 225         QHashDummyNode *next; \
 226         union { uint h; key_type key; }; \
 227 \
 228         inline QHashDummyNode(key_type /* key0 */) {} \
 229     }; \
 230 \
 231     template <class T> \
 232     struct QHashNode<key_type, T> { \
 233         QHashNode *next; \
 234         union { uint h; key_type key; }; \
 235         T value; \
 236 \
 237         inline QHashNode(key_type /* key0 */) {} \
 238         inline QHashNode(key_type /* key0 */, const T &value0) : value(value0) {} \
 239         inline bool same_key(uint h0, key_type) { return h0 == h; } \
 240     }
 241
 242 #if defined(Q_BYTE_ORDER) && Q_BYTE_ORDER == Q_LITTLE_ENDIAN
 243 Q_HASH_DECLARE_INT_NODES(short);
 244 Q_HASH_DECLARE_INT_NODES(ushort);
 245 #endif
 246 Q_HASH_DECLARE_INT_NODES(int);
 247 Q_HASH_DECLARE_INT_NODES(uint);
 248 #undef Q_HASH_DECLARE_INT_NODES
 249
 250 template <class Key, class T>
 251 class QHash
 252 {
 253     typedef QHashDummyNode<Key, T> DummyNode;
 254     typedef QHashNode<Key, T> Node;
 255
 256     union {
 257         QHashData *d;
 258         QHashNode<Key, T> *e;
 259     };
 260
 261     static inline Node *concrete(QHashData::Node *node) {
 262         return reinterpret_cast<Node *>(node);
 263     }
 264
 265     static inline int alignOfNode() { return qMax<int>(sizeof(void*), Q_ALIGNOF(Node)); }
 266     static inline int alignOfDummyNode() { return qMax<int>(sizeof(void*), Q_ALIGNOF(DummyNode)); }
 267
 268 public:
 269     inline QHash() : d(const_cast<QHashData *>(&QHashData::shared_null)) { }
 270     inline QHash(const QHash<Key, T> &other) : d(other.d) { d->ref.ref(); if (!d->sharable) detach(); }
 271     inline ~QHash() { if (!d->ref.deref()) freeData(d); }
 272
 273     QHash<Key, T> &operator=(const QHash<Key, T> &other);
 274 #ifdef Q_COMPILER_RVALUE_REFS
 275     inline QHash<Key, T> &operator=(QHash<Key, T> &&other)
 276     { qSwap(d, other.d); return *this; }
 277 #endif
 278     inline void swap(QHash<Key, T> &other) { qSwap(d, other.d); }
 279
 280     bool operator==(const QHash<Key, T> &other) const;
 281     inline bool operator!=(const QHash<Key, T> &other) const { return !(*this == other); }
 282
 283     inline int size() const { return d->size; }
 284
 285     inline bool isEmpty() const { return d->size == 0; }
 286
 287     inline int capacity() const { return d->numBuckets; }
 288     void reserve(int size);
 289     inline void squeeze() { reserve(1); }
 290
 291     inline void detach() { if (d->ref.isShared()) detach_helper(); }
 292     inline bool isDetached() const { return !d->ref.isShared(); }
 293     inline void setSharable(bool sharable) { if (!sharable) detach(); if (d != &QHashData::shared_null) d->sharable = sharable; }
 294     inline bool isSharedWith(const QHash<Key, T> &other) const { return d == other.d; }
 295
 296     void clear();
 297
 298     int remove(const Key &key);
 299     T take(const Key &key);
 300
 301     bool contains(const Key &key) const;
 302     const Key key(const T &value) const;
 303     const Key key(const T &value, const Key &defaultKey) const;
 304     const T value(const Key &key) const;
 305     const T value(const Key &key, const T &defaultValue) const;
 306     T &operator[](const Key &key);
 307     const T operator[](const Key &key) const;
 308
 309     QList<Key> uniqueKeys() const;
 310     QList<Key> keys() const;
 311     QList<Key> keys(const T &value) const;
 312     QList<T> values() const;
 313     QList<T> values(const Key &key) const;
 314     int count(const Key &key) const;
 315
 316     class const_iterator;
 317
 318     class iterator
 319     {
 320         friend class const_iterator;
 321         friend class QHash<Key, T>;
 322         QHashData::Node *i;
 323
 324     public:
 325         typedef std::bidirectional_iterator_tag iterator_category;
 326         typedef qptrdiff difference_type;
 327         typedef T value_type;
 328         typedef T *pointer;
 329         typedef T &reference;
 330
 331         inline iterator() : i(0) { }
 332         explicit inline iterator(void *node) : i(reinterpret_cast<QHashData::Node *>(node)) { }
 333
 334         inline const Key &key() const { return concrete(i)->key; }
 335         inline T &value() const { return concrete(i)->value; }
 336         inline T &operator*() const { return concrete(i)->value; }
 337         inline T *operator->() const { return &concrete(i)->value; }
 338         inline bool operator==(const iterator &o) const { return i == o.i; }
 339         inline bool operator!=(const iterator &o) const { return i != o.i; }
 340
 341         inline iterator &operator++() {
 342             i = QHashData::nextNode(i);
 343             return *this;
 344         }
 345         inline iterator operator++(int) {
 346             iterator r = *this;
 347             i = QHashData::nextNode(i);
 348             return r;
 349         }
 350         inline iterator &operator--() {
 351             i = QHashData::previousNode(i);
 352             return *this;
 353         }
 354         inline iterator operator--(int) {
 355             iterator r = *this;
 356             i = QHashData::previousNode(i);
 357             return r;
 358         }
 359         inline iterator operator+(int j) const
 360         { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
 361         inline iterator operator-(int j) const { return operator+(-j); }
 362         inline iterator &operator+=(int j) { return *this = *this + j; }
 363         inline iterator &operator-=(int j) { return *this = *this - j; }
 364
 365         // ### Qt 5: not sure this is necessary anymore
 366 #ifdef QT_STRICT_ITERATORS
 367     private:
 368 #else
 369     public:
 370 #endif
 371         inline bool operator==(const const_iterator &o) const
 372             { return i == o.i; }
 373         inline bool operator!=(const const_iterator &o) const
 374             { return i != o.i; }
 375     };
 376     friend class iterator;
 377
 378     class const_iterator
 379     {
 380         friend class iterator;
 381         QHashData::Node *i;
 382
 383     public:
 384         typedef std::bidirectional_iterator_tag iterator_category;
 385         typedef qptrdiff difference_type;
 386         typedef T value_type;
 387         typedef const T *pointer;
 388         typedef const T &reference;
 389
 390         inline const_iterator() : i(0) { }
 391         explicit inline const_iterator(void *node)
 392             : i(reinterpret_cast<QHashData::Node *>(node)) { }
 393 #ifdef QT_STRICT_ITERATORS
 394         explicit inline const_iterator(const iterator &o)
 395 #else
 396         inline const_iterator(const iterator &o)
 397 #endif
 398         { i = o.i; }
 399
 400         inline const Key &key() const { return concrete(i)->key; }
 401         inline const T &value() const { return concrete(i)->value; }
 402         inline const T &operator*() const { return concrete(i)->value; }
 403         inline const T *operator->() const { return &concrete(i)->value; }
 404         inline bool operator==(const const_iterator &o) const { return i == o.i; }
 405         inline bool operator!=(const const_iterator &o) const { return i != o.i; }
 406
 407         inline const_iterator &operator++() {
 408             i = QHashData::nextNode(i);
 409             return *this;
 410         }
 411         inline const_iterator operator++(int) {
 412             const_iterator r = *this;
 413             i = QHashData::nextNode(i);
 414             return r;
 415         }
 416         inline const_iterator &operator--() {
 417             i = QHashData::previousNode(i);
 418             return *this;
 419         }
 420         inline const_iterator operator--(int) {
 421             const_iterator r = *this;
 422             i = QHashData::previousNode(i);
 423             return r;
 424         }
 425         inline const_iterator operator+(int j) const
 426         { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
 427         inline const_iterator operator-(int j) const { return operator+(-j); }
 428         inline const_iterator &operator+=(int j) { return *this = *this + j; }
 429         inline const_iterator &operator-=(int j) { return *this = *this - j; }
 430
 431         // ### Qt 5: not sure this is necessary anymore
 432 #ifdef QT_STRICT_ITERATORS
 433     private:
 434         inline bool operator==(const iterator &o) const { return operator==(const_iterator(o)); }
 435         inline bool operator!=(const iterator &o) const { return operator!=(const_iterator(o)); }
 436 #endif
 437     };
 438     friend class const_iterator;
 439
 440     // STL style
 441     inline iterator begin() { detach(); return iterator(d->firstNode()); }
 442     inline const_iterator begin() const { return const_iterator(d->firstNode()); }
 443     inline const_iterator cbegin() const { return const_iterator(d->firstNode()); }
 444     inline const_iterator constBegin() const { return const_iterator(d->firstNode()); }
 445     inline iterator end() { detach(); return iterator(e); }
 446     inline const_iterator end() const { return const_iterator(e); }
 447     inline const_iterator cend() const { return const_iterator(e); }
 448     inline const_iterator constEnd() const { return const_iterator(e); }
 449     iterator erase(iterator it);
 450
 451     // more Qt
 452     typedef iterator Iterator;
 453     typedef const_iterator ConstIterator;
 454     inline int count() const { return d->size; }
 455     iterator find(const Key &key);
 456     const_iterator find(const Key &key) const;
 457     const_iterator constFind(const Key &key) const;
 458     iterator insert(const Key &key, const T &value);
 459     iterator insertMulti(const Key &key, const T &value);
 460     QHash<Key, T> &unite(const QHash<Key, T> &other);
 461
 462     // STL compatibility
 463     typedef T mapped_type;
 464     typedef Key key_type;
 465     typedef qptrdiff difference_type;
 466     typedef int size_type;
 467
 468     inline bool empty() const { return isEmpty(); }
 469
 470 #ifdef QT_QHASH_DEBUG
 471     inline void dump() const { d->dump(); }
 472     inline void checkSanity() const { d->checkSanity(); }
 473 #endif
 474
 475 private:
 476     void detach_helper();
 477     void freeData(QHashData *d);
 478     Node **findNode(const Key &key, uint *hp = 0) const;
 479     Node *createNode(uint h, const Key &key, const T &value, Node **nextNode);
 480     void deleteNode(Node *node);
 481     static void deleteNode2(QHashData::Node *node);
 482
 483     static void duplicateNode(QHashData::Node *originalNode, void *newNode);
 484 };
 485
 486
 487 template <class Key, class T>
 488 Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode(Node *node)
 489 {
 490     deleteNode2(reinterpret_cast<QHashData::Node*>(node));
 491     d->freeNode(node);
 492 }
 493
 494 template <class Key, class T>
 495 Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode2(QHashData::Node *node)
 496 {
 497 #ifdef Q_CC_BOR
 498     concrete(node)->~QHashNode<Key, T>();
 499 #else
 500     concrete(node)->~Node();
 501 #endif
 502 }
 503
 504 template <class Key, class T>
 505 Q_INLINE_TEMPLATE void QHash<Key, T>::duplicateNode(QHashData::Node *node, void *newNode)
 506 {
 507     Node *concreteNode = concrete(node);
 508     if (QTypeInfo<T>::isDummy) {
 509         (void) new (newNode) DummyNode(concreteNode->key);
 510     } else {
 511         (void) new (newNode) Node(concreteNode->key, concreteNode->value);
 512     }
 513 }
 514
 515 template <class Key, class T>
 516 Q_INLINE_TEMPLATE typename QHash<Key, T>::Node *
 517 QHash<Key, T>::createNode(uint ah, const Key &akey, const T &avalue, Node **anextNode)
 518 {
 519     Node *node;
 520
 521     if (QTypeInfo<T>::isDummy) {
 522         node = reinterpret_cast<Node *>(new (d->allocateNode(alignOfDummyNode())) DummyNode(akey));
 523     } else {
 524         node = new (d->allocateNode(alignOfNode())) Node(akey, avalue);
 525     }
 526
 527     node->h = ah;
 528     node->next = *anextNode;
 529     *anextNode = node;
 530     ++d->size;
 531     return node;
 532 }
 533
 534 template <class Key, class T>
 535 Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::unite(const QHash<Key, T> &other)
 536 {
 537     QHash<Key, T> copy(other);
 538     const_iterator it = copy.constEnd();
 539     while (it != copy.constBegin()) {
 540         --it;
 541         insertMulti(it.key(), it.value());
 542     }
 543     return *this;
 544 }
 545
 546 template <class Key, class T>
 547 Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::freeData(QHashData *x)
 548 {
 549     x->free_helper(deleteNode2);
 550 }
 551
 552 template <class Key, class T>
 553 Q_INLINE_TEMPLATE void QHash<Key, T>::clear()
 554 {
 555     *this = QHash<Key,T>();
 556 }
 557
 558 template <class Key, class T>
 559 Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::detach_helper()
 560 {
 561     QHashData *x = d->detach_helper(duplicateNode, deleteNode2,
 562         QTypeInfo<T>::isDummy ? sizeof(DummyNode) : sizeof(Node),
 563         QTypeInfo<T>::isDummy ? alignOfDummyNode() : alignOfNode());
 564     if (!d->ref.deref())
 565         freeData(d);
 566     d = x;
 567 }
 568
 569 template <class Key, class T>
 570 Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::operator=(const QHash<Key, T> &other)
 571 {
 572     if (d != other.d) {
 573         QHashData *o = other.d;
 574         o->ref.ref();
 575         if (!d->ref.deref())
 576             freeData(d);
 577         d = o;
 578         if (!d->sharable)
 579             detach_helper();
 580     }
 581     return *this;
 582 }
 583
 584 template <class Key, class T>
 585 Q_INLINE_TEMPLATE const T QHash<Key, T>::value(const Key &akey) const
 586 {
 587     Node *node;
 588     if (d->size == 0 || (node = *findNode(akey)) == e) {
 589         return T();
 590     } else {
 591         return node->value;
 592     }
 593 }
 594
 595 template <class Key, class T>
 596 Q_INLINE_TEMPLATE const T QHash<Key, T>::value(const Key &akey, const T &adefaultValue) const
 597 {
 598     Node *node;
 599     if (d->size == 0 || (node = *findNode(akey)) == e) {
 600         return adefaultValue;
 601     } else {
 602         return node->value;
 603     }
 604 }
 605
 606 template <class Key, class T>
 607 Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::uniqueKeys() const
 608 {
 609     QList<Key> res;
 610     res.reserve(size()); // May be too much, but assume short lifetime
 611     const_iterator i = begin();
 612     if (i != end()) {
 613         for (;;) {
 614             const Key &aKey = i.key();
 615             res.append(aKey);
 616             do {
 617                 if (++i == end())
 618                     goto break_out_of_outer_loop;
 619             } while (aKey == i.key());
 620         }
 621     }
 622 break_out_of_outer_loop:
 623     return res;
 624 }
 625
 626 template <class Key, class T>
 627 Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys() const
 628 {
 629     QList<Key> res;
 630     res.reserve(size());
 631     const_iterator i = begin();
 632     while (i != end()) {
 633         res.append(i.key());
 634         ++i;
 635     }
 636     return res;
 637 }
 638
 639 template <class Key, class T>
 640 Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys(const T &avalue) const
 641 {
 642     QList<Key> res;
 643     const_iterator i = begin();
 644     while (i != end()) {
 645         if (i.value() == avalue)
 646             res.append(i.key());
 647         ++i;
 648     }
 649     return res;
 650 }
 651
 652 template <class Key, class T>
 653 Q_OUTOFLINE_TEMPLATE const Key QHash<Key, T>::key(const T &avalue) const
 654 {
 655     return key(avalue, Key());
 656 }
 657
 658 template <class Key, class T>
 659 Q_OUTOFLINE_TEMPLATE const Key QHash<Key, T>::key(const T &avalue, const Key &defaultValue) const
 660 {
 661     const_iterator i = begin();
 662     while (i != end()) {
 663         if (i.value() == avalue)
 664             return i.key();
 665         ++i;
 666     }
 667
 668     return defaultValue;
 669 }
 670
 671 template <class Key, class T>
 672 Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values() const
 673 {
 674     QList<T> res;
 675     res.reserve(size());
 676     const_iterator i = begin();
 677     while (i != end()) {
 678         res.append(i.value());
 679         ++i;
 680     }
 681     return res;
 682 }
 683
 684 template <class Key, class T>
 685 Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values(const Key &akey) const
 686 {
 687     QList<T> res;
 688     Node *node = *findNode(akey);
 689     if (node != e) {
 690         do {
 691             res.append(node->value);
 692         } while ((node = node->next) != e && node->key == akey);
 693     }
 694     return res;
 695 }
 696
 697 template <class Key, class T>
 698 Q_OUTOFLINE_TEMPLATE int QHash<Key, T>::count(const Key &akey) const
 699 {
 700     int cnt = 0;
 701     Node *node = *findNode(akey);
 702     if (node != e) {
 703         do {
 704             ++cnt;
 705         } while ((node = node->next) != e && node->key == akey);
 706     }
 707     return cnt;
 708 }
 709
 710 template <class Key, class T>
 711 Q_INLINE_TEMPLATE const T QHash<Key, T>::operator[](const Key &akey) const
 712 {
 713     return value(akey);
 714 }
 715
 716 template <class Key, class T>
 717 Q_INLINE_TEMPLATE T &QHash<Key, T>::operator[](const Key &akey)
 718 {
 719     detach();
 720
 721     uint h;
 722     Node **node = findNode(akey, &h);
 723     if (*node == e) {
 724         if (d->willGrow())
 725             node = findNode(akey, &h);
 726         return createNode(h, akey, T(), node)->value;
 727     }
 728     return (*node)->value;
 729 }
 730
 731 template <class Key, class T>
 732 Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insert(const Key &akey,
 733                                                                          const T &avalue)
 734 {
 735     detach();
 736
 737     uint h;
 738     Node **node = findNode(akey, &h);
 739     if (*node == e) {
 740         if (d->willGrow())
 741             node = findNode(akey, &h);
 742         return iterator(createNode(h, akey, avalue, node));
 743     }
 744
 745     if (!QTypeInfo<T>::isDummy)
 746         (*node)->value = avalue;
 747     return iterator(*node);
 748 }
 749
 750 template <class Key, class T>
 751 Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insertMulti(const Key &akey,
 752                                                                               const T &avalue)
 753 {
 754     detach();
 755     d->willGrow();
 756
 757     uint h;
 758     Node **nextNode = findNode(akey, &h);
 759     return iterator(createNode(h, akey, avalue, nextNode));
 760 }
 761
 762 template <class Key, class T>
 763 Q_OUTOFLINE_TEMPLATE int QHash<Key, T>::remove(const Key &akey)
 764 {
 765     if (isEmpty()) // prevents detaching shared null
 766         return 0;
 767     detach();
 768
 769     int oldSize = d->size;
 770     Node **node = findNode(akey);
 771     if (*node != e) {
 772         bool deleteNext = true;
 773         do {
 774             Node *next = (*node)->next;
 775             deleteNext = (next != e && next->key == (*node)->key);
 776             deleteNode(*node);
 777             *node = next;
 778             --d->size;
 779         } while (deleteNext);
 780         d->hasShrunk();
 781     }
 782     return oldSize - d->size;
 783 }
 784
 785 template <class Key, class T>
 786 Q_OUTOFLINE_TEMPLATE T QHash<Key, T>::take(const Key &akey)
 787 {
 788     if (isEmpty()) // prevents detaching shared null
 789         return T();
 790     detach();
 791
 792     Node **node = findNode(akey);
 793     if (*node != e) {
 794         T t = (*node)->value;
 795         Node *next = (*node)->next;
 796         deleteNode(*node);
 797         *node = next;
 798         --d->size;
 799         d->hasShrunk();
 800         return t;
 801     }
 802     return T();
 803 }
 804
 805 template <class Key, class T>
 806 Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::erase(iterator it)
 807 {
 808     if (it == iterator(e))
 809         return it;
 810
 811     iterator ret = it;
 812     ++ret;
 813
 814     Node *node = concrete(it.i);
 815     Node **node_ptr = reinterpret_cast<Node **>(&d->buckets[node->h % d->numBuckets]);
 816     while (*node_ptr != node)
 817         node_ptr = &(*node_ptr)->next;
 818     *node_ptr = node->next;
 819     deleteNode(node);
 820     --d->size;
 821     return ret;
 822 }
 823
 824 template <class Key, class T>
 825 Q_INLINE_TEMPLATE void QHash<Key, T>::reserve(int asize)
 826 {
 827     detach();
 828     d->rehash(-qMax(asize, 1));
 829 }
 830
 831 template <class Key, class T>
 832 Q_INLINE_TEMPLATE typename QHash<Key, T>::const_iterator QHash<Key, T>::find(const Key &akey) const
 833 {
 834     return const_iterator(*findNode(akey));
 835 }
 836
 837 template <class Key, class T>
 838 Q_INLINE_TEMPLATE typename QHash<Key, T>::const_iterator QHash<Key, T>::constFind(const Key &akey) const
 839 {
 840     return const_iterator(*findNode(akey));
 841 }
 842
 843 template <class Key, class T>
 844 Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::find(const Key &akey)
 845 {
 846     detach();
 847     return iterator(*findNode(akey));
 848 }
 849
 850 template <class Key, class T>
 851 Q_INLINE_TEMPLATE bool QHash<Key, T>::contains(const Key &akey) const
 852 {
 853     return *findNode(akey) != e;
 854 }
 855
 856 template <class Key, class T>
 857 Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::Node **QHash<Key, T>::findNode(const Key &akey,
 858                                                                             uint *ahp) const
 859 {
 860     Node **node;
 861     uint h = 0;
 862
 863     if (d->numBuckets || ahp) {
 864         h = qHash(akey, 0);
 865         if (ahp)
 866             *ahp = h;
 867     }
 868     if (d->numBuckets) {
 869         node = reinterpret_cast<Node **>(&d->buckets[h % d->numBuckets]);
 870         Q_ASSERT(*node == e || (*node)->next);
 871         while (*node != e && !(*node)->same_key(h, akey))
 872             node = &(*node)->next;
 873     } else {
 874         node = const_cast<Node **>(reinterpret_cast<const Node * const *>(&e));
 875     }
 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     inline void swap(QMultiHash<Key, T> &other) { QHash<Key, T>::swap(other); } // prevent QMultiHash<->QHash swaps
 912
 913     inline typename QHash<Key, T>::iterator replace(const Key &key, const T &value)
 914     { return QHash<Key, T>::insert(key, value); }
 915
 916     inline typename QHash<Key, T>::iterator insert(const Key &key, const T &value)
 917     { return QHash<Key, T>::insertMulti(key, value); }
 918
 919     inline QMultiHash &operator+=(const QMultiHash &other)
 920     { this->unite(other); return *this; }
 921     inline QMultiHash operator+(const QMultiHash &other) const
 922     { QMultiHash result = *this; result += other; return result; }
 923
 924 #if !defined(Q_NO_USING_KEYWORD) && !defined(Q_CC_RVCT)
 925     // RVCT compiler doesn't handle using-keyword right when used functions are overloaded in child class
 926     using QHash<Key, T>::contains;
 927     using QHash<Key, T>::remove;
 928     using QHash<Key, T>::count;
 929     using QHash<Key, T>::find;
 930     using QHash<Key, T>::constFind;
 931 #else
 932     inline bool contains(const Key &key) const
 933     { return QHash<Key, T>::contains(key); }
 934     inline int remove(const Key &key)
 935     { return QHash<Key, T>::remove(key); }
 936     inline int count(const Key &key) const
 937     { return QHash<Key, T>::count(key); }
 938     inline int count() const
 939     { return QHash<Key, T>::count(); }
 940     inline typename QHash<Key, T>::iterator find(const Key &key)
 941     { return QHash<Key, T>::find(key); }
 942     inline typename QHash<Key, T>::const_iterator find(const Key &key) const
 943     { return QHash<Key, T>::find(key); }
 944     inline typename QHash<Key, T>::const_iterator constFind(const Key &key) const
 945     { return QHash<Key, T>::constFind(key); }
 946 #endif
 947
 948     bool contains(const Key &key, const T &value) const;
 949
 950     int remove(const Key &key, const T &value);
 951
 952     int count(const Key &key, const T &value) const;
 953
 954     typename QHash<Key, T>::iterator find(const Key &key, const T &value) {
 955         typename QHash<Key, T>::iterator i(find(key));
 956         typename QHash<Key, T>::iterator end(this->end());
 957         while (i != end && i.key() == key) {
 958             if (i.value() == value)
 959                 return i;
 960             ++i;
 961         }
 962         return end;
 963     }
 964     typename QHash<Key, T>::const_iterator find(const Key &key, const T &value) const {
 965         typename QHash<Key, T>::const_iterator i(constFind(key));
 966         typename QHash<Key, T>::const_iterator end(QHash<Key, T>::constEnd());
 967         while (i != end && i.key() == key) {
 968             if (i.value() == value)
 969                 return i;
 970             ++i;
 971         }
 972         return end;
 973     }
 974     typename QHash<Key, T>::const_iterator constFind(const Key &key, const T &value) const
 975         { return find(key, value); }
 976 private:
 977     T &operator[](const Key &key);
 978     const T operator[](const Key &key) const;
 979 };
 980
 981 template <class Key, class T>
 982 Q_INLINE_TEMPLATE bool QMultiHash<Key, T>::contains(const Key &key, const T &value) const
 983 {
 984     return constFind(key, value) != QHash<Key, T>::constEnd();
 985 }
 986
 987 template <class Key, class T>
 988 Q_INLINE_TEMPLATE int QMultiHash<Key, T>::remove(const Key &key, const T &value)
 989 {
 990     int n = 0;
 991     typename QHash<Key, T>::iterator i(find(key));
 992     typename QHash<Key, T>::iterator end(QHash<Key, T>::end());
 993     while (i != end && i.key() == key) {
 994         if (i.value() == value) {
 995             i = this->erase(i);
 996             ++n;
 997         } else {
 998             ++i;
 999         }
1000     }
1001     return n;
1002 }
1003
1004 template <class Key, class T>
1005 Q_INLINE_TEMPLATE int QMultiHash<Key, T>::count(const Key &key, const T &value) const
1006 {
1007     int n = 0;
1008     typename QHash<Key, T>::const_iterator i(constFind(key));
1009     typename QHash<Key, T>::const_iterator end(QHash<Key, T>::constEnd());
1010     while (i != end && i.key() == key) {
1011         if (i.value() == value)
1012             ++n;
1013         ++i;
1014     }
1015     return n;
1016 }
1017
1018 Q_DECLARE_ASSOCIATIVE_ITERATOR(Hash)
1019 Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Hash)
1020
1021 QT_END_NAMESPACE
1022
1023 QT_END_HEADER
1024
1025 #endif // QHASH_H