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

- File List
- File Members

# qmap.h

Go to the documentation of this file.

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