Rewrite QMap to use a RB tree

QMap used to use a skiplist in Qt 4.x, which has variable
sized nodes and we can thus not optimise using custom
allocators.

The rewrite now uses a red-black tree, and all allocations
and tree operations happen in the cpp file. This will allow
us to introduce custom allocation schemes in later versions
of Qt.

Added some more tests and a benchmark. Memory consumption
of the new QMap implementation is pretty much the same as before.
Performance of insertion and lookup has increased by 10-30%. iteration
is slower, but still extremely fast and should not matter compared
to the work usually done when iterating.

Change-Id: I8796c0e4b207d01111e2ead7ae55afb464dd88f5
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>

2 files changed, 715 insertions, 552 deletions

diff --git a/src/corelib/tools/qmap.cpp b/src/corelib/tools/qmap.cpp
index b585bdbbc8..90521d343c 100644
--- a/src/corelib/tools/qmap.cpp
+++ b/src/corelib/tools/qmap.cpp
@@ -50,170 +50,316 @@
 
 QT_BEGIN_NAMESPACE
 
-const QMapData QMapData::shared_null = {
-    const_cast<QMapData *>(&shared_null),
-    { const_cast<QMapData *>(&shared_null), 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
-    Q_REFCOUNT_INITIALIZE_STATIC, 0, 0, 0, false, true, false, 0
-};
+const QMapDataBase QMapDataBase::shared_null = { Q_REFCOUNT_INITIALIZE_STATIC, 0, { 0, 0, 0 } };
 
-QMapData *QMapData::createData(int alignment)
+const QMapNodeBase *QMapNodeBase::nextNode() const
 {
-    QMapData *d = new QMapData;
-    Q_CHECK_PTR(d);
-    Node *e = reinterpret_cast<Node *>(d);
-    e->backward = e;
-    e->forward[0] = e;
-    d->ref.initializeOwned();
-    d->topLevel = 0;
-    d->size = 0;
-    d->randomBits = 0;
-    d->insertInOrder = false;
-    d->sharable = true;
-    d->strictAlignment = alignment > 8;
-    d->reserved = 0;
-    return d;
+    const QMapNodeBase *n = this;
+    if (n->right) {
+        n = n->right;
+        while (n->left)
+            n = n->left;
+    } else {
+        const QMapNodeBase *y = n->parent();
+        while (y && n == y->right) {
+            n = y;
+            y = n->parent();
+        }
+        n = y;
+    }
+    return n;
 }
 
-void QMapData::continueFreeData(int offset)
+const QMapNodeBase *QMapNodeBase::previousNode() const
 {
-    Node *e = reinterpret_cast<Node *>(this);
-    Node *cur = e->forward[0];
-    Node *prev;
-    while (cur != e) {
-        prev = cur;
-        cur = cur->forward[0];
-        if (strictAlignment)
-            qFreeAligned(reinterpret_cast<char *>(prev) - offset);
-        else
-            free(reinterpret_cast<char *>(prev) - offset);
+    const QMapNodeBase *n = this;
+    if (n->left) {
+        n = n->left;
+        while (n->right)
+            n = n->right;
+    } else {
+        const QMapNodeBase *y = n->parent();
+        while (y && n == y->left) {
+            n = y;
+            y = n->parent();
+        }
+        n = y;
     }
-    delete this;
+    return n;
 }
 
-/*!
-    Creates a new node inside the data structure.
-
-    \a update is an array with pointers to the node after which the new node
-    should be inserted. Because of the strange skip list data structure there
-    could be several pointers to this node on different levels.
-    \a offset is an amount of bytes that needs to reserved just before the
-    QMapData::Node structure.
-
-    \a alignment dictates the alignment for the data.
 
-    \internal
-    \since 4.6
-*/
-QMapData::Node *QMapData::node_create(Node *update[], int offset, int alignment)
+void QMapDataBase::rotateLeft(QMapNodeBase *x)
 {
-    int level = 0;
-    uint mask = (1 << Sparseness) - 1;
-
-    while ((randomBits & mask) == mask && level < LastLevel) {
-        ++level;
-        mask <<= Sparseness;
-    }
-
-    if (level > topLevel) {
-        Node *e = reinterpret_cast<Node *>(this);
-        level = ++topLevel;
-        e->forward[level] = e;
-        update[level] = e;
-    }
-
-    ++randomBits;
-    if (level == 3 && !insertInOrder)
-        randomBits = qrand();
+    QMapNodeBase *&root = header.left;
+    QMapNodeBase *y = x->right;
+    x->right = y->left;
+    if (y->left != 0)
+        y->left->setParent(x);
+    y->setParent(x->parent());
+    if (x == root)
+        root = y;
+    else if (x == x->parent()->left)
+        x->parent()->left = y;
+    else
+        x->parent()->right = y;
+    y->left = x;
+    x->setParent(y);
+}
 
-    void *concreteNode = strictAlignment ?
-                         qMallocAligned(offset + sizeof(Node) + level * sizeof(Node *), alignment) :
-                         malloc(offset + sizeof(Node) + level * sizeof(Node *));
-    Q_CHECK_PTR(concreteNode);
 
-    Node *abstractNode = reinterpret_cast<Node *>(reinterpret_cast<char *>(concreteNode) + offset);
+void QMapDataBase::rotateRight(QMapNodeBase *x)
+{
+    QMapNodeBase *&root = header.left;
+    QMapNodeBase *y = x->left;
+    x->left = y->right;
+    if (y->right != 0)
+        y->right->setParent(x);
+    y->setParent(x->parent());
+    if (x == root)
+        root = y;
+    else if (x == x->parent()->right)
+        x->parent()->right = y;
+    else
+        x->parent()->left = y;
+    y->right = x;
+    x->setParent(y);
+}
 
-    abstractNode->backward = update[0];
-    update[0]->forward[0]->backward = abstractNode;
 
-    for (int i = level; i >= 0; i--) {
-        abstractNode->forward[i] = update[i]->forward[i];
-        update[i]->forward[i] = abstractNode;
-        update[i] = abstractNode;
+void QMapDataBase::rebalance(QMapNodeBase *x)
+{
+    QMapNodeBase *&root = header.left;
+    x->setColor(QMapNodeBase::Red);
+    while (x != root && x->parent()->color() == QMapNodeBase::Red) {
+        if (x->parent() == x->parent()->parent()->left) {
+            QMapNodeBase *y = x->parent()->parent()->right;
+            if (y && y->color() == QMapNodeBase::Red) {
+                x->parent()->setColor(QMapNodeBase::Black);
+                y->setColor(QMapNodeBase::Black);
+                x->parent()->parent()->setColor(QMapNodeBase::Red);
+                x = x->parent()->parent();
+            } else {
+                if (x == x->parent()->right) {
+                    x = x->parent();
+                    rotateLeft(x);
+                }
+                x->parent()->setColor(QMapNodeBase::Black);
+                x->parent()->parent()->setColor(QMapNodeBase::Red);
+                rotateRight (x->parent()->parent());
+            }
+        } else {
+            QMapNodeBase *y = x->parent()->parent()->left;
+            if (y && y->color() == QMapNodeBase::Red) {
+                x->parent()->setColor(QMapNodeBase::Black);
+                y->setColor(QMapNodeBase::Black);
+                x->parent()->parent()->setColor(QMapNodeBase::Red);
+                x = x->parent()->parent();
+            } else {
+                if (x == x->parent()->left) {
+                    x = x->parent();
+                    rotateRight(x);
+                }
+                x->parent()->setColor(QMapNodeBase::Black);
+                x->parent()->parent()->setColor(QMapNodeBase::Red);
+                rotateLeft(x->parent()->parent());
+            }
+        }
     }
-    ++size;
-    return abstractNode;
+    root->setColor(QMapNodeBase::Black);
 }
 
-void QMapData::node_delete(Node *update[], int offset, Node *node)
+void QMapDataBase::freeNodeAndRebalance(QMapNodeBase *z)
 {
-    node->forward[0]->backward = node->backward;
-
-    for (int i = 0; i <= topLevel; ++i) {
-        if (update[i]->forward[i] != node)
-            break;
-        update[i]->forward[i] = node->forward[i];
+    QMapNodeBase *&root = header.left;
+    QMapNodeBase *y = z;
+    QMapNodeBase *x;
+    QMapNodeBase *x_parent;
+    if (y->left == 0) {
+        x = y->right;
+    } else {
+        if (y->right == 0) {
+            x = y->left;
+        } else {
+            y = y->right;
+            while (y->left != 0)
+                y = y->left;
+            x = y->right;
+        }
     }
+    if (y != z) {
+        z->left->setParent(y);
+        y->left = z->left;
+        if (y != z->right) {
+            x_parent = y->parent();
+            if (x)
+                x->setParent(y->parent());
+            y->parent()->left = x;
+            y->right = z->right;
+            z->right->setParent(y);
+        } else {
+            x_parent = y;
+        }
+        if (root == z)
+            root = y;
+        else if (z->parent()->left == z)
+            z->parent()->left = y;
+        else
+            z->parent()->right = y;
+        y->setParent(z->parent());
+        // Swap the colors
+        QMapNodeBase::Color c = y->color();
+        y->setColor(z->color());
+        z->setColor(c);
+        y = z;
+    } else {
+        x_parent = y->parent();
+        if (x)
+            x->setParent(y->parent());
+        if (root == z)
+            root = x;
+        else if (z->parent()->left == z)
+            z->parent()->left = x;
+        else
+            z->parent()->right = x;
+    }
+    if (y->color() != QMapNodeBase::Red) {
+        while (x != root && (x == 0 || x->color() == QMapNodeBase::Black)) {
+            if (x == x_parent->left) {
+                QMapNodeBase *w = x_parent->right;
+                if (w->color() == QMapNodeBase::Red) {
+                    w->setColor(QMapNodeBase::Black);
+                    x_parent->setColor(QMapNodeBase::Red);
+                    rotateLeft(x_parent);
+                    w = x_parent->right;
+                }
+                if ((w->left == 0 || w->left->color() == QMapNodeBase::Black) &&
+                    (w->right == 0 || w->right->color() == QMapNodeBase::Black)) {
+                    w->setColor(QMapNodeBase::Red);
+                    x = x_parent;
+                    x_parent = x_parent->parent();
+                } else {
+                    if (w->right == 0 || w->right->color() == QMapNodeBase::Black) {
+                        if (w->left)
+                            w->left->setColor(QMapNodeBase::Black);
+                        w->setColor(QMapNodeBase::Red);
+                        rotateRight(w);
+                        w = x_parent->right;
+                    }
+                    w->setColor(x_parent->color());
+                    x_parent->setColor(QMapNodeBase::Black);
+                    if (w->right)
+                        w->right->setColor(QMapNodeBase::Black);
+                    rotateLeft(x_parent);
+                    break;
+                }
+            } else {
+            QMapNodeBase *w = x_parent->left;
+            if (w->color() == QMapNodeBase::Red) {
+                w->setColor(QMapNodeBase::Black);
+                x_parent->setColor(QMapNodeBase::Red);
+                rotateRight(x_parent);
+                w = x_parent->left;
+            }
+            if ((w->right == 0 || w->right->color() == QMapNodeBase::Black) &&
+                (w->left == 0 || w->left->color() == QMapNodeBase::Black)) {
+                w->setColor(QMapNodeBase::Red);
+                x = x_parent;
+                x_parent = x_parent->parent();
+            } else {
+                if (w->left == 0 || w->left->color() == QMapNodeBase::Black) {
+                    if (w->right)
+                        w->right->setColor(QMapNodeBase::Black);
+                    w->setColor(QMapNodeBase::Red);
+                    rotateLeft(w);
+                    w = x_parent->left;
+                }
+                w->setColor(x_parent->color());
+                x_parent->setColor(QMapNodeBase::Black);
+                if (w->left)
+                    w->left->setColor(QMapNodeBase::Black);
+                rotateRight(x_parent);
+                break;
+            }
+        }
+    }
+    if (x)
+        x->setColor(QMapNodeBase::Black);
+    }
+    free(y);
     --size;
-    if (strictAlignment)
-        qFreeAligned(reinterpret_cast<char *>(node) - offset);
-    else
-        free(reinterpret_cast<char *>(node) - offset);
 }
 
-#ifdef QT_QMAP_DEBUG
+static inline int qMapAlignmentThreshold()
+{
+    // malloc on 32-bit platforms should return pointers that are 8-byte
+    // aligned or more while on 64-bit platforms they should be 16-byte aligned
+    // or more
+    return 2 * sizeof(void*);
+}
 
-uint QMapData::adjust_ptr(Node *node)
+static inline void *qMapAllocate(int alloc, int alignment)
 {
-    if (node == reinterpret_cast<Node *>(this)) {
-       return (uint)0xDEADBEEF;
-    } else {
-        return (uint)node;
-    }
+    return alignment > qMapAlignmentThreshold()
+        ? qMallocAligned(alloc, alignment)
+        : ::malloc(alloc);
 }
 
-void QMapData::dump()
+static inline void qMapDeallocate(QMapNodeBase *node, int alignment)
 {
-    qDebug("Map data (ref = %d, size = %d, randomBits = %#.8x)", int(ref), size, randomBits);
+    if (alignment > qMapAlignmentThreshold())
+        qFreeAligned(node);
+    else
+        ::free(node);
+}
 
-    QString preOutput;
-    QVector<QString> output(topLevel + 1);
-    Node *e = reinterpret_cast<Node *>(this);
+QMapNodeBase *QMapDataBase::createNode(int alloc, int alignment, QMapNodeBase *parent, bool left)
+{
+    QMapNodeBase *node = static_cast<QMapNodeBase *>(qMapAllocate(alloc, alignment));
+    Q_CHECK_PTR(node);
 
-    QString str;
-    str.sprintf("    %.8x", adjust_ptr(reinterpret_cast<Node *>(this)));
-    preOutput += str;
+    memset(node, 0, alloc);
+    ++size;
 
-    Node *update[LastLevel + 1];
-    for (int i = 0; i <= topLevel; ++i) {
-        str.sprintf("%d: [%.8x] -", i, adjust_ptr(reinterpret_cast<Node *>(forward[i])));
-        output[i] += str;
-        update[i] = reinterpret_cast<Node *>(forward[i]);
+    if (parent) {
+        if (left) {
+            parent->left = node;
+        } else {
+            parent->right = node;
+        }
+        node->setParent(parent);
+        rebalance(node);
     }
+    return node;
+}
+
+void QMapDataBase::freeTree(QMapNodeBase *root, int alignment)
+{
+    if (root->left)
+        freeTree(root->left, alignment);
+    if (root->right)
+        freeTree(root->right, alignment);
+    qMapDeallocate(root, alignment);
+}
 
-    Node *node = reinterpret_cast<Node *>(forward[0]);
-    while (node != e) {
-        int level = 0;
-        while (level < topLevel && update[level + 1] == node)
-            ++level;
+QMapDataBase *QMapDataBase::createData()
+{
+    QMapDataBase *d = new QMapDataBase;
+
+    d->ref.initializeOwned();
+    d->size = 0;
 
-        str.sprintf("       %.8x", adjust_ptr(node));
-        preOutput += str;
+    d->header.p = 0;
+    d->header.left = 0;
+    d->header.right = 0;
 
-        for (int i = 0; i <= level; ++i) {
-            str.sprintf("-> [%.8x] -", adjust_ptr(node->forward[i]));
-            output[i] += str;
-            update[i] = node->forward[i];
-        }
-        for (int j = level + 1; j <= topLevel; ++j)
-            output[j] += QLatin1String("---------------");
-        node = node->forward[0];
-    }
+    return d;
+}
 
-    qDebug("%s", preOutput.ascii());
-    for (int i = 0; i <= topLevel; ++i)
-        qDebug("%s", output[i].ascii());
+void QMapDataBase::freeData(QMapDataBase *d)
+{
+    delete d;
 }
-#endif
 
 /*!
     \class QMap
@@ -482,11 +628,6 @@ void QMapData::dump()
     \internal
 */
 
-/*! \fn void QMap::setInsertInOrder(bool sharable)
-
-    \internal
-*/
-
 /*! \fn void QMap::clear()
 
     Removes all items from the map.
@@ -529,22 +670,21 @@ void QMapData::dump()
 
 /*! \fn const T QMap::value(const Key &key) const
 
-    Returns the value associated with the key \a key.
-
-    If the map contains no item with key \a key, the function
-    returns a \l{default-constructed value}. If there are multiple
-    items for \a key in the map, the value of the most recently
-    inserted one is returned.
-
-    \sa key(), values(), contains(), operator[]()
 */
 
 /*! \fn const T QMap::value(const Key &key, const T &defaultValue) const
 
     \overload
 
+    Returns the value associated with the key \a key.
+
     If the map contains no item with key \a key, the function returns
-    \a defaultValue.
+    \a defaultValue. If no \a defaultValue is specified, the function
+    returns a \l{default-constructed value}. If there are multiple
+    items for \a key in the map, the value of the most recently
+    inserted one is returned.
+
+    \sa key(), values(), contains(), operator[]()
 */
 
 /*! \fn T &QMap::operator[](const Key &key)
@@ -606,32 +746,21 @@ void QMapData::dump()
     by value.
 */
 
-/*! \fn Key QMap::key(const T &value) const
-
-    Returns the first key with value \a value.
-
-    If the map contains no item with value \a value, the function
-    returns a \link {default-constructed value} default-constructed
-    key \endlink.
-
-    This function can be slow (\l{linear time}), because QMap's
-    internal data structure is optimized for fast lookup by key, not
-    by value.
-
-    \sa value(), keys()
-*/
-
 /*!
     \fn Key QMap::key(const T &value, const Key &defaultKey) const
     \since 4.3
     \overload
 
     Returns the first key with value \a value, or \a defaultKey if
-    the map contains no item with value \a value.
+    the map contains no item with value \a value. If no \a defaultKey
+    is provided the function returns a \link {default-constructed value}
+    default-constructed key \endlink.
 
     This function can be slow (\l{linear time}), because QMap's
     internal data structure is optimized for fast lookup by key, not
     by value.
+
+    \sa value(), keys()
 */
 
 /*! \fn QList<T> QMap::values() const
diff --git a/src/corelib/tools/qmap.h b/src/corelib/tools/qmap.h
index dbbbcce162..3f46a8ad1e 100644
--- a/src/corelib/tools/qmap.h
+++ b/src/corelib/tools/qmap.h
@@ -45,6 +45,11 @@
 #include <QtCore/qiterator.h>
 #include <QtCore/qlist.h>
 #include <QtCore/qrefcount.h>
+#include <QtCore/qpair.h>
+
+#ifdef Q_MAP_DEBUG
+#include <QtCore/qdebug.h>
+#endif
 
 #ifndef QT_NO_STL
 #include <map>
@@ -56,39 +61,6 @@ QT_BEGIN_HEADER
 
 QT_BEGIN_NAMESPACE
 
-
-struct Q_CORE_EXPORT QMapData
-{
-    struct Node {
-        Node *backward;
-        Node *forward[1];
-    };
-    enum { LastLevel = 11, Sparseness = 3 };
-
-    QMapData *backward;
-    QMapData *forward[QMapData::LastLevel + 1];
-    QtPrivate::RefCount ref;
-    int topLevel;
-    int size;
-    uint randomBits;
-    uint insertInOrder : 1;
-    uint sharable : 1;
-    uint strictAlignment : 1;
-    uint reserved : 29;
-
-    static QMapData *createData(int alignment);
-    void continueFreeData(int offset);
-    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 const QMapData shared_null;
-};
-
-
 /*
     QMap uses qMapLessThanKey() to compare keys. The default
     implementation uses operator<(). For pointer types,
@@ -104,85 +76,275 @@ template <class Key> inline bool qMapLessThanKey(const Key &key1, const Key &key
     return key1 < key2;
 }
 
-template <class Ptr> inline bool qMapLessThanKey(Ptr *key1, Ptr *key2)
+template <class Ptr> inline bool qMapLessThanKey(const Ptr *key1, const Ptr *key2)
 {
-    Q_ASSERT(sizeof(quintptr) == sizeof(Ptr *));
+    Q_STATIC_ASSERT(sizeof(quintptr) == sizeof(const Ptr *));
     return quintptr(key1) < quintptr(key2);
 }
 
-template <class Ptr> inline bool qMapLessThanKey(const Ptr *key1, const Ptr *key2)
+struct QMapDataBase;
+template <class Key, class T> struct QMapData;
+
+struct Q_CORE_EXPORT QMapNodeBase
 {
-    Q_ASSERT(sizeof(quintptr) == sizeof(const Ptr *));
-    return quintptr(key1) < quintptr(key2);
-}
+    quintptr p;
+    QMapNodeBase *left;
+    QMapNodeBase *right;
+
+    enum Color { Red = 0, Black = 1 };
+    enum { Mask = 3 }; // reserve the second bit as well
+
+    const QMapNodeBase *nextNode() const;
+    QMapNodeBase *nextNode() { return const_cast<QMapNodeBase *>(const_cast<const QMapNodeBase *>(this)->nextNode()); }
+    const QMapNodeBase *previousNode() const;
+    QMapNodeBase *previousNode() { return const_cast<QMapNodeBase *>(const_cast<const QMapNodeBase *>(this)->previousNode()); }
+
+    Color color() const { return Color(p & 1); }
+    void setColor(Color c) { if (c == Black) p |= Black; else p &= ~Black; }
+    QMapNodeBase *parent() const { return reinterpret_cast<QMapNodeBase *>(p & ~Mask); }
+    void setParent(QMapNodeBase *pp) { p = (p & Mask) | quintptr(pp); }
+
+    QMapNodeBase *minimumNode() { QMapNodeBase *n = this; while (n->left) n = n->left; return n; }
+    QMapNodeBase *maximumNode() { QMapNodeBase *n = this; while (n->right) n = n->right; return n; }
+    const QMapNodeBase *minimumNode() const { const QMapNodeBase *n = this; while (n->left) n = n->left; return n; }
+    const QMapNodeBase *maximumNode() const { const QMapNodeBase *n = this; while (n->right) n = n->right; return n; }
+};
 
 template <class Key, class T>
-struct QMapNode {
+struct QMapNode : public QMapNodeBase
+{
     Key key;
     T value;
 
+    inline QMapNode *leftNode() const { return static_cast<QMapNode *>(left); }
+    inline QMapNode *rightNode() const { return static_cast<QMapNode *>(right); }
+
+    inline const QMapNode *nextNode() const { return static_cast<const QMapNode *>(QMapNodeBase::nextNode()); }
+    inline const QMapNode *previousNode() const { return static_cast<const QMapNode *>(QMapNodeBase::previousNode()); }
+    inline QMapNode *nextNode() { return static_cast<QMapNode *>(QMapNodeBase::nextNode()); }
+    inline QMapNode *previousNode() { return static_cast<QMapNode *>(QMapNodeBase::previousNode()); }
+
+    QMapNode *minimumNode() { return static_cast<QMapNode *>(QMapNodeBase::minimumNode()); }
+    QMapNode *maximumNode() { return static_cast<QMapNode *>(QMapNodeBase::maximumNode()); }
+    const QMapNode *minimumNode() const { return static_cast<QMapNode *>(QMapNodeBase::minimumNode()); }
+    const QMapNode *maximumNode() const { return static_cast<QMapNode *>(QMapNodeBase::maximumNode()); }
+
+    QMapNode<Key, T> *copy(QMapData<Key, T> *d) const;
+
+    void destroySubTree();
+
+    QMapNode<Key, T> *lowerBound(const Key &key);
+    QMapNode<Key, T> *upperBound(const Key &key);
+
 private:
-    // never access these members through this structure.
-    // see below
-    QMapData::Node *backward;
-    QMapData::Node *forward[1];
+    QMapNode() Q_DECL_EQ_DELETE;
+    Q_DISABLE_COPY(QMapNode)
 };
 
 template <class Key, class T>
-struct QMapPayloadNode
+inline QMapNode<Key, T> *QMapNode<Key, T>::lowerBound(const Key &akey)
 {
-    Key key;
-    T value;
+    QMapNode<Key, T> *n = this;
+    QMapNode<Key, T> *last = 0;
+    while (n) {
+        if (!qMapLessThanKey(n->key, akey)) {
+            last = n;
+            n = n->leftNode();
+        } else {
+            n = n->rightNode();
+        }
+    }
+    return last;
+}
 
-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>
+inline QMapNode<Key, T> *QMapNode<Key, T>::upperBound(const Key &akey)
+{
+    QMapNode<Key, T> *n = this;
+    QMapNode<Key, T> *last = 0;
+    while (n) {
+        if (qMapLessThanKey(akey, n->key)) {
+            last = n;
+            n = n->leftNode();
+        } else {
+            n = n->rightNode();
+        }
+    }
+    return last;
+}
+
+
+
+struct Q_CORE_EXPORT QMapDataBase
+{
+    QtPrivate::RefCount ref;
+    int size;
+    QMapNodeBase header;
+
+    void rotateLeft(QMapNodeBase *x);
+    void rotateRight(QMapNodeBase *x);
+    void rebalance(QMapNodeBase *x);
+    void freeNodeAndRebalance(QMapNodeBase *z);
+
+    QMapNodeBase *createNode(int size, int alignment, QMapNodeBase *parent, bool left);
+    void freeTree(QMapNodeBase *root, int alignment);
+
+    static const QMapDataBase shared_null;
+
+    static QMapDataBase *createData();
+    static void freeData(QMapDataBase *d);
 };
 
 template <class Key, class T>
-class QMap
+struct QMapData : public QMapDataBase
 {
     typedef QMapNode<Key, T> Node;
-    typedef QMapPayloadNode<Key, T> PayloadNode;
 
-    union {
-        QMapData *d;
-        QMapData::Node *e;
-    };
+    Node *root() const { return static_cast<Node *>(header.left); }
 
-    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
+    const Node *end() const { return static_cast<const Node *>(&header); }
+    Node *end() { return static_cast<Node *>(&header); }
+    const Node *begin() const { if (root()) return root()->minimumNode(); return end(); }
+    Node *begin() { if (root()) return root()->minimumNode(); return end(); }
+
+    void deleteNode(Node *z);
+    Node *findNode(const Key &akey) const;
+    void nodeRange(const Key &akey, Node **first, Node **last);
+
+    Node *createNode(const Key &k, const T &v, Node *parent = 0, bool left = false)
+    {
+        Node *n = static_cast<Node *>(QMapDataBase::createNode(sizeof(Node), Q_ALIGNOF(Node),
+                                      parent, left));
+        QT_TRY {
+            new (&n->key) Key(k);
+            QT_TRY {
+                new (&n->value) T(v);
+            } QT_CATCH(...) {
+                n->key.~Key();
+                QT_RETHROW;
+            }
+        } QT_CATCH(...) {
+            QMapDataBase::freeNodeAndRebalance(n);
+            QT_RETHROW;
+        }
+        return n;
     }
-    static inline Node *concrete(QMapData::Node *node) {
-        return reinterpret_cast<Node *>(reinterpret_cast<char *>(node) - payload());
+
+    static QMapData *create() {
+        return static_cast<QMapData *>(createData());
     }
 
+    void free() {
+        if (root()) {
+            root()->destroySubTree();
+            freeTree(header.left, Q_ALIGNOF(Node));
+        }
+        freeData(this);
+    }
+};
+
+template <class Key, class T>
+QMapNode<Key, T> *QMapNode<Key, T>::copy(QMapData<Key, T> *d) const
+{
+    QMapNode<Key, T> *n = d->createNode(key, value);
+    n->setColor(color());
+    if (left) {
+        n->left = leftNode()->copy(d);
+        n->left->setParent(n);
+    } else {
+        n->left = 0;
+    }
+    if (right) {
+        n->right = rightNode()->copy(d);
+        n->right->setParent(n);
+    } else {
+        n->right = 0;
+    }
+    return n;
+}
+
+template <class Key, class T>
+void QMapNode<Key, T>::destroySubTree()
+{
+    if (QTypeInfo<Key>::isComplex)
+        key.~Key();
+    if (QTypeInfo<T>::isComplex)
+        value.~T();
+    if (QTypeInfo<Key>::isComplex || QTypeInfo<T>::isComplex) {
+        if (left)
+            leftNode()->destroySubTree();
+        if (right)
+            rightNode()->destroySubTree();
+    }
+}
+
+template <class Key, class T>
+void QMapData<Key, T>::deleteNode(QMapNode<Key, T> *z)
+{
+    if (QTypeInfo<Key>::isComplex)
+        z->key.~Key();
+    if (QTypeInfo<T>::isComplex)
+        z->value.~T();
+    freeNodeAndRebalance(z);
+}
+
+template <class Key, class T>
+QMapNode<Key, T> *QMapData<Key, T>::findNode(const Key &akey) const
+{
+    Node *lb = root()->lowerBound(akey);
+    if (lb && !qMapLessThanKey(akey, lb->key))
+        return lb;
+    return 0;
+}
+
+
+template <class Key, class T>
+void QMapData<Key, T>::nodeRange(const Key &akey, QMapNode<Key, T> **first, QMapNode<Key, T> **last)
+{
+    Node *n = root();
+    Node *l = end();
+    while (n) {
+        if (qMapLessThanKey(akey, n->key)) {
+            l = n;
+            n = n->leftNode();
+        } else if (qMapLessThanKey(n->key, akey)) {
+            n = n->rightNode();
+        } else {
+            *first = n->leftNode()->lowerBound(akey);
+            if (!*first)
+                *first = n;
+            *last = n->rightNode()->upperBound(akey);
+            if (!*last)
+                *last = l;
+            return;
+        }
+    }
+    *first = *last = l;
+}
+
+
+template <class Key, class T>
+class QMap
+{
+    typedef QMapNode<Key, T> Node;
+
+    QMapData<Key, T> *d;
+
 public:
-    inline QMap() : d(const_cast<QMapData *>(&QMapData::shared_null)) { }
-    inline QMap(const QMap<Key, T> &other) : d(other.d)
-    { d->ref.ref(); if (!d->sharable) detach(); }
-    inline ~QMap() { if (!d->ref.deref()) freeData(d); }
+    inline QMap() : d(static_cast<QMapData<Key, T> *>(const_cast<QMapDataBase *>(&QMapDataBase::shared_null))) { }
+    QMap(const QMap<Key, T> &other);
+
+    inline ~QMap() { if (!d->ref.deref()) d->free(); }
 
     QMap<Key, T> &operator=(const QMap<Key, T> &other);
 #ifdef Q_COMPILER_RVALUE_REFS
+    inline QMap(QMap<Key, T> &&other)
+        : d(other.d)
+    {
+        other.d = static_cast<QMapData<Key, T> *>(
+                const_cast<QMapDataBase *>(&QMapDataBase::shared_null));
+    }
+
     inline QMap<Key, T> &operator=(QMap<Key, T> &&other)
     { qSwap(d, other.d); return *this; }
 #endif
@@ -201,9 +363,16 @@ public:
 
     inline void detach() { if (d->ref.isShared()) detach_helper(); }
     inline bool isDetached() const { return !d->ref.isShared(); }
-    inline void setSharable(bool sharable) { if (!sharable) detach(); if (d != &QMapData::shared_null) d->sharable = sharable; }
+    inline void setSharable(bool sharable)
+    {
+        if (sharable == d->ref.isSharable())
+            return;
+        if (!sharable)
+            detach();
+        // Don't call on shared_null
+        d->ref.setSharable(sharable);
+    }
     inline bool isSharedWith(const QMap<Key, T> &other) const { return d == other.d; }
-    inline void setInsertInOrder(bool ordered) { if (ordered) detach(); if (d != &QMapData::shared_null) d->insertInOrder = ordered; }
 
     void clear();
 
@@ -211,10 +380,8 @@ public:
     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;
+    const Key key(const T &value, const Key &defaultKey = Key()) const;
+    const T value(const Key &key, const T &defaultValue = T()) const;
     T &operator[](const Key &key);
     const T operator[](const Key &key) const;
 
@@ -230,7 +397,7 @@ public:
     class iterator
     {
         friend class const_iterator;
-        QMapData::Node *i;
+        Node *i;
 
     public:
         typedef std::bidirectional_iterator_tag iterator_category;
@@ -239,34 +406,32 @@ public:
         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 iterator(Node *node) : i(node) { }
 
-        inline const Key &key() const { return concrete(i)->key; }
-        inline T &value() const { return concrete(i)->value; }
-        inline T &operator*() const { return concrete(i)->value; }
-        inline T *operator->() const { return &concrete(i)->value; }
+        inline const Key &key() const { return i->key; }
+        inline T &value() const { return i->value; }
+        inline T &operator*() const { return i->value; }
+        inline T *operator->() const { return &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];
+            i = i->nextNode();
             return *this;
         }
         inline iterator operator++(int) {
             iterator r = *this;
-            i = i->forward[0];
+            i = i->nextNode();
             return r;
         }
         inline iterator &operator--() {
-            i = i->backward;
+            i = i->previousNode();
             return *this;
         }
         inline iterator operator--(int) {
             iterator r = *this;
-            i = i->backward;
+            i = i->previousNode();
             return r;
         }
         inline iterator operator+(int j) const
@@ -275,7 +440,6 @@ public:
         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
@@ -285,17 +449,14 @@ public:
             { 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 QMap<Key, T>;
     };
     friend class iterator;
 
     class const_iterator
     {
         friend class iterator;
-        QMapData::Node *i;
+        const Node *i;
 
     public:
         typedef std::bidirectional_iterator_tag iterator_category;
@@ -304,10 +465,8 @@ public:
         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) { }
+        inline const_iterator(const Node *node) : i(node) { }
 #ifdef QT_STRICT_ITERATORS
         explicit inline const_iterator(const iterator &o)
 #else
@@ -315,29 +474,29 @@ public:
 #endif
         { i = o.i; }
 
-        inline const Key &key() const { return concrete(i)->key; }
-        inline const T &value() const { return concrete(i)->value; }
-        inline const T &operator*() const { return concrete(i)->value; }
-        inline const T *operator->() const { return &concrete(i)->value; }
+        inline const Key &key() const { return i->key; }
+        inline const T &value() const { return i->value; }
+        inline const T &operator*() const { return i->value; }
+        inline const T *operator->() const { return &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];
+            i = i->nextNode();
             return *this;
         }
         inline const_iterator operator++(int) {
             const_iterator r = *this;
-            i = i->forward[0];
+            i = i->nextNode();
             return r;
         }
         inline const_iterator &operator--() {
-            i = i->backward;
+            i = i->previousNode();
             return *this;
         }
         inline const_iterator operator--(int) {
             const_iterator r = *this;
-            i = i->backward;
+            i = i->previousNode();
             return r;
         }
         inline const_iterator operator+(int j) const
@@ -346,31 +505,24 @@ public:
         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) const { return operator==(const_iterator(o)); }
         inline bool operator!=(const iterator &o) const { return operator!=(const_iterator(o)); }
 #endif
-
-    private:
-        // ### Qt 5: remove
-        inline operator bool() const { return false; }
+        friend class QMap<Key, T>;
     };
     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 cbegin() 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 cend() const { return const_iterator(e); }
-    inline const_iterator constEnd() const { return const_iterator(e); }
+    inline iterator begin() { detach(); return iterator(d->begin()); }
+    inline const_iterator begin() const { return const_iterator(d->begin()); }
+    inline const_iterator constBegin() const { return const_iterator(d->begin()); }
+    inline const_iterator cbegin() const { return const_iterator(d->begin()); }
+    inline iterator end() { detach(); return iterator(d->end()); }
+    inline const_iterator end() const { return const_iterator(d->end()); }
+    inline const_iterator constEnd() const { return const_iterator(d->end()); }
+    inline const_iterator cend() const { return const_iterator(d->end()); }
     iterator erase(iterator it);
 
     // more Qt
@@ -394,110 +546,52 @@ public:
     typedef qptrdiff difference_type;
     typedef int size_type;
     inline bool empty() const { return isEmpty(); }
+    QPair<iterator, iterator> equal_range(const Key &akey);
 
-#ifdef QT_QMAP_DEBUG
-    inline void dump() const { d->dump(); }
+#ifdef Q_MAP_DEBUG
+    void dump() const;
 #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)
+inline QMap<Key, T>::QMap(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;
+    if (other.d->ref.ref()) {
+        d = other.d;
+    } else {
+        d = QMapData<Key, T>::create();
+        if (other.d->header.left) {
+            d->header.left = static_cast<Node *>(other.d->header.left)->copy(d);
+            d->header.left->setParent(&d->header);
         }
-    } 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
+Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::operator=(const QMap<Key, T> &other)
 {
-    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;
+    if (d != other.d) {
+        QMap<Key, T> tmp(other);
+        tmp.swap(*this);
     }
+    return *this;
 }
 
 template <class Key, class T>
-Q_INLINE_TEMPLATE const T QMap<Key, T>::value(const Key &akey) const
+Q_INLINE_TEMPLATE void QMap<Key, T>::clear()
 {
-    QMapData::Node *node;
-    if (d->size == 0 || (node = findNode(akey)) == e) {
-        return T();
-    } else {
-        return concrete(node)->value;
-    }
+    *this = QMap<Key, T>();
 }
 
+
 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;
-    }
+    Node *n = d->findNode(akey);
+    return n ? n->value : adefaultValue;
 }
 
 template <class Key, class T>
@@ -510,24 +604,25 @@ 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;
+    Node *n = d->findNode(akey);
+    if (!n)
+        return *insert(akey, T());
+    return n->value;
 }
 
 template <class Key, class T>
 Q_INLINE_TEMPLATE int QMap<Key, T>::count(const Key &akey) const
 {
+    Node *firstNode;
+    Node *lastNode;
+    d->nodeRange(akey, &firstNode, &lastNode);
+
+    const_iterator first(firstNode);
+    const const_iterator last(lastNode);
     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));
+    while (first != last) {
+        ++cnt;
+        ++first;
     }
     return cnt;
 }
@@ -535,23 +630,34 @@ Q_INLINE_TEMPLATE int QMap<Key, T>::count(const Key &akey) const
 template <class Key, class T>
 Q_INLINE_TEMPLATE bool QMap<Key, T>::contains(const Key &akey) const
 {
-    return findNode(akey) != e;
+    return d->findNode(akey) != 0;
 }
 
 template <class Key, class T>
-Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insert(const Key &akey,
-                                                                       const T &avalue)
+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;
+    Node *n = d->root();
+    Node *y = d->end();
+    Node *last = 0;
+    bool  left = true;
+    while (n) {
+        y = n;
+        if (!qMapLessThanKey(n->key, akey)) {
+            last = n;
+            left = true;
+            n = n->leftNode();
+        } else {
+            left = false;
+            n = n->rightNode();
+        }
     }
-    return iterator(node);
+    if (last && !qMapLessThanKey(akey, last->key)) {
+        last->value = avalue;
+        return iterator(last);
+    }
+    Node *z = d->createNode(akey, avalue, y, left);
+    return iterator(z);
 }
 
 template <class Key, class T>
@@ -559,29 +665,37 @@ Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(cons
                                                                             const T &avalue)
 {
     detach();
-
-    QMapData::Node *update[QMapData::LastLevel + 1];
-    mutableFindNode(update, akey);
-    return iterator(node_create(d, update, akey, avalue));
+    Node* y = d->end();
+    Node* x = static_cast<Node *>(d->root());
+    bool left = true;
+    while (x != 0) {
+        left = !qMapLessThanKey(x->key, akey);
+        y = x;
+        x = left ? x->leftNode() : x->rightNode();
+    }
+    Node *z = d->createNode(akey, avalue, y, left);
+    return iterator(z);
 }
 
 template <class Key, class T>
-Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::find(const Key &akey) const
+Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::constFind(const Key &akey) const
 {
-    return const_iterator(findNode(akey));
+    Node *n = d->findNode(akey);
+    return const_iterator(n ? n : d->end());
 }
 
 template <class Key, class T>
-Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::constFind(const Key &akey) const
+Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::find(const Key &akey) const
 {
-    return const_iterator(findNode(akey));
+    return constFind(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));
+    Node *n = d->findNode(akey);
+    return iterator(n ? n : d->end());
 }
 
 template <class Key, class T>
@@ -598,56 +712,46 @@ Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::unite(const QMap<Key, T> &other)
 }
 
 template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE void QMap<Key, T>::freeData(QMapData *x)
+QPair<typename QMap<Key, T>::iterator, typename QMap<Key, T>::iterator> QMap<Key, T>::equal_range(const Key &akey)
 {
-    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
+    detach();
+    Node *first, *last;
+    d->nodeRange(akey, &first, &last);
+    return QPair<iterator, iterator>(iterator(first), iterator(last));
+}
+
+#ifdef Q_MAP_DEBUG
+template <class Key, class T>
+void QMap<Key, T>::dump() const
+{
+    const_iterator it = begin();
+    qDebug() << "map dump:";
+    while (it != end()) {
+        const QMapNodeBase *n = it.i;
+        int depth = 0;
+        while (n && n != d->root()) {
+            ++depth;
+            n = n->parent();
         }
+        QByteArray space(4*depth, ' ');
+        qDebug() << space << (it.i->color() == Node::Red ? "Red  " : "Black") << it.i << it.i->left << it.i->right
+                 << it.key() << it.value();
+        ++it;
     }
-    x->continueFreeData(payload());
+    qDebug() << "---------";
 }
+#endif
 
 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);
+    int n = 0;
+    while (Node *node = d->findNode(akey)) {
+        d->deleteNode(node);
+        ++n;
     }
-    return oldSize - d->size;
+    return n;
 }
 
 template <class Key, class T>
@@ -655,21 +759,10 @@ 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);
+    Node *node = d->findNode(akey);
+    if (node) {
+        T t = node->value;
+        d->deleteNode(node);
         return t;
     }
     return T();
@@ -678,82 +771,26 @@ Q_OUTOFLINE_TEMPLATE T QMap<Key, T>::take(const Key &akey)
 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))
+    if (it == iterator(d->end()))
         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();
+    Node *n = it.i;
+    ++it;
+    d->deleteNode(n);
+    return it;
 }
 
 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;
+    QMapData<Key, T> *x = QMapData<Key, T>::create();
+    if (d->header.left) {
+        x->header.left = static_cast<Node *>(d->header.left)->copy(x);
+        x->header.left->setParent(&x->header);
     }
     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;
-    }
+        d->free();
+    d = x;
 }
 
 template <class Key, class T>
@@ -769,7 +806,7 @@ Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::uniqueKeys() const
             do {
                 if (++i == end())
                     goto break_out_of_outer_loop;
-            } while (!(aKey < i.key()));   // loop while (key == i.key())
+            } while (!qMapLessThanKey(aKey, i.key()));   // loop while (key == i.key())
         }
     }
 break_out_of_outer_loop:
@@ -803,12 +840,6 @@ Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys(const T &avalue) const
 }
 
 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();
@@ -838,49 +869,54 @@ 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) {
+    Node *n = d->findNode(akey);
+    if (n) {
+        const_iterator it(n);
         do {
-            res.append(concrete(node)->value);
-            node = node->forward[0];
-        } while (node != e && !qMapLessThanKey<Key>(akey, concrete(node)->key));
+            res.append(*it);
+            ++it;
+        } while (it != constEnd() && !qMapLessThanKey<Key>(akey, it.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
+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]);
+    Node *lb = d->root()->lowerBound(akey);
+    if (!lb)
+        lb = d->end();
+    return const_iterator(lb);
 }
 
 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));
+    Node *lb = d->root()->lowerBound(akey);
+    if (!lb)
+        lb = d->end();
+    return iterator(lb);
 }
 
 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);
+    Node *ub = d->root()->upperBound(akey);
+    if (!ub)
+        ub = d->end();
+    return const_iterator(ub);
 }
 
 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));
+    Node *ub = d->root()->upperBound(akey);
+    if (!ub)
+        ub = d->end();
+    return iterator(ub);
 }
 
 template <class Key, class T>
@@ -907,14 +943,12 @@ Q_OUTOFLINE_TEMPLATE bool QMap<Key, T>::operator==(const QMap<Key, T> &other) co
 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;
+    d = QMapData<Key, T>::create();
     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>