1 /****************************************************************************

     2 **

     3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

     4 ** All rights reserved.

     5 ** Contact: Nokia Corporation (qt-info@nokia.com)

     6 **

     7 ** This file is part of the QtCore module of the Qt Toolkit.

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

    11 ** This file contains pre-release code and may not be distributed.

    12 ** You may use this file in accordance with the terms and conditions

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    15 **

    16 ** GNU Lesser General Public License Usage

    17 ** Alternatively, this file may be used under the terms of the GNU Lesser

    18 ** General Public License version 2.1 as published by the Free Software

    19 ** Foundation and appearing in the file LICENSE.LGPL included in the

    20 ** packaging of this file.  Please review the following information to

    21 ** ensure the GNU Lesser General Public License version 2.1 requirements

    22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

    23 **

    24 ** In addition, as a special exception, Nokia gives you certain additional

    25 ** rights.  These rights are described in the Nokia Qt LGPL Exception

    26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

    27 **

    28 ** If you have questions regarding the use of this file, please contact

    29 ** Nokia at qt-info@nokia.com.

    30 **

    31 **

    32 **

    33 **

    34 **

    35 **

    36 **

    37 **

    38 ** $QT_END_LICENSE$

    39 **

    40 ****************************************************************************/

    41 

    42 #ifndef QMAP_H

    43 #define QMAP_H

    44 

    45 #include <QtCore/qatomic.h>

    46 #include <QtCore/qiterator.h>

    47 #include <QtCore/qlist.h>

    48 

    49 #ifndef QT_NO_STL

    50 #include <map>

    51 #endif

    52 

    53 #include <new>

    54 

    55 QT_BEGIN_HEADER

    56 

    57 QT_BEGIN_NAMESPACE

    58 

    59 QT_MODULE(Core)

    60 

    61 struct Q_CORE_EXPORT QMapData

    62 {

    63     struct Node {

    64         Node *backward;

    65         Node *forward[1];

    66     };

    67     enum { LastLevel = 11, Sparseness = 3 };

    68 

    69     QMapData *backward;

    70     QMapData *forward[QMapData::LastLevel + 1];

    71     QBasicAtomicInt ref;

    72     int topLevel;

    73     int size;

    74     uint randomBits;

    75     uint insertInOrder : 1;

    76     uint sharable : 1;

    77 

    78     static QMapData *createData();

    79     void continueFreeData(int offset);

    80     Node *node_create(Node *update[], int offset);

    81     void node_delete(Node *update[], int offset, Node *node);

    82 #ifdef QT_QMAP_DEBUG

    83     uint adjust_ptr(Node *node);

    84     void dump();

    85 #endif

    86 

    87     static QMapData shared_null;

    88 };

    89 

    90 

    91 /*

    92     QMap uses qMapLessThanKey() to compare keys. The default

    93     implementation uses operator<(). For pointer types,

    94     qMapLessThanKey() casts the pointers to integers before it

    95     compares them, because operator<() is undefined on pointers

    96     that come from different memory blocks. (In practice, this

    97     is only a problem when running a program such as

    98     BoundsChecker.)

    99 */

   100 

   101 template <class Key> inline bool qMapLessThanKey(const Key &key1, const Key &key2)

   102 {

   103     return key1 < key2;

   104 }

   105 

   106 #ifndef QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION

   107 template <class Ptr> inline bool qMapLessThanKey(Ptr *key1, Ptr *key2)

   108 {

   109     Q_ASSERT(sizeof(quintptr) == sizeof(Ptr *));

   110     return quintptr(key1) < quintptr(key2);

   111 }

   112 

   113 template <class Ptr> inline bool qMapLessThanKey(const Ptr *key1, const Ptr *key2)

   114 {

   115     Q_ASSERT(sizeof(quintptr) == sizeof(const Ptr *));

   116     return quintptr(key1) < quintptr(key2);

   117 }

   118 #endif // QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION

   119 

   120 template <class Key, class T>

   121 struct QMapNode {

   122     Key key;

   123     T value;

   124     QMapData::Node *backward;

   125     QMapData::Node *forward[1];

   126 };

   127 

   128 template <class Key, class T>

   129 struct QMapPayloadNode

   130 {

   131     Key key;

   132     T value;

   133     QMapData::Node *backward;

   134 };

   135 

   136 template <class Key, class T>

   137 class QMap

   138 {

   139     typedef QMapNode<Key, T> Node;

   140     typedef QMapPayloadNode<Key, T> PayloadNode;

   141 

   142     union {

   143         QMapData *d;

   144         QMapData::Node *e;

   145     };

   146 

   147     static inline int payload() { return sizeof(PayloadNode) - sizeof(QMapData::Node *); }

   148     static inline Node *concrete(QMapData::Node *node) {

   149         return reinterpret_cast<Node *>(reinterpret_cast<char *>(node) - payload());

   150     }

   151 

   152 public:

   153     inline QMap() : d(&QMapData::shared_null) { d->ref.ref(); }

   154     inline QMap(const QMap<Key, T> &other) : d(other.d)

   155     { d->ref.ref(); if (!d->sharable) detach(); }

   156     inline ~QMap() { if (!d) return; if (!d->ref.deref()) freeData(d); }

   157 

   158     QMap<Key, T> &operator=(const QMap<Key, T> &other);

   159 #ifndef QT_NO_STL

   160     explicit QMap(const typename std::map<Key, T> &other);

   161     std::map<Key, T> toStdMap() const;

   162 #endif

   163 

   164     bool operator==(const QMap<Key, T> &other) const;

   165     inline bool operator!=(const QMap<Key, T> &other) const { return !(*this == other); }

   166 

   167     inline int size() const { return d->size; }

   168 

   169     inline bool isEmpty() const { return d->size == 0; }

   170 

   171     inline void detach() { if (d->ref != 1) detach_helper(); }

   172     inline bool isDetached() const { return d->ref == 1; }

   173     inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }

   174     inline void setInsertInOrder(bool ordered) { d->insertInOrder = ordered; }

   175 

   176     void clear();

   177 

   178     int remove(const Key &key);

   179     T take(const Key &key);

   180 

   181     bool contains(const Key &key) const;

   182     const Key key(const T &value) const;

   183     const Key key(const T &value, const Key &defaultKey) const;

   184     const T value(const Key &key) const;

   185     const T value(const Key &key, const T &defaultValue) const;

   186     T &operator[](const Key &key);

   187     const T operator[](const Key &key) const;

   188 

   189     QList<Key> uniqueKeys() const;

   190     QList<Key> keys() const;

   191     QList<Key> keys(const T &value) const;

   192     QList<T> values() const;

   193     QList<T> values(const Key &key) const;

   194     int count(const Key &key) const;

   195 

   196     class const_iterator;

   197 

   198     class iterator

   199     {

   200         friend class const_iterator;

   201         QMapData::Node *i;

   202 

   203     public:

   204         typedef std::bidirectional_iterator_tag iterator_category;

   205         typedef ptrdiff_t difference_type;

   206         typedef T value_type;

   207         typedef T *pointer;

   208         typedef T &reference;

   209 

   210         // ### Qt 5: get rid of 'operator Node *'

   211         inline operator QMapData::Node *() const { return i; }

   212         inline iterator() : i(0) { }

   213         inline iterator(QMapData::Node *node) : i(node) { }

   214 

   215         inline const Key &key() const { return concrete(i)->key; }

   216         inline T &value() const { return concrete(i)->value; }

   217 #ifdef QT3_SUPPORT

   218         inline QT3_SUPPORT T &data() const { return concrete(i)->value; }

   219 #endif

   220         inline T &operator*() const { return concrete(i)->value; }

   221         inline T *operator->() const { return &concrete(i)->value; }

   222         inline bool operator==(const iterator &o) const { return i == o.i; }

   223         inline bool operator!=(const iterator &o) const { return i != o.i; }

   224 

   225         inline iterator &operator++() {

   226             i = i->forward[0];

   227             return *this;

   228         }

   229         inline iterator operator++(int) {

   230             iterator r = *this;

   231             i = i->forward[0];

   232             return r;

   233         }

   234         inline iterator &operator--() {

   235             i = i->backward;

   236             return *this;

   237         }

   238         inline iterator operator--(int) {

   239             iterator r = *this;

   240             i = i->backward;

   241             return r;

   242         }

   243         inline iterator operator+(int j) const

   244         { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }

   245         inline iterator operator-(int j) const { return operator+(-j); }

   246         inline iterator &operator+=(int j) { return *this = *this + j; }

   247         inline iterator &operator-=(int j) { return *this = *this - j; }

   248 

   249         // ### Qt 5: not sure this is necessary anymore

   250 #ifdef QT_STRICT_ITERATORS

   251     private:

   252 #else

   253     public:

   254 #endif

   255         inline bool operator==(const const_iterator &o) const

   256             { return i == o.i; }

   257         inline bool operator!=(const const_iterator &o) const

   258             { return i != o.i; }

   259 

   260     private:

   261         // ### Qt 5: remove

   262         inline operator bool() const { return false; }

   263     };

   264     friend class iterator;

   265 

   266     class const_iterator

   267     {

   268         friend class iterator;

   269         QMapData::Node *i;

   270 

   271     public:

   272         typedef std::bidirectional_iterator_tag iterator_category;

   273         typedef ptrdiff_t difference_type;

   274         typedef T value_type;

   275         typedef const T *pointer;

   276         typedef const T &reference;

   277 

   278         // ### Qt 5: get rid of 'operator Node *'

   279         inline operator QMapData::Node *() const { return i; }

   280         inline const_iterator() : i(0) { }

   281         inline const_iterator(QMapData::Node *node) : i(node) { }

   282 #ifdef QT_STRICT_ITERATORS

   283         explicit inline const_iterator(const iterator &o)

   284 #else

   285         inline const_iterator(const iterator &o)

   286 #endif

   287         { i = o.i; }

   288 

   289         inline const Key &key() const { return concrete(i)->key; }

   290         inline const T &value() const { return concrete(i)->value; }

   291 #ifdef QT3_SUPPORT

   292         inline QT3_SUPPORT const T &data() const { return concrete(i)->value; }

   293 #endif

   294         inline const T &operator*() const { return concrete(i)->value; }

   295         inline const T *operator->() const { return &concrete(i)->value; }

   296         inline bool operator==(const const_iterator &o) const { return i == o.i; }

   297         inline bool operator!=(const const_iterator &o) const { return i != o.i; }

   298 

   299         inline const_iterator &operator++() {

   300             i = i->forward[0];

   301             return *this;

   302         }

   303         inline const_iterator operator++(int) {

   304             const_iterator r = *this;

   305             i = i->forward[0];

   306             return r;

   307         }

   308         inline const_iterator &operator--() {

   309             i = i->backward;

   310             return *this;

   311         }

   312         inline const_iterator operator--(int) {

   313             const_iterator r = *this;

   314             i = i->backward;

   315             return r;

   316         }

   317         inline const_iterator operator+(int j) const

   318         { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }

   319         inline const_iterator operator-(int j) const { return operator+(-j); }

   320         inline const_iterator &operator+=(int j) { return *this = *this + j; }

   321         inline const_iterator &operator-=(int j) { return *this = *this - j; }

   322 

   323         // ### Qt 5: not sure this is necessary anymore

   324 #ifdef QT_STRICT_ITERATORS

   325     private:

   326         inline bool operator==(const iterator &o) { return operator==(const_iterator(o)); }

   327         inline bool operator!=(const iterator &o) { return operator!=(const_iterator(o)); }

   328 #endif

   329 

   330     private:

   331         // ### Qt 5: remove

   332         inline operator bool() const { return false; }

   333     };

   334     friend class const_iterator;

   335 

   336     // STL style

   337     inline iterator begin() { detach(); return iterator(e->forward[0]); }

   338     inline const_iterator begin() const { return const_iterator(e->forward[0]); }

   339     inline const_iterator constBegin() const { return const_iterator(e->forward[0]); }

   340     inline iterator end() {

   341         detach();

   342         return iterator(e);

   343     }

   344     inline const_iterator end() const { return const_iterator(e); }

   345     inline const_iterator constEnd() const { return const_iterator(e); }

   346     iterator erase(iterator it);

   347 #ifdef QT3_SUPPORT

   348     inline QT3_SUPPORT iterator remove(iterator it) { return erase(it); }

   349     inline QT3_SUPPORT void erase(const Key &aKey) { remove(aKey); }

   350 #endif

   351 

   352     // more Qt

   353     typedef iterator Iterator;

   354     typedef const_iterator ConstIterator;

   355     inline int count() const { return d->size; }

   356     iterator find(const Key &key);

   357     const_iterator find(const Key &key) const;

   358     const_iterator constFind(const Key &key) const;

   359     iterator lowerBound(const Key &key);

   360     const_iterator lowerBound(const Key &key) const;

   361     iterator upperBound(const Key &key);

   362     const_iterator upperBound(const Key &key) const;

   363     iterator insert(const Key &key, const T &value);

   364 #ifdef QT3_SUPPORT

   365     QT3_SUPPORT iterator insert(const Key &key, const T &value, bool overwrite);

   366 #endif

   367     iterator insertMulti(const Key &key, const T &value);

   368 #ifdef QT3_SUPPORT

   369     inline QT3_SUPPORT iterator replace(const Key &aKey, const T &aValue) { return insert(aKey, aValue); }

   370 #endif

   371     QMap<Key, T> &unite(const QMap<Key, T> &other);

   372 

   373     // STL compatibility

   374     typedef Key key_type;

   375     typedef T mapped_type;

   376     typedef ptrdiff_t difference_type;

   377     typedef int size_type;

   378     inline bool empty() const { return isEmpty(); }

   379 

   380 #ifdef QT_QMAP_DEBUG

   381     inline void dump() const { d->dump(); }

   382 #endif

   383 

   384 private:

   385     void detach_helper();

   386     void freeData(QMapData *d);

   387     QMapData::Node *findNode(const Key &key) const;

   388     QMapData::Node *mutableFindNode(QMapData::Node *update[], const Key &key) const;

   389     QMapData::Node *node_create(QMapData *d, QMapData::Node *update[], const Key &key,

   390                                 const T &value);

   391 };

   392 

   393 template <class Key, class T>

   394 Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::operator=(const QMap<Key, T> &other)

   395 {

   396     if (d != other.d) {

   397         other.d->ref.ref();

   398         if (!d->ref.deref())

   399             freeData(d);

   400         d = other.d;

   401         if (!d->sharable)

   402             detach_helper();

   403     }

   404     return *this;

   405 }

   406 

   407 template <class Key, class T>

   408 Q_INLINE_TEMPLATE void QMap<Key, T>::clear()

   409 {

   410     *this = QMap<Key, T>();

   411 }

   412 

   413 template <class Key, class T>

   414 Q_INLINE_TEMPLATE typename QMapData::Node *

   415 QMap<Key, T>::node_create(QMapData *adt, QMapData::Node *aupdate[], const Key &akey, const T &avalue)

   416 {

   417     QMapData::Node *abstractNode = adt->node_create(aupdate, payload());

   418     QT_TRY {

   419         Node *concreteNode = concrete(abstractNode);

   420         new (&concreteNode->key) Key(akey);

   421         QT_TRY {

   422             new (&concreteNode->value) T(avalue);

   423         } QT_CATCH(...) {

   424             concreteNode->key.~Key();

   425             QT_RETHROW;

   426         }

   427     } QT_CATCH(...) {

   428         adt->node_delete(aupdate, payload(), abstractNode);

   429         QT_RETHROW;

   430     }

   431 

   432     // clean up the update array for further insertions

   433     /*

   434     for (int i = 0; i <= d->topLevel; ++i) {

   435         if ( aupdate[i]==reinterpret_cast<QMapData::Node *>(adt) || aupdate[i]->forward[i] != abstractNode)

   436             break;

   437         aupdate[i] = abstractNode;

   438     }

   439 */

   440 

   441     return abstractNode;

   442 }

   443 

   444 template <class Key, class T>

   445 Q_INLINE_TEMPLATE QMapData::Node *QMap<Key, T>::findNode(const Key &akey) const

   446 {

   447     QMapData::Node *cur = e;

   448     QMapData::Node *next = e;

   449 

   450     for (int i = d->topLevel; i >= 0; i--) {

   451         while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))

   452             cur = next;

   453     }

   454 

   455     if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {

   456         return next;

   457     } else {

   458         return e;

   459     }

   460 }

   461 

   462 template <class Key, class T>

   463 Q_INLINE_TEMPLATE const T QMap<Key, T>::value(const Key &akey) const

   464 {

   465     QMapData::Node *node;

   466     if (d->size == 0 || (node = findNode(akey)) == e) {

   467         return T();

   468     } else {

   469         return concrete(node)->value;

   470     }

   471 }

   472 

   473 template <class Key, class T>

   474 Q_INLINE_TEMPLATE const T QMap<Key, T>::value(const Key &akey, const T &adefaultValue) const

   475 {

   476     QMapData::Node *node;

   477     if (d->size == 0 || (node = findNode(akey)) == e) {

   478         return adefaultValue;

   479     } else {

   480         return concrete(node)->value;

   481     }

   482 }

   483 

   484 template <class Key, class T>

   485 Q_INLINE_TEMPLATE const T QMap<Key, T>::operator[](const Key &akey) const

   486 {

   487     return value(akey);

   488 }

   489 

   490 template <class Key, class T>

   491 Q_INLINE_TEMPLATE T &QMap<Key, T>::operator[](const Key &akey)

   492 {

   493     detach();

   494 

   495     QMapData::Node *update[QMapData::LastLevel + 1];

   496     QMapData::Node *node = mutableFindNode(update, akey);

   497     if (node == e)

   498         node = node_create(d, update, akey, T());

   499     return concrete(node)->value;

   500 }

   501 

   502 template <class Key, class T>

   503 Q_INLINE_TEMPLATE int QMap<Key, T>::count(const Key &akey) const

   504 {

   505     int cnt = 0;

   506     QMapData::Node *node = findNode(akey);

   507     if (node != e) {

   508         do {

   509             ++cnt;

   510             node = node->forward[0];

   511         } while (node != e && !qMapLessThanKey<Key>(akey, concrete(node)->key));

   512     }

   513     return cnt;

   514 }

   515 

   516 template <class Key, class T>

   517 Q_INLINE_TEMPLATE bool QMap<Key, T>::contains(const Key &akey) const

   518 {

   519     return findNode(akey) != e;

   520 }

   521 

   522 template <class Key, class T>

   523 Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insert(const Key &akey,

   524                                                                        const T &avalue)

   525 {

   526     detach();

   527 

   528     QMapData::Node *update[QMapData::LastLevel + 1];

   529     QMapData::Node *node = mutableFindNode(update, akey);

   530     if (node == e) {

   531         node = node_create(d, update, akey, avalue);

   532     } else {

   533         concrete(node)->value = avalue;

   534     }

   535     return iterator(node);

   536 }

   537 

   538 #ifdef QT3_SUPPORT

   539 template <class Key, class T>

   540 Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insert(const Key &akey,

   541                                                                        const T &avalue,

   542                                                                        bool aoverwrite)

   543 {

   544     detach();

   545 

   546     QMapData::Node *update[QMapData::LastLevel + 1];

   547     QMapData::Node *node = mutableFindNode(update, akey);

   548     if (node == e) {

   549         node = node_create(d, update, akey, avalue);

   550     } else {

   551         if (aoverwrite)

   552             concrete(node)->value = avalue;

   553     }

   554     return iterator(node);

   555 }

   556 #endif

   557 

   558 template <class Key, class T>

   559 Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const Key &akey,

   560                                                                             const T &avalue)

   561 {

   562     detach();

   563 

   564     QMapData::Node *update[QMapData::LastLevel + 1];

   565     mutableFindNode(update, akey);

   566     return iterator(node_create(d, update, akey, avalue));

   567 }

   568 

   569 template <class Key, class T>

   570 Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::find(const Key &akey) const

   571 {

   572     return const_iterator(findNode(akey));

   573 }

   574 

   575 template <class Key, class T>

   576 Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::constFind(const Key &akey) const

   577 {

   578     return const_iterator(findNode(akey));

   579 }

   580 

   581 template <class Key, class T>

   582 Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::find(const Key &akey)

   583 {

   584     detach();

   585     return iterator(findNode(akey));

   586 }

   587 

   588 template <class Key, class T>

   589 Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::unite(const QMap<Key, T> &other)

   590 {

   591     QMap<Key, T> copy(other);

   592     const_iterator it = copy.constEnd();

   593     const const_iterator b = copy.constBegin();

   594     while (it != b) {

   595         --it;

   596         insertMulti(it.key(), it.value());

   597     }

   598     return *this;

   599 }

   600 

   601 template <class Key, class T>

   602 Q_OUTOFLINE_TEMPLATE void QMap<Key, T>::freeData(QMapData *x)

   603 {

   604     if (QTypeInfo<Key>::isComplex || QTypeInfo<T>::isComplex) {

   605         QMapData *cur = x;

   606         QMapData *next = cur->forward[0];

   607         while (next != x) {

   608             cur = next;

   609             next = cur->forward[0];

   610 #if defined(_MSC_VER) && (_MSC_VER >= 1300)

   611 #pragma warning(disable:4189)

   612 #endif

   613             Node *concreteNode = concrete(reinterpret_cast<QMapData::Node *>(cur));

   614             concreteNode->key.~Key();

   615             concreteNode->value.~T();

   616 #if defined(_MSC_VER) && (_MSC_VER >= 1300)

   617 #pragma warning(default:4189)

   618 #endif

   619         }

   620     }

   621     x->continueFreeData(payload());

   622 }

   623 

   624 template <class Key, class T>

   625 Q_OUTOFLINE_TEMPLATE int QMap<Key, T>::remove(const Key &akey)

   626 {

   627     detach();

   628 

   629     QMapData::Node *update[QMapData::LastLevel + 1];

   630     QMapData::Node *cur = e;

   631     QMapData::Node *next = e;

   632     int oldSize = d->size;

   633 

   634     for (int i = d->topLevel; i >= 0; i--) {

   635         while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))

   636             cur = next;

   637         update[i] = cur;

   638     }

   639 

   640     if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {

   641         bool deleteNext = true;

   642         do {

   643             cur = next;

   644             next = cur->forward[0];

   645             deleteNext = (next != e && !qMapLessThanKey<Key>(concrete(cur)->key, concrete(next)->key));

   646             concrete(cur)->key.~Key();

   647             concrete(cur)->value.~T();

   648             d->node_delete(update, payload(), cur);

   649         } while (deleteNext);

   650     }

   651     return oldSize - d->size;

   652 }

   653 

   654 template <class Key, class T>

   655 Q_OUTOFLINE_TEMPLATE T QMap<Key, T>::take(const Key &akey)

   656 {

   657     detach();

   658 

   659     QMapData::Node *update[QMapData::LastLevel + 1];

   660     QMapData::Node *cur = e;

   661     QMapData::Node *next = e;

   662 

   663     for (int i = d->topLevel; i >= 0; i--) {

   664         while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))

   665             cur = next;

   666         update[i] = cur;

   667     }

   668 

   669     if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {

   670         T t = concrete(next)->value;

   671         concrete(next)->key.~Key();

   672         concrete(next)->value.~T();

   673         d->node_delete(update, payload(), next);

   674         return t;

   675     }

   676     return T();

   677 }

   678 

   679 template <class Key, class T>

   680 Q_OUTOFLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::erase(iterator it)

   681 {

   682     QMapData::Node *update[QMapData::LastLevel + 1];

   683     QMapData::Node *cur = e;

   684     QMapData::Node *next = e;

   685 

   686     if (it == iterator(e))

   687         return it;

   688 

   689     for (int i = d->topLevel; i >= 0; i--) {

   690         while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, it.key()))

   691             cur = next;

   692         update[i] = cur;

   693     }

   694 

   695     while (next != e) {

   696         cur = next;

   697         next = cur->forward[0];

   698         if (cur == it) {

   699             concrete(cur)->key.~Key();

   700             concrete(cur)->value.~T();

   701             d->node_delete(update, payload(), cur);

   702             return iterator(next);

   703         }

   704 

   705         for (int i = 0; i <= d->topLevel; ++i) {

   706             if (update[i]->forward[i] != cur)

   707                 break;

   708             update[i] = cur;

   709         }

   710     }

   711     return end();

   712 }

   713 

   714 template <class Key, class T>

   715 Q_OUTOFLINE_TEMPLATE void QMap<Key, T>::detach_helper()

   716 {

   717     union { QMapData *d; QMapData::Node *e; } x;

   718     x.d = QMapData::createData();

   719     if (d->size) {

   720         x.d->insertInOrder = true;

   721         QMapData::Node *update[QMapData::LastLevel + 1];

   722         QMapData::Node *cur = e->forward[0];

   723         update[0] = x.e;

   724         while (cur != e) {

   725             QT_TRY {

   726                 Node *concreteNode = concrete(cur);

   727                 node_create(x.d, update, concreteNode->key, concreteNode->value);

   728             } QT_CATCH(...) {

   729                 freeData(x.d);

   730                 QT_RETHROW;

   731             }

   732             cur = cur->forward[0];

   733         }

   734         x.d->insertInOrder = false;

   735     }

   736     if (!d->ref.deref())

   737         freeData(d);

   738     d = x.d;

   739 }

   740 

   741 template <class Key, class T>

   742 Q_OUTOFLINE_TEMPLATE QMapData::Node *QMap<Key, T>::mutableFindNode(QMapData::Node *aupdate[],

   743                                                                    const Key &akey) const

   744 {

   745     QMapData::Node *cur = e;

   746     QMapData::Node *next = e;

   747 

   748     for (int i = d->topLevel; i >= 0; i--) {

   749         while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))

   750             cur = next;

   751         aupdate[i] = cur;

   752     }

   753     if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {

   754         return next;

   755     } else {

   756         return e;

   757     }

   758 }

   759 

   760 template <class Key, class T>

   761 Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::uniqueKeys() const

   762 {

   763     QList<Key> res;

   764     const_iterator i = begin();

   765     if (i != end()) {

   766         for (;;) {

   767             const Key &aKey = i.key();

   768             res.append(aKey);

   769             do {

   770                 if (++i == end())

   771                     goto break_out_of_outer_loop;

   772             } while (!(aKey < i.key()));   // loop while (key == i.key())

   773         }

   774     }

   775 break_out_of_outer_loop:

   776     return res;

   777 }

   778 

   779 template <class Key, class T>

   780 Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys() const

   781 {

   782     QList<Key> res;

   783     const_iterator i = begin();

   784     while (i != end()) {

   785         res.append(i.key());

   786         ++i;

   787     }

   788     return res;

   789 }

   790 

   791 template <class Key, class T>

   792 Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys(const T &avalue) const

   793 {

   794     QList<Key> res;

   795     const_iterator i = begin();

   796     while (i != end()) {

   797         if (i.value() == avalue)

   798             res.append(i.key());

   799         ++i;

   800     }

   801     return res;

   802 }

   803 

   804 template <class Key, class T>

   805 Q_OUTOFLINE_TEMPLATE const Key QMap<Key, T>::key(const T &avalue) const

   806 {

   807     return key(avalue, Key());

   808 }

   809 

   810 template <class Key, class T>

   811 Q_OUTOFLINE_TEMPLATE const Key QMap<Key, T>::key(const T &avalue, const Key &defaultKey) const

   812 {

   813     const_iterator i = begin();

   814     while (i != end()) {

   815         if (i.value() == avalue)

   816             return i.key();

   817         ++i;

   818     }

   819 

   820     return defaultKey;

   821 }

   822 

   823 template <class Key, class T>

   824 Q_OUTOFLINE_TEMPLATE QList<T> QMap<Key, T>::values() const

   825 {

   826     QList<T> res;

   827     const_iterator i = begin();

   828     while (i != end()) {

   829         res.append(i.value());

   830         ++i;

   831     }

   832     return res;

   833 }

   834 

   835 template <class Key, class T>

   836 Q_OUTOFLINE_TEMPLATE QList<T> QMap<Key, T>::values(const Key &akey) const

   837 {

   838     QList<T> res;

   839     QMapData::Node *node = findNode(akey);

   840     if (node != e) {

   841         do {

   842             res.append(concrete(node)->value);

   843             node = node->forward[0];

   844         } while (node != e && !qMapLessThanKey<Key>(akey, concrete(node)->key));

   845     }

   846     return res;

   847 }

   848 

   849 template <class Key, class T>

   850 Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator

   851 QMap<Key, T>::lowerBound(const Key &akey) const

   852 {

   853     QMapData::Node *update[QMapData::LastLevel + 1];

   854     mutableFindNode(update, akey);

   855     return const_iterator(update[0]->forward[0]);

   856 }

   857 

   858 template <class Key, class T>

   859 Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::lowerBound(const Key &akey)

   860 {

   861     detach();

   862     return static_cast<QMapData::Node *>(const_cast<const QMap *>(this)->lowerBound(akey));

   863 }

   864 

   865 template <class Key, class T>

   866 Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator

   867 QMap<Key, T>::upperBound(const Key &akey) const

   868 {

   869     QMapData::Node *update[QMapData::LastLevel + 1];

   870     mutableFindNode(update, akey);

   871     QMapData::Node *node = update[0]->forward[0];

   872     while (node != e && !qMapLessThanKey<Key>(akey, concrete(node)->key))

   873         node = node->forward[0];

   874     return const_iterator(node);

   875 }

   876 

   877 template <class Key, class T>

   878 Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::upperBound(const Key &akey)

   879 {

   880     detach();

   881     return static_cast<QMapData::Node *>(const_cast<const QMap *>(this)->upperBound(akey));

   882 }

   883 

   884 template <class Key, class T>

   885 Q_OUTOFLINE_TEMPLATE bool QMap<Key, T>::operator==(const QMap<Key, T> &other) const

   886 {

   887     if (size() != other.size())

   888         return false;

   889     if (d == other.d)

   890         return true;

   891 

   892     const_iterator it1 = begin();

   893     const_iterator it2 = other.begin();

   894 

   895     while (it1 != end()) {

   896         if (!(it1.value() == it2.value()) || qMapLessThanKey(it1.key(), it2.key()) || qMapLessThanKey(it2.key(), it1.key()))

   897             return false;

   898         ++it2;

   899         ++it1;

   900     }

   901     return true;

   902 }

   903 

   904 #ifndef QT_NO_STL

   905 template <class Key, class T>

   906 Q_OUTOFLINE_TEMPLATE QMap<Key, T>::QMap(const std::map<Key, T> &other)

   907 {

   908     d = QMapData::createData();

   909     d->insertInOrder = true;

   910     typename std::map<Key,T>::const_iterator it = other.end();

   911     while (it != other.begin()) {

   912         --it;

   913         insert((*it).first, (*it).second);

   914     }

   915     d->insertInOrder = false;

   916 }

   917 

   918 template <class Key, class T>

   919 Q_OUTOFLINE_TEMPLATE std::map<Key, T> QMap<Key, T>::toStdMap() const

   920 {

   921     std::map<Key, T> map;

   922     const_iterator it = end();

   923     while (it != begin()) {

   924         --it;

   925         map.insert(std::pair<Key, T>(it.key(), it.value()));

   926     }

   927     return map;

   928 }

   929 

   930 #endif // QT_NO_STL

   931 

   932 template <class Key, class T>

   933 class QMultiMap : public QMap<Key, T>

   934 {

   935 public:

   936     QMultiMap() {}

   937     QMultiMap(const QMap<Key, T> &other) : QMap<Key, T>(other) {}

   938 

   939     inline typename QMap<Key, T>::iterator replace(const Key &key, const T &value)

   940     { return QMap<Key, T>::insert(key, value); }

   941     inline typename QMap<Key, T>::iterator insert(const Key &key, const T &value)

   942     { return QMap<Key, T>::insertMulti(key, value); }

   943 

   944     inline QMultiMap &operator+=(const QMultiMap &other)

   945     { unite(other); return *this; }

   946     inline QMultiMap operator+(const QMultiMap &other) const

   947     { QMultiMap result = *this; result += other; return result; }

   948 

   949 #if !defined(Q_NO_USING_KEYWORD) && !defined(Q_CC_RVCT)

   950     // RVCT compiler doesn't handle using-keyword right when used functions are overloaded in child class

   951     using QMap<Key, T>::contains;

   952     using QMap<Key, T>::remove;

   953     using QMap<Key, T>::count;

   954     using QMap<Key, T>::find;

   955     using QMap<Key, T>::constFind;

   956 #else

   957     inline bool contains(const Key &key) const

   958     { return QMap<Key, T>::contains(key); }

   959     inline int remove(const Key &key)

   960     { return QMap<Key, T>::remove(key); }

   961     inline int count(const Key &key) const

   962     { return QMap<Key, T>::count(key); }

   963     inline int count() const

   964     { return QMap<Key, T>::count(); }

   965     inline typename QMap<Key, T>::iterator find(const Key &key)

   966     { return QMap<Key, T>::find(key); }

   967     inline typename QMap<Key, T>::const_iterator find(const Key &key) const

   968     { return QMap<Key, T>::find(key); }

   969     inline typename QMap<Key, T>::const_iterator constFind(const Key &key) const

   970     { return QMap<Key, T>::constFind(key); }

   971 #endif

   972 

   973     bool contains(const Key &key, const T &value) const;

   974 

   975     int remove(const Key &key, const T &value);

   976 

   977     int count(const Key &key, const T &value) const;

   978 

   979     typename QMap<Key, T>::iterator find(const Key &key, const T &value) {

   980         typename QMap<Key, T>::iterator i(find(key));

   981         typename QMap<Key, T>::iterator end(this->end());

   982         while (i != end && !qMapLessThanKey<Key>(key, i.key())) {

   983             if (i.value() == value)

   984                 return i;

   985             ++i;

   986         }

   987         return end;

   988     }

   989     typename QMap<Key, T>::const_iterator find(const Key &key, const T &value) const {

   990         typename QMap<Key, T>::const_iterator i(constFind(key));

   991         typename QMap<Key, T>::const_iterator end(QMap<Key, T>::constEnd());

   992         while (i != end && !qMapLessThanKey<Key>(key, i.key())) {

   993             if (i.value() == value)

   994                 return i;

   995             ++i;

   996         }

   997         return end;

   998     }

   999     typename QMap<Key, T>::const_iterator constFind(const Key &key, const T &value) const

  1000         { return find(key, value); }

  1001 private:

  1002     T &operator[](const Key &key);

  1003     const T operator[](const Key &key) const;

  1004 };

  1005 

  1006 template <class Key, class T>

  1007 Q_INLINE_TEMPLATE bool QMultiMap<Key, T>::contains(const Key &key, const T &value) const

  1008 {

  1009     return constFind(key, value) != QMap<Key, T>::constEnd();

  1010 }

  1011 

  1012 template <class Key, class T>

  1013 Q_INLINE_TEMPLATE int QMultiMap<Key, T>::remove(const Key &key, const T &value)

  1014 {

  1015     int n = 0;

  1016     typename QMap<Key, T>::iterator i(find(key));

  1017     typename QMap<Key, T>::iterator end(QMap<Key, T>::end());

  1018     while (i != end && !qMapLessThanKey<Key>(key, i.key())) {

  1019         if (i.value() == value) {

  1020 #if defined(Q_CC_RVCT)

  1021             // RVCT has problems with scoping, apparently.

  1022             i = QMap<Key, T>::erase(i);

  1023 #else

  1024             i = erase(i);

  1025 #endif

  1026             ++n;

  1027         } else {

  1028             ++i;

  1029         }

  1030     }

  1031     return n;

  1032 }

  1033 

  1034 template <class Key, class T>

  1035 Q_INLINE_TEMPLATE int QMultiMap<Key, T>::count(const Key &key, const T &value) const

  1036 {

  1037     int n = 0;

  1038     typename QMap<Key, T>::const_iterator i(constFind(key));

  1039     typename QMap<Key, T>::const_iterator end(QMap<Key, T>::constEnd());

  1040     while (i != end && !qMapLessThanKey<Key>(key, i.key())) {

  1041         if (i.value() == value)

  1042             ++n;

  1043         ++i;

  1044     }

  1045     return n;

  1046 }

  1047 

  1048 Q_DECLARE_ASSOCIATIVE_ITERATOR(Map)

  1049 Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Map)

  1050 

  1051 QT_END_NAMESPACE

  1052 

  1053 QT_END_HEADER

  1054 

  1055 #endif // QMAP_H