diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/corelib/tools/qmap.cpp | 18 | ||||
-rw-r--r-- | src/corelib/tools/qmap.h | 8 |
2 files changed, 23 insertions, 3 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> |