QMap 5.0 - keep track of leftmost node (BIC)

This suggestion keeps track of the most left node.
The point is that constBegin() becomes a lot faster.

That speeds up iteration a bit, and makes it O(1) to get the
first element. The penalty in insert and remove is very small.
On large trees it seems to be less than 1%.

It should be noticed that constBegin() is a very common hint
on my planned change to 5.1, and this opperation will without
this patch cost 2 x log N. One when the user calls the hint
with begin - and one where it is compared with begin.

Other std::maps has a very fast begin(). E.g
http://www.cplusplus.com/reference/stl/map/begin/
(begin with constant time)

Change-Id: I221f6755aa8bd16a5189771c5bc8ae56c8ee0fb4
Reviewed-by: Lars Knoll <lars.knoll@digia.com>

4 files changed, 133 insertions, 4 deletions

diff --git a/src/corelib/tools/qmap.cpp b/src/corelib/tools/qmap.cpp
index dea87c6b63..7c33d60750 100644
--- a/src/corelib/tools/qmap.cpp
+++ b/src/corelib/tools/qmap.cpp
@@ -50,7 +50,7 @@
 
 QT_BEGIN_NAMESPACE
 
-const QMapDataBase QMapDataBase::shared_null = { Q_REFCOUNT_INITIALIZE_STATIC, 0, { 0, 0, 0 } };
+const QMapDataBase QMapDataBase::shared_null = { Q_REFCOUNT_INITIALIZE_STATIC, 0, { 0, 0, 0 }, 0 };
 
 const QMapNodeBase *QMapNodeBase::nextNode() const
 {
@@ -177,6 +177,12 @@ void QMapDataBase::freeNodeAndRebalance(QMapNodeBase *z)
     QMapNodeBase *x_parent;
     if (y->left == 0) {
         x = y->right;
+        if (y == mostLeftNode) {
+            if (x)
+                mostLeftNode = x; // It cannot have (left) children due the red black invariant.
+            else
+                mostLeftNode = y->parent();
+        }
     } else {
         if (y->right == 0) {
             x = y->left;
@@ -290,6 +296,13 @@ void QMapDataBase::freeNodeAndRebalance(QMapNodeBase *z)
     --size;
 }
 
+void QMapDataBase::recalcMostLeftNode()
+{
+    mostLeftNode = &header;
+    while (mostLeftNode->left)
+        mostLeftNode = mostLeftNode->left;
+}
+
 static inline int qMapAlignmentThreshold()
 {
     // malloc on 32-bit platforms should return pointers that are 8-byte
@@ -324,6 +337,8 @@ QMapNodeBase *QMapDataBase::createNode(int alloc, int alignment, QMapNodeBase *p
     if (parent) {
         if (left) {
             parent->left = node;
+            if (parent == mostLeftNode)
+                mostLeftNode = node;
         } else {
             parent->right = node;
         }
@@ -352,6 +367,7 @@ QMapDataBase *QMapDataBase::createData()
     d->header.p = 0;
     d->header.left = 0;
     d->header.right = 0;
+    d->mostLeftNode = &(d->header);
 
     return d;
 }
diff --git a/src/corelib/tools/qmap.h b/src/corelib/tools/qmap.h
index 0e726e8394..e0b267ce20 100644
--- a/src/corelib/tools/qmap.h
+++ b/src/corelib/tools/qmap.h
@@ -173,11 +173,13 @@ struct Q_CORE_EXPORT QMapDataBase
     QtPrivate::RefCount ref;
     int size;
     QMapNodeBase header;
+    QMapNodeBase *mostLeftNode;
 
     void rotateLeft(QMapNodeBase *x);
     void rotateRight(QMapNodeBase *x);
     void rebalance(QMapNodeBase *x);
     void freeNodeAndRebalance(QMapNodeBase *z);
+    void recalcMostLeftNode();
 
     QMapNodeBase *createNode(int size, int alignment, QMapNodeBase *parent, bool left);
     void freeTree(QMapNodeBase *root, int alignment);
@@ -197,8 +199,8 @@ struct QMapData : public QMapDataBase
 
     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(); }
+    const Node *begin() const { if (root()) return static_cast<const Node*>(mostLeftNode); return end(); }
+    Node *begin() { if (root()) return static_cast<Node*>(mostLeftNode); return end(); }
 
     void deleteNode(Node *z);
     Node *findNode(const Key &akey) const;
@@ -555,6 +557,7 @@ inline QMap<Key, T>::QMap(const QMap<Key, T> &other)
         if (other.d->header.left) {
             d->header.left = static_cast<Node *>(other.d->header.left)->copy(d);
             d->header.left->setParent(&d->header);
+            d->recalcMostLeftNode();
         }
     }
 }
@@ -780,6 +783,7 @@ Q_OUTOFLINE_TEMPLATE void QMap<Key, T>::detach_helper()
     if (!d->ref.deref())
         d->destroy();
     d = x;
+    d->recalcMostLeftNode();
 }
 
 template <class Key, class T>
