Initial import from the monolithic Qt.

This is the beginning of revision history for this module. If you
want to look at revision history older than this, please refer to the
Qt Git wiki for how to use Git history grafting. At the time of
writing, this wiki is located here:

http://qt.gitorious.org/qt/pages/GitIntroductionWithQt

If you have already performed the grafting and you don't see any
history beyond this commit, try running "git log" with the "--follow"
argument.

Branched from the monolithic repo, Qt master branch, at commit
896db169ea224deb96c59ce8af800d019de63f12

1 files changed, 1090 insertions, 0 deletions

diff --git a/src/corelib/tools/qmap.h b/src/corelib/tools/qmap.h
new file mode 100644
index 0000000000..6ac30dd5a7
--- /dev/null
+++ b/src/corelib/tools/qmap.h
@@ -0,0 +1,1090 @@
+/****************************************************************************
+**
+** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the QtCore module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the Technology Preview License Agreement accompanying
+** this package.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file.  Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights.  These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#ifndef QMAP_H
+#define QMAP_H
+
+#include <QtCore/qatomic.h>
+#include <QtCore/qiterator.h>
+#include <QtCore/qlist.h>
+
+#ifndef QT_NO_STL
+#include <map>
+#endif
+
+#include <new>
+
+QT_BEGIN_HEADER
+
+QT_BEGIN_NAMESPACE
+
+QT_MODULE(Core)
+
+struct Q_CORE_EXPORT QMapData
+{
+    struct Node {
+        Node *backward;
+        Node *forward[1];
+    };
+    enum { LastLevel = 11, Sparseness = 3 };
+
+    QMapData *backward;
+    QMapData *forward[QMapData::LastLevel + 1];
+    QBasicAtomicInt ref;
+    int topLevel;
+    int size;
+    uint randomBits;
+    uint insertInOrder : 1;
+    uint sharable : 1;
+    uint strictAlignment : 1;
+    uint reserved : 29;
+
+    static QMapData *createData(); // ### Qt5 remove me
+    static QMapData *createData(int alignment);
+    void continueFreeData(int offset);
+    Node *node_create(Node *update[], int offset); // ### Qt5 remove me
+    Node *node_create(Node *update[], int offset, int alignment);
+    void node_delete(Node *update[], int offset, Node *node);
+#ifdef QT_QMAP_DEBUG
+    uint adjust_ptr(Node *node);
+    void dump();
+#endif
+
+    static QMapData shared_null;
+};
+
+
+/*
+    QMap uses qMapLessThanKey() to compare keys. The default
+    implementation uses operator<(). For pointer types,
+    qMapLessThanKey() casts the pointers to integers before it
+    compares them, because operator<() is undefined on pointers
+    that come from different memory blocks. (In practice, this
+    is only a problem when running a program such as
+    BoundsChecker.)
+*/
+
+template <class Key> inline bool qMapLessThanKey(const Key &key1, const Key &key2)
+{
+    return key1 < key2;
+}
+
+template <class Ptr> inline bool qMapLessThanKey(Ptr *key1, Ptr *key2)
+{
+    Q_ASSERT(sizeof(quintptr) == sizeof(Ptr *));
+    return quintptr(key1) < quintptr(key2);
+}
+
+template <class Ptr> inline bool qMapLessThanKey(const Ptr *key1, const Ptr *key2)
+{
+    Q_ASSERT(sizeof(quintptr) == sizeof(const Ptr *));
+    return quintptr(key1) < quintptr(key2);
+}
+
+template <class Key, class T>
+struct QMapNode {
+    Key key;
+    T value;
+
+private:
+    // never access these members through this structure.
+    // see below
+    QMapData::Node *backward;
+    QMapData::Node *forward[1];
+};
+
+template <class Key, class T>
+struct QMapPayloadNode
+{
+    Key key;
+    T value;
+
+private:
+    // QMap::e is a pointer to QMapData::Node, which matches the member
+    // below. However, the memory allocation node in QMapData::node_create
+    // allocates sizeof(QMapPayloNode) and incorrectly calculates the offset
+    // of 'backward' below. If the alignment of QMapPayloadNode is larger
+    // than the alignment of a pointer, the 'backward' member is aligned to
+    // the end of this structure, not to 'value' above, and will occupy the
+    // tail-padding area.
+    //
+    //  e.g., on a 32-bit archictecture with Key = int and
+    //        sizeof(T) = alignof(T) = 8
+    //   0        4        8        12       16       20       24  byte
+    //   |   key  |   PAD  |      value      |backward|  PAD   |   correct layout
+    //   |   key  |   PAD  |      value      |        |backward|   how it's actually used
+    //   |<-----  value of QMap::payload() = 20 ----->|
+    QMapData::Node *backward;
+};
+
+template <class Key, class T>
+class QMap
+{
+    typedef QMapNode<Key, T> Node;
+    typedef QMapPayloadNode<Key, T> PayloadNode;
+
+    union {
+        QMapData *d;
+        QMapData::Node *e;
+    };
+
+    static inline int payload() { return sizeof(PayloadNode) - sizeof(QMapData::Node *); }
+    static inline int alignment() {
+#ifdef Q_ALIGNOF
+        return int(qMax(sizeof(void*), Q_ALIGNOF(Node)));
+#else
+        return 0;
+#endif
+    }
+    static inline Node *concrete(QMapData::Node *node) {
+        return reinterpret_cast<Node *>(reinterpret_cast<char *>(node) - payload());
+    }
+
+public:
+    inline QMap() : d(&QMapData::shared_null) { d->ref.ref(); }
+    inline QMap(const QMap<Key, T> &other) : d(other.d)
+    { d->ref.ref(); if (!d->sharable) detach(); }
+    inline ~QMap() { if (!d) return; if (!d->ref.deref()) freeData(d); }
+
+    QMap<Key, T> &operator=(const QMap<Key, T> &other);
+#ifdef Q_COMPILER_RVALUE_REFS
+    inline QMap<Key, T> &operator=(QMap<Key, T> &&other)
+    { qSwap(d, other.d); return *this; }
+#endif
+    inline void swap(QMap<Key, T> &other) { qSwap(d, other.d); }
+#ifndef QT_NO_STL
+    explicit QMap(const typename std::map<Key, T> &other);
+    std::map<Key, T> toStdMap() const;
+#endif
+
+    bool operator==(const QMap<Key, T> &other) const;
+    inline bool operator!=(const QMap<Key, T> &other) const { return !(*this == other); }
+
+    inline int size() const { return d->size; }
+
+    inline bool isEmpty() const { return d->size == 0; }
+
+    inline void detach() { if (d->ref != 1) detach_helper(); }
+    inline bool isDetached() const { return d->ref == 1; }
+    inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }
+    inline bool isSharedWith(const QMap<Key, T> &other) const { return d == other.d; }
+    inline void setInsertInOrder(bool ordered) { d->insertInOrder = ordered; }
+
+    void clear();
+
+    int remove(const Key &key);
+    T take(const Key &key);
+
+    bool contains(const Key &key) const;
+    const Key key(const T &value) const;
+    const Key key(const T &value, const Key &defaultKey) const;
+    const T value(const Key &key) const;
+    const T value(const Key &key, const T &defaultValue) const;
+    T &operator[](const Key &key);
+    const T operator[](const Key &key) const;
+
+    QList<Key> uniqueKeys() const;
+    QList<Key> keys() const;
+    QList<Key> keys(const T &value) const;
+    QList<T> values() const;
+    QList<T> values(const Key &key) const;
+    int count(const Key &key) const;
+
+    class const_iterator;
+
+    class iterator
+    {
+        friend class const_iterator;
+        QMapData::Node *i;
+
+    public:
+        typedef std::bidirectional_iterator_tag iterator_category;
+        typedef qptrdiff difference_type;
+        typedef T value_type;
+        typedef T *pointer;
+        typedef T &reference;
+
+        // ### Qt 5: get rid of 'operator Node *'
+        inline operator QMapData::Node *() const { return i; }
+        inline iterator() : i(0) { }
+        inline iterator(QMapData::Node *node) : i(node) { }
+
+        inline const Key &key() const { return concrete(i)->key; }
+        inline T &value() const { return concrete(i)->value; }
+#ifdef QT3_SUPPORT
+        inline QT3_SUPPORT T &data() const { return concrete(i)->value; }
+#endif
+        inline T &operator*() const { return concrete(i)->value; }
+        inline T *operator->() const { return &concrete(i)->value; }
+        inline bool operator==(const iterator &o) const { return i == o.i; }
+        inline bool operator!=(const iterator &o) const { return i != o.i; }
+
+        inline iterator &operator++() {
+            i = i->forward[0];
+            return *this;
+        }
+        inline iterator operator++(int) {
+            iterator r = *this;
+            i = i->forward[0];
+            return r;
+        }
+        inline iterator &operator--() {
+            i = i->backward;
+            return *this;
+        }
+        inline iterator operator--(int) {
+            iterator r = *this;
+            i = i->backward;
+            return r;
+        }
+        inline iterator operator+(int j) const
+        { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
+        inline iterator operator-(int j) const { return operator+(-j); }
+        inline iterator &operator+=(int j) { return *this = *this + j; }
+        inline iterator &operator-=(int j) { return *this = *this - j; }
+
+        // ### Qt 5: not sure this is necessary anymore
+#ifdef QT_STRICT_ITERATORS
+    private:
+#else
+    public:
+#endif
+        inline bool operator==(const const_iterator &o) const
+            { return i == o.i; }
+        inline bool operator!=(const const_iterator &o) const
+            { return i != o.i; }
+
+    private:
+        // ### Qt 5: remove
+        inline operator bool() const { return false; }
+    };
+    friend class iterator;
+
+    class const_iterator
+    {
+        friend class iterator;
+        QMapData::Node *i;
+
+    public:
+        typedef std::bidirectional_iterator_tag iterator_category;
+        typedef qptrdiff difference_type;
+        typedef T value_type;
+        typedef const T *pointer;
+        typedef const T &reference;
+
+        // ### Qt 5: get rid of 'operator Node *'
+        inline operator QMapData::Node *() const { return i; }
+        inline const_iterator() : i(0) { }
+        inline const_iterator(QMapData::Node *node) : i(node) { }
+#ifdef QT_STRICT_ITERATORS
+        explicit inline const_iterator(const iterator &o)
+#else
+        inline const_iterator(const iterator &o)
+#endif
+        { i = o.i; }
+
+        inline const Key &key() const { return concrete(i)->key; }
+        inline const T &value() const { return concrete(i)->value; }
+#ifdef QT3_SUPPORT
+        inline QT3_SUPPORT const T &data() const { return concrete(i)->value; }
+#endif
+        inline const T &operator*() const { return concrete(i)->value; }
+        inline const T *operator->() const { return &concrete(i)->value; }
+        inline bool operator==(const const_iterator &o) const { return i == o.i; }
+        inline bool operator!=(const const_iterator &o) const { return i != o.i; }
+
+        inline const_iterator &operator++() {
+            i = i->forward[0];
+            return *this;
+        }
+        inline const_iterator operator++(int) {
+            const_iterator r = *this;
+            i = i->forward[0];
+            return r;
+        }
+        inline const_iterator &operator--() {
+            i = i->backward;
+            return *this;
+        }
+        inline const_iterator operator--(int) {
+            const_iterator r = *this;
+            i = i->backward;
+            return r;
+        }
+        inline const_iterator operator+(int j) const
+        { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
+        inline const_iterator operator-(int j) const { return operator+(-j); }
+        inline const_iterator &operator+=(int j) { return *this = *this + j; }
+        inline const_iterator &operator-=(int j) { return *this = *this - j; }
+
+        // ### Qt 5: not sure this is necessary anymore
+#ifdef QT_STRICT_ITERATORS
+    private:
+        inline bool operator==(const iterator &o) { return operator==(const_iterator(o)); }
+        inline bool operator!=(const iterator &o) { return operator!=(const_iterator(o)); }
+#endif
+
+    private:
+        // ### Qt 5: remove
+        inline operator bool() const { return false; }
+    };
+    friend class const_iterator;
+
+    // STL style
+    inline iterator begin() { detach(); return iterator(e->forward[0]); }
+    inline const_iterator begin() const { return const_iterator(e->forward[0]); }
+    inline const_iterator constBegin() const { return const_iterator(e->forward[0]); }
+    inline iterator end() {
+        detach();
+        return iterator(e);
+    }
+    inline const_iterator end() const { return const_iterator(e); }
+    inline const_iterator constEnd() const { return const_iterator(e); }
+    iterator erase(iterator it);
+#ifdef QT3_SUPPORT
+    inline QT3_SUPPORT iterator remove(iterator it) { return erase(it); }
+    inline QT3_SUPPORT void erase(const Key &aKey) { remove(aKey); }
+#endif
+
+    // more Qt
+    typedef iterator Iterator;
+    typedef const_iterator ConstIterator;
+    inline int count() const { return d->size; }
+    iterator find(const Key &key);
+    const_iterator find(const Key &key) const;
+    const_iterator constFind(const Key &key) const;
+    iterator lowerBound(const Key &key);
+    const_iterator lowerBound(const Key &key) const;
+    iterator upperBound(const Key &key);
+    const_iterator upperBound(const Key &key) const;
+    iterator insert(const Key &key, const T &value);
+#ifdef QT3_SUPPORT
+    QT3_SUPPORT iterator insert(const Key &key, const T &value, bool overwrite);
+#endif
+    iterator insertMulti(const Key &key, const T &value);
+#ifdef QT3_SUPPORT
+    inline QT3_SUPPORT iterator replace(const Key &aKey, const T &aValue) { return insert(aKey, aValue); }
+#endif
+    QMap<Key, T> &unite(const QMap<Key, T> &other);
+
+    // STL compatibility
+    typedef Key key_type;
+    typedef T mapped_type;
+    typedef qptrdiff difference_type;
+    typedef int size_type;
+    inline bool empty() const { return isEmpty(); }
+
+#ifdef QT_QMAP_DEBUG
+    inline void dump() const { d->dump(); }
+#endif
+
+private:
+    void detach_helper();
+    void freeData(QMapData *d);
+    QMapData::Node *findNode(const Key &key) const;
+    QMapData::Node *mutableFindNode(QMapData::Node *update[], const Key &key) const;
+    QMapData::Node *node_create(QMapData *d, QMapData::Node *update[], const Key &key,
+                                const T &value);
+};
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::operator=(const QMap<Key, T> &other)
+{
+    if (d != other.d) {
+        QMapData* o = other.d;
+        o->ref.ref();
+        if (!d->ref.deref())
+            freeData(d);
+        d = o;
+        if (!d->sharable)
+            detach_helper();
+    }
+    return *this;
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE void QMap<Key, T>::clear()
+{
+    *this = QMap<Key, T>();
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE typename QMapData::Node *
+QMap<Key, T>::node_create(QMapData *adt, QMapData::Node *aupdate[], const Key &akey, const T &avalue)
+{
+    QMapData::Node *abstractNode = adt->node_create(aupdate, payload(), alignment());
+    QT_TRY {
+        Node *concreteNode = concrete(abstractNode);
+        new (&concreteNode->key) Key(akey);
+        QT_TRY {
+            new (&concreteNode->value) T(avalue);
+        } QT_CATCH(...) {
+            concreteNode->key.~Key();
+            QT_RETHROW;
+        }
+    } QT_CATCH(...) {
+        adt->node_delete(aupdate, payload(), abstractNode);
+        QT_RETHROW;
+    }
+
+    // clean up the update array for further insertions
+    /*
+    for (int i = 0; i <= d->topLevel; ++i) {
+        if ( aupdate[i]==reinterpret_cast<QMapData::Node *>(adt) || aupdate[i]->forward[i] != abstractNode)
+            break;
+        aupdate[i] = abstractNode;
+    }
+*/
+
+    return abstractNode;
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE QMapData::Node *QMap<Key, T>::findNode(const Key &akey) const
+{
+    QMapData::Node *cur = e;
+    QMapData::Node *next = e;
+
+    for (int i = d->topLevel; i >= 0; i--) {
+        while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))
+            cur = next;
+    }
+
+    if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
+        return next;
+    } else {
+        return e;
+    }
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE const T QMap<Key, T>::value(const Key &akey) const
+{
+    QMapData::Node *node;
+    if (d->size == 0 || (node = findNode(akey)) == e) {
+        return T();
+    } else {
+        return concrete(node)->value;
+    }
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE const T QMap<Key, T>::value(const Key &akey, const T &adefaultValue) const
+{
+    QMapData::Node *node;
+    if (d->size == 0 || (node = findNode(akey)) == e) {
+        return adefaultValue;
+    } else {
+        return concrete(node)->value;
+    }
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE const T QMap<Key, T>::operator[](const Key &akey) const
+{
+    return value(akey);
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE T &QMap<Key, T>::operator[](const Key &akey)
+{
+    detach();
+
+    QMapData::Node *update[QMapData::LastLevel + 1];
+    QMapData::Node *node = mutableFindNode(update, akey);
+    if (node == e)
+        node = node_create(d, update, akey, T());
+    return concrete(node)->value;
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE int QMap<Key, T>::count(const Key &akey) const
+{
+    int cnt = 0;
+    QMapData::Node *node = findNode(akey);
+    if (node != e) {
+        do {
+            ++cnt;
+            node = node->forward[0];
+        } while (node != e && !qMapLessThanKey<Key>(akey, concrete(node)->key));
+    }
+    return cnt;
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE bool QMap<Key, T>::contains(const Key &akey) const
+{
+    return findNode(akey) != e;
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insert(const Key &akey,
+                                                                       const T &avalue)
+{
+    detach();
+
+    QMapData::Node *update[QMapData::LastLevel + 1];
+    QMapData::Node *node = mutableFindNode(update, akey);
+    if (node == e) {
+        node = node_create(d, update, akey, avalue);
+    } else {
+        concrete(node)->value = avalue;
+    }
+    return iterator(node);
+}
+
+#ifdef QT3_SUPPORT
+template <class Key, class T>
+Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insert(const Key &akey,
+                                                                       const T &avalue,
+                                                                       bool aoverwrite)
+{
+    detach();
+
+    QMapData::Node *update[QMapData::LastLevel + 1];
+    QMapData::Node *node = mutableFindNode(update, akey);
+    if (node == e) {
+        node = node_create(d, update, akey, avalue);
+    } else {
+        if (aoverwrite)
+            concrete(node)->value = avalue;
+    }
+    return iterator(node);
+}
+#endif
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const Key &akey,
+                                                                            const T &avalue)
+{
+    detach();
+
+    QMapData::Node *update[QMapData::LastLevel + 1];
+    mutableFindNode(update, akey);
+    return iterator(node_create(d, update, akey, avalue));
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::find(const Key &akey) const
+{
+    return const_iterator(findNode(akey));
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::constFind(const Key &akey) const
+{
+    return const_iterator(findNode(akey));
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::find(const Key &akey)
+{
+    detach();
+    return iterator(findNode(akey));
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::unite(const QMap<Key, T> &other)
+{
+    QMap<Key, T> copy(other);
+    const_iterator it = copy.constEnd();
+    const const_iterator b = copy.constBegin();
+    while (it != b) {
+        --it;
+        insertMulti(it.key(), it.value());
+    }
+    return *this;
+}
+
+template <class Key, class T>
+Q_OUTOFLINE_TEMPLATE void QMap<Key, T>::freeData(QMapData *x)
+{
+    if (QTypeInfo<Key>::isComplex || QTypeInfo<T>::isComplex) {
+        QMapData *cur = x;
+        QMapData *next = cur->forward[0];
+        while (next != x) {
+            cur = next;
+            next = cur->forward[0];
+#if defined(_MSC_VER)
+#pragma warning(disable:4189)
+#endif
+            Node *concreteNode = concrete(reinterpret_cast<QMapData::Node *>(cur));
+            concreteNode->key.~Key();
+            concreteNode->value.~T();
+#if defined(_MSC_VER)
+#pragma warning(default:4189)
+#endif
+        }
+    }
+    x->continueFreeData(payload());
+}
+
+template <class Key, class T>
+Q_OUTOFLINE_TEMPLATE int QMap<Key, T>::remove(const Key &akey)
+{
+    detach();
+
+    QMapData::Node *update[QMapData::LastLevel + 1];
+    QMapData::Node *cur = e;
+    QMapData::Node *next = e;
+    int oldSize = d->size;
+
+    for (int i = d->topLevel; i >= 0; i--) {
+        while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))
+            cur = next;
+        update[i] = cur;
+    }
+
+    if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
+        bool deleteNext = true;
+        do {
+            cur = next;
+            next = cur->forward[0];
+            deleteNext = (next != e && !qMapLessThanKey<Key>(concrete(cur)->key, concrete(next)->key));
+            concrete(cur)->key.~Key();
+            concrete(cur)->value.~T();
+            d->node_delete(update, payload(), cur);
+        } while (deleteNext);
+    }
+    return oldSize - d->size;
+}
+
+template <class Key, class T>
+Q_OUTOFLINE_TEMPLATE T QMap<Key, T>::take(const Key &akey)
+{
+    detach();
+
+    QMapData::Node *update[QMapData::LastLevel + 1];
+    QMapData::Node *cur = e;
+    QMapData::Node *next = e;
+
+    for (int i = d->topLevel; i >= 0; i--) {
+        while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))
+            cur = next;
+        update[i] = cur;
+    }
+
+    if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
+        T t = concrete(next)->value;
+        concrete(next)->key.~Key();
+        concrete(next)->value.~T();
+        d->node_delete(update, payload(), next);
+        return t;
+    }
+    return T();
+}
+
+template <class Key, class T>
+Q_OUTOFLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::erase(iterator it)
+{
+    QMapData::Node *update[QMapData::LastLevel + 1];
+    QMapData::Node *cur = e;
+    QMapData::Node *next = e;
+
+    if (it == iterator(e))
+        return it;
+
+    for (int i = d->topLevel; i >= 0; i--) {
+        while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, it.key()))
+            cur = next;
+        update[i] = cur;
+    }
+
+    while (next != e) {
+        cur = next;
+        next = cur->forward[0];
+        if (cur == it) {
+            concrete(cur)->key.~Key();
+            concrete(cur)->value.~T();
+            d->node_delete(update, payload(), cur);
+            return iterator(next);
+        }
+
+        for (int i = 0; i <= d->topLevel; ++i) {
+            if (update[i]->forward[i] != cur)
+                break;
+            update[i] = cur;
+        }
+    }
+    return end();
+}
+
+template <class Key, class T>
+Q_OUTOFLINE_TEMPLATE void QMap<Key, T>::detach_helper()
+{
+    union { QMapData *d; QMapData::Node *e; } x;
+    x.d = QMapData::createData(alignment());
+    if (d->size) {
+        x.d->insertInOrder = true;
+        QMapData::Node *update[QMapData::LastLevel + 1];
+        QMapData::Node *cur = e->forward[0];
+        update[0] = x.e;
+        while (cur != e) {
+            QT_TRY {
+                Node *concreteNode = concrete(cur);
+                node_create(x.d, update, concreteNode->key, concreteNode->value);
+            } QT_CATCH(...) {
+                freeData(x.d);
+                QT_RETHROW;
+            }
+            cur = cur->forward[0];
+        }
+        x.d->insertInOrder = false;
+    }
+    if (!d->ref.deref())
+        freeData(d);
+    d = x.d;
+}
+
+template <class Key, class T>
+Q_OUTOFLINE_TEMPLATE QMapData::Node *QMap<Key, T>::mutableFindNode(QMapData::Node *aupdate[],
+                                                                   const Key &akey) const
+{
+    QMapData::Node *cur = e;
+    QMapData::Node *next = e;
+
+    for (int i = d->topLevel; i >= 0; i--) {
+        while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))
+            cur = next;
+        aupdate[i] = cur;
+    }
+    if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
+        return next;
+    } else {
+        return e;
+    }
+}
+
+template <class Key, class T>
+Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::uniqueKeys() const
+{
+    QList<Key> res;
+    res.reserve(size()); // May be too much, but assume short lifetime
+    const_iterator i = begin();
+    if (i != end()) {
+        for (;;) {
+            const Key &aKey = i.key();
+            res.append(aKey);
+            do {
+                if (++i == end())
+                    goto break_out_of_outer_loop;
+            } while (!(aKey < i.key()));   // loop while (key == i.key())
+        }
+    }
+break_out_of_outer_loop:
+    return res;
+}
+
+template <class Key, class T>
+Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys() const
+{
+    QList<Key> res;
+    res.reserve(size());
+    const_iterator i = begin();
+    while (i != end()) {
+        res.append(i.key());
+        ++i;
+    }
+    return res;
+}
+
+template <class Key, class T>
+Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys(const T &avalue) const
+{
+    QList<Key> res;
+    const_iterator i = begin();
+    while (i != end()) {
+        if (i.value() == avalue)
+            res.append(i.key());
+        ++i;
+    }
+    return res;
+}
+
+template <class Key, class T>
+Q_OUTOFLINE_TEMPLATE const Key QMap<Key, T>::key(const T &avalue) const
+{
+    return key(avalue, Key());
+}
+
+template <class Key, class T>
+Q_OUTOFLINE_TEMPLATE const Key QMap<Key, T>::key(const T &avalue, const Key &defaultKey) const
+{
+    const_iterator i = begin();
+    while (i != end()) {
+        if (i.value() == avalue)
+            return i.key();
+        ++i;
+    }
+
+    return defaultKey;
+}
+
+template <class Key, class T>
+Q_OUTOFLINE_TEMPLATE QList<T> QMap<Key, T>::values() const
+{
+    QList<T> res;
+    res.reserve(size());
+    const_iterator i = begin();
+    while (i != end()) {
+        res.append(i.value());
+        ++i;
+    }
+    return res;
+}
+
+template <class Key, class T>
+Q_OUTOFLINE_TEMPLATE QList<T> QMap<Key, T>::values(const Key &akey) const
+{
+    QList<T> res;
+    QMapData::Node *node = findNode(akey);
+    if (node != e) {
+        do {
+            res.append(concrete(node)->value);
+            node = node->forward[0];
+        } while (node != e && !qMapLessThanKey<Key>(akey, concrete(node)->key));
+    }
+    return res;
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator
+QMap<Key, T>::lowerBound(const Key &akey) const
+{
+    QMapData::Node *update[QMapData::LastLevel + 1];
+    mutableFindNode(update, akey);
+    return const_iterator(update[0]->forward[0]);
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::lowerBound(const Key &akey)
+{
+    detach();
+    return static_cast<QMapData::Node *>(const_cast<const QMap *>(this)->lowerBound(akey));
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator
+QMap<Key, T>::upperBound(const Key &akey) const
+{
+    QMapData::Node *update[QMapData::LastLevel + 1];
+    mutableFindNode(update, akey);
+    QMapData::Node *node = update[0]->forward[0];
+    while (node != e && !qMapLessThanKey<Key>(akey, concrete(node)->key))
+        node = node->forward[0];
+    return const_iterator(node);
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::upperBound(const Key &akey)
+{
+    detach();
+    return static_cast<QMapData::Node *>(const_cast<const QMap *>(this)->upperBound(akey));
+}
+
+template <class Key, class T>
+Q_OUTOFLINE_TEMPLATE bool QMap<Key, T>::operator==(const QMap<Key, T> &other) const
+{
+    if (size() != other.size())
+        return false;
+    if (d == other.d)
+        return true;
+
+    const_iterator it1 = begin();
+    const_iterator it2 = other.begin();
+
+    while (it1 != end()) {
+        if (!(it1.value() == it2.value()) || qMapLessThanKey(it1.key(), it2.key()) || qMapLessThanKey(it2.key(), it1.key()))
+            return false;
+        ++it2;
+        ++it1;
+    }
+    return true;
+}
+
+#ifndef QT_NO_STL
+template <class Key, class T>
+Q_OUTOFLINE_TEMPLATE QMap<Key, T>::QMap(const std::map<Key, T> &other)
+{
+    d = QMapData::createData(alignment());
+    d->insertInOrder = true;
+    typename std::map<Key,T>::const_iterator it = other.end();
+    while (it != other.begin()) {
+        --it;
+        insert((*it).first, (*it).second);
+    }
+    d->insertInOrder = false;
+}
+
+template <class Key, class T>
+Q_OUTOFLINE_TEMPLATE std::map<Key, T> QMap<Key, T>::toStdMap() const
+{
+    std::map<Key, T> map;
+    const_iterator it = end();
+    while (it != begin()) {
+        --it;
+        map.insert(std::pair<Key, T>(it.key(), it.value()));
+    }
+    return map;
+}
+
+#endif // QT_NO_STL
+
+template <class Key, class T>
+class QMultiMap : public QMap<Key, T>
+{
+public:
+    QMultiMap() {}
+    QMultiMap(const QMap<Key, T> &other) : QMap<Key, T>(other) {}
+    inline void swap(QMultiMap<Key, T> &other) { QMap<Key, T>::swap(other); }
+
+    inline typename QMap<Key, T>::iterator replace(const Key &key, const T &value)
+    { return QMap<Key, T>::insert(key, value); }
+    inline typename QMap<Key, T>::iterator insert(const Key &key, const T &value)
+    { return QMap<Key, T>::insertMulti(key, value); }
+
+    inline QMultiMap &operator+=(const QMultiMap &other)
+    { this->unite(other); return *this; }
+    inline QMultiMap operator+(const QMultiMap &other) const
+    { QMultiMap result = *this; result += other; return result; }
+
+#if !defined(Q_NO_USING_KEYWORD) && !defined(Q_CC_RVCT)
+    // RVCT compiler doesn't handle using-keyword right when used functions are overloaded in child class
+    using QMap<Key, T>::contains;
+    using QMap<Key, T>::remove;
+    using QMap<Key, T>::count;
+    using QMap<Key, T>::find;
+    using QMap<Key, T>::constFind;
+#else
+    inline bool contains(const Key &key) const
+    { return QMap<Key, T>::contains(key); }
+    inline int remove(const Key &key)
+    { return QMap<Key, T>::remove(key); }
+    inline int count(const Key &key) const
+    { return QMap<Key, T>::count(key); }
+    inline int count() const
+    { return QMap<Key, T>::count(); }
+    inline typename QMap<Key, T>::iterator find(const Key &key)
+    { return QMap<Key, T>::find(key); }
+    inline typename QMap<Key, T>::const_iterator find(const Key &key) const
+    { return QMap<Key, T>::find(key); }
+    inline typename QMap<Key, T>::const_iterator constFind(const Key &key) const
+    { return QMap<Key, T>::constFind(key); }
+#endif
+
+    bool contains(const Key &key, const T &value) const;
+
+    int remove(const Key &key, const T &value);
+
+    int count(const Key &key, const T &value) const;
+
+    typename QMap<Key, T>::iterator find(const Key &key, const T &value) {
+        typename QMap<Key, T>::iterator i(find(key));
+        typename QMap<Key, T>::iterator end(this->end());
+        while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
+            if (i.value() == value)
+                return i;
+            ++i;
+        }
+        return end;
+    }
+    typename QMap<Key, T>::const_iterator find(const Key &key, const T &value) const {
+        typename QMap<Key, T>::const_iterator i(constFind(key));
+        typename QMap<Key, T>::const_iterator end(QMap<Key, T>::constEnd());
+        while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
+            if (i.value() == value)
+                return i;
+            ++i;
+        }
+        return end;
+    }
+    typename QMap<Key, T>::const_iterator constFind(const Key &key, const T &value) const
+        { return find(key, value); }
+private:
+    T &operator[](const Key &key);
+    const T operator[](const Key &key) const;
+};
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE bool QMultiMap<Key, T>::contains(const Key &key, const T &value) const
+{
+    return constFind(key, value) != QMap<Key, T>::constEnd();
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE int QMultiMap<Key, T>::remove(const Key &key, const T &value)
+{
+    int n = 0;
+    typename QMap<Key, T>::iterator i(find(key));
+    typename QMap<Key, T>::iterator end(QMap<Key, T>::end());
+    while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
+        if (i.value() == value) {
+            i = this->erase(i);
+            ++n;
+        } else {
+            ++i;
+        }
+    }
+    return n;
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE int QMultiMap<Key, T>::count(const Key &key, const T &value) const
+{
+    int n = 0;
+    typename QMap<Key, T>::const_iterator i(constFind(key));
+    typename QMap<Key, T>::const_iterator end(QMap<Key, T>::constEnd());
+    while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
+        if (i.value() == value)
+            ++n;
+        ++i;
+    }
+    return n;
+}
+
+Q_DECLARE_ASSOCIATIVE_ITERATOR(Map)
+Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Map)
+
+QT_END_NAMESPACE
+
+QT_END_HEADER
+
+#endif // QMAP_H