开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > Windows编程 > 系统编程 > 查看源码
qhash.h
资源名称：rootfs-7-9.tar.gz　[点击查看]
上传用户：detong
上传日期：2022-06-22
资源大小：20675k
文件大小：29k
源码类别：

系统编程

开发平台：

Unix_Linux

qhash.h：源码内容
  1. /****************************************************************************
  2. **
  3. ** Copyright (C) 2008 Nokia Corporation and/or its subsidiary(-ies).
  4. ** Contact: Qt Software Information (qt-info@nokia.com)
  5. **
  6. ** This file is part of the QtCore module of the Qt Toolkit.
  7. **
  8. ** Commercial Usage
  9. ** Licensees holding valid Qt Commercial licenses may use this file in
  10. ** accordance with the Qt Commercial License Agreement provided with the
  11. ** Software or, alternatively, in accordance with the terms contained in
  12. ** a written agreement between you and Nokia.
  13. **
  14. **
  15. ** GNU General Public License Usage
  16. ** Alternatively, this file may be used under the terms of the GNU
  17. ** General Public License versions 2.0 or 3.0 as published by the Free
  18. ** Software Foundation and appearing in the file LICENSE.GPL included in
  19. ** the packaging of this file.  Please review the following information
  20. ** to ensure GNU General Public Licensing requirements will be met:
  21. ** http://www.fsf.org/licensing/licenses/info/GPLv2.html and
  22. ** http://www.gnu.org/copyleft/gpl.html.  In addition, as a special
  23. ** exception, Nokia gives you certain additional rights. These rights
  24. ** are described in the Nokia Qt GPL Exception version 1.3, included in
  25. ** the file GPL_EXCEPTION.txt in this package.
  26. **
  27. ** Qt for Windows(R) Licensees
  28. ** As a special exception, Nokia, as the sole copyright holder for Qt
  29. ** Designer, grants users of the Qt/Eclipse Integration plug-in the
  30. ** right for the Qt/Eclipse Integration to link to functionality
  31. ** provided by Qt Designer and its related libraries.
  32. **
  33. ** If you are unsure which license is appropriate for your use, please
  34. ** contact the sales department at qt-sales@nokia.com.
  35. **
  36. ****************************************************************************/
  38. #ifndef QHASH_H
  39. #define QHASH_H
  41. #include <QtCore/qatomic.h>
  42. #include <QtCore/qchar.h>
  43. #include <QtCore/qiterator.h>
  44. #include <QtCore/qlist.h>
  45. #include <QtCore/qpair.h>
  47. QT_BEGIN_HEADER
  49. QT_BEGIN_NAMESPACE
  51. #undef QT_QHASH_DEBUG
  52. QT_MODULE(Core)
  54. class QBitArray;
  55. class QByteArray;
  56. class QString;
  57. class QStringRef;
  59. inline uint qHash(char key) { return uint(key); }
  60. inline uint qHash(uchar key) { return uint(key); }
  61. inline uint qHash(signed char key) { return uint(key); }
  62. inline uint qHash(ushort key) { return uint(key); }
  63. inline uint qHash(short key) { return uint(key); }
  64. inline uint qHash(uint key) { return key; }
  65. inline uint qHash(int key) { return uint(key); }
  66. inline uint qHash(ulong key)
  67. {
  68.     if (sizeof(ulong) > sizeof(uint)) {
  69.         return uint((key >> (8 * sizeof(uint) - 1)) ^ key);
  70.     } else {
  71.         return uint(key);
  72.     }
  73. }
  74. inline uint qHash(long key) { return qHash(ulong(key)); }
  75. inline uint qHash(quint64 key)
  76. {
  77.     if (sizeof(quint64) > sizeof(uint)) {
  78.         return uint((key >> (8 * sizeof(uint) - 1)) ^ key);
  79.     } else {
  80.         return uint(key);
  81.     }
  82. }
  83. inline uint qHash(qint64 key) { return qHash(quint64(key)); }
  84. inline uint qHash(QChar key) { return qHash(key.unicode()); }
  85. Q_CORE_EXPORT uint qHash(const QByteArray &key);
  86. Q_CORE_EXPORT uint qHash(const QString &key);
  87. Q_CORE_EXPORT uint qHash(const QStringRef &key);
  88. Q_CORE_EXPORT uint qHash(const QBitArray &key);
  90. #if defined(Q_CC_MSVC)
  91. #pragma warning( push )
  92. #pragma warning( disable : 4311 ) // disable pointer truncation warning
  93. #endif
  94. template <class T> inline uint qHash(const T *key)
  95. {
  96.     if (sizeof(const T *) > sizeof(uint))
  97.         return qHash(reinterpret_cast<quint64>(key));
  98.     else
  99.         return uint(reinterpret_cast<ulong>(key));
  100. }
  101. #if defined(Q_CC_MSVC)
  102. #pragma warning( pop )
  103. #endif
  105. template <typename T1, typename T2> inline uint qHash(const QPair<T1, T2> &key)
  106. {
  107.     uint h1 = qHash(key.first);
  108.     uint h2 = qHash(key.second);
  109.     return ((h1 << 16) | (h1 >> 16)) ^ h2;
  110. }
  112. struct Q_CORE_EXPORT QHashData
  113. {
  114.     struct Node {
  115.         Node *next;
  116.         uint h;
  117.     };
  119.     Node *fakeNext;
  120.     Node **buckets;
  121.     QBasicAtomicInt ref;
  122.     int size;
  123.     int nodeSize;
  124.     short userNumBits;
  125.     short numBits;
  126.     int numBuckets;
  127.     uint sharable : 1;
  129.     void *allocateNode();
  130.     void freeNode(void *node);
  131.     QHashData *detach_helper(void (*node_duplicate)(Node *, void *), int nodeSize);
  132.     void mightGrow();
  133.     bool willGrow();
  134.     void hasShrunk();
  135.     void rehash(int hint);
  136.     void destroyAndFree();
  137.     Node *firstNode();
  138. #ifdef QT_QHASH_DEBUG
  139.     void dump();
  140.     void checkSanity();
  141. #endif
  142.     static Node *nextNode(Node *node);
  143.     static Node *previousNode(Node *node);
  145.     static QHashData shared_null;
  146. };
  148. inline void QHashData::mightGrow() // ### Qt 5: eliminate
  149. { 
  150.     if (size >= numBuckets)
  151.         rehash(numBits + 1);
  152. }  
  154. inline bool QHashData::willGrow()
  155. {
  156.     if (size >= numBuckets) {
  157.         rehash(numBits + 1);
  158.         return true;
  159.     } else {
  160.         return false;
  161.     }
  162. }
  164. inline void QHashData::hasShrunk()
  165. {
  166.     if (size <= (numBuckets >> 3) && numBits > userNumBits)
  167.         rehash(qMax(int(numBits) - 2, int(userNumBits)));
  168. }
  170. inline QHashData::Node *QHashData::firstNode()
  171. {
  172.     Node *e = reinterpret_cast<Node *>(this);
  173.     Node **bucket = buckets;
  174.     int n = numBuckets;
  175.     while (n--) {
  176.         if (*bucket != e)
  177.             return *bucket;
  178.         ++bucket;
  179.     }
  180.     return e;
  181. }
  183. struct QHashDummyValue
  184. {
  185. };
  187. inline bool operator==(const QHashDummyValue & /* v1 */, const QHashDummyValue & /* v2 */)
  188. {
  189.     return true;
  190. }
  192. Q_DECLARE_TYPEINFO(QHashDummyValue, Q_MOVABLE_TYPE | Q_DUMMY_TYPE);
  194. template <class Key, class T>
  195. struct QHashDummyNode
  196. {
  197.     QHashDummyNode *next;
  198.     uint h;
  199.     Key key;
  201.     inline QHashDummyNode(const Key &key0) : key(key0) {}
  202. };
  204. template <class Key, class T>
  205. struct QHashNode
  206. {
  207.     QHashNode *next;
  208.     uint h;
  209.     Key key;
  210.     T value;
  212.     inline QHashNode(const Key &key0) : key(key0) {} // ### remove in 5.0
  213.     inline QHashNode(const Key &key0, const T &value0) : key(key0), value(value0) {}
  214.     inline bool same_key(uint h0, const Key &key0) { return h0 == h && key0 == key; }
  215. };
  217. #ifndef QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION
  218. #define Q_HASH_DECLARE_INT_NODES(key_type) 
  219.     template <class T> 
  220.     struct QHashDummyNode<key_type, T> { 
  221.         QHashDummyNode *next; 
  222.         union { uint h; key_type key; }; 
  224.         inline QHashDummyNode(key_type /* key0 */) {} 
  225.     }; 
  227.     template <class T> 
  228.     struct QHashNode<key_type, T> { 
  229.         QHashNode *next; 
  230.         union { uint h; key_type key; }; 
  231.         T value; 
  233.         inline QHashNode(key_type /* key0 */) {} 
  234.         inline QHashNode(key_type /* key0 */, const T &value0) : value(value0) {} 
  235.         inline bool same_key(uint h0, key_type) { return h0 == h; } 
  236.     }
  238. #if defined(Q_BYTE_ORDER) && Q_BYTE_ORDER == Q_LITTLE_ENDIAN
  239. Q_HASH_DECLARE_INT_NODES(short);
  240. Q_HASH_DECLARE_INT_NODES(ushort);
  241. #endif
  242. Q_HASH_DECLARE_INT_NODES(int);
  243. Q_HASH_DECLARE_INT_NODES(uint);
  244. #undef Q_HASH_DECLARE_INT_NODES
  245. #endif // QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION
  247. template <class Key, class T>
  248. class QHash
  249. {
  250.     typedef QHashDummyNode<Key, T> DummyNode;
  251.     typedef QHashNode<Key, T> Node;
  253.     union {
  254.         QHashData *d;
  255.         QHashNode<Key, T> *e;
  256.     };
  258.     static inline Node *concrete(QHashData::Node *node) {
  259.         return reinterpret_cast<Node *>(node);
  260.     }
  262. public:
  263.     inline QHash() : d(&QHashData::shared_null) { d->ref.ref(); }
  264.     inline QHash(const QHash<Key, T> &other) : d(other.d) { d->ref.ref(); if (!d->sharable) detach(); }
  265.     inline ~QHash() { if (!d->ref.deref()) freeData(d); }
  267.     QHash<Key, T> &operator=(const QHash<Key, T> &other);
  269.     bool operator==(const QHash<Key, T> &other) const;
  270.     inline bool operator!=(const QHash<Key, T> &other) const { return !(*this == other); }
  272.     inline int size() const { return d->size; }
  274.     inline bool isEmpty() const { return d->size == 0; }
  276.     inline int capacity() const { return d->numBuckets; }
  277.     void reserve(int size);
  278.     inline void squeeze() { reserve(1); }
  280.     inline void detach() { if (d->ref != 1) detach_helper(); }
  281.     inline bool isDetached() const { return d->ref == 1; }
  282.     inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }
  284.     void clear();
  286.     int remove(const Key &key);
  287.     T take(const Key &key);
  289.     bool contains(const Key &key) const;
  290.     const Key key(const T &value) const;
  291.     const Key key(const T &value, const Key &defaultKey) const;
  292.     const T value(const Key &key) const;
  293.     const T value(const Key &key, const T &defaultValue) const;
  294.     T &operator[](const Key &key);
  295.     const T operator[](const Key &key) const;
  297.     QList<Key> uniqueKeys() const;
  298.     QList<Key> keys() const;
  299.     QList<Key> keys(const T &value) const;
  300.     QList<T> values() const;
  301.     QList<T> values(const Key &key) const;
  302.     int count(const Key &key) const;
  304.     class const_iterator;
  306.     class iterator
  307.     {
  308.         friend class const_iterator;
  309.         QHashData::Node *i;
  311.     public:
  312.         typedef std::bidirectional_iterator_tag iterator_category;
  313.         typedef ptrdiff_t difference_type;
  314.         typedef T value_type;
  315.         typedef T *pointer;
  316.         typedef T &reference;
  318.         // ### Qt 5: get rid of 'operator Node *'
  319.         inline operator Node *() const { return concrete(i); }
  320.         inline iterator() : i(0) { }
  321.         explicit inline iterator(void *node) : i(reinterpret_cast<QHashData::Node *>(node)) { }
  323.         inline const Key &key() const { return concrete(i)->key; }
  324.         inline T &value() const { return concrete(i)->value; }
  325.         inline T &operator*() const { return concrete(i)->value; }
  326.         inline T *operator->() const { return &concrete(i)->value; }
  327.         inline bool operator==(const iterator &o) const { return i == o.i; }
  328.         inline bool operator!=(const iterator &o) const { return i != o.i; }
  330.         inline iterator &operator++() {
  331.             i = QHashData::nextNode(i);
  332.             return *this;
  333.         }
  334.         inline iterator operator++(int) {
  335.             iterator r = *this;
  336.             i = QHashData::nextNode(i);
  337.             return r;
  338.         }
  339.         inline iterator &operator--() {
  340.             i = QHashData::previousNode(i);
  341.             return *this;
  342.         }
  343.         inline iterator operator--(int) {
  344.             iterator r = *this;
  345.             i = QHashData::previousNode(i);
  346.             return r;
  347.         }
  348.         inline iterator operator+(int j) const
  349.         { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
  350.         inline iterator operator-(int j) const { return operator+(-j); }
  351.         inline iterator &operator+=(int j) { return *this = *this + j; }
  352.         inline iterator &operator-=(int j) { return *this = *this - j; }
  354.         // ### Qt 5: not sure this is necessary anymore
  355. #ifdef QT_STRICT_ITERATORS
  356.     private:
  357. #else
  358.     public:
  359. #endif
  360.         inline bool operator==(const const_iterator &o) const
  361.             { return i == o.i; }
  362.         inline bool operator!=(const const_iterator &o) const
  363.             { return i != o.i; }
  365.     private:
  366.         // ### Qt 5: remove
  367.         inline operator bool() const { return false; }
  368.     };
  369.     friend class iterator;
  371.     class const_iterator
  372.     {
  373.         friend class iterator;
  374.         QHashData::Node *i;
  376.     public:
  377.         typedef std::bidirectional_iterator_tag iterator_category;
  378.         typedef ptrdiff_t difference_type;
  379.         typedef T value_type;
  380.         typedef const T *pointer;
  381.         typedef const T &reference;
  383.         // ### Qt 5: get rid of 'operator Node *'
  384.         inline operator Node *() const { return concrete(i); }
  385.         inline const_iterator() : i(0) { }
  386.         explicit inline const_iterator(void *node)
  387.             : i(reinterpret_cast<QHashData::Node *>(node)) { }
  388. #ifdef QT_STRICT_ITERATORS
  389.         explicit inline const_iterator(const iterator &o)
  390. #else
  391.         inline const_iterator(const iterator &o)
  392. #endif
  393.         { i = o.i; }
  395.         inline const Key &key() const { return concrete(i)->key; }
  396.         inline const T &value() const { return concrete(i)->value; }
  397.         inline const T &operator*() const { return concrete(i)->value; }
  398.         inline const T *operator->() const { return &concrete(i)->value; }
  399.         inline bool operator==(const const_iterator &o) const { return i == o.i; }
  400.         inline bool operator!=(const const_iterator &o) const { return i != o.i; }
  402.         inline const_iterator &operator++() {
  403.             i = QHashData::nextNode(i);
  404.             return *this;
  405.         }
  406.         inline const_iterator operator++(int) {
  407.             const_iterator r = *this;
  408.             i = QHashData::nextNode(i);
  409.             return r;
  410.         }
  411.         inline const_iterator &operator--() {
  412.             i = QHashData::previousNode(i);
  413.             return *this;
  414.         }
  415.         inline const_iterator operator--(int) {
  416.             const_iterator r = *this;
  417.             i = QHashData::previousNode(i);
  418.             return r;
  419.         }
  420.         inline const_iterator operator+(int j) const
  421.         { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
  422.         inline const_iterator operator-(int j) const { return operator+(-j); }
  423.         inline const_iterator &operator+=(int j) { return *this = *this + j; }
  424.         inline const_iterator &operator-=(int j) { return *this = *this - j; }
  426.         // ### Qt 5: not sure this is necessary anymore
  427. #ifdef QT_STRICT_ITERATORS
  428.     private:
  429.         inline bool operator==(const iterator &o) const { return operator==(const_iterator(o)); }
  430.         inline bool operator!=(const iterator &o) const { return operator!=(const_iterator(o)); }
  431. #endif
  433.     private:
  434.         // ### Qt 5: remove
  435.         inline operator bool() const { return false; }
  436.     };
  437.     friend class const_iterator;
  439.     // STL style
  440.     inline iterator begin() { detach(); return iterator(d->firstNode()); }
  441.     inline const_iterator begin() const { return const_iterator(d->firstNode()); }
  442.     inline const_iterator constBegin() const { return const_iterator(d->firstNode()); }
  443.     inline iterator end() { detach(); return iterator(e); }
  444.     inline const_iterator end() const { return const_iterator(e); }
  445.     inline const_iterator constEnd() const { return const_iterator(e); }
  446.     iterator erase(iterator it);
  448.     // more Qt
  449.     typedef iterator Iterator;
  450.     typedef const_iterator ConstIterator;
  451.     inline int count() const { return d->size; }
  452.     iterator find(const Key &key);
  453.     const_iterator find(const Key &key) const;
  454.     const_iterator constFind(const Key &key) const;
  455.     iterator insert(const Key &key, const T &value);
  456.     iterator insertMulti(const Key &key, const T &value);
  457.     QHash<Key, T> &unite(const QHash<Key, T> &other);
  459.     // STL compatibility
  460.     typedef T mapped_type;
  461.     typedef Key key_type;
  462.     typedef ptrdiff_t difference_type;
  463.     typedef int size_type;
  465.     inline bool empty() const { return isEmpty(); }
  467. #ifdef QT_QHASH_DEBUG
  468.     inline void dump() const { d->dump(); }
  469.     inline void checkSanity() const { d->checkSanity(); }
  470. #endif
  472. private:
  473.     void detach_helper();
  474.     void freeData(QHashData *d);
  475.     Node **findNode(const Key &key, uint *hp = 0) const;
  476.     Node *createNode(uint h, const Key &key, const T &value, Node **nextNode);
  477.     void deleteNode(Node *node);
  479.     static void duplicateNode(QHashData::Node *originalNode, void *newNode);
  480. };
  482. template <class Key, class T>
  483. Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode(Node *node)
  484. {
  485. #ifdef Q_CC_BOR
  486.     node->~QHashNode<Key, T>();
  487. #elif defined(QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION)
  488.     node->~QHashNode();
  489. #else
  490.     node->~Node();
  491. #endif
  492.     d->freeNode(node);
  493. }
  495. template <class Key, class T>
  496. Q_INLINE_TEMPLATE void QHash<Key, T>::duplicateNode(QHashData::Node *node, void *newNode)
  497. {
  498.     Node *concreteNode = concrete(node);
  499.     if (QTypeInfo<T>::isDummy) {
  500.         (void) new (newNode) DummyNode(concreteNode->key);
  501.     } else {
  502.         (void) new (newNode) Node(concreteNode->key, concreteNode->value);
  503.     }
  504. }
  506. template <class Key, class T>
  507. Q_INLINE_TEMPLATE typename QHash<Key, T>::Node *
  508. QHash<Key, T>::createNode(uint ah, const Key &akey, const T &avalue, Node **anextNode)
  509. {
  510.     Node *node;
  512.     if (QTypeInfo<T>::isDummy) {
  513.         node = reinterpret_cast<Node *>(new (d->allocateNode()) DummyNode(akey));
  514.     } else {
  515.         node = new (d->allocateNode()) Node(akey, avalue);
  516.     }
  518.     node->h = ah;
  519.     node->next = *anextNode;
  520.     *anextNode = node;
  521.     ++d->size;
  522.     return node;
  523. }
  525. template <class Key, class T>
  526. Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::unite(const QHash<Key, T> &other)
  527. {
  528.     QHash<Key, T> copy(other);
  529.     const_iterator it = copy.constEnd();
  530.     while (it != copy.constBegin()) {
  531.         --it;
  532.         insertMulti(it.key(), it.value());
  533.     }
  534.     return *this;
  535. }
  537. template <class Key, class T>
  538. Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::freeData(QHashData *x)
  539. {
  540.     Node *e_for_x = reinterpret_cast<Node *>(x);
  541.     Node **bucket = reinterpret_cast<Node **>(x->buckets);
  542.     int n = x->numBuckets;
  543.     while (n--) {
  544.         Node *cur = *bucket++;
  545.         while (cur != e_for_x) {
  546.             Node *next = cur->next;
  547.             deleteNode(cur);
  548.             cur = next;
  549.         }
  550.     }
  551.     x->destroyAndFree();
  552. }
  554. template <class Key, class T>
  555. Q_INLINE_TEMPLATE void QHash<Key, T>::clear()
  556. {
  557.     *this = QHash<Key,T>();
  558. }
  560. template <class Key, class T>
  561. Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::detach_helper()
  562. {
  563.     QHashData *x = d->detach_helper(duplicateNode,
  564.         QTypeInfo<T>::isDummy ? sizeof(DummyNode) : sizeof(Node));
  565.     if (!d->ref.deref())
  566.         freeData(d);
  567.     d = x;
  568. }
  570. template <class Key, class T>
  571. Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::operator=(const QHash<Key, T> &other)
  572. {
  573.     if (d != other.d) {
  574.         other.d->ref.ref();
  575.         if (!d->ref.deref())
  576.             freeData(d);
  577.         d = other.d;
  578.         if (!d->sharable)
  579.             detach_helper();
  580.     }
  581.     return *this;
  582. }
  584. template <class Key, class T>
  585. Q_INLINE_TEMPLATE const T QHash<Key, T>::value(const Key &akey) const
  586. {
  587.     Node *node;
  588.     if (d->size == 0 || (node = *findNode(akey)) == e) {
  589.         return T();
  590.     } else {
  591.         return node->value;
  592.     }
  593. }
  595. template <class Key, class T>
  596. Q_INLINE_TEMPLATE const T QHash<Key, T>::value(const Key &akey, const T &adefaultValue) const
  597. {
  598.     Node *node;
  599.     if (d->size == 0 || (node = *findNode(akey)) == e) {
  600.         return adefaultValue;
  601.     } else {
  602.         return node->value;
  603.     }
  604. }
  606. template <class Key, class T>
  607. Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::uniqueKeys() const
  608. {
  609.     QList<Key> res;
  610.     const_iterator i = begin();
  611.     if (i != end()) {
  612.         for (;;) {
  613.             const Key &aKey = i.key();
  614.             res.append(aKey);
  615.             do {
  616.                 if (++i == end())
  617.                     goto break_out_of_outer_loop;
  618.             } while (aKey == i.key());
  619.         }
  620.     }
  621. break_out_of_outer_loop:
  622.     return res;
  623. }
  625. template <class Key, class T>
  626. Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys() const
  627. {
  628.     QList<Key> res;
  629.     const_iterator i = begin();
  630.     while (i != end()) {
  631.         res.append(i.key());
  632.         ++i;
  633.     }
  634.     return res;
  635. }
  637. template <class Key, class T>
  638. Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys(const T &avalue) const
  639. {
  640.     QList<Key> res;
  641.     const_iterator i = begin();
  642.     while (i != end()) {
  643.         if (i.value() == avalue)
  644.             res.append(i.key());
  645.         ++i;
  646.     }
  647.     return res;
  648. }
  650. template <class Key, class T>
  651. Q_OUTOFLINE_TEMPLATE const Key QHash<Key, T>::key(const T &avalue) const
  652. {
  653.     return key(avalue, Key());
  654. }
  656. template <class Key, class T>
  657. Q_OUTOFLINE_TEMPLATE const Key QHash<Key, T>::key(const T &avalue, const Key &defaultValue) const
  658. {
  659.     const_iterator i = begin();
  660.     while (i != end()) {
  661.         if (i.value() == avalue)
  662.             return i.key();
  663.         ++i;
  664.     }
  666.     return defaultValue;
  667. }
  669. template <class Key, class T>
  670. Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values() const
  671. {
  672.     QList<T> res;
  673.     const_iterator i = begin();
  674.     while (i != end()) {
  675.         res.append(i.value());
  676.         ++i;
  677.     }
  678.     return res;
  679. }
  681. template <class Key, class T>
  682. Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values(const Key &akey) const
  683. {
  684.     QList<T> res;
  685.     Node *node = *findNode(akey);
  686.     if (node != e) {
  687.         do {
  688.             res.append(node->value);
  689.         } while ((node = node->next) != e && node->key == akey);
  690.     }
  691.     return res;
  692. }
  694. template <class Key, class T>
  695. Q_OUTOFLINE_TEMPLATE int QHash<Key, T>::count(const Key &akey) const
  696. {
  697.     int cnt = 0;
  698.     Node *node = *findNode(akey);
  699.     if (node != e) {
  700.         do {
  701.             ++cnt;
  702.         } while ((node = node->next) != e && node->key == akey);
  703.     }
  704.     return cnt;
  705. }
  707. template <class Key, class T>
  708. Q_INLINE_TEMPLATE const T QHash<Key, T>::operator[](const Key &akey) const
  709. {
  710.     return value(akey);
  711. }
  713. template <class Key, class T>
  714. Q_INLINE_TEMPLATE T &QHash<Key, T>::operator[](const Key &akey)
  715. {
  716.     detach();
  718.     uint h;
  719.     Node **node = findNode(akey, &h);
  720.     if (*node == e) {
  721.         if (d->willGrow())
  722.             node = findNode(akey, &h);
  723.         return createNode(h, akey, T(), node)->value;
  724.     }
  725.     return (*node)->value;
  726. }
  728. template <class Key, class T>
  729. Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insert(const Key &akey,
  730.                                                                          const T &avalue)
  731. {
  732.     detach();
  734.     uint h;
  735.     Node **node = findNode(akey, &h);
  736.     if (*node == e) {
  737.         if (d->willGrow())
  738.             node = findNode(akey, &h);
  739.         return iterator(createNode(h, akey, avalue, node));
  740.     }
  742.     if (!QTypeInfo<T>::isDummy)
  743.         (*node)->value = avalue;
  744.     return iterator(*node);
  745. }
  747. template <class Key, class T>
  748. Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insertMulti(const Key &akey,
  749.                                                                               const T &avalue)
  750. {
  751.     detach();
  752.     d->willGrow();
  754.     uint h;
  755.     Node **nextNode = findNode(akey, &h);
  756.     return iterator(createNode(h, akey, avalue, nextNode));
  757. }
  759. template <class Key, class T>
  760. Q_OUTOFLINE_TEMPLATE int QHash<Key, T>::remove(const Key &akey)
  761. {
  762.     detach();
  764.     int oldSize = d->size;
  765.     Node **node = findNode(akey);
  766.     if (*node != e) {
  767.         bool deleteNext = true;
  768.         do {
  769.             Node *next = (*node)->next;
  770.             deleteNext = (next != e && next->key == (*node)->key);
  771.             deleteNode(*node);
  772.             *node = next;
  773.             --d->size;
  774.         } while (deleteNext);
  775.         d->hasShrunk();
  776.     }
  777.     return oldSize - d->size;
  778. }
  780. template <class Key, class T>
  781. Q_OUTOFLINE_TEMPLATE T QHash<Key, T>::take(const Key &akey)
  782. {
  783.     detach();
  785.     Node **node = findNode(akey);
  786.     if (*node != e) {
  787.         T t = (*node)->value;
  788.         Node *next = (*node)->next;
  789.         deleteNode(*node);
  790.         *node = next;
  791.         --d->size;
  792.         d->hasShrunk();
  793.         return t;
  794.     }
  795.     return T();
  796. }
  798. template <class Key, class T>
  799. Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::erase(iterator it)
  800. {
  801.     if (it == iterator(e))
  802.         return it;
  804.     iterator ret = it;
  805.     ++ret;
  807.     Node *node = it;
  808.     Node **node_ptr = reinterpret_cast<Node **>(&d->buckets[node->h % d->numBuckets]);
  809.     while (*node_ptr != node)
  810.         node_ptr = &(*node_ptr)->next;
  811.     *node_ptr = node->next;
  812.     deleteNode(node);
  813.     --d->size;
  814.     return ret;
  815. }
  817. template <class Key, class T>
  818. Q_INLINE_TEMPLATE void QHash<Key, T>::reserve(int asize)
  819. {
  820.     detach();
  821.     d->rehash(-qMax(asize, 1));
  822. }
  824. template <class Key, class T>
  825. Q_INLINE_TEMPLATE typename QHash<Key, T>::const_iterator QHash<Key, T>::find(const Key &akey) const
  826. {
  827.     return const_iterator(*findNode(akey));
  828. }
  830. template <class Key, class T>
  831. Q_INLINE_TEMPLATE typename QHash<Key, T>::const_iterator QHash<Key, T>::constFind(const Key &akey) const
  832. {
  833.     return const_iterator(*findNode(akey));
  834. }
  836. template <class Key, class T>
  837. Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::find(const Key &akey)
  838. {
  839.     detach();
  840.     return iterator(*findNode(akey));
  841. }
  843. template <class Key, class T>
  844. Q_INLINE_TEMPLATE bool QHash<Key, T>::contains(const Key &akey) const
  845. {
  846.     return *findNode(akey) != e;
  847. }
  849. template <class Key, class T>
  850. Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::Node **QHash<Key, T>::findNode(const Key &akey,
  851.                                                                             uint *ahp) const
  852. {
  853.     Node **node;
  854.     uint h = qHash(akey);
  856.     if (d->numBuckets) {
  857.         node = reinterpret_cast<Node **>(&d->buckets[h % d->numBuckets]);
  858.         Q_ASSERT(*node == e || (*node)->next);
  859.         while (*node != e && !(*node)->same_key(h, akey))
  860.             node = &(*node)->next;
  861.     } else {
  862.         node = const_cast<Node **>(reinterpret_cast<const Node * const *>(&e));
  863.     }
  864.     if (ahp)
  865.         *ahp = h;
  866.     return node;
  867. }
  869. template <class Key, class T>
  870. Q_OUTOFLINE_TEMPLATE bool QHash<Key, T>::operator==(const QHash<Key, T> &other) const
  871. {
  872.     if (size() != other.size())
  873.         return false;
  874.     if (d == other.d)
  875.         return true;
  877.     const_iterator it = begin();
  879.     while (it != end()) {
  880.         const Key &akey = it.key();
  882.         const_iterator it2 = other.find(akey);
  883.         do {
  884.             if (it2 == other.end() || !(it2.key() == akey))
  885.                 return false;
  886.             if (!QTypeInfo<T>::isDummy && !(it.value() == it2.value()))
  887.                 return false;
  888.             ++it;
  889.             ++it2;
  890.         } while (it != end() && it.key() == akey);
  891.     }
  892.     return true;
  893. }
  895. template <class Key, class T>
  896. class QMultiHash : public QHash<Key, T>
  897. {
  898. public:
  899.     QMultiHash() {}
  900.     QMultiHash(const QHash<Key, T> &other) : QHash<Key, T>(other) {}
  902.     inline typename QHash<Key, T>::iterator replace(const Key &key, const T &value)
  903.     { return QHash<Key, T>::insert(key, value); }
  905.     inline typename QHash<Key, T>::iterator insert(const Key &key, const T &value)
  906.     { return QHash<Key, T>::insertMulti(key, value); }
  908.     inline QMultiHash &operator+=(const QMultiHash &other)
  909.     { unite(other); return *this; }
  910.     inline QMultiHash operator+(const QMultiHash &other) const
  911.     { QMultiHash result = *this; result += other; return result; }
  913. #ifndef Q_NO_USING_KEYWORD
  914.     using QHash<Key, T>::contains;
  915.     using QHash<Key, T>::remove;
  916.     using QHash<Key, T>::count;
  917.     using QHash<Key, T>::find;
  918.     using QHash<Key, T>::constFind;
  919. #else
  920.     inline bool contains(const Key &key) const
  921.     { return QHash<Key, T>::contains(key); }
  922.     inline int remove(const Key &key)
  923.     { return QHash<Key, T>::remove(key); }
  924.     inline int count(const Key &key) const
  925.     { return QHash<Key, T>::count(key); }
  926.     inline int count() const
  927.     { return QHash<Key, T>::count(); }
  928.     inline typename QHash<Key, T>::iterator find(const Key &key)
  929.     { return QHash<Key, T>::find(key); }
  930.     inline typename QHash<Key, T>::const_iterator find(const Key &key) const
  931.     { return QHash<Key, T>::find(key); }
  932.     inline typename QHash<Key, T>::const_iterator constFind(const Key &key) const
  933.     { return QHash<Key, T>::constFind(key); }
  934. #endif
  936.     bool contains(const Key &key, const T &value) const;
  938.     int remove(const Key &key, const T &value);
  940.     int count(const Key &key, const T &value) const;
  942.     typename QHash<Key, T>::iterator find(const Key &key, const T &value) {
  943.         typename QHash<Key, T>::iterator i(find(key));
  944.         typename QHash<Key, T>::iterator end(this->end());
  945.         while (i != end && i.key() == key) {
  946.             if (i.value() == value)
  947.                 return i;
  948.             ++i;
  949.         }
  950.         return end;
  951.     }
  952.     typename QHash<Key, T>::const_iterator find(const Key &key, const T &value) const {
  953.         typename QHash<Key, T>::const_iterator i(constFind(key));
  954.         typename QHash<Key, T>::const_iterator end(QHash<Key, T>::constEnd());
  955.         while (i != end && i.key() == key) {
  956.             if (i.value() == value)
  957.                 return i;
  958.             ++i;
  959.         }
  960.         return end;
  961.     }
  962.     typename QHash<Key, T>::const_iterator constFind(const Key &key, const T &value) const
  963.         { return find(key, value); }
  964. private:
  965.     T &operator[](const Key &key);
  966.     const T operator[](const Key &key) const;
  967. };
  969. template <class Key, class T>
  970. Q_INLINE_TEMPLATE bool QMultiHash<Key, T>::contains(const Key &key, const T &value) const
  971. {
  972.     return constFind(key, value) != QHash<Key, T>::constEnd();
  973. }
  975. template <class Key, class T>
  976. Q_INLINE_TEMPLATE int QMultiHash<Key, T>::remove(const Key &key, const T &value)
  977. {
  978.     int n = 0;
  979.     typename QHash<Key, T>::iterator i(find(key));
  980.     typename QHash<Key, T>::const_iterator end(QHash<Key, T>::constEnd());
  981.     while (i != end && i.key() == key) {
  982.         if (i.value() == value) {
  983.             i = erase(i);
  984.             ++n;
  985.         } else {
  986.             ++i;
  987.         }
  988.     }
  989.     return n;
  990. }
  992. template <class Key, class T>
  993. Q_INLINE_TEMPLATE int QMultiHash<Key, T>::count(const Key &key, const T &value) const
  994. {
  995.     int n = 0;
  996.     typename QHash<Key, T>::const_iterator i(constFind(key));
  997.     typename QHash<Key, T>::const_iterator end(QHash<Key, T>::constEnd());
  998.     while (i != end && i.key() == key) {
  999.         if (i.value() == value)
  1000.             ++n;
  1001.         ++i;
  1002.     }
  1003.     return n;
  1004. }
  1006. Q_DECLARE_ASSOCIATIVE_ITERATOR(Hash)
  1007. Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Hash)
  1009. QT_END_NAMESPACE
  1011. QT_END_HEADER
  1013. #endif // QHASH_H