diff --git a/tests/auto/corelib/tools/qmap/tst_qmap.cpp b/tests/auto/corelib/tools/qmap/tst_qmap.cpp
index e07b3fc81e..9c53563a5c 100644
--- a/tests/auto/corelib/tools/qmap/tst_qmap.cpp
+++ b/tests/auto/corelib/tools/qmap/tst_qmap.cpp
@@ -49,6 +49,9 @@
 class tst_QMap : public QObject
 {
     Q_OBJECT
+protected:
+    template <class KEY, class VALUE>
+    void sanityCheckTree(const QMap<KEY, VALUE> &m, int calledFromLine);
 public slots:
     void init();
 private slots:
@@ -79,6 +82,7 @@ private slots:
     void setSharable();
 
     void insert();
+    void checkMostLeftNode();
 };
 
 typedef QMap<QString, QString> StringMap;
@@ -115,6 +119,28 @@ QDebug operator << (QDebug d, const MyClass &c) {
     return d;
 }
 
+template <class KEY, class VALUE>
+void tst_QMap::sanityCheckTree(const QMap<KEY, VALUE> &m, int calledFromLine)
+{
+    QString possibleFrom;
+    possibleFrom.setNum(calledFromLine);
+    possibleFrom = "Called from line: " + possibleFrom;
+    int count = 0;
+    typename QMap<KEY, VALUE>::const_iterator oldite = m.constBegin();
+    for (typename QMap<KEY, VALUE>::const_iterator i = m.constBegin(); i != m.constEnd(); ++i) {
+        count++;
+        bool oldIteratorIsLarger = i.key() < oldite.key();
+        QVERIFY2(!oldIteratorIsLarger, possibleFrom.toUtf8());
+        oldite = i;
+    }
+    if (m.size() != count) { // Fail
+        qDebug() << possibleFrom;
+        QCOMPARE(m.size(), count);
+    }
+    if (m.size() == 0)
+        QVERIFY(m.constBegin() == m.constEnd());
+}
+
 void tst_QMap::init()
 {
     MyClass::count = 0;
@@ -280,6 +306,7 @@ void tst_QMap::clear()
         map.insert( "key0", MyClass( "value1" ) );
         map.insert( "key1", MyClass( "value2" ) );
         map.clear();
+        sanityCheckTree(map, __LINE__);
         QVERIFY( map.isEmpty() );
     }
     QCOMPARE( MyClass::count, int(0) );
@@ -400,6 +427,8 @@ void tst_QMap::swap()
     m1.swap(m2);
     QCOMPARE(m1.value(1),QLatin1String("m2[1]"));
     QCOMPARE(m2.value(0),QLatin1String("m1[0]"));
+    sanityCheckTree(m1, __LINE__);
+    sanityCheckTree(m2, __LINE__);
 }
 
 void tst_QMap::operator_eq()
@@ -631,7 +660,7 @@ void tst_QMap::lowerUpperBound()
 
 void tst_QMap::mergeCompare()
 {
-    QMap<int, QString> map1, map2, map3;
+    QMap<int, QString> map1, map2, map3, map1b, map2b;
 
     map1.insert(1,"ett");
     map1.insert(3,"tre");
@@ -641,6 +670,13 @@ void tst_QMap::mergeCompare()
     map2.insert(4,"fyra");
 
     map1.unite(map2);
+    sanityCheckTree(map1, __LINE__);
+
+    map1b = map1;
+    map2b = map2;
+    map2b.insert(0, "nul");
+    map1b.unite(map2b);
+    sanityCheckTree(map1b, __LINE__);
 
     QVERIFY(map1.value(1) == "ett");
     QVERIFY(map1.value(2) == "tvo");
@@ -958,9 +994,11 @@ void tst_QMap::setSharable()
 
         QVERIFY(!map.isDetached());
         QVERIFY(copy.isSharedWith(map));
+        sanityCheckTree(copy, __LINE__);
     }
 
     map.setSharable(false);
