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>

1 files changed, 287 insertions, 158 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