qmap.h
上传用户:detong
上传日期:2022-06-22
资源大小:20675k
文件大小:30k
源码类别:

系统编程

开发平台:

Unix_Linux

  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. ****************************************************************************/
  37. #ifndef QMAP_H
  38. #define QMAP_H
  39. #include <QtCore/qatomic.h>
  40. #include <QtCore/qiterator.h>
  41. #include <QtCore/qlist.h>
  42. #ifndef QT_NO_STL
  43. #include <map>
  44. #endif
  45. #include <new>
  46. #undef QT_MAP_DEBUG
  47. QT_BEGIN_HEADER
  48. QT_BEGIN_NAMESPACE
  49. QT_MODULE(Core)
  50. struct Q_CORE_EXPORT QMapData
  51. {
  52.     struct Node {
  53.         Node *backward;
  54.         Node *forward[1];
  55.     };
  56.     enum { LastLevel = 11, Sparseness = 3 };
  57.     QMapData *backward;
  58.     QMapData *forward[QMapData::LastLevel + 1];
  59.     QBasicAtomicInt ref;
  60.     int topLevel;
  61.     int size;
  62.     uint randomBits;
  63.     uint insertInOrder : 1;
  64.     uint sharable : 1;
  65.     static QMapData *createData();
  66.     void continueFreeData(int offset);
  67.     Node *node_create(Node *update[], int offset);
  68.     void node_delete(Node *update[], int offset, Node *node);
  69. #ifdef QT_QMAP_DEBUG
  70.     uint adjust_ptr(Node *node);
  71.     void dump();
  72. #endif
  73.     static QMapData shared_null;
  74. };
  75. /*
  76.     QMap uses qMapLessThanKey() to compare keys. The default
  77.     implementation uses operator<(). For pointer types,
  78.     qMapLessThanKey() casts the pointers to integers before it
  79.     compares them, because operator<() is undefined on pointers
  80.     that come from different memory blocks. (In practice, this
  81.     is only a problem when running a program such as
  82.     BoundsChecker.)
  83. */
  84. template <class Key> inline bool qMapLessThanKey(const Key &key1, const Key &key2)
  85. {
  86.     return key1 < key2;
  87. }
  88. #ifndef QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION
  89. template <class Ptr> inline bool qMapLessThanKey(Ptr *key1, Ptr *key2)
  90. {
  91.     Q_ASSERT(sizeof(ulong) == sizeof(Ptr *));
  92.     return reinterpret_cast<ulong>(key1) < reinterpret_cast<ulong>(key2);
  93. }
  94. template <class Ptr> inline bool qMapLessThanKey(const Ptr *key1, const Ptr *key2)
  95. {
  96.     Q_ASSERT(sizeof(ulong) == sizeof(const Ptr *));
  97.     return reinterpret_cast<ulong>(key1) < reinterpret_cast<ulong>(key2);
  98. }
  99. #endif // QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION
  100. template <class Key, class T>
  101. class QMap
  102. {
  103.     struct Node {
  104.         Key key;
  105.         T value;
  106.         QMapData::Node *backward;
  107.         QMapData::Node *forward[1];
  108.     };
  109.     union {
  110.         QMapData *d;
  111.         QMapData::Node *e;
  112.     };
  113.     struct PayloadNode
  114.     {
  115.         Key key;
  116.         T value;
  117.         QMapData::Node *backward;
  118.     };
  119.     static inline int payload() { return sizeof(PayloadNode) - sizeof(QMapData::Node *); }
  120.     static inline Node *concrete(QMapData::Node *node) {
  121.         return reinterpret_cast<Node *>(reinterpret_cast<char *>(node) - payload());
  122.     }
  123. public:
  124.     inline QMap() : d(&QMapData::shared_null) { d->ref.ref(); }
  125.     inline QMap(const QMap<Key, T> &other) : d(other.d)
  126.     { d->ref.ref(); if (!d->sharable) detach(); }
  127.     inline ~QMap() { if (!d) return; if (!d->ref.deref()) freeData(d); }
  128.     QMap<Key, T> &operator=(const QMap<Key, T> &other);
  129. #ifndef QT_NO_STL
  130.     explicit QMap(const typename std::map<Key, T> &other);
  131.     std::map<Key, T> toStdMap() const;
  132. #endif
  133.     bool operator==(const QMap<Key, T> &other) const;
  134.     inline bool operator!=(const QMap<Key, T> &other) const { return !(*this == other); }
  135.     inline int size() const { return d->size; }
  136.     inline bool isEmpty() const { return d->size == 0; }
  137.     inline void detach() { if (d->ref != 1) detach_helper(); }
  138.     inline bool isDetached() const { return d->ref == 1; }
  139.     inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }
  140.     inline void setInsertInOrder(bool ordered) { d->insertInOrder = ordered; }
  141.     void clear();
  142.     int remove(const Key &key);
  143.     T take(const Key &key);
  144.     bool contains(const Key &key) const;
  145.     const Key key(const T &value) const;
  146.     const Key key(const T &value, const Key &defaultKey) const;
  147.     const T value(const Key &key) const;
  148.     const T value(const Key &key, const T &defaultValue) const;
  149.     T &operator[](const Key &key);
  150.     const T operator[](const Key &key) const;
  151.     QList<Key> uniqueKeys() const;
  152.     QList<Key> keys() const;
  153.     QList<Key> keys(const T &value) const;
  154.     QList<T> values() const;
  155.     QList<T> values(const Key &key) const;
  156.     int count(const Key &key) const;
  157.     class const_iterator;
  158.     class iterator
  159.     {
  160.         friend class const_iterator;
  161.         QMapData::Node *i;
  162.     public:
  163.         typedef std::bidirectional_iterator_tag iterator_category;
  164.         typedef ptrdiff_t difference_type;
  165.         typedef T value_type;
  166.         typedef T *pointer;
  167.         typedef T &reference;
  168.         // ### Qt 5: get rid of 'operator Node *'
  169.         inline operator QMapData::Node *() const { return i; }
  170.         inline iterator() : i(0) { }
  171.         inline iterator(QMapData::Node *node) : i(node) { }
  172.         inline const Key &key() const { return concrete(i)->key; }
  173.         inline T &value() const { return concrete(i)->value; }
  174. #ifdef QT3_SUPPORT
  175.         inline QT3_SUPPORT T &data() const { return concrete(i)->value; }
  176. #endif
  177.         inline T &operator*() const { return concrete(i)->value; }
  178.         inline T *operator->() const { return &concrete(i)->value; }
  179.         inline bool operator==(const iterator &o) const { return i == o.i; }
  180.         inline bool operator!=(const iterator &o) const { return i != o.i; }
  181.         inline iterator &operator++() {
  182.             i = i->forward[0];
  183.             return *this;
  184.         }
  185.         inline iterator operator++(int) {
  186.             iterator r = *this;
  187.             i = i->forward[0];
  188.             return r;
  189.         }
  190.         inline iterator &operator--() {
  191.             i = i->backward;
  192.             return *this;
  193.         }
  194.         inline iterator operator--(int) {
  195.             iterator r = *this;
  196.             i = i->backward;
  197.             return r;
  198.         }
  199.         inline iterator operator+(int j) const
  200.         { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
  201.         inline iterator operator-(int j) const { return operator+(-j); }
  202.         inline iterator &operator+=(int j) { return *this = *this + j; }
  203.         inline iterator &operator-=(int j) { return *this = *this - j; }
  204.         // ### Qt 5: not sure this is necessary anymore
  205. #ifdef QT_STRICT_ITERATORS
  206.     private:
  207. #else
  208.     public:
  209. #endif
  210.         inline bool operator==(const const_iterator &o) const
  211.             { return i == o.i; }
  212.         inline bool operator!=(const const_iterator &o) const
  213.             { return i != o.i; }
  214.     private:
  215.         // ### Qt 5: remove
  216.         inline operator bool() const { return false; }
  217.     };
  218.     friend class iterator;
  219.     class const_iterator
  220.     {
  221.         friend class iterator;
  222.         QMapData::Node *i;
  223.     public:
  224.         typedef std::bidirectional_iterator_tag iterator_category;
  225.         typedef ptrdiff_t difference_type;
  226.         typedef T value_type;
  227.         typedef const T *pointer;
  228.         typedef const T &reference;
  229.         // ### Qt 5: get rid of 'operator Node *'
  230.         inline operator QMapData::Node *() const { return i; }
  231.         inline const_iterator() : i(0) { }
  232.         inline const_iterator(QMapData::Node *node) : i(node) { }
  233. #ifdef QT_STRICT_ITERATORS
  234.         explicit inline const_iterator(const iterator &o)
  235. #else
  236.         inline const_iterator(const iterator &o)
  237. #endif
  238.         { i = o.i; }
  239.         inline const Key &key() const { return concrete(i)->key; }
  240.         inline const T &value() const { return concrete(i)->value; }
  241. #ifdef QT3_SUPPORT
  242.         inline QT3_SUPPORT const T &data() const { return concrete(i)->value; }
  243. #endif
  244.         inline const T &operator*() const { return concrete(i)->value; }
  245.         inline const T *operator->() const { return &concrete(i)->value; }
  246.         inline bool operator==(const const_iterator &o) const { return i == o.i; }
  247.         inline bool operator!=(const const_iterator &o) const { return i != o.i; }
  248.         inline const_iterator &operator++() {
  249.             i = i->forward[0];
  250.             return *this;
  251.         }
  252.         inline const_iterator operator++(int) {
  253.             const_iterator r = *this;
  254.             i = i->forward[0];
  255.             return r;
  256.         }
  257.         inline const_iterator &operator--() {
  258.             i = i->backward;
  259.             return *this;
  260.         }
  261.         inline const_iterator operator--(int) {
  262.             const_iterator r = *this;
  263.             i = i->backward;
  264.             return r;
  265.         }
  266.         inline const_iterator operator+(int j) const
  267.         { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
  268.         inline const_iterator operator-(int j) const { return operator+(-j); }
  269.         inline const_iterator &operator+=(int j) { return *this = *this + j; }
  270.         inline const_iterator &operator-=(int j) { return *this = *this - j; }
  271.         // ### Qt 5: not sure this is necessary anymore
  272. #ifdef QT_STRICT_ITERATORS
  273.     private:
  274.         inline bool operator==(const iterator &o) { return operator==(const_iterator(o)); }
  275.         inline bool operator!=(const iterator &o) { return operator!=(const_iterator(o)); }
  276. #endif
  277.     private:
  278.         // ### Qt 5: remove
  279.         inline operator bool() const { return false; }
  280.     };
  281.     friend class const_iterator;
  282.     // STL style
  283.     inline iterator begin() { detach(); return iterator(e->forward[0]); }
  284.     inline const_iterator begin() const { return const_iterator(e->forward[0]); }
  285.     inline const_iterator constBegin() const { return const_iterator(e->forward[0]); }
  286.     inline iterator end() {
  287.         detach();
  288.         return iterator(e);
  289.     }
  290.     inline const_iterator end() const { return const_iterator(e); }
  291.     inline const_iterator constEnd() const { return const_iterator(e); }
  292.     iterator erase(iterator it);
  293. #ifdef QT3_SUPPORT
  294.     inline QT3_SUPPORT iterator remove(iterator it) { return erase(it); }
  295.     inline QT3_SUPPORT void erase(const Key &aKey) { remove(aKey); }
  296. #endif
  297.     // more Qt
  298.     typedef iterator Iterator;
  299.     typedef const_iterator ConstIterator;
  300.     inline int count() const { return d->size; }
  301.     iterator find(const Key &key);
  302.     const_iterator find(const Key &key) const;
  303.     const_iterator constFind(const Key &key) const;
  304.     iterator lowerBound(const Key &key);
  305.     const_iterator lowerBound(const Key &key) const;
  306.     iterator upperBound(const Key &key);
  307.     const_iterator upperBound(const Key &key) const;
  308.     iterator insert(const Key &key, const T &value);
  309. #ifdef QT3_SUPPORT
  310.     QT3_SUPPORT iterator insert(const Key &key, const T &value, bool overwrite);
  311. #endif
  312.     iterator insertMulti(const Key &key, const T &value);
  313. #ifdef QT3_SUPPORT
  314.     inline QT3_SUPPORT iterator replace(const Key &aKey, const T &aValue) { return insert(aKey, aValue); }
  315. #endif
  316.     QMap<Key, T> &unite(const QMap<Key, T> &other);
  317.     // STL compatibility
  318.     typedef Key key_type;
  319.     typedef T mapped_type;
  320.     typedef ptrdiff_t difference_type;
  321.     typedef int size_type;
  322.     inline bool empty() const { return isEmpty(); }
  323. #ifdef QT_QMAP_DEBUG
  324.     inline void dump() const { d->dump(); }
  325. #endif
  326. private:
  327.     void detach_helper();
  328.     void freeData(QMapData *d);
  329.     QMapData::Node *findNode(const Key &key) const;
  330.     QMapData::Node *mutableFindNode(QMapData::Node *update[], const Key &key) const;
  331.     QMapData::Node *node_create(QMapData *d, QMapData::Node *update[], const Key &key,
  332.                                 const T &value);
  333. };
  334. template <class Key, class T>
  335. Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::operator=(const QMap<Key, T> &other)
  336. {
  337.     if (d != other.d) {
  338.         other.d->ref.ref();
  339.         if (!d->ref.deref())
  340.             freeData(d);
  341.         d = other.d;
  342.         if (!d->sharable)
  343.             detach_helper();
  344.     }
  345.     return *this;
  346. }
  347. template <class Key, class T>
  348. Q_INLINE_TEMPLATE void QMap<Key, T>::clear()
  349. {
  350.     *this = QMap<Key, T>();
  351. }
  352. template <class Key, class T>
  353. Q_INLINE_TEMPLATE typename QMapData::Node *
  354. QMap<Key, T>::node_create(QMapData *adt, QMapData::Node *aupdate[], const Key &akey, const T &avalue)
  355. {
  356.     QMapData::Node *abstractNode = adt->node_create(aupdate, payload());
  357.     Node *concreteNode = concrete(abstractNode);
  358.     new (&concreteNode->key) Key(akey);
  359.     new (&concreteNode->value) T(avalue);
  360.     return abstractNode;
  361. }
  362. template <class Key, class T>
  363. Q_INLINE_TEMPLATE QMapData::Node *QMap<Key, T>::findNode(const Key &akey) const
  364. {
  365.     QMapData::Node *cur = e;
  366.     QMapData::Node *next = e;
  367.     for (int i = d->topLevel; i >= 0; i--) {
  368.         while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))
  369.             cur = next;
  370.     }
  371.     if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
  372.         return next;
  373.     } else {
  374.         return e;
  375.     }
  376. }
  377. template <class Key, class T>
  378. Q_INLINE_TEMPLATE const T QMap<Key, T>::value(const Key &akey) const
  379. {
  380.     QMapData::Node *node;
  381.     if (d->size == 0 || (node = findNode(akey)) == e) {
  382.         return T();
  383.     } else {
  384.         return concrete(node)->value;
  385.     }
  386. }
  387. template <class Key, class T>
  388. Q_INLINE_TEMPLATE const T QMap<Key, T>::value(const Key &akey, const T &adefaultValue) const
  389. {
  390.     QMapData::Node *node;
  391.     if (d->size == 0 || (node = findNode(akey)) == e) {
  392.         return adefaultValue;
  393.     } else {
  394.         return concrete(node)->value;
  395.     }
  396. }
  397. template <class Key, class T>
  398. Q_INLINE_TEMPLATE const T QMap<Key, T>::operator[](const Key &akey) const
  399. {
  400.     return value(akey);
  401. }
  402. template <class Key, class T>
  403. Q_INLINE_TEMPLATE T &QMap<Key, T>::operator[](const Key &akey)
  404. {
  405.     detach();
  406.     QMapData::Node *update[QMapData::LastLevel + 1];
  407.     QMapData::Node *node = mutableFindNode(update, akey);
  408.     if (node == e)
  409.         node = node_create(d, update, akey, T());
  410.     return concrete(node)->value;
  411. }
  412. template <class Key, class T>
  413. Q_INLINE_TEMPLATE int QMap<Key, T>::count(const Key &akey) const
  414. {
  415.     int cnt = 0;
  416.     QMapData::Node *node = findNode(akey);
  417.     if (node != e) {
  418.         do {
  419.             ++cnt;
  420.             node = node->forward[0];
  421.         } while (node != e && !qMapLessThanKey<Key>(akey, concrete(node)->key));
  422.     }
  423.     return cnt;
  424. }
  425. template <class Key, class T>
  426. Q_INLINE_TEMPLATE bool QMap<Key, T>::contains(const Key &akey) const
  427. {
  428.     return findNode(akey) != e;
  429. }
  430. template <class Key, class T>
  431. Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insert(const Key &akey,
  432.                                                                        const T &avalue)
  433. {
  434.     detach();
  435.     QMapData::Node *update[QMapData::LastLevel + 1];
  436.     QMapData::Node *node = mutableFindNode(update, akey);
  437.     if (node == e) {
  438.         node = node_create(d, update, akey, avalue);
  439.     } else {
  440.         concrete(node)->value = avalue;
  441.     }
  442.     return iterator(node);
  443. }
  444. #ifdef QT3_SUPPORT
  445. template <class Key, class T>
  446. Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insert(const Key &akey,
  447.                                                                        const T &avalue,
  448.                                                                        bool aoverwrite)
  449. {
  450.     detach();
  451.     QMapData::Node *update[QMapData::LastLevel + 1];
  452.     QMapData::Node *node = mutableFindNode(update, akey);
  453.     if (node == e) {
  454.         node = node_create(d, update, akey, avalue);
  455.     } else {
  456.         if (aoverwrite)
  457.             concrete(node)->value = avalue;
  458.     }
  459.     return iterator(node);
  460. }
  461. #endif
  462. template <class Key, class T>
  463. Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const Key &akey,
  464.                                                                             const T &avalue)
  465. {
  466.     detach();
  467.     QMapData::Node *update[QMapData::LastLevel + 1];
  468.     mutableFindNode(update, akey);
  469.     return iterator(node_create(d, update, akey, avalue));
  470. }
  471. template <class Key, class T>
  472. Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::find(const Key &akey) const
  473. {
  474.     return const_iterator(findNode(akey));
  475. }
  476. template <class Key, class T>
  477. Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::constFind(const Key &akey) const
  478. {
  479.     return const_iterator(findNode(akey));
  480. }
  481. template <class Key, class T>
  482. Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::find(const Key &akey)
  483. {
  484.     detach();
  485.     return iterator(findNode(akey));
  486. }
  487. template <class Key, class T>
  488. Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::unite(const QMap<Key, T> &other)
  489. {
  490.     QMap<Key, T> copy(other);
  491.     const_iterator it = copy.constEnd();
  492.     const const_iterator b = copy.constBegin();
  493.     while (it != b) {
  494.         --it;
  495.         insertMulti(it.key(), it.value());
  496.     }
  497.     return *this;
  498. }
  499. template <class Key, class T>
  500. Q_OUTOFLINE_TEMPLATE void QMap<Key, T>::freeData(QMapData *x)
  501. {
  502.     if (QTypeInfo<Key>::isComplex || QTypeInfo<T>::isComplex) {
  503.         QMapData::Node *y = reinterpret_cast<QMapData::Node *>(x);
  504.         QMapData::Node *cur = y;
  505.         QMapData::Node *next = cur->forward[0];
  506.         while (next != y) {
  507.             cur = next;
  508.             next = cur->forward[0];
  509. #if defined(_MSC_VER) && (_MSC_VER >= 1300)
  510. #pragma warning(disable:4189)
  511. #endif
  512.             Node *concreteNode = concrete(cur);
  513.             concreteNode->key.~Key();
  514.             concreteNode->value.~T();
  515. #if defined(_MSC_VER) && (_MSC_VER >= 1300)
  516. #pragma warning(default:4189)
  517. #endif
  518.         }
  519.     }
  520.     x->continueFreeData(payload());
  521. }
  522. template <class Key, class T>
  523. Q_OUTOFLINE_TEMPLATE int QMap<Key, T>::remove(const Key &akey)
  524. {
  525.     detach();
  526.     QMapData::Node *update[QMapData::LastLevel + 1];
  527.     QMapData::Node *cur = e;
  528.     QMapData::Node *next = e;
  529.     int oldSize = d->size;
  530.     for (int i = d->topLevel; i >= 0; i--) {
  531.         while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))
  532.             cur = next;
  533.         update[i] = cur;
  534.     }
  535.     if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
  536.         bool deleteNext = true;
  537.         do {
  538.             cur = next;
  539.             next = cur->forward[0];
  540.             deleteNext = (next != e && !qMapLessThanKey<Key>(concrete(cur)->key, concrete(next)->key));
  541.             concrete(cur)->key.~Key();
  542.             concrete(cur)->value.~T();
  543.             d->node_delete(update, payload(), cur);
  544.         } while (deleteNext);
  545.     }
  546.     return oldSize - d->size;
  547. }
  548. template <class Key, class T>
  549. Q_OUTOFLINE_TEMPLATE T QMap<Key, T>::take(const Key &akey)
  550. {
  551.     detach();
  552.     QMapData::Node *update[QMapData::LastLevel + 1];
  553.     QMapData::Node *cur = e;
  554.     QMapData::Node *next = e;
  555.     for (int i = d->topLevel; i >= 0; i--) {
  556.         while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))
  557.             cur = next;
  558.         update[i] = cur;
  559.     }
  560.     if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
  561.         T t = concrete(next)->value;
  562.         concrete(next)->key.~Key();
  563.         concrete(next)->value.~T();
  564.         d->node_delete(update, payload(), next);
  565.         return t;
  566.     }
  567.     return T();
  568. }
  569. template <class Key, class T>
  570. Q_OUTOFLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::erase(iterator it)
  571. {
  572.     QMapData::Node *update[QMapData::LastLevel + 1];
  573.     QMapData::Node *cur = e;
  574.     QMapData::Node *next = e;
  575.     if (it == iterator(e))
  576.         return it;
  577.     for (int i = d->topLevel; i >= 0; i--) {
  578.         while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, it.key()))
  579.             cur = next;
  580.         update[i] = cur;
  581.     }
  582.     while (next != e) {
  583.         cur = next;
  584.         next = cur->forward[0];
  585.         if (cur == it) {
  586.             concrete(cur)->key.~Key();
  587.             concrete(cur)->value.~T();
  588.             d->node_delete(update, payload(), cur);
  589.             return iterator(next);
  590.         }
  591.         for (int i = 0; i <= d->topLevel; ++i) {
  592.             if (update[i]->forward[i] != cur)
  593.                 break;
  594.             update[i] = cur;
  595.         }
  596.     }
  597.     return end();
  598. }
  599. template <class Key, class T>
  600. Q_OUTOFLINE_TEMPLATE void QMap<Key, T>::detach_helper()
  601. {
  602.     union { QMapData *d; QMapData::Node *e; } x;
  603.     x.d = QMapData::createData();
  604.     if (d->size) {
  605.         x.d->insertInOrder = true;
  606.         QMapData::Node *update[QMapData::LastLevel + 1];
  607.         QMapData::Node *cur = e->forward[0];
  608.         update[0] = x.e;
  609.         while (cur != e) {
  610.             Node *concreteNode = concrete(cur);
  611.             node_create(x.d, update, concreteNode->key, concreteNode->value);
  612.             cur = cur->forward[0];
  613.         }
  614.         x.d->insertInOrder = false;
  615.     }
  616.     if (!d->ref.deref())
  617.         freeData(d);
  618.     d = x.d;
  619. }
  620. template <class Key, class T>
  621. Q_OUTOFLINE_TEMPLATE QMapData::Node *QMap<Key, T>::mutableFindNode(QMapData::Node *aupdate[],
  622.                                                                    const Key &akey) const
  623. {
  624.     QMapData::Node *cur = e;
  625.     QMapData::Node *next = e;
  626.     for (int i = d->topLevel; i >= 0; i--) {
  627.         while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))
  628.             cur = next;
  629.         aupdate[i] = cur;
  630.     }
  631.     if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
  632.         return next;
  633.     } else {
  634.         return e;
  635.     }
  636. }
  637. template <class Key, class T>
  638. Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::uniqueKeys() const
  639. {
  640.     QList<Key> res;
  641.     const_iterator i = begin();
  642.     if (i != end()) {
  643.         for (;;) {
  644.             const Key &aKey = i.key();
  645.             res.append(aKey);
  646.             do {
  647.                 if (++i == end())
  648.                     goto break_out_of_outer_loop;
  649.             } while (!(aKey < i.key()));   // loop while (key == i.key())
  650.         }
  651.     }
  652. break_out_of_outer_loop:
  653.     return res;
  654. }
  655. template <class Key, class T>
  656. Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys() const
  657. {
  658.     QList<Key> res;
  659.     const_iterator i = begin();
  660.     while (i != end()) {
  661.         res.append(i.key());
  662.         ++i;
  663.     }
  664.     return res;
  665. }
  666. template <class Key, class T>
  667. Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys(const T &avalue) const
  668. {
  669.     QList<Key> res;
  670.     const_iterator i = begin();
  671.     while (i != end()) {
  672.         if (i.value() == avalue)
  673.             res.append(i.key());
  674.         ++i;
  675.     }
  676.     return res;
  677. }
  678. template <class Key, class T>
  679. Q_OUTOFLINE_TEMPLATE const Key QMap<Key, T>::key(const T &avalue) const
  680. {
  681.     return key(avalue, Key());
  682. }
  683. template <class Key, class T>
  684. Q_OUTOFLINE_TEMPLATE const Key QMap<Key, T>::key(const T &avalue, const Key &defaultKey) const
  685. {
  686.     const_iterator i = begin();
  687.     while (i != end()) {
  688.         if (i.value() == avalue)
  689.             return i.key();
  690.         ++i;
  691.     }
  692.     return defaultKey;
  693. }
  694. template <class Key, class T>
  695. Q_OUTOFLINE_TEMPLATE QList<T> QMap<Key, T>::values() const
  696. {
  697.     QList<T> res;
  698.     const_iterator i = begin();
  699.     while (i != end()) {
  700.         res.append(i.value());
  701.         ++i;
  702.     }
  703.     return res;
  704. }
  705. template <class Key, class T>
  706. Q_OUTOFLINE_TEMPLATE QList<T> QMap<Key, T>::values(const Key &akey) const
  707. {
  708.     QList<T> res;
  709.     QMapData::Node *node = findNode(akey);
  710.     if (node != e) {
  711.         do {
  712.             res.append(concrete(node)->value);
  713.             node = node->forward[0];
  714.         } while (node != e && !qMapLessThanKey<Key>(akey, concrete(node)->key));
  715.     }
  716.     return res;
  717. }
  718. template <class Key, class T>
  719. Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator
  720. QMap<Key, T>::lowerBound(const Key &akey) const
  721. {
  722.     QMapData::Node *update[QMapData::LastLevel + 1];
  723.     mutableFindNode(update, akey);
  724.     return const_iterator(update[0]->forward[0]);
  725. }
  726. template <class Key, class T>
  727. Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::lowerBound(const Key &akey)
  728. {
  729.     detach();
  730.     return static_cast<QMapData::Node *>(const_cast<const QMap *>(this)->lowerBound(akey));
  731. }
  732. template <class Key, class T>
  733. Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator
  734. QMap<Key, T>::upperBound(const Key &akey) const
  735. {
  736.     QMapData::Node *update[QMapData::LastLevel + 1];
  737.     mutableFindNode(update, akey);
  738.     QMapData::Node *node = update[0]->forward[0];
  739.     while (node != e && !qMapLessThanKey<Key>(akey, concrete(node)->key))
  740.         node = node->forward[0];
  741.     return const_iterator(node);
  742. }
  743. template <class Key, class T>
  744. Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::upperBound(const Key &akey)
  745. {
  746.     detach();
  747.     return static_cast<QMapData::Node *>(const_cast<const QMap *>(this)->upperBound(akey));
  748. }
  749. template <class Key, class T>
  750. Q_OUTOFLINE_TEMPLATE bool QMap<Key, T>::operator==(const QMap<Key, T> &other) const
  751. {
  752.     if (size() != other.size())
  753.         return false;
  754.     if (d == other.d)
  755.         return true;
  756.     const_iterator it1 = begin();
  757.     const_iterator it2 = other.begin();
  758.     while (it1 != end()) {
  759.         if (!(it1.value() == it2.value()) || qMapLessThanKey(it1.key(), it2.key()) || qMapLessThanKey(it2.key(), it1.key()))
  760.             return false;
  761.         ++it2;
  762.         ++it1;
  763.     }
  764.     return true;
  765. }
  766. #ifndef QT_NO_STL
  767. template <class Key, class T>
  768. Q_OUTOFLINE_TEMPLATE QMap<Key, T>::QMap(const std::map<Key, T> &other)
  769. {
  770.     d = QMapData::createData();
  771.     d->insertInOrder = true;
  772.     typename std::map<Key,T>::const_iterator it = other.end();
  773.     while (it != other.begin()) {
  774.         --it;
  775.         insert((*it).first, (*it).second);
  776.     }
  777.     d->insertInOrder = false;
  778. }
  779. template <class Key, class T>
  780. Q_OUTOFLINE_TEMPLATE std::map<Key, T> QMap<Key, T>::toStdMap() const
  781. {
  782.     std::map<Key, T> map;
  783.     const_iterator it = end();
  784.     while (it != begin()) {
  785.         --it;
  786.         map.insert(std::pair<Key, T>(it.key(), it.value()));
  787.     }
  788.     return map;
  789. }
  790. #endif // QT_NO_STL
  791. template <class Key, class T>
  792. class QMultiMap : public QMap<Key, T>
  793. {
  794. public:
  795.     QMultiMap() {}
  796.     QMultiMap(const QMap<Key, T> &other) : QMap<Key, T>(other) {}
  797.     inline typename QMap<Key, T>::iterator replace(const Key &key, const T &value)
  798.     { return QMap<Key, T>::insert(key, value); }
  799.     inline typename QMap<Key, T>::iterator insert(const Key &key, const T &value)
  800.     { return QMap<Key, T>::insertMulti(key, value); }
  801.     inline QMultiMap &operator+=(const QMultiMap &other)
  802.     { unite(other); return *this; }
  803.     inline QMultiMap operator+(const QMultiMap &other) const
  804.     { QMultiMap result = *this; result += other; return result; }
  805. #ifndef Q_NO_USING_KEYWORD
  806.     using QMap<Key, T>::contains;
  807.     using QMap<Key, T>::remove;
  808.     using QMap<Key, T>::count;
  809.     using QMap<Key, T>::find;
  810.     using QMap<Key, T>::constFind;
  811. #else
  812.     inline bool contains(const Key &key) const
  813.     { return QMap<Key, T>::contains(key); }
  814.     inline int remove(const Key &key)
  815.     { return QMap<Key, T>::remove(key); }
  816.     inline int count(const Key &key) const
  817.     { return QMap<Key, T>::count(key); }
  818.     inline int count() const
  819.     { return QMap<Key, T>::count(); }
  820.     inline typename QMap<Key, T>::iterator find(const Key &key)
  821.     { return QMap<Key, T>::find(key); }
  822.     inline typename QMap<Key, T>::const_iterator find(const Key &key) const
  823.     { return QMap<Key, T>::find(key); }
  824.     inline typename QMap<Key, T>::const_iterator constFind(const Key &key) const
  825.     { return QMap<Key, T>::constFind(key); }
  826. #endif
  827.     bool contains(const Key &key, const T &value) const;
  828.     int remove(const Key &key, const T &value);
  829.     int count(const Key &key, const T &value) const;
  830.     typename QMap<Key, T>::iterator find(const Key &key, const T &value) {
  831.         typename QMap<Key, T>::iterator i(find(key));
  832.         typename QMap<Key, T>::iterator end(this->end());
  833.         while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
  834.             if (i.value() == value)
  835.                 return i;
  836.             ++i;
  837.         }
  838.         return end;
  839.     }
  840.     typename QMap<Key, T>::const_iterator find(const Key &key, const T &value) const {
  841.         typename QMap<Key, T>::const_iterator i(constFind(key));
  842.         typename QMap<Key, T>::const_iterator end(QMap<Key, T>::constEnd());
  843.         while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
  844.             if (i.value() == value)
  845.                 return i;
  846.             ++i;
  847.         }
  848.         return end;
  849.     }
  850.     typename QMap<Key, T>::const_iterator constFind(const Key &key, const T &value) const
  851.         { return find(key, value); }
  852. private:
  853.     T &operator[](const Key &key);
  854.     const T operator[](const Key &key) const;
  855. };
  856. template <class Key, class T>
  857. Q_INLINE_TEMPLATE bool QMultiMap<Key, T>::contains(const Key &key, const T &value) const
  858. {
  859.     return constFind(key, value) != QMap<Key, T>::constEnd();
  860. }
  861. template <class Key, class T>
  862. Q_INLINE_TEMPLATE int QMultiMap<Key, T>::remove(const Key &key, const T &value)
  863. {
  864.     int n = 0;
  865.     typename QMap<Key, T>::iterator i(find(key));
  866.     typename QMap<Key, T>::const_iterator end(QMap<Key, T>::constEnd());
  867.     while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
  868.         if (i.value() == value) {
  869.             i = erase(i);
  870.             ++n;
  871.         } else {
  872.             ++i;
  873.         }
  874.     }
  875.     return n;
  876. }
  877. template <class Key, class T>
  878. Q_INLINE_TEMPLATE int QMultiMap<Key, T>::count(const Key &key, const T &value) const
  879. {
  880.     int n = 0;
  881.     typename QMap<Key, T>::const_iterator i(constFind(key));
  882.     typename QMap<Key, T>::const_iterator end(QMap<Key, T>::constEnd());
  883.     while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
  884.         if (i.value() == value)
  885.             ++n;
  886.         ++i;
  887.     }
  888.     return n;
  889. }
  890. Q_DECLARE_ASSOCIATIVE_ITERATOR(Map)
  891. Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Map)
  892. QT_END_NAMESPACE
  893. QT_END_HEADER
  894. #endif // QMAP_H