+    sanityCheckTree(map, __LINE__);
     QVERIFY(map.isDetached());
     QCOMPARE(map.size(), 4);
     QCOMPARE(const_(map)[4], QString("quatro"));
@@ -975,6 +1013,8 @@ void tst_QMap::setSharable()
         QCOMPARE(const_(copy)[4], QString("quatro"));
 
         QCOMPARE(map, copy);
+        sanityCheckTree(map, __LINE__);
+        sanityCheckTree(copy, __LINE__);
     }
 
     map.setSharable(true);
@@ -1012,5 +1052,57 @@ void tst_QMap::insert()
     }
 }
 
+void tst_QMap::checkMostLeftNode()
+{
+    QMap<int, int> map;
+
+    map.insert(100, 1);
+    sanityCheckTree(map, __LINE__);
+
+    // insert
+    map.insert(99, 1);
+    sanityCheckTree(map, __LINE__);
+    map.insert(98, 1);
+    sanityCheckTree(map, __LINE__);
+    map.insert(97, 1);
+    sanityCheckTree(map, __LINE__);
+    map.insert(96, 1);
+    sanityCheckTree(map, __LINE__);
+    map.insert(95, 1);
+
+    // remove
+    sanityCheckTree(map, __LINE__);
+    map.take(95);
+    sanityCheckTree(map, __LINE__);
+    map.remove(96);
+    sanityCheckTree(map, __LINE__);
+    map.erase(map.begin());
+    sanityCheckTree(map, __LINE__);
+    map.remove(97);
+    sanityCheckTree(map, __LINE__);
+    map.remove(98);
+    sanityCheckTree(map, __LINE__);
+    map.remove(99);
+    sanityCheckTree(map, __LINE__);
+    map.remove(100);
+    sanityCheckTree(map, __LINE__);
+    map.insert(200, 1);
+    QCOMPARE(map.constBegin().key(), 200);
+    sanityCheckTree(map, __LINE__);
+    // remove the non left most node
+    map.insert(202, 2);
+    map.insert(203, 3);
+    map.insert(204, 4);
+    map.remove(202);
+    sanityCheckTree(map, __LINE__);
+    map.remove(203);
+    sanityCheckTree(map, __LINE__);
+    map.remove(204);
+    sanityCheckTree(map, __LINE__);
+    // erase last item
+    map.erase(map.begin());
+    sanityCheckTree(map, __LINE__);
+}
+
 QTEST_APPLESS_MAIN(tst_QMap)
 #include "tst_qmap.moc"
diff --git a/tests/benchmarks/corelib/tools/qmap/main.cpp b/tests/benchmarks/corelib/tools/qmap/main.cpp
index c3b9c18cd2..4d9833b7a1 100644
--- a/tests/benchmarks/corelib/tools/qmap/main.cpp
+++ b/tests/benchmarks/corelib/tools/qmap/main.cpp
@@ -61,6 +61,7 @@ private slots:
 
     void iteration();
     void toStdMap();
+    void iterator_begin();
 };
 
 
@@ -172,6 +173,22 @@ void tst_QMap::toStdMap()
     }
 }
 
+void tst_QMap::iterator_begin()
+{
+    QMap<int, int> map;
+    for (int i = 0; i < 100000; ++i)
+        map.insert(i, i);
+
+    QBENCHMARK {
+        for (int i = 0; i < 100000; ++i) {
+            QMap<int, int>::const_iterator it = map.constBegin();
+            QMap<int, int>::const_iterator end = map.constEnd();
+            if (it == end) // same as if (false)
+                ++it;
+        }
+    }
+}
+
 QTEST_MAIN(tst_QMap)
 
 #include "main.moc"