summaryrefslogtreecommitdiffstats
path: root/src/corelib/tools/qmap.cpp
diff options
context:
space:
mode:
authorThorbjørn Lund Martsum <tmartsum@gmail.com>2012-09-27 14:56:43 +0200
committerThe Qt Project <gerrit-noreply@qt-project.org>2012-10-27 07:35:57 +0200
commit6e4d7bbb0baeff2362e3d25be6aedcb68e7909b0 (patch)
tree40c0cc4ecaaa9db45205d83bfbfac93f99f993b0 /src/corelib/tools/qmap.cpp
parentcfc3eeea1b3fbf31998deef65fb01214d44d36fd (diff)
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>
Diffstat (limited to 'src/corelib/tools/qmap.cpp')
-rw-r--r--src/corelib/tools/qmap.cpp18
1 files changed, 17 insertions, 1 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;
}