- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files
- Directories
- Examples

- File List
- File Members

# qhash.h

Go to the documentation of this file.

    00001 /****************************************************************************
    00002 **
    00003 ** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies).
    00004 ** All rights reserved.
    00005 ** Contact: Nokia Corporation (qt-info@nokia.com)
    00006 **
    00007 ** This file is part of the QtCore module of the Qt Toolkit.
    00008 **
    00009 ** $QT_BEGIN_LICENSE:LGPL$
    00010 ** Commercial Usage
    00011 ** Licensees holding valid Qt Commercial licenses may use this file in
    00012 ** accordance with the Qt Commercial License Agreement provided with the
    00013 ** Software or, alternatively, in accordance with the terms contained in
    00014 ** a written agreement between you and Nokia.
    00015 **
    00016 ** GNU Lesser General Public License Usage
    00017 ** Alternatively, this file may be used under the terms of the GNU Lesser
    00018 ** General Public License version 2.1 as published by the Free Software
    00019 ** Foundation and appearing in the file LICENSE.LGPL included in the
    00020 ** packaging of this file.  Please review the following information to
    00021 ** ensure the GNU Lesser General Public License version 2.1 requirements
    00022 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
    00023 **
    00024 ** In addition, as a special exception, Nokia gives you certain additional
    00025 ** rights.  These rights are described in the Nokia Qt LGPL Exception
    00026 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this module.
    00027 **
    00028 ** GNU General Public License Usage
    00029 ** Alternatively, this file may be used under the terms of the GNU
    00030 ** General Public License version 3.0 as published by the Free Software
    00031 ** Foundation and appearing in the file LICENSE.GPL included in the
    00032 ** packaging of this file.  Please review the following information to
    00033 ** ensure the GNU General Public License version 3.0 requirements will be
    00034 ** met: http://www.gnu.org/copyleft/gpl.html.
    00035 **
    00036 ** If you have questions regarding the use of this file, please contact
    00037 ** Nokia at qt-info@nokia.com.
    00038 ** $QT_END_LICENSE$
    00039 **
    00040 ****************************************************************************/
    00041
    00042 #ifndef QHASH_H
    00043 #define QHASH_H
    00044
    00045 #include <QtCore/qatomic.h>
    00046 #include <QtCore/qchar.h>
    00047 #include <QtCore/qiterator.h>
    00048 #include <QtCore/qlist.h>
    00049 #include <QtCore/qpair.h>
    00050
    00051 QT_BEGIN_HEADER
    00052
    00053 QT_BEGIN_NAMESPACE
    00054
    00055 QT_MODULE(Core)
    00056
    00057 class QBitArray;
    00058 class QByteArray;
    00059 class QString;
    00060 class QStringRef;
    00061
    00062 inline uint qHash(char key) { return uint(key); }
    00063 inline uint qHash(uchar key) { return uint(key); }
    00064 inline uint qHash(signed char key) { return uint(key); }
    00065 inline uint qHash(ushort key) { return uint(key); }
    00066 inline uint qHash(short key) { return uint(key); }
    00067 inline uint qHash(uint key) { return key; }
    00068 inline uint qHash(int key) { return uint(key); }
    00069 inline uint qHash(ulong key)
    00070 {
    00071     if (sizeof(ulong) > sizeof(uint)) {
    00072         return uint(((key >> (8 * sizeof(uint) - 1)) ^ key) & (~0U));
    00073     } else {
    00074         return uint(key & (~0U));
    00075     }
    00076 }
    00077 inline uint qHash(long key) { return qHash(ulong(key)); }
    00078 inline uint qHash(quint64 key)
    00079 {
    00080     if (sizeof(quint64) > sizeof(uint)) {
    00081         return uint(((key >> (8 * sizeof(uint) - 1)) ^ key) & (~0U));
    00082     } else {
    00083         return uint(key & (~0U));
    00084     }
    00085 }
    00086 inline uint qHash(qint64 key) { return qHash(quint64(key)); }
    00087 inline uint qHash(QChar key) { return qHash(key.unicode()); }
    00088 Q_CORE_EXPORT uint qHash(const QByteArray &key);
    00089 Q_CORE_EXPORT uint qHash(const QString &key);
    00090 Q_CORE_EXPORT uint qHash(const QStringRef &key);
    00091 Q_CORE_EXPORT uint qHash(const QBitArray &key);
    00092
    00093 #if defined(Q_CC_MSVC)
    00094 #pragma warning( push )
    00095 #pragma warning( disable : 4311 ) // disable pointer truncation warning
    00096 #endif
    00097 template <class T> inline uint qHash(const T *key)
    00098 {
    00099     return qHash(reinterpret_cast<quintptr>(key));
    00100 }
    00101 #if defined(Q_CC_MSVC)
    00102 #pragma warning( pop )
    00103 #endif
    00104
    00105 template <typename T1, typename T2> inline uint qHash(const QPair<T1, T2> &key)
    00106 {
    00107     uint h1 = qHash(key.first);
    00108     uint h2 = qHash(key.second);
    00109     return ((h1 << 16) | (h1 >> 16)) ^ h2;
    00110 }
    00111
    00112 struct Q_CORE_EXPORT QHashData
    00113 {
    00114     struct Node {
    00115         Node *next;
    00116         uint h;
    00117     };
    00118
    00119     Node *fakeNext;
    00120     Node **buckets;
    00121     QBasicAtomicInt ref;
    00122     int size;
    00123     int nodeSize;
    00124     short userNumBits;
    00125     short numBits;
    00126     int numBuckets;
    00127     uint sharable : 1;
    00128     uint strictAlignment : 1;
    00129     uint reserved : 30;
    00130
    00131     void *allocateNode(); // ### Qt5 remove me
    00132     void *allocateNode(int nodeAlign);
    00133     void freeNode(void *node);
    00134     QHashData *detach_helper(void (*node_duplicate)(Node *, void *), int nodeSize); // ### Qt5 remove me
    00135     QHashData *detach_helper2(void (*node_duplicate)(Node *, void *), void (*node_delete)(Node *),
    00136                               int nodeSize, int nodeAlign);
    00137     void mightGrow();
    00138     bool willGrow();
    00139     void hasShrunk();
    00140     void rehash(int hint);
    00141     void free_helper(void (*node_delete)(Node *));
    00142     void destroyAndFree(); // ### Qt5 remove me
    00143     Node *firstNode();
    00144 #ifdef QT_QHASH_DEBUG
    00145     void dump();
    00146     void checkSanity();
    00147 #endif
    00148     static Node *nextNode(Node *node);
    00149     static Node *previousNode(Node *node);
    00150
    00151     static QHashData shared_null;
    00152 };
    00153
    00154 inline void QHashData::mightGrow() // ### Qt 5: eliminate
    00155 {
    00156     if (size >= numBuckets)
    00157         rehash(numBits + 1);
    00158 }
    00159
    00160 inline bool QHashData::willGrow()
    00161 {
    00162     if (size >= numBuckets) {
    00163         rehash(numBits + 1);
    00164         return true;
    00165     } else {
    00166         return false;
    00167     }
    00168 }
    00169
    00170 inline void QHashData::hasShrunk()
    00171 {
    00172     if (size <= (numBuckets >> 3) && numBits > userNumBits) {
    00173         QT_TRY {
    00174             rehash(qMax(int(numBits) - 2, int(userNumBits)));
    00175         } QT_CATCH(const std::bad_alloc &) {
    00176             // ignore bad allocs - shrinking shouldn't throw. rehash is exception safe.
    00177         }
    00178     }
    00179 }
    00180
    00181 inline QHashData::Node *QHashData::firstNode()
    00182 {
    00183     Node *e = reinterpret_cast<Node *>(this);
    00184     Node **bucket = buckets;
    00185     int n = numBuckets;
    00186     while (n--) {
    00187         if (*bucket != e)
    00188             return *bucket;
    00189         ++bucket;
    00190     }
    00191     return e;
    00192 }
    00193
    00194 struct QHashDummyValue
    00195 {
    00196 };
    00197
    00198 inline bool operator==(const QHashDummyValue & /* v1 */, const QHashDummyValue & /* v2 */)
    00199 {
    00200     return true;
    00201 }
    00202
    00203 Q_DECLARE_TYPEINFO(QHashDummyValue, Q_MOVABLE_TYPE | Q_DUMMY_TYPE);
    00204
    00205 template <class Key, class T>
    00206 struct QHashDummyNode
    00207 {
    00208     QHashDummyNode *next;
    00209     uint h;
    00210     Key key;
    00211
    00212     inline QHashDummyNode(const Key &key0) : key(key0) {}
    00213 };
    00214
    00215 template <class Key, class T>
    00216 struct QHashNode
    00217 {
    00218     QHashNode *next;
    00219     uint h;
    00220     Key key;
    00221     T value;
    00222
    00223     inline QHashNode(const Key &key0) : key(key0) {} // ### remove in 5.0
    00224     inline QHashNode(const Key &key0, const T &value0) : key(key0), value(value0) {}
    00225     inline bool same_key(uint h0, const Key &key0) { return h0 == h && key0 == key; }
    00226 };
    00227
    00228 #ifndef QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION
    00229 #define Q_HASH_DECLARE_INT_NODES(key_type) \
    00230     template <class T> \
    00231     struct QHashDummyNode<key_type, T> { \
    00232         QHashDummyNode *next; \
    00233         union { uint h; key_type key; }; \
    00234 \
    00235         inline QHashDummyNode(key_type /* key0 */) {} \
    00236     }; \
    00237 \
    00238     template <class T> \
    00239     struct QHashNode<key_type, T> { \
    00240         QHashNode *next; \
    00241         union { uint h; key_type key; }; \
    00242         T value; \
    00243 \
    00244         inline QHashNode(key_type /* key0 */) {} \
    00245         inline QHashNode(key_type /* key0 */, const T &value0) : value(value0) {} \
    00246         inline bool same_key(uint h0, key_type) { return h0 == h; } \
    00247     }
    00248
    00249 #if defined(Q_BYTE_ORDER) && Q_BYTE_ORDER == Q_LITTLE_ENDIAN
    00250 Q_HASH_DECLARE_INT_NODES(short);
    00251 Q_HASH_DECLARE_INT_NODES(ushort);
    00252 #endif
    00253 Q_HASH_DECLARE_INT_NODES(int);
    00254 Q_HASH_DECLARE_INT_NODES(uint);
    00255 #undef Q_HASH_DECLARE_INT_NODES
    00256 #endif // QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION
    00257
    00258 template <class Key, class T>
    00259 class QHash
    00260 {
    00261     typedef QHashDummyNode<Key, T> DummyNode;
    00262     typedef QHashNode<Key, T> Node;
    00263
    00264     union {
    00265         QHashData *d;
    00266         QHashNode<Key, T> *e;
    00267     };
    00268
    00269     static inline Node *concrete(QHashData::Node *node) {
    00270         return reinterpret_cast<Node *>(node);
    00271     }
    00272
    00273 #ifdef Q_ALIGNOF
    00274     static inline int alignOfNode() { return qMax<int>(sizeof(void*), Q_ALIGNOF(Node)); }
    00275     static inline int alignOfDummyNode() { return qMax<int>(sizeof(void*), Q_ALIGNOF(DummyNode)); }
    00276 #else
    00277     static inline int alignOfNode() { return 0; }
    00278     static inline int alignOfDummyNode() { return 0; }
    00279 #endif
    00280
    00281 public:
    00282     inline QHash() : d(&QHashData::shared_null) { d->ref.ref(); }
    00283     inline QHash(const QHash<Key, T> &other) : d(other.d) { d->ref.ref(); if (!d->sharable) detach(); }
    00284     inline ~QHash() { if (!d->ref.deref()) freeData(d); }
    00285
    00286     QHash<Key, T> &operator=(const QHash<Key, T> &other);
    00287
    00288     bool operator==(const QHash<Key, T> &other) const;
    00289     inline bool operator!=(const QHash<Key, T> &other) const { return !(*this == other); }
    00290
    00291     inline int size() const { return d->size; }
    00292
    00293     inline bool isEmpty() const { return d->size == 0; }
    00294
    00295     inline int capacity() const { return d->numBuckets; }
    00296     void reserve(int size);
    00297     inline void squeeze() { reserve(1); }
    00298
    00299     inline void detach() { if (d->ref != 1) detach_helper(); }
    00300     inline bool isDetached() const { return d->ref == 1; }
    00301     inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }
    00302     inline bool isSharedWith(const QHash<Key, T> &other) const { return d == other.d; }
    00303
    00304     void clear();
    00305
    00306     int remove(const Key &key);
    00307     T take(const Key &key);
    00308
    00309     bool contains(const Key &key) const;
    00310     const Key key(const T &value) const;
    00311     const Key key(const T &value, const Key &defaultKey) const;
    00312     const T value(const Key &key) const;
    00313     const T value(const Key &key, const T &defaultValue) const;
    00314     T &operator[](const Key &key);
    00315     const T operator[](const Key &key) const;
    00316
    00317     QList<Key> uniqueKeys() const;
    00318     QList<Key> keys() const;
    00319     QList<Key> keys(const T &value) const;
    00320     QList<T> values() const;
    00321     QList<T> values(const Key &key) const;
    00322     int count(const Key &key) const;
    00323
    00324     class const_iterator;
    00325
    00326     class iterator
    00327     {
    00328         friend class const_iterator;
    00329         QHashData::Node *i;
    00330
    00331     public:
    00332         typedef std::bidirectional_iterator_tag iterator_category;
    00333         typedef qptrdiff difference_type;
    00334         typedef T value_type;
    00335         typedef T *pointer;
    00336         typedef T &reference;
    00337
    00338         // ### Qt 5: get rid of 'operator Node *'
    00339         inline operator Node *() const { return concrete(i); }
    00340         inline iterator() : i(0) { }
    00341         explicit inline iterator(void *node) : i(reinterpret_cast<QHashData::Node *>(node)) { }
    00342
    00343         inline const Key &key() const { return concrete(i)->key; }
    00344         inline T &value() const { return concrete(i)->value; }
    00345         inline T &operator*() const { return concrete(i)->value; }
    00346         inline T *operator->() const { return &concrete(i)->value; }
    00347         inline bool operator==(const iterator &o) const { return i == o.i; }
    00348         inline bool operator!=(const iterator &o) const { return i != o.i; }
    00349
    00350         inline iterator &operator++() {
    00351             i = QHashData::nextNode(i);
    00352             return *this;
    00353         }
    00354         inline iterator operator++(int) {
    00355             iterator r = *this;
    00356             i = QHashData::nextNode(i);
    00357             return r;
    00358         }
    00359         inline iterator &operator--() {
    00360             i = QHashData::previousNode(i);
    00361             return *this;
    00362         }
    00363         inline iterator operator--(int) {
    00364             iterator r = *this;
    00365             i = QHashData::previousNode(i);
    00366             return r;
    00367         }
    00368         inline iterator operator+(int j) const
    00369         { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
    00370         inline iterator operator-(int j) const { return operator+(-j); }
    00371         inline iterator &operator+=(int j) { return *this = *this + j; }
    00372         inline iterator &operator-=(int j) { return *this = *this - j; }
    00373
    00374         // ### Qt 5: not sure this is necessary anymore
    00375 #ifdef QT_STRICT_ITERATORS
    00376     private:
    00377 #else
    00378     public:
    00379 #endif
    00380         inline bool operator==(const const_iterator &o) const
    00381             { return i == o.i; }
    00382         inline bool operator!=(const const_iterator &o) const
    00383             { return i != o.i; }
    00384
    00385     private:
    00386         // ### Qt 5: remove
    00387         inline operator bool() const { return false; }
    00388     };
    00389     friend class iterator;
    00390
    00391     class const_iterator
    00392     {
    00393         friend class iterator;
    00394         QHashData::Node *i;
    00395
    00396     public:
    00397         typedef std::bidirectional_iterator_tag iterator_category;
    00398         typedef qptrdiff difference_type;
    00399         typedef T value_type;
    00400         typedef const T *pointer;
    00401         typedef const T &reference;
    00402
    00403         // ### Qt 5: get rid of 'operator Node *'
    00404         inline operator Node *() const { return concrete(i); }
    00405         inline const_iterator() : i(0) { }
    00406         explicit inline const_iterator(void *node)
    00407             : i(reinterpret_cast<QHashData::Node *>(node)) { }
    00408 #ifdef QT_STRICT_ITERATORS
    00409         explicit inline const_iterator(const iterator &o)
    00410 #else
    00411         inline const_iterator(const iterator &o)
    00412 #endif
    00413         { i = o.i; }
    00414
    00415         inline const Key &key() const { return concrete(i)->key; }
    00416         inline const T &value() const { return concrete(i)->value; }
    00417         inline const T &operator*() const { return concrete(i)->value; }
    00418         inline const T *operator->() const { return &concrete(i)->value; }
    00419         inline bool operator==(const const_iterator &o) const { return i == o.i; }
    00420         inline bool operator!=(const const_iterator &o) const { return i != o.i; }
    00421
    00422         inline const_iterator &operator++() {
    00423             i = QHashData::nextNode(i);
    00424             return *this;
    00425         }
    00426         inline const_iterator operator++(int) {
    00427             const_iterator r = *this;
    00428             i = QHashData::nextNode(i);
    00429             return r;
    00430         }
    00431         inline const_iterator &operator--() {
    00432             i = QHashData::previousNode(i);
    00433             return *this;
    00434         }
    00435         inline const_iterator operator--(int) {
    00436             const_iterator r = *this;
    00437             i = QHashData::previousNode(i);
    00438             return r;
    00439         }
    00440         inline const_iterator operator+(int j) const
    00441         { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
    00442         inline const_iterator operator-(int j) const { return operator+(-j); }
    00443         inline const_iterator &operator+=(int j) { return *this = *this + j; }
    00444         inline const_iterator &operator-=(int j) { return *this = *this - j; }
    00445
    00446         // ### Qt 5: not sure this is necessary anymore
    00447 #ifdef QT_STRICT_ITERATORS
    00448     private:
    00449         inline bool operator==(const iterator &o) const { return operator==(const_iterator(o)); }
    00450         inline bool operator!=(const iterator &o) const { return operator!=(const_iterator(o)); }
    00451 #endif
    00452
    00453     private:
    00454         // ### Qt 5: remove
    00455         inline operator bool() const { return false; }
    00456     };
    00457     friend class const_iterator;
    00458
    00459     // STL style
    00460     inline iterator begin() { detach(); return iterator(d->firstNode()); }
    00461     inline const_iterator begin() const { return const_iterator(d->firstNode()); }
    00462     inline const_iterator constBegin() const { return const_iterator(d->firstNode()); }
    00463     inline iterator end() { detach(); return iterator(e); }
    00464     inline const_iterator end() const { return const_iterator(e); }
    00465     inline const_iterator constEnd() const { return const_iterator(e); }
    00466     iterator erase(iterator it);
    00467
    00468     // more Qt
    00469     typedef iterator Iterator;
    00470     typedef const_iterator ConstIterator;
    00471     inline int count() const { return d->size; }
    00472     iterator find(const Key &key);
    00473     const_iterator find(const Key &key) const;
    00474     const_iterator constFind(const Key &key) const;
    00475     iterator insert(const Key &key, const T &value);
    00476     iterator insertMulti(const Key &key, const T &value);
    00477     QHash<Key, T> &unite(const QHash<Key, T> &other);
    00478
    00479     // STL compatibility
    00480     typedef T mapped_type;
    00481     typedef Key key_type;
    00482     typedef qptrdiff difference_type;
    00483     typedef int size_type;
    00484
    00485     inline bool empty() const { return isEmpty(); }
    00486
    00487 #ifdef QT_QHASH_DEBUG
    00488     inline void dump() const { d->dump(); }
    00489     inline void checkSanity() const { d->checkSanity(); }
    00490 #endif
    00491
    00492 private:
    00493     void detach_helper();
    00494     void freeData(QHashData *d);
    00495     Node **findNode(const Key &key, uint *hp = 0) const;
    00496     Node *createNode(uint h, const Key &key, const T &value, Node **nextNode);
    00497     void deleteNode(Node *node);
    00498     static void deleteNode2(QHashData::Node *node);
    00499
    00500     static void duplicateNode(QHashData::Node *originalNode, void *newNode);
    00501 };
    00502
    00503
    00504 template <class Key, class T>
    00505 Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode(Node *node)
    00506 {
    00507     deleteNode2(reinterpret_cast<QHashData::Node*>(node));
    00508     d->freeNode(node);
    00509 }
    00510
    00511 template <class Key, class T>
    00512 Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode2(QHashData::Node *node)
    00513 {
    00514 #ifdef Q_CC_BOR
    00515     concrete(node)->~QHashNode<Key, T>();
    00516 #elif defined(QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION)
    00517     concrete(node)->~QHashNode();
    00518 #else
    00519     concrete(node)->~Node();
    00520 #endif
    00521 }
    00522
    00523 template <class Key, class T>
    00524 Q_INLINE_TEMPLATE void QHash<Key, T>::duplicateNode(QHashData::Node *node, void *newNode)
    00525 {
    00526     Node *concreteNode = concrete(node);
    00527     if (QTypeInfo<T>::isDummy) {
    00528         (void) new (newNode) DummyNode(concreteNode->key);
    00529     } else {
    00530         (void) new (newNode) Node(concreteNode->key, concreteNode->value);
    00531     }
    00532 }
    00533
    00534 template <class Key, class T>
    00535 Q_INLINE_TEMPLATE typename QHash<Key, T>::Node *
    00536 QHash<Key, T>::createNode(uint ah, const Key &akey, const T &avalue, Node **anextNode)
    00537 {
    00538     Node *node;
    00539
    00540     if (QTypeInfo<T>::isDummy) {
    00541         node = reinterpret_cast<Node *>(new (d->allocateNode(alignOfDummyNode())) DummyNode(akey));
    00542     } else {
    00543         node = new (d->allocateNode(alignOfNode())) Node(akey, avalue);
    00544     }
    00545
    00546     node->h = ah;
    00547     node->next = *anextNode;
    00548     *anextNode = node;
    00549     ++d->size;
    00550     return node;
    00551 }
    00552
    00553 template <class Key, class T>
    00554 Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::unite(const QHash<Key, T> &other)
    00555 {
    00556     QHash<Key, T> copy(other);
    00557     const_iterator it = copy.constEnd();
    00558     while (it != copy.constBegin()) {
    00559         --it;
    00560         insertMulti(it.key(), it.value());
    00561     }
    00562     return *this;
    00563 }
    00564
    00565 template <class Key, class T>
    00566 Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::freeData(QHashData *x)
    00567 {
    00568     x->free_helper(deleteNode2);
    00569 }
    00570
    00571 template <class Key, class T>
    00572 Q_INLINE_TEMPLATE void QHash<Key, T>::clear()
    00573 {
    00574     *this = QHash<Key,T>();
    00575 }
    00576
    00577 template <class Key, class T>
    00578 Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::detach_helper()
    00579 {
    00580     QHashData *x = d->detach_helper2(duplicateNode, deleteNode2,
    00581         QTypeInfo<T>::isDummy ? sizeof(DummyNode) : sizeof(Node),
    00582         QTypeInfo<T>::isDummy ? alignOfDummyNode() : alignOfNode());
    00583     if (!d->ref.deref())
    00584         freeData(d);
    00585     d = x;
    00586 }
    00587
    00588 template <class Key, class T>
    00589 Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::operator=(const QHash<Key, T> &other)
    00590 {
    00591     if (d != other.d) {
    00592         QHashData *o = other.d;
    00593         o->ref.ref();
    00594         if (!d->ref.deref())
    00595             freeData(d);
    00596         d = o;
    00597         if (!d->sharable)
    00598             detach_helper();
    00599     }
    00600     return *this;
    00601 }
    00602
    00603 template <class Key, class T>
    00604 Q_INLINE_TEMPLATE const T QHash<Key, T>::value(const Key &akey) const
    00605 {
    00606     Node *node;
    00607     if (d->size == 0 || (node = *findNode(akey)) == e) {
    00608         return T();
    00609     } else {
    00610         return node->value;
    00611     }
    00612 }
    00613
    00614 template <class Key, class T>
    00615 Q_INLINE_TEMPLATE const T QHash<Key, T>::value(const Key &akey, const T &adefaultValue) const
    00616 {
    00617     Node *node;
    00618     if (d->size == 0 || (node = *findNode(akey)) == e) {
    00619         return adefaultValue;
    00620     } else {
    00621         return node->value;
    00622     }
    00623 }
    00624
    00625 template <class Key, class T>
    00626 Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::uniqueKeys() const
    00627 {
    00628     QList<Key> res;
    00629     res.reserve(size()); // May be too much, but assume short lifetime
    00630     const_iterator i = begin();
    00631     if (i != end()) {
    00632         for (;;) {
    00633             const Key &aKey = i.key();
    00634             res.append(aKey);
    00635             do {
    00636                 if (++i == end())
    00637                     goto break_out_of_outer_loop;
    00638             } while (aKey == i.key());
    00639         }
    00640     }
    00641 break_out_of_outer_loop:
    00642     return res;
    00643 }
    00644
    00645 template <class Key, class T>
    00646 Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys() const
    00647 {
    00648     QList<Key> res;
    00649     res.reserve(size());
    00650     const_iterator i = begin();
    00651     while (i != end()) {
    00652         res.append(i.key());
    00653         ++i;
    00654     }
    00655     return res;
    00656 }
    00657
    00658 template <class Key, class T>
    00659 Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys(const T &avalue) const
    00660 {
    00661     QList<Key> res;
    00662     const_iterator i = begin();
    00663     while (i != end()) {
    00664         if (i.value() == avalue)
    00665             res.append(i.key());
    00666         ++i;
    00667     }
    00668     return res;
    00669 }
    00670
    00671 template <class Key, class T>
    00672 Q_OUTOFLINE_TEMPLATE const Key QHash<Key, T>::key(const T &avalue) const
    00673 {
    00674     return key(avalue, Key());
    00675 }
    00676
    00677 template <class Key, class T>
    00678 Q_OUTOFLINE_TEMPLATE const Key QHash<Key, T>::key(const T &avalue, const Key &defaultValue) const
    00679 {
    00680     const_iterator i = begin();
    00681     while (i != end()) {
    00682         if (i.value() == avalue)
    00683             return i.key();
    00684         ++i;
    00685     }
    00686
    00687     return defaultValue;
    00688 }
    00689
    00690 template <class Key, class T>
    00691 Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values() const
    00692 {
    00693     QList<T> res;
    00694     res.reserve(size());
    00695     const_iterator i = begin();
    00696     while (i != end()) {
    00697         res.append(i.value());
    00698         ++i;
    00699     }
    00700     return res;
    00701 }
    00702
    00703 template <class Key, class T>
    00704 Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values(const Key &akey) const
    00705 {
    00706     QList<T> res;
    00707     Node *node = *findNode(akey);
    00708     if (node != e) {
    00709         do {
    00710             res.append(node->value);
    00711         } while ((node = node->next) != e && node->key == akey);
    00712     }
    00713     return res;
    00714 }
    00715
    00716 template <class Key, class T>
    00717 Q_OUTOFLINE_TEMPLATE int QHash<Key, T>::count(const Key &akey) const
    00718 {
    00719     int cnt = 0;
    00720     Node *node = *findNode(akey);
    00721     if (node != e) {
    00722         do {
    00723             ++cnt;
    00724         } while ((node = node->next) != e && node->key == akey);
    00725     }
    00726     return cnt;
    00727 }
    00728
    00729 template <class Key, class T>
    00730 Q_INLINE_TEMPLATE const T QHash<Key, T>::operator[](const Key &akey) const
    00731 {
    00732     return value(akey);
    00733 }
    00734
    00735 template <class Key, class T>
    00736 Q_INLINE_TEMPLATE T &QHash<Key, T>::operator[](const Key &akey)
    00737 {
    00738     detach();
    00739
    00740     uint h;
    00741     Node **node = findNode(akey, &h);
    00742     if (*node == e) {
    00743         if (d->willGrow())
    00744             node = findNode(akey, &h);
    00745         return createNode(h, akey, T(), node)->value;
    00746     }
    00747     return (*node)->value;
    00748 }
    00749
    00750 template <class Key, class T>
    00751 Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insert(const Key &akey,
    00752                                                                          const T &avalue)
    00753 {
    00754     detach();
    00755
    00756     uint h;
    00757     Node **node = findNode(akey, &h);
    00758     if (*node == e) {
    00759         if (d->willGrow())
    00760             node = findNode(akey, &h);
    00761         return iterator(createNode(h, akey, avalue, node));
    00762     }
    00763
    00764     if (!QTypeInfo<T>::isDummy)
    00765         (*node)->value = avalue;
    00766     return iterator(*node);
    00767 }
    00768
    00769 template <class Key, class T>
    00770 Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insertMulti(const Key &akey,
    00771                                                                               const T &avalue)
    00772 {
    00773     detach();
    00774     d->willGrow();
    00775
    00776     uint h;
    00777     Node **nextNode = findNode(akey, &h);
    00778     return iterator(createNode(h, akey, avalue, nextNode));
    00779 }
    00780
    00781 template <class Key, class T>
    00782 Q_OUTOFLINE_TEMPLATE int QHash<Key, T>::remove(const Key &akey)
    00783 {
    00784     if (isEmpty()) // prevents detaching shared null
    00785         return 0;
    00786     detach();
    00787
    00788     int oldSize = d->size;
    00789     Node **node = findNode(akey);
    00790     if (*node != e) {
    00791         bool deleteNext = true;
    00792         do {
    00793             Node *next = (*node)->next;
    00794             deleteNext = (next != e && next->key == (*node)->key);
    00795             deleteNode(*node);
    00796             *node = next;
    00797             --d->size;
    00798         } while (deleteNext);
    00799         d->hasShrunk();
    00800     }
    00801     return oldSize - d->size;
    00802 }
    00803
    00804 template <class Key, class T>
    00805 Q_OUTOFLINE_TEMPLATE T QHash<Key, T>::take(const Key &akey)
    00806 {
    00807     if (isEmpty()) // prevents detaching shared null
    00808         return T();
    00809     detach();
    00810
    00811     Node **node = findNode(akey);
    00812     if (*node != e) {
    00813         T t = (*node)->value;
    00814         Node *next = (*node)->next;
    00815         deleteNode(*node);
    00816         *node = next;
    00817         --d->size;
    00818         d->hasShrunk();
    00819         return t;
    00820     }
    00821     return T();
    00822 }
    00823
    00824 template <class Key, class T>
    00825 Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::erase(iterator it)
    00826 {
    00827     if (it == iterator(e))
    00828         return it;
    00829
    00830     iterator ret = it;
    00831     ++ret;
    00832
    00833     Node *node = it;
    00834     Node **node_ptr = reinterpret_cast<Node **>(&d->buckets[node->h % d->numBuckets]);
    00835     while (*node_ptr != node)
    00836         node_ptr = &(*node_ptr)->next;
    00837     *node_ptr = node->next;
    00838     deleteNode(node);
    00839     --d->size;
    00840     return ret;
    00841 }
    00842
    00843 template <class Key, class T>
    00844 Q_INLINE_TEMPLATE void QHash<Key, T>::reserve(int asize)
    00845 {
    00846     detach();
    00847     d->rehash(-qMax(asize, 1));
    00848 }
    00849
    00850 template <class Key, class T>
    00851 Q_INLINE_TEMPLATE typename QHash<Key, T>::const_iterator QHash<Key, T>::find(const Key &akey) const
    00852 {
    00853     return const_iterator(*findNode(akey));
    00854 }
    00855
    00856 template <class Key, class T>
    00857 Q_INLINE_TEMPLATE typename QHash<Key, T>::const_iterator QHash<Key, T>::constFind(const Key &akey) const
    00858 {
    00859     return const_iterator(*findNode(akey));
    00860 }
    00861
    00862 template <class Key, class T>
    00863 Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::find(const Key &akey)
    00864 {
    00865     detach();
    00866     return iterator(*findNode(akey));
    00867 }
    00868
    00869 template <class Key, class T>
    00870 Q_INLINE_TEMPLATE bool QHash<Key, T>::contains(const Key &akey) const
    00871 {
    00872     return *findNode(akey) != e;
    00873 }
    00874
    00875 template <class Key, class T>
    00876 Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::Node **QHash<Key, T>::findNode(const Key &akey,
    00877                                                                             uint *ahp) const
    00878 {
    00879     Node **node;
    00880     uint h = qHash(akey);
    00881
    00882     if (d->numBuckets) {
    00883         node = reinterpret_cast<Node **>(&d->buckets[h % d->numBuckets]);
    00884         Q_ASSERT(*node == e || (*node)->next);
    00885         while (*node != e && !(*node)->same_key(h, akey))
    00886             node = &(*node)->next;
    00887     } else {
    00888         node = const_cast<Node **>(reinterpret_cast<const Node * const *>(&e));
    00889     }
    00890     if (ahp)
    00891         *ahp = h;
    00892     return node;
    00893 }
    00894
    00895 template <class Key, class T>
    00896 Q_OUTOFLINE_TEMPLATE bool QHash<Key, T>::operator==(const QHash<Key, T> &other) const
    00897 {
    00898     if (size() != other.size())
    00899         return false;
    00900     if (d == other.d)
    00901         return true;
    00902
    00903     const_iterator it = begin();
    00904
    00905     while (it != end()) {
    00906         const Key &akey = it.key();
    00907
    00908         const_iterator it2 = other.find(akey);
    00909         do {
    00910             if (it2 == other.end() || !(it2.key() == akey))
    00911                 return false;
    00912             if (!QTypeInfo<T>::isDummy && !(it.value() == it2.value()))
    00913                 return false;
    00914             ++it;
    00915             ++it2;
    00916         } while (it != end() && it.key() == akey);
    00917     }
    00918     return true;
    00919 }
    00920
    00921 template <class Key, class T>
    00922 class QMultiHash : public QHash<Key, T>
    00923 {
    00924 public:
    00925     QMultiHash() {}
    00926     QMultiHash(const QHash<Key, T> &other) : QHash<Key, T>(other) {}
    00927
    00928     inline typename QHash<Key, T>::iterator replace(const Key &key, const T &value)
    00929     { return QHash<Key, T>::insert(key, value); }
    00930
    00931     inline typename QHash<Key, T>::iterator insert(const Key &key, const T &value)
    00932     { return QHash<Key, T>::insertMulti(key, value); }
    00933
    00934     inline QMultiHash &operator+=(const QMultiHash &other)
    00935     { this->unite(other); return *this; }
    00936     inline QMultiHash operator+(const QMultiHash &other) const
    00937     { QMultiHash result = *this; result += other; return result; }
    00938
    00939 #if !defined(Q_NO_USING_KEYWORD) && !defined(Q_CC_RVCT)
    00940     // RVCT compiler doesn't handle using-keyword right when used functions are overloaded in child class
    00941     using QHash<Key, T>::contains;
    00942     using QHash<Key, T>::remove;
    00943     using QHash<Key, T>::count;
    00944     using QHash<Key, T>::find;
    00945     using QHash<Key, T>::constFind;
    00946 #else
    00947     inline bool contains(const Key &key) const
    00948     { return QHash<Key, T>::contains(key); }
    00949     inline int remove(const Key &key)
    00950     { return QHash<Key, T>::remove(key); }
    00951     inline int count(const Key &key) const
    00952     { return QHash<Key, T>::count(key); }
    00953     inline int count() const
    00954     { return QHash<Key, T>::count(); }
    00955     inline typename QHash<Key, T>::iterator find(const Key &key)
    00956     { return QHash<Key, T>::find(key); }
    00957     inline typename QHash<Key, T>::const_iterator find(const Key &key) const
    00958     { return QHash<Key, T>::find(key); }
    00959     inline typename QHash<Key, T>::const_iterator constFind(const Key &key) const
    00960     { return QHash<Key, T>::constFind(key); }
    00961 #endif
    00962
    00963     bool contains(const Key &key, const T &value) const;
    00964
    00965     int remove(const Key &key, const T &value);
    00966
    00967     int count(const Key &key, const T &value) const;
    00968
    00969     typename QHash<Key, T>::iterator find(const Key &key, const T &value) {
    00970         typename QHash<Key, T>::iterator i(find(key));
    00971         typename QHash<Key, T>::iterator end(this->end());
    00972         while (i != end && i.key() == key) {
    00973             if (i.value() == value)
    00974                 return i;
    00975             ++i;
    00976         }
    00977         return end;
    00978     }
    00979     typename QHash<Key, T>::const_iterator find(const Key &key, const T &value) const {
    00980         typename QHash<Key, T>::const_iterator i(constFind(key));
    00981         typename QHash<Key, T>::const_iterator end(QHash<Key, T>::constEnd());
    00982         while (i != end && i.key() == key) {
    00983             if (i.value() == value)
    00984                 return i;
    00985             ++i;
    00986         }
    00987         return end;
    00988     }
    00989     typename QHash<Key, T>::const_iterator constFind(const Key &key, const T &value) const
    00990         { return find(key, value); }
    00991 private:
    00992     T &operator[](const Key &key);
    00993     const T operator[](const Key &key) const;
    00994 };
    00995
    00996 template <class Key, class T>
    00997 Q_INLINE_TEMPLATE bool QMultiHash<Key, T>::contains(const Key &key, const T &value) const
    00998 {
    00999     return constFind(key, value) != QHash<Key, T>::constEnd();
    01000 }
    01001
    01002 template <class Key, class T>
    01003 Q_INLINE_TEMPLATE int QMultiHash<Key, T>::remove(const Key &key, const T &value)
    01004 {
    01005     int n = 0;
    01006     typename QHash<Key, T>::iterator i(find(key));
    01007     typename QHash<Key, T>::iterator end(QHash<Key, T>::end());
    01008     while (i != end && i.key() == key) {
    01009         if (i.value() == value) {
    01010             i = this->erase(i);
    01011             ++n;
    01012         } else {
    01013             ++i;
    01014         }
    01015     }
    01016     return n;
    01017 }
    01018
    01019 template <class Key, class T>
    01020 Q_INLINE_TEMPLATE int QMultiHash<Key, T>::count(const Key &key, const T &value) const
    01021 {
    01022     int n = 0;
    01023     typename QHash<Key, T>::const_iterator i(constFind(key));
    01024     typename QHash<Key, T>::const_iterator end(QHash<Key, T>::constEnd());
    01025     while (i != end && i.key() == key) {
    01026         if (i.value() == value)
    01027             ++n;
    01028         ++i;
    01029     }
    01030     return n;
    01031 }
    01032
    01033 Q_DECLARE_ASSOCIATIVE_ITERATOR(Hash)
    01034 Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Hash)
    01035
    01036 QT_END_NAMESPACE
    01037
    01038 QT_END_HEADER
    01039
    01040 #endif // QHASH_H