From 6e4d7bbb0baeff2362e3d25be6aedcb68e7909b0 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Thorbj=C3=B8rn=20Lund=20Martsum?= <tmartsum@gmail.com>
Date: Thu, 27 Sep 2012 14:56:43 +0200
Subject: 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>
---
 src/corelib/tools/qmap.cpp | 18 +++++++++++++++++-
 1 file changed, 17 insertions(+), 1 deletion(-)

(limited to 'src/corelib/tools/qmap.cpp')

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;
 }
-- 
cgit v1.2.3