LCOV - code coverage report
Current view: top level - usr/include/x86_64-linux-gnu/qt5/QtCore - qhash.h (source / functions) Hit Total Coverage
Test: coverage.info Lines: 0 86 0.0 %
Date: 2016-11-29 15:07:43 Functions: 0 68 0.0 %

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

Generated by: LCOV version 1.11