LCOV - code coverage report
Current view: top level - usr/include/x86_64-linux-gnu/qt5/QtCore - qmap.h (source / functions) Hit Total Coverage
Test: coverage.info Lines: 106 131 80.9 %
Date: 2016-11-29 15:07:43 Functions: 47 53 88.7 %

          Line data    Source code
       1             : /****************************************************************************
       2             : **
       3             : ** Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies).
       4             : ** Contact: http://www.qt-project.org/legal
       5             : **
       6             : ** This file is part of the QtCore module of the Qt Toolkit.
       7             : **
       8             : ** $QT_BEGIN_LICENSE:LGPL$
       9             : ** Commercial License Usage
      10             : ** Licensees holding valid commercial Qt licenses may use this file in
      11             : ** accordance with the commercial license agreement provided with the
      12             : ** Software or, alternatively, in accordance with the terms contained in
      13             : ** a written agreement between you and Digia.  For licensing terms and
      14             : ** conditions see http://qt.digia.com/licensing.  For further information
      15             : ** use the contact form at http://qt.digia.com/contact-us.
      16             : **
      17             : ** GNU Lesser General Public License Usage
      18             : ** Alternatively, this file may be used under the terms of the GNU Lesser
      19             : ** General Public License version 2.1 as published by the Free Software
      20             : ** Foundation and appearing in the file LICENSE.LGPL included in the
      21             : ** packaging of this file.  Please review the following information to
      22             : ** ensure the GNU Lesser General Public License version 2.1 requirements
      23             : ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
      24             : **
      25             : ** In addition, as a special exception, Digia gives you certain additional
      26             : ** rights.  These rights are described in the Digia Qt LGPL Exception
      27             : ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
      28             : **
      29             : ** GNU General Public License Usage
      30             : ** Alternatively, this file may be used under the terms of the GNU
      31             : ** General Public License version 3.0 as published by the Free Software
      32             : ** Foundation and appearing in the file LICENSE.GPL included in the
      33             : ** packaging of this file.  Please review the following information to
      34             : ** ensure the GNU General Public License version 3.0 requirements will be
      35             : ** met: http://www.gnu.org/copyleft/gpl.html.
      36             : **
      37             : **
      38             : ** $QT_END_LICENSE$
      39             : **
      40             : ****************************************************************************/
      41             : 
      42             : #ifndef QMAP_H
      43             : #define QMAP_H
      44             : 
      45             : #include <QtCore/qiterator.h>
      46             : #include <QtCore/qlist.h>
      47             : #include <QtCore/qrefcount.h>
      48             : #include <QtCore/qpair.h>
      49             : 
      50             : #ifdef Q_MAP_DEBUG
      51             : #include <QtCore/qdebug.h>
      52             : #endif
      53             : 
      54             : #include <map>
      55             : #include <new>
      56             : 
      57             : #ifdef Q_COMPILER_INITIALIZER_LISTS
      58             : #include <initializer_list>
      59             : #endif
      60             : 
      61             : QT_BEGIN_NAMESPACE
      62             : 
      63             : /*
      64             :     QMap uses qMapLessThanKey() to compare keys. The default
      65             :     implementation uses operator<(). For pointer types,
      66             :     qMapLessThanKey() casts the pointers to integers before it
      67             :     compares them, because operator<() is undefined on pointers
      68             :     that come from different memory blocks. (In practice, this
      69             :     is only a problem when running a program such as
      70             :     BoundsChecker.)
      71             : */
      72             : 
      73         176 : template <class Key> inline bool qMapLessThanKey(const Key &key1, const Key &key2)
      74             : {
      75         176 :     return key1 < key2;
      76             : }
      77             : 
      78             : template <class Ptr> inline bool qMapLessThanKey(const Ptr *key1, const Ptr *key2)
      79             : {
      80             :     Q_STATIC_ASSERT(sizeof(quintptr) == sizeof(const Ptr *));
      81             :     return quintptr(key1) < quintptr(key2);
      82             : }
      83             : 
      84             : struct QMapDataBase;
      85             : template <class Key, class T> struct QMapData;
      86             : 
      87             : struct Q_CORE_EXPORT QMapNodeBase
      88             : {
      89             :     quintptr p;
      90             :     QMapNodeBase *left;
      91             :     QMapNodeBase *right;
      92             : 
      93             :     enum Color { Red = 0, Black = 1 };
      94             :     enum { Mask = 3 }; // reserve the second bit as well
      95             : 
      96             :     const QMapNodeBase *nextNode() const;
      97             :     QMapNodeBase *nextNode() { return const_cast<QMapNodeBase *>(const_cast<const QMapNodeBase *>(this)->nextNode()); }
      98             :     const QMapNodeBase *previousNode() const;
      99             :     QMapNodeBase *previousNode() { return const_cast<QMapNodeBase *>(const_cast<const QMapNodeBase *>(this)->previousNode()); }
     100             : 
     101           0 :     Color color() const { return Color(p & 1); }
     102           0 :     void setColor(Color c) { if (c == Black) p |= Black; else p &= ~Black; }
     103             :     QMapNodeBase *parent() const { return reinterpret_cast<QMapNodeBase *>(p & ~Mask); }
     104           0 :     void setParent(QMapNodeBase *pp) { p = (p & Mask) | quintptr(pp); }
     105             : };
     106             : 
     107             : template <class Key, class T>
     108             : struct QMapNode : public QMapNodeBase
     109             : {
     110             :     Key key;
     111             :     T value;
     112             : 
     113          69 :     inline QMapNode *leftNode() const { return static_cast<QMapNode *>(left); }
     114          65 :     inline QMapNode *rightNode() const { return static_cast<QMapNode *>(right); }
     115             : 
     116          11 :     inline const QMapNode *nextNode() const { return static_cast<const QMapNode *>(QMapNodeBase::nextNode()); }
     117             :     inline const QMapNode *previousNode() const { return static_cast<const QMapNode *>(QMapNodeBase::previousNode()); }
     118             :     inline QMapNode *nextNode() { return static_cast<QMapNode *>(QMapNodeBase::nextNode()); }
     119             :     inline QMapNode *previousNode() { return static_cast<QMapNode *>(QMapNodeBase::previousNode()); }
     120             : 
     121             :     QMapNode<Key, T> *copy(QMapData<Key, T> *d) const;
     122             : 
     123             :     void destroySubTree();
     124             : 
     125             :     QMapNode<Key, T> *lowerBound(const Key &key);
     126             :     QMapNode<Key, T> *upperBound(const Key &key);
     127             : 
     128             : private:
     129             :     QMapNode() Q_DECL_EQ_DELETE;
     130             :     Q_DISABLE_COPY(QMapNode)
     131             : };
     132             : 
     133             : template <class Key, class T>
     134          54 : inline QMapNode<Key, T> *QMapNode<Key, T>::lowerBound(const Key &akey)
     135             : {
     136          54 :     QMapNode<Key, T> *n = this;
     137          54 :     QMapNode<Key, T> *lastNode = 0;
     138         196 :     while (n) {
     139          88 :         if (!qMapLessThanKey(n->key, akey)) {
     140          60 :             lastNode = n;
     141          60 :             n = n->leftNode();
     142             :         } else {
     143          28 :             n = n->rightNode();
     144             :         }
     145             :     }
     146          54 :     return lastNode;
     147             : }
     148             : 
     149             : template <class Key, class T>
     150             : inline QMapNode<Key, T> *QMapNode<Key, T>::upperBound(const Key &akey)
     151             : {
     152             :     QMapNode<Key, T> *n = this;
     153             :     QMapNode<Key, T> *lastNode = 0;
     154             :     while (n) {
     155             :         if (qMapLessThanKey(akey, n->key)) {
     156             :             lastNode = n;
     157             :             n = n->leftNode();
     158             :         } else {
     159             :             n = n->rightNode();
     160             :         }
     161             :     }
     162             :     return lastNode;
     163             : }
     164             : 
     165             : 
     166             : 
     167             : struct Q_CORE_EXPORT QMapDataBase
     168             : {
     169             :     QtPrivate::RefCount ref;
     170             :     int size;
     171             :     QMapNodeBase header;
     172             :     QMapNodeBase *mostLeftNode;
     173             : 
     174             :     void rotateLeft(QMapNodeBase *x);
     175             :     void rotateRight(QMapNodeBase *x);
     176             :     void rebalance(QMapNodeBase *x);
     177             :     void freeNodeAndRebalance(QMapNodeBase *z);
     178             :     void recalcMostLeftNode();
     179             : 
     180             :     QMapNodeBase *createNode(int size, int alignment, QMapNodeBase *parent, bool left);
     181             :     void freeTree(QMapNodeBase *root, int alignment);
     182             : 
     183             :     static const QMapDataBase shared_null;
     184             : 
     185             :     static QMapDataBase *createData();
     186             :     static void freeData(QMapDataBase *d);
     187             : };
     188             : 
     189             : template <class Key, class T>
     190             : struct QMapData : public QMapDataBase
     191             : {
     192             :     typedef QMapNode<Key, T> Node;
     193             : 
     194         140 :     Node *root() const { return static_cast<Node *>(header.left); }
     195             : 
     196             :     const Node *end() const { return static_cast<const Node *>(&header); }
     197          59 :     Node *end() { return static_cast<Node *>(&header); }
     198             :     const Node *begin() const { if (root()) return static_cast<const Node*>(mostLeftNode); return end(); }
     199           1 :     Node *begin() { if (root()) return static_cast<Node*>(mostLeftNode); return end(); }
     200             : 
     201             :     void deleteNode(Node *z);
     202             :     Node *findNode(const Key &akey) const;
     203             :     void nodeRange(const Key &akey, Node **firstNode, Node **lastNode);
     204             : 
     205          47 :     Node *createNode(const Key &k, const T &v, Node *parent = 0, bool left = false)
     206             :     {
     207             :         Node *n = static_cast<Node *>(QMapDataBase::createNode(sizeof(Node), Q_ALIGNOF(Node),
     208          47 :                                       parent, left));
     209             :         QT_TRY {
     210          47 :             new (&n->key) Key(k);
     211             :             QT_TRY {
     212          47 :                 new (&n->value) T(v);
     213           0 :             } QT_CATCH(...) {
     214             :                 n->key.~Key();
     215           0 :                 QT_RETHROW;
     216             :             }
     217           0 :         } QT_CATCH(...) {
     218           0 :             QMapDataBase::freeNodeAndRebalance(n);
     219           0 :             QT_RETHROW;
     220             :         }
     221          47 :         return n;
     222             :     }
     223             : 
     224           7 :     static QMapData *create() {
     225           7 :         return static_cast<QMapData *>(createData());
     226             :     }
     227             : 
     228           7 :     void destroy() {
     229           7 :         if (root()) {
     230           1 :             root()->destroySubTree();
     231           1 :             freeTree(header.left, Q_ALIGNOF(Node));
     232             :         }
     233           7 :         freeData(this);
     234           7 :     }
     235             : };
     236             : 
     237             : template <class Key, class T>
     238           0 : QMapNode<Key, T> *QMapNode<Key, T>::copy(QMapData<Key, T> *d) const
     239             : {
     240           0 :     QMapNode<Key, T> *n = d->createNode(key, value);
     241           0 :     n->setColor(color());
     242           0 :     if (left) {
     243           0 :         n->left = leftNode()->copy(d);
     244           0 :         n->left->setParent(n);
     245             :     } else {
     246           0 :         n->left = 0;
     247             :     }
     248           0 :     if (right) {
     249           0 :         n->right = rightNode()->copy(d);
     250           0 :         n->right->setParent(n);
     251             :     } else {
     252           0 :         n->right = 0;
     253             :     }
     254           0 :     return n;
     255             : }
     256             : 
     257             : #if defined(Q_CC_MSVC)
     258             : #pragma warning( push )
     259             : #pragma warning( disable : 4127 ) // conditional expression is constant
     260             : #endif
     261             : 
     262             : template <class Key, class T>
     263          11 : void QMapNode<Key, T>::destroySubTree()
     264             : {
     265             :     if (QTypeInfo<Key>::isComplex)
     266             :         key.~Key();
     267             :     if (QTypeInfo<T>::isComplex)
     268          11 :         value.~T();
     269             :     if (QTypeInfo<Key>::isComplex || QTypeInfo<T>::isComplex) {
     270          11 :         if (left)
     271           5 :             leftNode()->destroySubTree();
     272          11 :         if (right)
     273           5 :             rightNode()->destroySubTree();
     274             :     }
     275          11 : }
     276             : 
     277             : #if defined(Q_CC_MSVC)
     278             : #pragma warning( pop )
     279             : #endif
     280             : 
     281             : template <class Key, class T>
     282          36 : void QMapData<Key, T>::deleteNode(QMapNode<Key, T> *z)
     283             : {
     284             :     if (QTypeInfo<Key>::isComplex)
     285             :         z->key.~Key();
     286             :     if (QTypeInfo<T>::isComplex)
     287             :         z->value.~T();
     288          36 :     freeNodeAndRebalance(z);
     289          36 : }
     290             : 
     291             : template <class Key, class T>
     292          84 : QMapNode<Key, T> *QMapData<Key, T>::findNode(const Key &akey) const
     293             : {
     294          84 :     if (Node *r = root()) {
     295          54 :         Node *lb = r->lowerBound(akey);
     296          54 :         if (lb && !qMapLessThanKey(akey, lb->key))
     297          48 :             return lb;
     298             :     }
     299          36 :     return 0;
     300             : }
     301             : 
     302             : 
     303             : template <class Key, class T>
     304             : void QMapData<Key, T>::nodeRange(const Key &akey, QMapNode<Key, T> **firstNode, QMapNode<Key, T> **lastNode)
     305             : {
     306             :     Node *n = root();
     307             :     Node *l = end();
     308             :     while (n) {
     309             :         if (qMapLessThanKey(akey, n->key)) {
     310             :             l = n;
     311             :             n = n->leftNode();
     312             :         } else if (qMapLessThanKey(n->key, akey)) {
     313             :             n = n->rightNode();
     314             :         } else {
     315             :             *firstNode = n->leftNode() ? n->leftNode()->lowerBound(akey) : 0;
     316             :             if (!*firstNode)
     317             :                 *firstNode = n;
     318             :             *lastNode = n->rightNode() ? n->rightNode()->upperBound(akey) : 0;
     319             :             if (!*lastNode)
     320             :                 *lastNode = l;
     321             :             return;
     322             :         }
     323             :     }
     324             :     *firstNode = *lastNode = l;
     325             : }
     326             : 
     327             : 
     328             : template <class Key, class T>
     329             : class QMap
     330             : {
     331             :     typedef QMapNode<Key, T> Node;
     332             : 
     333             :     QMapData<Key, T> *d;
     334             : 
     335             : public:
     336           6 :     inline QMap() : d(static_cast<QMapData<Key, T> *>(const_cast<QMapDataBase *>(&QMapDataBase::shared_null))) { }
     337             : #ifdef Q_COMPILER_INITIALIZER_LISTS
     338           1 :     inline QMap(std::initializer_list<std::pair<Key,T> > list)
     339           1 :         : d(static_cast<QMapData<Key, T> *>(const_cast<QMapDataBase *>(&QMapDataBase::shared_null)))
     340             :     {
     341          12 :         for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it)
     342          11 :             insert(it->first, it->second);
     343           1 :     }
     344             : #endif
     345             :     QMap(const QMap<Key, T> &other);
     346             : 
     347           7 :     inline ~QMap() { if (!d->ref.deref()) d->destroy(); }
     348             : 
     349             :     QMap<Key, T> &operator=(const QMap<Key, T> &other);
     350             : #ifdef Q_COMPILER_RVALUE_REFS
     351             :     inline QMap(QMap<Key, T> &&other)
     352             :         : d(other.d)
     353             :     {
     354             :         other.d = static_cast<QMapData<Key, T> *>(
     355             :                 const_cast<QMapDataBase *>(&QMapDataBase::shared_null));
     356             :     }
     357             : 
     358             :     inline QMap<Key, T> &operator=(QMap<Key, T> &&other)
     359             :     { qSwap(d, other.d); return *this; }
     360             : #endif
     361             :     inline void swap(QMap<Key, T> &other) { qSwap(d, other.d); }
     362             :     explicit QMap(const typename std::map<Key, T> &other);
     363             :     std::map<Key, T> toStdMap() const;
     364             : 
     365             :     bool operator==(const QMap<Key, T> &other) const;
     366             :     inline bool operator!=(const QMap<Key, T> &other) const { return !(*this == other); }
     367             : 
     368           1 :     inline int size() const { return d->size; }
     369             : 
     370             :     inline bool isEmpty() const { return d->size == 0; }
     371             : 
     372          83 :     inline void detach() { if (d->ref.isShared()) detach_helper(); }
     373             :     inline bool isDetached() const { return !d->ref.isShared(); }
     374             : #if QT_SUPPORTS(UNSHARABLE_CONTAINERS)
     375             :     inline void setSharable(bool sharable)
     376             :     {
     377             :         if (sharable == d->ref.isSharable())
     378             :             return;
     379             :         if (!sharable)
     380             :             detach();
     381             :         // Don't call on shared_null
     382             :         d->ref.setSharable(sharable);
     383             :     }
     384             : #endif
     385             :     inline bool isSharedWith(const QMap<Key, T> &other) const { return d == other.d; }
     386             : 
     387             :     void clear();
     388             : 
     389             :     int remove(const Key &key);
     390             :     T take(const Key &key);
     391             : 
     392             :     bool contains(const Key &key) const;
     393             :     const Key key(const T &value, const Key &defaultKey = Key()) const;
     394             :     const T value(const Key &key, const T &defaultValue = T()) const;
     395             :     T &operator[](const Key &key);
     396             :     const T operator[](const Key &key) const;
     397             : 
     398             :     QList<Key> uniqueKeys() const;
     399             :     QList<Key> keys() const;
     400             :     QList<Key> keys(const T &value) const;
     401             :     QList<T> values() const;
     402             :     QList<T> values(const Key &key) const;
     403             :     int count(const Key &key) const;
     404             : 
     405             :     inline const Key &firstKey() const { Q_ASSERT(!isEmpty()); return constBegin().key(); }
     406             :     inline const Key &lastKey() const { Q_ASSERT(!isEmpty()); return (constEnd() - 1).key(); }
     407             : 
     408             :     inline T &first() { Q_ASSERT(!isEmpty()); return *begin(); }
     409             :     inline const T &first() const { Q_ASSERT(!isEmpty()); return *constBegin(); }
     410             :     inline T &last() { Q_ASSERT(!isEmpty()); return *(end() - 1); }
     411             :     inline const T &last() const { Q_ASSERT(!isEmpty()); return *(constEnd() - 1); }
     412             : 
     413             :     class const_iterator;
     414             : 
     415             :     class iterator
     416             :     {
     417             :         friend class const_iterator;
     418             :         Node *i;
     419             : 
     420             :     public:
     421             :         typedef std::bidirectional_iterator_tag iterator_category;
     422             :         typedef qptrdiff difference_type;
     423             :         typedef T value_type;
     424             :         typedef T *pointer;
     425             :         typedef T &reference;
     426             : 
     427             :         inline iterator() : i(0) { }
     428          47 :         inline iterator(Node *node) : i(node) { }
     429             : 
     430             :         inline const Key &key() const { return i->key; }
     431             :         inline T &value() const { return i->value; }
     432             :         inline T &operator*() const { return i->value; }
     433             :         inline T *operator->() const { return &i->value; }
     434             :         inline bool operator==(const iterator &o) const { return i == o.i; }
     435             :         inline bool operator!=(const iterator &o) const { return i != o.i; }
     436             : 
     437             :         inline iterator &operator++() {
     438             :             i = i->nextNode();
     439             :             return *this;
     440             :         }
     441             :         inline iterator operator++(int) {
     442             :             iterator r = *this;
     443             :             i = i->nextNode();
     444             :             return r;
     445             :         }
     446             :         inline iterator &operator--() {
     447             :             i = i->previousNode();
     448             :             return *this;
     449             :         }
     450             :         inline iterator operator--(int) {
     451             :             iterator r = *this;
     452             :             i = i->previousNode();
     453             :             return r;
     454             :         }
     455             :         inline iterator operator+(int j) const
     456             :         { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
     457             :         inline iterator operator-(int j) const { return operator+(-j); }
     458             :         inline iterator &operator+=(int j) { return *this = *this + j; }
     459             :         inline iterator &operator-=(int j) { return *this = *this - j; }
     460             : 
     461             : #ifndef QT_STRICT_ITERATORS
     462             :     public:
     463             :         inline bool operator==(const const_iterator &o) const
     464             :             { return i == o.i; }
     465             :         inline bool operator!=(const const_iterator &o) const
     466             :             { return i != o.i; }
     467             : #endif
     468             :         friend class QMap<Key, T>;
     469             :     };
     470             :     friend class iterator;
     471             : 
     472             :     class const_iterator
     473             :     {
     474             :         friend class iterator;
     475             :         const Node *i;
     476             : 
     477             :     public:
     478             :         typedef std::bidirectional_iterator_tag iterator_category;
     479             :         typedef qptrdiff difference_type;
     480             :         typedef T value_type;
     481             :         typedef const T *pointer;
     482             :         typedef const T &reference;
     483             : 
     484             :         inline const_iterator() : i(0) { }
     485          13 :         inline const_iterator(const Node *node) : i(node) { }
     486             : #ifdef QT_STRICT_ITERATORS
     487             :         explicit inline const_iterator(const iterator &o)
     488             : #else
     489             :         inline const_iterator(const iterator &o)
     490             : #endif
     491             :         { i = o.i; }
     492             : 
     493          11 :         inline const Key &key() const { return i->key; }
     494             :         inline const T &value() const { return i->value; }
     495             :         inline const T &operator*() const { return i->value; }
     496             :         inline const T *operator->() const { return &i->value; }
     497             :         inline bool operator==(const const_iterator &o) const { return i == o.i; }
     498          12 :         inline bool operator!=(const const_iterator &o) const { return i != o.i; }
     499             : 
     500          11 :         inline const_iterator &operator++() {
     501          11 :             i = i->nextNode();
     502          11 :             return *this;
     503             :         }
     504             :         inline const_iterator operator++(int) {
     505             :             const_iterator r = *this;
     506             :             i = i->nextNode();
     507             :             return r;
     508             :         }
     509             :         inline const_iterator &operator--() {
     510             :             i = i->previousNode();
     511             :             return *this;
     512             :         }
     513             :         inline const_iterator operator--(int) {
     514             :             const_iterator r = *this;
     515             :             i = i->previousNode();
     516             :             return r;
     517             :         }
     518             :         inline const_iterator operator+(int j) const
     519             :         { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
     520             :         inline const_iterator operator-(int j) const { return operator+(-j); }
     521             :         inline const_iterator &operator+=(int j) { return *this = *this + j; }
     522             :         inline const_iterator &operator-=(int j) { return *this = *this - j; }
     523             : 
     524             : #ifdef QT_STRICT_ITERATORS
     525             :     private:
     526             :         inline bool operator==(const iterator &o) const { return operator==(const_iterator(o)); }
     527             :         inline bool operator!=(const iterator &o) const { return operator!=(const_iterator(o)); }
     528             : #endif
     529             :         friend class QMap<Key, T>;
     530             :     };
     531             :     friend class const_iterator;
     532             : 
     533             :     // STL style
     534             :     inline iterator begin() { detach(); return iterator(d->begin()); }
     535           1 :     inline const_iterator begin() const { return const_iterator(d->begin()); }
     536             :     inline const_iterator constBegin() const { return const_iterator(d->begin()); }
     537             :     inline const_iterator cbegin() const { return const_iterator(d->begin()); }
     538             :     inline iterator end() { detach(); return iterator(d->end()); }
     539          12 :     inline const_iterator end() const { return const_iterator(d->end()); }
     540             :     inline const_iterator constEnd() const { return const_iterator(d->end()); }
     541             :     inline const_iterator cend() const { return const_iterator(d->end()); }
     542             :     iterator erase(iterator it);
     543             : 
     544             :     // more Qt
     545             :     typedef iterator Iterator;
     546             :     typedef const_iterator ConstIterator;
     547             :     inline int count() const { return d->size; }
     548             :     iterator find(const Key &key);
     549             :     const_iterator find(const Key &key) const;
     550             :     const_iterator constFind(const Key &key) const;
     551             :     iterator lowerBound(const Key &key);
     552             :     const_iterator lowerBound(const Key &key) const;
     553             :     iterator upperBound(const Key &key);
     554             :     const_iterator upperBound(const Key &key) const;
     555             :     iterator insert(const Key &key, const T &value);
     556             :     iterator insert(const_iterator pos, const Key &key, const T &value);
     557             :     iterator insertMulti(const Key &key, const T &value);
     558             :     iterator insertMulti(const_iterator pos, const Key &akey, const T &avalue);
     559             :     QMap<Key, T> &unite(const QMap<Key, T> &other);
     560             : 
     561             :     // STL compatibility
     562             :     typedef Key key_type;
     563             :     typedef T mapped_type;
     564             :     typedef qptrdiff difference_type;
     565             :     typedef int size_type;
     566             :     inline bool empty() const { return isEmpty(); }
     567             :     QPair<iterator, iterator> equal_range(const Key &akey);
     568             : 
     569             : #ifdef Q_MAP_DEBUG
     570             :     void dump() const;
     571             : #endif
     572             : 
     573             : private:
     574             :     void detach_helper();
     575             :     bool isValidIterator(const const_iterator &ci) const
     576             :     {
     577             : #if defined(QT_DEBUG) && !defined(Q_MAP_NO_ITERATOR_DEBUG)
     578             :         const QMapNodeBase *n = ci.i;
     579             :         while (n->parent())
     580             :             n = n->parent();
     581             :         return n->left == d->root();
     582             : #else
     583             :         Q_UNUSED(ci);
     584             :         return true;
     585             : #endif
     586             :     }
     587             : };
     588             : 
     589             : template <class Key, class T>
     590             : inline QMap<Key, T>::QMap(const QMap<Key, T> &other)
     591             : {
     592             :     if (other.d->ref.ref()) {
     593             :         d = other.d;
     594             :     } else {
     595             :         d = QMapData<Key, T>::create();
     596             :         if (other.d->header.left) {
     597             :             d->header.left = static_cast<Node *>(other.d->header.left)->copy(d);
     598             :             d->header.left->setParent(&d->header);
     599             :             d->recalcMostLeftNode();
     600             :         }
     601             :     }
     602             : }
     603             : 
     604             : template <class Key, class T>
     605             : Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::operator=(const QMap<Key, T> &other)
     606             : {
     607             :     if (d != other.d) {
     608             :         QMap<Key, T> tmp(other);
     609             :         tmp.swap(*this);
     610             :     }
     611             :     return *this;
     612             : }
     613             : 
     614             : template <class Key, class T>
     615             : Q_INLINE_TEMPLATE void QMap<Key, T>::clear()
     616             : {
     617             :     *this = QMap<Key, T>();
     618             : }
     619             : 
     620             : 
     621             : template <class Key, class T>
     622          12 : Q_INLINE_TEMPLATE const T QMap<Key, T>::value(const Key &akey, const T &adefaultValue) const
     623             : {
     624          12 :     Node *n = d->findNode(akey);
     625          12 :     return n ? n->value : adefaultValue;
     626             : }
     627             : 
     628             : template <class Key, class T>
     629             : Q_INLINE_TEMPLATE const T QMap<Key, T>::operator[](const Key &akey) const
     630             : {
     631             :     return value(akey);
     632             : }
     633             : 
     634             : template <class Key, class T>
     635             : Q_INLINE_TEMPLATE T &QMap<Key, T>::operator[](const Key &akey)
     636             : {
     637             :     detach();
     638             :     Node *n = d->findNode(akey);
     639             :     if (!n)
     640             :         return *insert(akey, T());
     641             :     return n->value;
     642             : }
     643             : 
     644             : template <class Key, class T>
     645             : Q_INLINE_TEMPLATE int QMap<Key, T>::count(const Key &akey) const
     646             : {
     647             :     Node *firstNode;
     648             :     Node *lastNode;
     649             :     d->nodeRange(akey, &firstNode, &lastNode);
     650             : 
     651             :     const_iterator ci_first(firstNode);
     652             :     const const_iterator ci_last(lastNode);
     653             :     int cnt = 0;
     654             :     while (ci_first != ci_last) {
     655             :         ++cnt;
     656             :         ++ci_first;
     657             :     }
     658             :     return cnt;
     659             : }
     660             : 
     661             : template <class Key, class T>
     662             : Q_INLINE_TEMPLATE bool QMap<Key, T>::contains(const Key &akey) const
     663             : {
     664             :     return d->findNode(akey) != 0;
     665             : }
     666             : 
     667             : template <class Key, class T>
     668          47 : Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insert(const Key &akey, const T &avalue)
     669             : {
     670          47 :     detach();
     671          47 :     Node *n = d->root();
     672          47 :     Node *y = d->end();
     673          47 :     Node *lastNode = 0;
     674          47 :     bool  left = true;
     675         130 :     while (n) {
     676          36 :         y = n;
     677          36 :         if (!qMapLessThanKey(n->key, akey)) {
     678           4 :             lastNode = n;
     679           4 :             left = true;
     680           4 :             n = n->leftNode();
     681             :         } else {
     682          32 :             left = false;
     683          32 :             n = n->rightNode();
     684             :         }
     685             :     }
     686          47 :     if (lastNode && !qMapLessThanKey(akey, lastNode->key)) {
     687           0 :         lastNode->value = avalue;
     688           0 :         return iterator(lastNode);
     689             :     }
     690          47 :     Node *z = d->createNode(akey, avalue, y, left);
     691          47 :     return iterator(z);
     692             : }
     693             : 
     694             : template <class Key, class T>
     695             : typename QMap<Key, T>::iterator QMap<Key, T>::insert(const_iterator pos, const Key &akey, const T &avalue)
     696             : {
     697             :     if (d->ref.isShared())
     698             :         return this->insert(akey, avalue);
     699             : 
     700             :     Q_ASSERT_X(isValidIterator(pos), "QMap::insert", "The specified const_iterator argument 'it' is invalid");
     701             : 
     702             :     if (pos == constEnd()) {
     703             :         // Hint is that the Node is larger than (or equal to) the largest value.
     704             :         Node *n = static_cast<Node *>(pos.i->left);
     705             :         if (n) {
     706             :             while (n->right)
     707             :                 n = static_cast<Node *>(n->right);
     708             : 
     709             :             if (!qMapLessThanKey(n->key, akey))
     710             :                 return this->insert(akey, avalue); // ignore hint
     711             :             // This can be optimized by checking equal too.
     712             :             // we can overwrite if previous node key is strictly smaller
     713             :             // (or there is no previous node)
     714             : 
     715             :             Node *z = d->createNode(akey, avalue, n, false); // insert right most
     716             :             return iterator(z);
     717             :         }
     718             :         return this->insert(akey, avalue);
     719             :     } else {
     720             :         // Hint indicates that the node should be less (or equal to) the hint given
     721             :         // but larger than the previous value.
     722             :         Node *next = const_cast<Node*>(pos.i);
     723             :         if (qMapLessThanKey(next->key, akey))
     724             :             return this->insert(akey, avalue); // ignore hint
     725             : 
     726             :         if (pos == constBegin()) {
     727             :             // There is no previous value
     728             :             // Maybe overwrite left most value
     729             :             if (!qMapLessThanKey(akey, next->key)) {
     730             :                 next->value = avalue; // overwrite current iterator
     731             :                 return iterator(next);
     732             :             }
     733             :             // insert left most.
     734             :             Node *z = d->createNode(akey, avalue, begin().i, true);
     735             :             return iterator(z);
     736             :         } else {
     737             :             Node *prev = const_cast<Node*>(pos.i->previousNode());
     738             :             if (!qMapLessThanKey(prev->key, akey)) {
     739             :                 return this->insert(akey, avalue); // ignore hint
     740             :             }
     741             :             // Hint is ok
     742             :             if (!qMapLessThanKey(akey, next->key)) {
     743             :                 next->value = avalue; // overwrite current iterator
     744             :                 return iterator(next);
     745             :             }
     746             : 
     747             :             // we need to insert (not overwrite)
     748             :             if (prev->right == 0) {
     749             :                 Node *z = d->createNode(akey, avalue, prev, false);
     750             :                 return iterator(z);
     751             :             }
     752             :             if (next->left == 0) {
     753             :                 Node *z = d->createNode(akey, avalue, next, true);
     754             :                 return iterator(z);
     755             :             }
     756             :             Q_ASSERT(false); // We should have prev->right == 0 or next->left == 0.
     757             :             return this->insert(akey, avalue);
     758             :         }
     759             :     }
     760             : }
     761             : 
     762             : template <class Key, class T>
     763             : Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const Key &akey,
     764             :                                                                             const T &avalue)
     765             : {
     766             :     detach();
     767             :     Node* y = d->end();
     768             :     Node* x = static_cast<Node *>(d->root());
     769             :     bool left = true;
     770             :     while (x != 0) {
     771             :         left = !qMapLessThanKey(x->key, akey);
     772             :         y = x;
     773             :         x = left ? x->leftNode() : x->rightNode();
     774             :     }
     775             :     Node *z = d->createNode(akey, avalue, y, left);
     776             :     return iterator(z);
     777             : }
     778             : 
     779             : template <class Key, class T>
     780             : typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const_iterator pos, const Key &akey, const T &avalue)
     781             : {
     782             :     if (d->ref.isShared())
     783             :         return this->insertMulti(akey, avalue);
     784             : 
     785             :     Q_ASSERT_X(isValidIterator(pos), "QMap::insertMulti", "The specified const_iterator argument 'pos' is invalid");
     786             : 
     787             :     if (pos == constEnd()) {
     788             :         // Hint is that the Node is larger than (or equal to) the largest value.
     789             :         Node *n = static_cast<Node *>(pos.i->left);
     790             :         if (n) {
     791             :             while (n->right)
     792             :                 n = static_cast<Node *>(n->right);
     793             : 
     794             :             if (!qMapLessThanKey(n->key, akey))
     795             :                 return this->insertMulti(akey, avalue); // ignore hint
     796             :             Node *z = d->createNode(akey, avalue, n, false); // insert right most
     797             :             return iterator(z);
     798             :         }
     799             :         return this->insertMulti(akey, avalue);
     800             :     } else {
     801             :         // Hint indicates that the node should be less (or equal to) the hint given
     802             :         // but larger than the previous value.
     803             :         Node *next = const_cast<Node*>(pos.i);
     804             :         if (qMapLessThanKey(next->key, akey))
     805             :             return this->insertMulti(akey, avalue); // ignore hint
     806             : 
     807             :         if (pos == constBegin()) {
     808             :             // There is no previous value (insert left most)
     809             :             Node *z = d->createNode(akey, avalue, begin().i, true);
     810             :             return iterator(z);
     811             :         } else {
     812             :             Node *prev = const_cast<Node*>(pos.i->previousNode());
     813             :             if (!qMapLessThanKey(prev->key, akey))
     814             :                 return this->insertMulti(akey, avalue); // ignore hint
     815             : 
     816             :             // Hint is ok - do insert
     817             :             if (prev->right == 0) {
     818             :                 Node *z = d->createNode(akey, avalue, prev, false);
     819             :                 return iterator(z);
     820             :             }
     821             :             if (next->left == 0) {
     822             :                 Node *z = d->createNode(akey, avalue, next, true);
     823             :                 return iterator(z);
     824             :             }
     825             :             Q_ASSERT(false); // We should have prev->right == 0 or next->left == 0.
     826             :             return this->insertMulti(akey, avalue);
     827             :         }
     828             :     }
     829             : }
     830             : 
     831             : 
     832             : template <class Key, class T>
     833             : Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::constFind(const Key &akey) const
     834             : {
     835             :     Node *n = d->findNode(akey);
     836             :     return const_iterator(n ? n : d->end());
     837             : }
     838             : 
     839             : template <class Key, class T>
     840             : Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::find(const Key &akey) const
     841             : {
     842             :     return constFind(akey);
     843             : }
     844             : 
     845             : template <class Key, class T>
     846             : Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::find(const Key &akey)
     847             : {
     848             :     detach();
     849             :     Node *n = d->findNode(akey);
     850             :     return iterator(n ? n : d->end());
     851             : }
     852             : 
     853             : template <class Key, class T>
     854             : Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::unite(const QMap<Key, T> &other)
     855             : {
     856             :     QMap<Key, T> copy(other);
     857             :     const_iterator it = copy.constEnd();
     858             :     const const_iterator b = copy.constBegin();
     859             :     while (it != b) {
     860             :         --it;
     861             :         insertMulti(it.key(), it.value());
     862             :     }
     863             :     return *this;
     864             : }
     865             : 
     866             : template <class Key, class T>
     867             : QPair<typename QMap<Key, T>::iterator, typename QMap<Key, T>::iterator> QMap<Key, T>::equal_range(const Key &akey)
     868             : {
     869             :     detach();
     870             :     Node *firstNode, *lastNode;
     871             :     d->nodeRange(akey, &firstNode, &lastNode);
     872             :     return QPair<iterator, iterator>(iterator(firstNode), iterator(lastNode));
     873             : }
     874             : 
     875             : #ifdef Q_MAP_DEBUG
     876             : template <class Key, class T>
     877             : void QMap<Key, T>::dump() const
     878             : {
     879             :     const_iterator it = begin();
     880             :     qDebug() << "map dump:";
     881             :     while (it != end()) {
     882             :         const QMapNodeBase *n = it.i;
     883             :         int depth = 0;
     884             :         while (n && n != d->root()) {
     885             :             ++depth;
     886             :             n = n->parent();
     887             :         }
     888             :         QByteArray space(4*depth, ' ');
     889             :         qDebug() << space << (it.i->color() == Node::Red ? "Red  " : "Black") << it.i << it.i->left << it.i->right
     890             :                  << it.key() << it.value();
     891             :         ++it;
     892             :     }
     893             :     qDebug() << "---------";
     894             : }
     895             : #endif
     896             : 
     897             : template <class Key, class T>
     898          36 : Q_OUTOFLINE_TEMPLATE int QMap<Key, T>::remove(const Key &akey)
     899             : {
     900          36 :     detach();
     901          36 :     int n = 0;
     902          72 :     while (Node *node = d->findNode(akey)) {
     903          36 :         d->deleteNode(node);
     904          36 :         ++n;
     905             :     }
     906          36 :     return n;
     907             : }
     908             : 
     909             : template <class Key, class T>
     910             : Q_OUTOFLINE_TEMPLATE T QMap<Key, T>::take(const Key &akey)
     911             : {
     912             :     detach();
     913             : 
     914             :     Node *node = d->findNode(akey);
     915             :     if (node) {
     916             :         T t = node->value;
     917             :         d->deleteNode(node);
     918             :         return t;
     919             :     }
     920             :     return T();
     921             : }
     922             : 
     923             : template <class Key, class T>
     924             : Q_OUTOFLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::erase(iterator it)
     925             : {
     926             :     if (it == iterator(d->end()))
     927             :         return it;
     928             : 
     929             :     Q_ASSERT_X(isValidIterator(const_iterator(it)), "QMap::erase", "The specified iterator argument 'it' is invalid");
     930             : 
     931             :     if (d->ref.isShared()) {
     932             :         const_iterator oldBegin = constBegin();
     933             :         const_iterator old = const_iterator(it);
     934             :         int backStepsWithSameKey = 0;
     935             : 
     936             :         while (old != oldBegin) {
     937             :             --old;
     938             :             if (qMapLessThanKey(old.key(), it.key()))
     939             :                 break;
     940             :             ++backStepsWithSameKey;
     941             :         }
     942             : 
     943             :         it = find(old.key()); // ensures detach
     944             :         Q_ASSERT_X(it != iterator(d->end()), "QMap::erase", "Unable to locate same key in erase after detach.");
     945             : 
     946             :         while (backStepsWithSameKey > 0) {
     947             :             ++it;
     948             :             --backStepsWithSameKey;
     949             :         }
     950             :     }
     951             : 
     952             :     Node *n = it.i;
     953             :     ++it;
     954             :     d->deleteNode(n);
     955             :     return it;
     956             : }
     957             : 
     958             : template <class Key, class T>
     959           7 : Q_OUTOFLINE_TEMPLATE void QMap<Key, T>::detach_helper()
     960             : {
     961           7 :     QMapData<Key, T> *x = QMapData<Key, T>::create();
     962           7 :     if (d->header.left) {
     963           0 :         x->header.left = static_cast<Node *>(d->header.left)->copy(x);
     964           0 :         x->header.left->setParent(&x->header);
     965             :     }
     966           7 :     if (!d->ref.deref())
     967           0 :         d->destroy();
     968           7 :     d = x;
     969           7 :     d->recalcMostLeftNode();
     970           7 : }
     971             : 
     972             : template <class Key, class T>
     973             : Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::uniqueKeys() const
     974             : {
     975             :     QList<Key> res;
     976             :     res.reserve(size()); // May be too much, but assume short lifetime
     977             :     const_iterator i = begin();
     978             :     if (i != end()) {
     979             :         for (;;) {
     980             :             const Key &aKey = i.key();
     981             :             res.append(aKey);
     982             :             do {
     983             :                 if (++i == end())
     984             :                     goto break_out_of_outer_loop;
     985             :             } while (!qMapLessThanKey(aKey, i.key()));   // loop while (key == i.key())
     986             :         }
     987             :     }
     988             : break_out_of_outer_loop:
     989             :     return res;
     990             : }
     991             : 
     992             : template <class Key, class T>
     993           1 : Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys() const
     994             : {
     995           1 :     QList<Key> res;
     996           1 :     res.reserve(size());
     997           1 :     const_iterator i = begin();
     998          13 :     while (i != end()) {
     999          11 :         res.append(i.key());
    1000          11 :         ++i;
    1001             :     }
    1002           1 :     return res;
    1003             : }
    1004             : 
    1005             : template <class Key, class T>
    1006             : Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys(const T &avalue) const
    1007             : {
    1008             :     QList<Key> res;
    1009             :     const_iterator i = begin();
    1010             :     while (i != end()) {
    1011             :         if (i.value() == avalue)
    1012             :             res.append(i.key());
    1013             :         ++i;
    1014             :     }
    1015             :     return res;
    1016             : }
    1017             : 
    1018             : template <class Key, class T>
    1019             : Q_OUTOFLINE_TEMPLATE const Key QMap<Key, T>::key(const T &avalue, const Key &defaultKey) const
    1020             : {
    1021             :     const_iterator i = begin();
    1022             :     while (i != end()) {
    1023             :         if (i.value() == avalue)
    1024             :             return i.key();
    1025             :         ++i;
    1026             :     }
    1027             : 
    1028             :     return defaultKey;
    1029             : }
    1030             : 
    1031             : template <class Key, class T>
    1032             : Q_OUTOFLINE_TEMPLATE QList<T> QMap<Key, T>::values() const
    1033             : {
    1034             :     QList<T> res;
    1035             :     res.reserve(size());
    1036             :     const_iterator i = begin();
    1037             :     while (i != end()) {
    1038             :         res.append(i.value());
    1039             :         ++i;
    1040             :     }
    1041             :     return res;
    1042             : }
    1043             : 
    1044             : template <class Key, class T>
    1045             : Q_OUTOFLINE_TEMPLATE QList<T> QMap<Key, T>::values(const Key &akey) const
    1046             : {
    1047             :     QList<T> res;
    1048             :     Node *n = d->findNode(akey);
    1049             :     if (n) {
    1050             :         const_iterator it(n);
    1051             :         do {
    1052             :             res.append(*it);
    1053             :             ++it;
    1054             :         } while (it != constEnd() && !qMapLessThanKey<Key>(akey, it.key()));
    1055             :     }
    1056             :     return res;
    1057             : }
    1058             : 
    1059             : template <class Key, class T>
    1060             : Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::lowerBound(const Key &akey) const
    1061             : {
    1062             :     Node *lb = d->root() ? d->root()->lowerBound(akey) : 0;
    1063             :     if (!lb)
    1064             :         lb = d->end();
    1065             :     return const_iterator(lb);
    1066             : }
    1067             : 
    1068             : template <class Key, class T>
    1069             : Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::lowerBound(const Key &akey)
    1070             : {
    1071             :     detach();
    1072             :     Node *lb = d->root() ? d->root()->lowerBound(akey) : 0;
    1073             :     if (!lb)
    1074             :         lb = d->end();
    1075             :     return iterator(lb);
    1076             : }
    1077             : 
    1078             : template <class Key, class T>
    1079             : Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator
    1080             : QMap<Key, T>::upperBound(const Key &akey) const
    1081             : {
    1082             :     Node *ub = d->root() ? d->root()->upperBound(akey) : 0;
    1083             :     if (!ub)
    1084             :         ub = d->end();
    1085             :     return const_iterator(ub);
    1086             : }
    1087             : 
    1088             : template <class Key, class T>
    1089             : Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::upperBound(const Key &akey)
    1090             : {
    1091             :     detach();
    1092             :     Node *ub = d->root() ? d->root()->upperBound(akey) : 0;
    1093             :     if (!ub)
    1094             :         ub = d->end();
    1095             :     return iterator(ub);
    1096             : }
    1097             : 
    1098             : template <class Key, class T>
    1099             : Q_OUTOFLINE_TEMPLATE bool QMap<Key, T>::operator==(const QMap<Key, T> &other) const
    1100             : {
    1101             :     if (size() != other.size())
    1102             :         return false;
    1103             :     if (d == other.d)
    1104             :         return true;
    1105             : 
    1106             :     const_iterator it1 = begin();
    1107             :     const_iterator it2 = other.begin();
    1108             : 
    1109             :     while (it1 != end()) {
    1110             :         if (!(it1.value() == it2.value()) || qMapLessThanKey(it1.key(), it2.key()) || qMapLessThanKey(it2.key(), it1.key()))
    1111             :             return false;
    1112             :         ++it2;
    1113             :         ++it1;
    1114             :     }
    1115             :     return true;
    1116             : }
    1117             : 
    1118             : template <class Key, class T>
    1119             : Q_OUTOFLINE_TEMPLATE QMap<Key, T>::QMap(const std::map<Key, T> &other)
    1120             : {
    1121             :     d = QMapData<Key, T>::create();
    1122             :     typename std::map<Key,T>::const_iterator it = other.end();
    1123             :     while (it != other.begin()) {
    1124             :         --it;
    1125             :         d->createNode((*it).first, (*it).second, d->begin(), true); // insert on most left node.
    1126             :     }
    1127             : }
    1128             : 
    1129             : template <class Key, class T>
    1130             : Q_OUTOFLINE_TEMPLATE std::map<Key, T> QMap<Key, T>::toStdMap() const
    1131             : {
    1132             :     std::map<Key, T> map;
    1133             :     const_iterator it = end();
    1134             :     while (it != begin()) {
    1135             :         --it;
    1136             :         map.insert(map.begin(), std::pair<Key, T>(it.key(), it.value()));
    1137             :     }
    1138             :     return map;
    1139             : }
    1140             : 
    1141             : template <class Key, class T>
    1142             : class QMultiMap : public QMap<Key, T>
    1143             : {
    1144             : public:
    1145             :     QMultiMap() {}
    1146             : #ifdef Q_COMPILER_INITIALIZER_LISTS
    1147             :     inline QMultiMap(std::initializer_list<std::pair<Key,T> > list)
    1148             :     {
    1149             :         for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it)
    1150             :             insert(it->first, it->second);
    1151             :     }
    1152             : #endif
    1153             :     QMultiMap(const QMap<Key, T> &other) : QMap<Key, T>(other) {}
    1154             :     inline void swap(QMultiMap<Key, T> &other) { QMap<Key, T>::swap(other); }
    1155             : 
    1156             :     inline typename QMap<Key, T>::iterator replace(const Key &key, const T &value)
    1157             :     { return QMap<Key, T>::insert(key, value); }
    1158             :     inline typename QMap<Key, T>::iterator insert(const Key &key, const T &value)
    1159             :     { return QMap<Key, T>::insertMulti(key, value); }
    1160             :     inline typename QMap<Key, T>::iterator insert(typename QMap<Key, T>::const_iterator pos, const Key &key, const T &value)
    1161             :     { return QMap<Key, T>::insertMulti(pos, key, value); }
    1162             : 
    1163             :     inline QMultiMap &operator+=(const QMultiMap &other)
    1164             :     { this->unite(other); return *this; }
    1165             :     inline QMultiMap operator+(const QMultiMap &other) const
    1166             :     { QMultiMap result = *this; result += other; return result; }
    1167             : 
    1168             : #if !defined(Q_NO_USING_KEYWORD) && !defined(Q_CC_RVCT)
    1169             :     // RVCT compiler doesn't handle using-keyword right when used functions are overloaded in child class
    1170             :     using QMap<Key, T>::contains;
    1171             :     using QMap<Key, T>::remove;
    1172             :     using QMap<Key, T>::count;
    1173             :     using QMap<Key, T>::find;
    1174             :     using QMap<Key, T>::constFind;
    1175             : #else
    1176             :     inline bool contains(const Key &key) const
    1177             :     { return QMap<Key, T>::contains(key); }
    1178             :     inline int remove(const Key &key)
    1179             :     { return QMap<Key, T>::remove(key); }
    1180             :     inline int count(const Key &key) const
    1181             :     { return QMap<Key, T>::count(key); }
    1182             :     inline int count() const
    1183             :     { return QMap<Key, T>::count(); }
    1184             :     inline typename QMap<Key, T>::iterator find(const Key &key)
    1185             :     { return QMap<Key, T>::find(key); }
    1186             :     inline typename QMap<Key, T>::const_iterator find(const Key &key) const
    1187             :     { return QMap<Key, T>::find(key); }
    1188             :     inline typename QMap<Key, T>::const_iterator constFind(const Key &key) const
    1189             :     { return QMap<Key, T>::constFind(key); }
    1190             : #endif
    1191             : 
    1192             :     bool contains(const Key &key, const T &value) const;
    1193             : 
    1194             :     int remove(const Key &key, const T &value);
    1195             : 
    1196             :     int count(const Key &key, const T &value) const;
    1197             : 
    1198             :     typename QMap<Key, T>::iterator find(const Key &key, const T &value) {
    1199             :         typename QMap<Key, T>::iterator i(find(key));
    1200             :         typename QMap<Key, T>::iterator end(this->end());
    1201             :         while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
    1202             :             if (i.value() == value)
    1203             :                 return i;
    1204             :             ++i;
    1205             :         }
    1206             :         return end;
    1207             :     }
    1208             :     typename QMap<Key, T>::const_iterator find(const Key &key, const T &value) const {
    1209             :         typename QMap<Key, T>::const_iterator i(constFind(key));
    1210             :         typename QMap<Key, T>::const_iterator end(QMap<Key, T>::constEnd());
    1211             :         while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
    1212             :             if (i.value() == value)
    1213             :                 return i;
    1214             :             ++i;
    1215             :         }
    1216             :         return end;
    1217             :     }
    1218             :     typename QMap<Key, T>::const_iterator constFind(const Key &key, const T &value) const
    1219             :         { return find(key, value); }
    1220             : private:
    1221             :     T &operator[](const Key &key);
    1222             :     const T operator[](const Key &key) const;
    1223             : };
    1224             : 
    1225             : template <class Key, class T>
    1226             : Q_INLINE_TEMPLATE bool QMultiMap<Key, T>::contains(const Key &key, const T &value) const
    1227             : {
    1228             :     return constFind(key, value) != QMap<Key, T>::constEnd();
    1229             : }
    1230             : 
    1231             : template <class Key, class T>
    1232             : Q_INLINE_TEMPLATE int QMultiMap<Key, T>::remove(const Key &key, const T &value)
    1233             : {
    1234             :     int n = 0;
    1235             :     typename QMap<Key, T>::iterator i(find(key));
    1236             :     typename QMap<Key, T>::iterator end(QMap<Key, T>::end());
    1237             :     while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
    1238             :         if (i.value() == value) {
    1239             :             i = this->erase(i);
    1240             :             ++n;
    1241             :         } else {
    1242             :             ++i;
    1243             :         }
    1244             :     }
    1245             :     return n;
    1246             : }
    1247             : 
    1248             : template <class Key, class T>
    1249             : Q_INLINE_TEMPLATE int QMultiMap<Key, T>::count(const Key &key, const T &value) const
    1250             : {
    1251             :     int n = 0;
    1252             :     typename QMap<Key, T>::const_iterator i(constFind(key));
    1253             :     typename QMap<Key, T>::const_iterator end(QMap<Key, T>::constEnd());
    1254             :     while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
    1255             :         if (i.value() == value)
    1256             :             ++n;
    1257             :         ++i;
    1258             :     }
    1259             :     return n;
    1260             : }
    1261             : 
    1262             : Q_DECLARE_ASSOCIATIVE_ITERATOR(Map)
    1263             : Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Map)
    1264             : 
    1265             : QT_END_NAMESPACE
    1266             : 
    1267             : #endif // QMAP_H

Generated by: LCOV version 1.11