From 5cb0368516abd293daf67711a36bbacc99422e9a Mon Sep 17 00:00:00 2001 From: Lars Knoll Date: Mon, 19 Mar 2012 20:53:20 +0100 Subject: 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 --- src/corelib/tools/qmap.h | 822 ++++++++++++++++++++++++----------------------- 1 file changed, 428 insertions(+), 394 deletions(-) (limited to 'src/corelib/tools/qmap.h') diff --git a/src/corelib/tools/qmap.h b/src/corelib/tools/qmap.h index dbbbcce162..3f46a8ad1e 100644 --- a/src/corelib/tools/qmap.h +++ b/src/corelib/tools/qmap.h @@ -45,6 +45,11 @@ #include #include #include +#include + +#ifdef Q_MAP_DEBUG +#include +#endif #ifndef QT_NO_STL #include @@ -56,39 +61,6 @@ QT_BEGIN_HEADER QT_BEGIN_NAMESPACE - -struct Q_CORE_EXPORT QMapData -{ - struct Node { - Node *backward; - Node *forward[1]; - }; - enum { LastLevel = 11, Sparseness = 3 }; - - QMapData *backward; - QMapData *forward[QMapData::LastLevel + 1]; - QtPrivate::RefCount ref; - int topLevel; - int size; - uint randomBits; - uint insertInOrder : 1; - uint sharable : 1; - uint strictAlignment : 1; - uint reserved : 29; - - static QMapData *createData(int alignment); - void continueFreeData(int offset); - Node *node_create(Node *update[], int offset, int alignment); - void node_delete(Node *update[], int offset, Node *node); -#ifdef QT_QMAP_DEBUG - uint adjust_ptr(Node *node); - void dump(); -#endif - - static const QMapData shared_null; -}; - - /* QMap uses qMapLessThanKey() to compare keys. The default implementation uses operator<(). For pointer types, @@ -104,85 +76,275 @@ template inline bool qMapLessThanKey(const Key &key1, const Key &key return key1 < key2; } -template inline bool qMapLessThanKey(Ptr *key1, Ptr *key2) +template inline bool qMapLessThanKey(const Ptr *key1, const Ptr *key2) { - Q_ASSERT(sizeof(quintptr) == sizeof(Ptr *)); + Q_STATIC_ASSERT(sizeof(quintptr) == sizeof(const Ptr *)); return quintptr(key1) < quintptr(key2); } -template inline bool qMapLessThanKey(const Ptr *key1, const Ptr *key2) +struct QMapDataBase; +template struct QMapData; + +struct Q_CORE_EXPORT QMapNodeBase { - Q_ASSERT(sizeof(quintptr) == sizeof(const Ptr *)); - return quintptr(key1) < quintptr(key2); -} + quintptr p; + QMapNodeBase *left; + QMapNodeBase *right; + + enum Color { Red = 0, Black = 1 }; + enum { Mask = 3 }; // reserve the second bit as well + + const QMapNodeBase *nextNode() const; + QMapNodeBase *nextNode() { return const_cast(const_cast(this)->nextNode()); } + const QMapNodeBase *previousNode() const; + QMapNodeBase *previousNode() { return const_cast(const_cast(this)->previousNode()); } + + Color color() const { return Color(p & 1); } + void setColor(Color c) { if (c == Black) p |= Black; else p &= ~Black; } + QMapNodeBase *parent() const { return reinterpret_cast(p & ~Mask); } + void setParent(QMapNodeBase *pp) { p = (p & Mask) | quintptr(pp); } + + QMapNodeBase *minimumNode() { QMapNodeBase *n = this; while (n->left) n = n->left; return n; } + QMapNodeBase *maximumNode() { QMapNodeBase *n = this; while (n->right) n = n->right; return n; } + const QMapNodeBase *minimumNode() const { const QMapNodeBase *n = this; while (n->left) n = n->left; return n; } + const QMapNodeBase *maximumNode() const { const QMapNodeBase *n = this; while (n->right) n = n->right; return n; } +}; template -struct QMapNode { +struct QMapNode : public QMapNodeBase +{ Key key; T value; + inline QMapNode *leftNode() const { return static_cast(left); } + inline QMapNode *rightNode() const { return static_cast(right); } + + inline const QMapNode *nextNode() const { return static_cast(QMapNodeBase::nextNode()); } + inline const QMapNode *previousNode() const { return static_cast(QMapNodeBase::previousNode()); } + inline QMapNode *nextNode() { return static_cast(QMapNodeBase::nextNode()); } + inline QMapNode *previousNode() { return static_cast(QMapNodeBase::previousNode()); } + + QMapNode *minimumNode() { return static_cast(QMapNodeBase::minimumNode()); } + QMapNode *maximumNode() { return static_cast(QMapNodeBase::maximumNode()); } + const QMapNode *minimumNode() const { return static_cast(QMapNodeBase::minimumNode()); } + const QMapNode *maximumNode() const { return static_cast(QMapNodeBase::maximumNode()); } + + QMapNode *copy(QMapData *d) const; + + void destroySubTree(); + + QMapNode *lowerBound(const Key &key); + QMapNode *upperBound(const Key &key); + private: - // never access these members through this structure. - // see below - QMapData::Node *backward; - QMapData::Node *forward[1]; + QMapNode() Q_DECL_EQ_DELETE; + Q_DISABLE_COPY(QMapNode) }; template -struct QMapPayloadNode +inline QMapNode *QMapNode::lowerBound(const Key &akey) { - Key key; - T value; + QMapNode *n = this; + QMapNode *last = 0; + while (n) { + if (!qMapLessThanKey(n->key, akey)) { + last = n; + n = n->leftNode(); + } else { + n = n->rightNode(); + } + } + return last; +} -private: - // QMap::e is a pointer to QMapData::Node, which matches the member - // below. However, the memory allocation node in QMapData::node_create - // allocates sizeof(QMapPayloNode) and incorrectly calculates the offset - // of 'backward' below. If the alignment of QMapPayloadNode is larger - // than the alignment of a pointer, the 'backward' member is aligned to - // the end of this structure, not to 'value' above, and will occupy the - // tail-padding area. - // - // e.g., on a 32-bit archictecture with Key = int and - // sizeof(T) = alignof(T) = 8 - // 0 4 8 12 16 20 24 byte - // | key | PAD | value |backward| PAD | correct layout - // | key | PAD | value | |backward| how it's actually used - // |<----- value of QMap::payload() = 20 ----->| - QMapData::Node *backward; +template +inline QMapNode *QMapNode::upperBound(const Key &akey) +{ + QMapNode *n = this; + QMapNode *last = 0; + while (n) { + if (qMapLessThanKey(akey, n->key)) { + last = n; + n = n->leftNode(); + } else { + n = n->rightNode(); + } + } + return last; +} + + + +struct Q_CORE_EXPORT QMapDataBase +{ + QtPrivate::RefCount ref; + int size; + QMapNodeBase header; + + void rotateLeft(QMapNodeBase *x); + void rotateRight(QMapNodeBase *x); + void rebalance(QMapNodeBase *x); + void freeNodeAndRebalance(QMapNodeBase *z); + + QMapNodeBase *createNode(int size, int alignment, QMapNodeBase *parent, bool left); + void freeTree(QMapNodeBase *root, int alignment); + + static const QMapDataBase shared_null; + + static QMapDataBase *createData(); + static void freeData(QMapDataBase *d); }; template -class QMap +struct QMapData : public QMapDataBase { typedef QMapNode Node; - typedef QMapPayloadNode PayloadNode; - union { - QMapData *d; - QMapData::Node *e; - }; + Node *root() const { return static_cast(header.left); } - static inline int payload() { return sizeof(PayloadNode) - sizeof(QMapData::Node *); } - static inline int alignment() { -#ifdef Q_ALIGNOF - return int(qMax(sizeof(void*), Q_ALIGNOF(Node))); -#else - return 0; -#endif + const Node *end() const { return static_cast(&header); } + Node *end() { return static_cast(&header); } + const Node *begin() const { if (root()) return root()->minimumNode(); return end(); } + Node *begin() { if (root()) return root()->minimumNode(); return end(); } + + void deleteNode(Node *z); + Node *findNode(const Key &akey) const; + void nodeRange(const Key &akey, Node **first, Node **last); + + Node *createNode(const Key &k, const T &v, Node *parent = 0, bool left = false) + { + Node *n = static_cast(QMapDataBase::createNode(sizeof(Node), Q_ALIGNOF(Node), + parent, left)); + QT_TRY { + new (&n->key) Key(k); + QT_TRY { + new (&n->value) T(v); + } QT_CATCH(...) { + n->key.~Key(); + QT_RETHROW; + } + } QT_CATCH(...) { + QMapDataBase::freeNodeAndRebalance(n); + QT_RETHROW; + } + return n; } - static inline Node *concrete(QMapData::Node *node) { - return reinterpret_cast(reinterpret_cast(node) - payload()); + + static QMapData *create() { + return static_cast(createData()); } + void free() { + if (root()) { + root()->destroySubTree(); + freeTree(header.left, Q_ALIGNOF(Node)); + } + freeData(this); + } +}; + +template +QMapNode *QMapNode::copy(QMapData *d) const +{ + QMapNode *n = d->createNode(key, value); + n->setColor(color()); + if (left) { + n->left = leftNode()->copy(d); + n->left->setParent(n); + } else { + n->left = 0; + } + if (right) { + n->right = rightNode()->copy(d); + n->right->setParent(n); + } else { + n->right = 0; + } + return n; +} + +template +void QMapNode::destroySubTree() +{ + if (QTypeInfo::isComplex) + key.~Key(); + if (QTypeInfo::isComplex) + value.~T(); + if (QTypeInfo::isComplex || QTypeInfo::isComplex) { + if (left) + leftNode()->destroySubTree(); + if (right) + rightNode()->destroySubTree(); + } +} + +template +void QMapData::deleteNode(QMapNode *z) +{ + if (QTypeInfo::isComplex) + z->key.~Key(); + if (QTypeInfo::isComplex) + z->value.~T(); + freeNodeAndRebalance(z); +} + +template +QMapNode *QMapData::findNode(const Key &akey) const +{ + Node *lb = root()->lowerBound(akey); + if (lb && !qMapLessThanKey(akey, lb->key)) + return lb; + return 0; +} + + +template +void QMapData::nodeRange(const Key &akey, QMapNode **first, QMapNode **last) +{ + Node *n = root(); + Node *l = end(); + while (n) { + if (qMapLessThanKey(akey, n->key)) { + l = n; + n = n->leftNode(); + } else if (qMapLessThanKey(n->key, akey)) { + n = n->rightNode(); + } else { + *first = n->leftNode()->lowerBound(akey); + if (!*first) + *first = n; + *last = n->rightNode()->upperBound(akey); + if (!*last) + *last = l; + return; + } + } + *first = *last = l; +} + + +template +class QMap +{ + typedef QMapNode Node; + + QMapData *d; + public: - inline QMap() : d(const_cast(&QMapData::shared_null)) { } - inline QMap(const QMap &other) : d(other.d) - { d->ref.ref(); if (!d->sharable) detach(); } - inline ~QMap() { if (!d->ref.deref()) freeData(d); } + inline QMap() : d(static_cast *>(const_cast(&QMapDataBase::shared_null))) { } + QMap(const QMap &other); + + inline ~QMap() { if (!d->ref.deref()) d->free(); } QMap &operator=(const QMap &other); #ifdef Q_COMPILER_RVALUE_REFS + inline QMap(QMap &&other) + : d(other.d) + { + other.d = static_cast *>( + const_cast(&QMapDataBase::shared_null)); + } + inline QMap &operator=(QMap &&other) { qSwap(d, other.d); return *this; } #endif @@ -201,9 +363,16 @@ public: inline void detach() { if (d->ref.isShared()) detach_helper(); } inline bool isDetached() const { return !d->ref.isShared(); } - inline void setSharable(bool sharable) { if (!sharable) detach(); if (d != &QMapData::shared_null) d->sharable = sharable; } + inline void setSharable(bool sharable) + { + if (sharable == d->ref.isSharable()) + return; + if (!sharable) + detach(); + // Don't call on shared_null + d->ref.setSharable(sharable); + } inline bool isSharedWith(const QMap &other) const { return d == other.d; } - inline void setInsertInOrder(bool ordered) { if (ordered) detach(); if (d != &QMapData::shared_null) d->insertInOrder = ordered; } void clear(); @@ -211,10 +380,8 @@ public: T take(const Key &key); bool contains(const Key &key) const; - const Key key(const T &value) const; - const Key key(const T &value, const Key &defaultKey) const; - const T value(const Key &key) const; - const T value(const Key &key, const T &defaultValue) const; + const Key key(const T &value, const Key &defaultKey = Key()) const; + const T value(const Key &key, const T &defaultValue = T()) const; T &operator[](const Key &key); const T operator[](const Key &key) const; @@ -230,7 +397,7 @@ public: class iterator { friend class const_iterator; - QMapData::Node *i; + Node *i; public: typedef std::bidirectional_iterator_tag iterator_category; @@ -239,34 +406,32 @@ public: typedef T *pointer; typedef T &reference; - // ### Qt 5: get rid of 'operator Node *' - inline operator QMapData::Node *() const { return i; } inline iterator() : i(0) { } - inline iterator(QMapData::Node *node) : i(node) { } + inline iterator(Node *node) : i(node) { } - inline const Key &key() const { return concrete(i)->key; } - inline T &value() const { return concrete(i)->value; } - inline T &operator*() const { return concrete(i)->value; } - inline T *operator->() const { return &concrete(i)->value; } + inline const Key &key() const { return i->key; } + inline T &value() const { return i->value; } + inline T &operator*() const { return i->value; } + inline T *operator->() const { return &i->value; } inline bool operator==(const iterator &o) const { return i == o.i; } inline bool operator!=(const iterator &o) const { return i != o.i; } inline iterator &operator++() { - i = i->forward[0]; + i = i->nextNode(); return *this; } inline iterator operator++(int) { iterator r = *this; - i = i->forward[0]; + i = i->nextNode(); return r; } inline iterator &operator--() { - i = i->backward; + i = i->previousNode(); return *this; } inline iterator operator--(int) { iterator r = *this; - i = i->backward; + i = i->previousNode(); return r; } inline iterator operator+(int j) const @@ -275,7 +440,6 @@ public: inline iterator &operator+=(int j) { return *this = *this + j; } inline iterator &operator-=(int j) { return *this = *this - j; } - // ### Qt 5: not sure this is necessary anymore #ifdef QT_STRICT_ITERATORS private: #else @@ -285,17 +449,14 @@ public: { return i == o.i; } inline bool operator!=(const const_iterator &o) const { return i != o.i; } - - private: - // ### Qt 5: remove - inline operator bool() const { return false; } + friend class QMap; }; friend class iterator; class const_iterator { friend class iterator; - QMapData::Node *i; + const Node *i; public: typedef std::bidirectional_iterator_tag iterator_category; @@ -304,10 +465,8 @@ public: typedef const T *pointer; typedef const T &reference; - // ### Qt 5: get rid of 'operator Node *' - inline operator QMapData::Node *() const { return i; } inline const_iterator() : i(0) { } - inline const_iterator(QMapData::Node *node) : i(node) { } + inline const_iterator(const Node *node) : i(node) { } #ifdef QT_STRICT_ITERATORS explicit inline const_iterator(const iterator &o) #else @@ -315,29 +474,29 @@ public: #endif { i = o.i; } - inline const Key &key() const { return concrete(i)->key; } - inline const T &value() const { return concrete(i)->value; } - inline const T &operator*() const { return concrete(i)->value; } - inline const T *operator->() const { return &concrete(i)->value; } + inline const Key &key() const { return i->key; } + inline const T &value() const { return i->value; } + inline const T &operator*() const { return i->value; } + inline const T *operator->() const { return &i->value; } inline bool operator==(const const_iterator &o) const { return i == o.i; } inline bool operator!=(const const_iterator &o) const { return i != o.i; } inline const_iterator &operator++() { - i = i->forward[0]; + i = i->nextNode(); return *this; } inline const_iterator operator++(int) { const_iterator r = *this; - i = i->forward[0]; + i = i->nextNode(); return r; } inline const_iterator &operator--() { - i = i->backward; + i = i->previousNode(); return *this; } inline const_iterator operator--(int) { const_iterator r = *this; - i = i->backward; + i = i->previousNode(); return r; } inline const_iterator operator+(int j) const @@ -346,31 +505,24 @@ public: inline const_iterator &operator+=(int j) { return *this = *this + j; } inline const_iterator &operator-=(int j) { return *this = *this - j; } - // ### Qt 5: not sure this is necessary anymore #ifdef QT_STRICT_ITERATORS private: inline bool operator==(const iterator &o) const { return operator==(const_iterator(o)); } inline bool operator!=(const iterator &o) const { return operator!=(const_iterator(o)); } #endif - - private: - // ### Qt 5: remove - inline operator bool() const { return false; } + friend class QMap; }; friend class const_iterator; // STL style - inline iterator begin() { detach(); return iterator(e->forward[0]); } - inline const_iterator begin() const { return const_iterator(e->forward[0]); } - inline const_iterator cbegin() const { return const_iterator(e->forward[0]); } - inline const_iterator constBegin() const { return const_iterator(e->forward[0]); } - inline iterator end() { - detach(); - return iterator(e); - } - inline const_iterator end() const { return const_iterator(e); } - inline const_iterator cend() const { return const_iterator(e); } - inline const_iterator constEnd() const { return const_iterator(e); } + inline iterator begin() { detach(); return iterator(d->begin()); } + inline const_iterator begin() const { return const_iterator(d->begin()); } + inline const_iterator constBegin() const { return const_iterator(d->begin()); } + inline const_iterator cbegin() const { return const_iterator(d->begin()); } + inline iterator end() { detach(); return iterator(d->end()); } + inline const_iterator end() const { return const_iterator(d->end()); } + inline const_iterator constEnd() const { return const_iterator(d->end()); } + inline const_iterator cend() const { return const_iterator(d->end()); } iterator erase(iterator it); // more Qt @@ -394,110 +546,52 @@ public: typedef qptrdiff difference_type; typedef int size_type; inline bool empty() const { return isEmpty(); } + QPair equal_range(const Key &akey); -#ifdef QT_QMAP_DEBUG - inline void dump() const { d->dump(); } +#ifdef Q_MAP_DEBUG + void dump() const; #endif private: void detach_helper(); - void freeData(QMapData *d); - QMapData::Node *findNode(const Key &key) const; - QMapData::Node *mutableFindNode(QMapData::Node *update[], const Key &key) const; - QMapData::Node *node_create(QMapData *d, QMapData::Node *update[], const Key &key, - const T &value); }; template -Q_INLINE_TEMPLATE QMap &QMap::operator=(const QMap &other) +inline QMap::QMap(const QMap &other) { - if (d != other.d) { - QMapData* o = other.d; - o->ref.ref(); - if (!d->ref.deref()) - freeData(d); - d = o; - if (!d->sharable) - detach_helper(); - } - return *this; -} - -template -Q_INLINE_TEMPLATE void QMap::clear() -{ - *this = QMap(); -} - -template -Q_INLINE_TEMPLATE typename QMapData::Node * -QMap::node_create(QMapData *adt, QMapData::Node *aupdate[], const Key &akey, const T &avalue) -{ - QMapData::Node *abstractNode = adt->node_create(aupdate, payload(), alignment()); - QT_TRY { - Node *concreteNode = concrete(abstractNode); - new (&concreteNode->key) Key(akey); - QT_TRY { - new (&concreteNode->value) T(avalue); - } QT_CATCH(...) { - concreteNode->key.~Key(); - QT_RETHROW; + if (other.d->ref.ref()) { + d = other.d; + } else { + d = QMapData::create(); + if (other.d->header.left) { + d->header.left = static_cast(other.d->header.left)->copy(d); + d->header.left->setParent(&d->header); } - } QT_CATCH(...) { - adt->node_delete(aupdate, payload(), abstractNode); - QT_RETHROW; } - - // clean up the update array for further insertions - /* - for (int i = 0; i <= d->topLevel; ++i) { - if ( aupdate[i]==reinterpret_cast(adt) || aupdate[i]->forward[i] != abstractNode) - break; - aupdate[i] = abstractNode; - } -*/ - - return abstractNode; } template -Q_INLINE_TEMPLATE QMapData::Node *QMap::findNode(const Key &akey) const +Q_INLINE_TEMPLATE QMap &QMap::operator=(const QMap &other) { - QMapData::Node *cur = e; - QMapData::Node *next = e; - - for (int i = d->topLevel; i >= 0; i--) { - while ((next = cur->forward[i]) != e && qMapLessThanKey(concrete(next)->key, akey)) - cur = next; - } - - if (next != e && !qMapLessThanKey(akey, concrete(next)->key)) { - return next; - } else { - return e; + if (d != other.d) { + QMap tmp(other); + tmp.swap(*this); } + return *this; } template -Q_INLINE_TEMPLATE const T QMap::value(const Key &akey) const +Q_INLINE_TEMPLATE void QMap::clear() { - QMapData::Node *node; - if (d->size == 0 || (node = findNode(akey)) == e) { - return T(); - } else { - return concrete(node)->value; - } + *this = QMap(); } + template Q_INLINE_TEMPLATE const T QMap::value(const Key &akey, const T &adefaultValue) const { - QMapData::Node *node; - if (d->size == 0 || (node = findNode(akey)) == e) { - return adefaultValue; - } else { - return concrete(node)->value; - } + Node *n = d->findNode(akey); + return n ? n->value : adefaultValue; } template @@ -510,24 +604,25 @@ template Q_INLINE_TEMPLATE T &QMap::operator[](const Key &akey) { detach(); - - QMapData::Node *update[QMapData::LastLevel + 1]; - QMapData::Node *node = mutableFindNode(update, akey); - if (node == e) - node = node_create(d, update, akey, T()); - return concrete(node)->value; + Node *n = d->findNode(akey); + if (!n) + return *insert(akey, T()); + return n->value; } template Q_INLINE_TEMPLATE int QMap::count(const Key &akey) const { + Node *firstNode; + Node *lastNode; + d->nodeRange(akey, &firstNode, &lastNode); + + const_iterator first(firstNode); + const const_iterator last(lastNode); int cnt = 0; - QMapData::Node *node = findNode(akey); - if (node != e) { - do { - ++cnt; - node = node->forward[0]; - } while (node != e && !qMapLessThanKey(akey, concrete(node)->key)); + while (first != last) { + ++cnt; + ++first; } return cnt; } @@ -535,23 +630,34 @@ Q_INLINE_TEMPLATE int QMap::count(const Key &akey) const template Q_INLINE_TEMPLATE bool QMap::contains(const Key &akey) const { - return findNode(akey) != e; + return d->findNode(akey) != 0; } template -Q_INLINE_TEMPLATE typename QMap::iterator QMap::insert(const Key &akey, - const T &avalue) +Q_INLINE_TEMPLATE typename QMap::iterator QMap::insert(const Key &akey, const T &avalue) { detach(); - - QMapData::Node *update[QMapData::LastLevel + 1]; - QMapData::Node *node = mutableFindNode(update, akey); - if (node == e) { - node = node_create(d, update, akey, avalue); - } else { - concrete(node)->value = avalue; + Node *n = d->root(); + Node *y = d->end(); + Node *last = 0; + bool left = true; + while (n) { + y = n; + if (!qMapLessThanKey(n->key, akey)) { + last = n; + left = true; + n = n->leftNode(); + } else { + left = false; + n = n->rightNode(); + } } - return iterator(node); + if (last && !qMapLessThanKey(akey, last->key)) { + last->value = avalue; + return iterator(last); + } + Node *z = d->createNode(akey, avalue, y, left); + return iterator(z); } template @@ -559,29 +665,37 @@ Q_INLINE_TEMPLATE typename QMap::iterator QMap::insertMulti(cons const T &avalue) { detach(); - - QMapData::Node *update[QMapData::LastLevel + 1]; - mutableFindNode(update, akey); - return iterator(node_create(d, update, akey, avalue)); + Node* y = d->end(); + Node* x = static_cast(d->root()); + bool left = true; + while (x != 0) { + left = !qMapLessThanKey(x->key, akey); + y = x; + x = left ? x->leftNode() : x->rightNode(); + } + Node *z = d->createNode(akey, avalue, y, left); + return iterator(z); } template -Q_INLINE_TEMPLATE typename QMap::const_iterator QMap::find(const Key &akey) const +Q_INLINE_TEMPLATE typename QMap::const_iterator QMap::constFind(const Key &akey) const { - return const_iterator(findNode(akey)); + Node *n = d->findNode(akey); + return const_iterator(n ? n : d->end()); } template -Q_INLINE_TEMPLATE typename QMap::const_iterator QMap::constFind(const Key &akey) const +Q_INLINE_TEMPLATE typename QMap::const_iterator QMap::find(const Key &akey) const { - return const_iterator(findNode(akey)); + return constFind(akey); } template Q_INLINE_TEMPLATE typename QMap::iterator QMap::find(const Key &akey) { detach(); - return iterator(findNode(akey)); + Node *n = d->findNode(akey); + return iterator(n ? n : d->end()); } template @@ -598,56 +712,46 @@ Q_INLINE_TEMPLATE QMap &QMap::unite(const QMap &other) } template -Q_OUTOFLINE_TEMPLATE void QMap::freeData(QMapData *x) +QPair::iterator, typename QMap::iterator> QMap::equal_range(const Key &akey) { - if (QTypeInfo::isComplex || QTypeInfo::isComplex) { - QMapData *cur = x; - QMapData *next = cur->forward[0]; - while (next != x) { - cur = next; - next = cur->forward[0]; -#if defined(_MSC_VER) -#pragma warning(disable:4189) -#endif - Node *concreteNode = concrete(reinterpret_cast(cur)); - concreteNode->key.~Key(); - concreteNode->value.~T(); -#if defined(_MSC_VER) -#pragma warning(default:4189) -#endif + detach(); + Node *first, *last; + d->nodeRange(akey, &first, &last); + return QPair(iterator(first), iterator(last)); +} + +#ifdef Q_MAP_DEBUG +template +void QMap::dump() const +{ + const_iterator it = begin(); + qDebug() << "map dump:"; + while (it != end()) { + const QMapNodeBase *n = it.i; + int depth = 0; + while (n && n != d->root()) { + ++depth; + n = n->parent(); } + QByteArray space(4*depth, ' '); + qDebug() << space << (it.i->color() == Node::Red ? "Red " : "Black") << it.i << it.i->left << it.i->right + << it.key() << it.value(); + ++it; } - x->continueFreeData(payload()); + qDebug() << "---------"; } +#endif template Q_OUTOFLINE_TEMPLATE int QMap::remove(const Key &akey) { detach(); - - QMapData::Node *update[QMapData::LastLevel + 1]; - QMapData::Node *cur = e; - QMapData::Node *next = e; - int oldSize = d->size; - - for (int i = d->topLevel; i >= 0; i--) { - while ((next = cur->forward[i]) != e && qMapLessThanKey(concrete(next)->key, akey)) - cur = next; - update[i] = cur; - } - - if (next != e && !qMapLessThanKey(akey, concrete(next)->key)) { - bool deleteNext = true; - do { - cur = next; - next = cur->forward[0]; - deleteNext = (next != e && !qMapLessThanKey(concrete(cur)->key, concrete(next)->key)); - concrete(cur)->key.~Key(); - concrete(cur)->value.~T(); - d->node_delete(update, payload(), cur); - } while (deleteNext); + int n = 0; + while (Node *node = d->findNode(akey)) { + d->deleteNode(node); + ++n; } - return oldSize - d->size; + return n; } template @@ -655,21 +759,10 @@ Q_OUTOFLINE_TEMPLATE T QMap::take(const Key &akey) { detach(); - QMapData::Node *update[QMapData::LastLevel + 1]; - QMapData::Node *cur = e; - QMapData::Node *next = e; - - for (int i = d->topLevel; i >= 0; i--) { - while ((next = cur->forward[i]) != e && qMapLessThanKey(concrete(next)->key, akey)) - cur = next; - update[i] = cur; - } - - if (next != e && !qMapLessThanKey(akey, concrete(next)->key)) { - T t = concrete(next)->value; - concrete(next)->key.~Key(); - concrete(next)->value.~T(); - d->node_delete(update, payload(), next); + Node *node = d->findNode(akey); + if (node) { + T t = node->value; + d->deleteNode(node); return t; } return T(); @@ -678,82 +771,26 @@ Q_OUTOFLINE_TEMPLATE T QMap::take(const Key &akey) template Q_OUTOFLINE_TEMPLATE typename QMap::iterator QMap::erase(iterator it) { - QMapData::Node *update[QMapData::LastLevel + 1]; - QMapData::Node *cur = e; - QMapData::Node *next = e; - - if (it == iterator(e)) + if (it == iterator(d->end())) return it; - for (int i = d->topLevel; i >= 0; i--) { - while ((next = cur->forward[i]) != e && qMapLessThanKey(concrete(next)->key, it.key())) - cur = next; - update[i] = cur; - } - - while (next != e) { - cur = next; - next = cur->forward[0]; - if (cur == it) { - concrete(cur)->key.~Key(); - concrete(cur)->value.~T(); - d->node_delete(update, payload(), cur); - return iterator(next); - } - - for (int i = 0; i <= d->topLevel; ++i) { - if (update[i]->forward[i] != cur) - break; - update[i] = cur; - } - } - return end(); + Node *n = it.i; + ++it; + d->deleteNode(n); + return it; } template Q_OUTOFLINE_TEMPLATE void QMap::detach_helper() { - union { QMapData *d; QMapData::Node *e; } x; - x.d = QMapData::createData(alignment()); - if (d->size) { - x.d->insertInOrder = true; - QMapData::Node *update[QMapData::LastLevel + 1]; - QMapData::Node *cur = e->forward[0]; - update[0] = x.e; - while (cur != e) { - QT_TRY { - Node *concreteNode = concrete(cur); - node_create(x.d, update, concreteNode->key, concreteNode->value); - } QT_CATCH(...) { - freeData(x.d); - QT_RETHROW; - } - cur = cur->forward[0]; - } - x.d->insertInOrder = false; + QMapData *x = QMapData::create(); + if (d->header.left) { + x->header.left = static_cast(d->header.left)->copy(x); + x->header.left->setParent(&x->header); } if (!d->ref.deref()) - freeData(d); - d = x.d; -} - -template -Q_OUTOFLINE_TEMPLATE QMapData::Node *QMap::mutableFindNode(QMapData::Node *aupdate[], - const Key &akey) const -{ - QMapData::Node *cur = e; - QMapData::Node *next = e; - - for (int i = d->topLevel; i >= 0; i--) { - while ((next = cur->forward[i]) != e && qMapLessThanKey(concrete(next)->key, akey)) - cur = next; - aupdate[i] = cur; - } - if (next != e && !qMapLessThanKey(akey, concrete(next)->key)) { - return next; - } else { - return e; - } + d->free(); + d = x; } template @@ -769,7 +806,7 @@ Q_OUTOFLINE_TEMPLATE QList QMap::uniqueKeys() const do { if (++i == end()) goto break_out_of_outer_loop; - } while (!(aKey < i.key())); // loop while (key == i.key()) + } while (!qMapLessThanKey(aKey, i.key())); // loop while (key == i.key()) } } break_out_of_outer_loop: @@ -802,12 +839,6 @@ Q_OUTOFLINE_TEMPLATE QList QMap::keys(const T &avalue) const return res; } -template -Q_OUTOFLINE_TEMPLATE const Key QMap::key(const T &avalue) const -{ - return key(avalue, Key()); -} - template Q_OUTOFLINE_TEMPLATE const Key QMap::key(const T &avalue, const Key &defaultKey) const { @@ -838,49 +869,54 @@ template Q_OUTOFLINE_TEMPLATE QList QMap::values(const Key &akey) const { QList res; - QMapData::Node *node = findNode(akey); - if (node != e) { + Node *n = d->findNode(akey); + if (n) { + const_iterator it(n); do { - res.append(concrete(node)->value); - node = node->forward[0]; - } while (node != e && !qMapLessThanKey(akey, concrete(node)->key)); + res.append(*it); + ++it; + } while (it != constEnd() && !qMapLessThanKey(akey, it.key())); } return res; } template -Q_INLINE_TEMPLATE typename QMap::const_iterator -QMap::lowerBound(const Key &akey) const +Q_INLINE_TEMPLATE typename QMap::const_iterator QMap::lowerBound(const Key &akey) const { - QMapData::Node *update[QMapData::LastLevel + 1]; - mutableFindNode(update, akey); - return const_iterator(update[0]->forward[0]); + Node *lb = d->root()->lowerBound(akey); + if (!lb) + lb = d->end(); + return const_iterator(lb); } template Q_INLINE_TEMPLATE typename QMap::iterator QMap::lowerBound(const Key &akey) { detach(); - return static_cast(const_cast(this)->lowerBound(akey)); + Node *lb = d->root()->lowerBound(akey); + if (!lb) + lb = d->end(); + return iterator(lb); } template Q_INLINE_TEMPLATE typename QMap::const_iterator QMap::upperBound(const Key &akey) const { - QMapData::Node *update[QMapData::LastLevel + 1]; - mutableFindNode(update, akey); - QMapData::Node *node = update[0]->forward[0]; - while (node != e && !qMapLessThanKey(akey, concrete(node)->key)) - node = node->forward[0]; - return const_iterator(node); + Node *ub = d->root()->upperBound(akey); + if (!ub) + ub = d->end(); + return const_iterator(ub); } template Q_INLINE_TEMPLATE typename QMap::iterator QMap::upperBound(const Key &akey) { detach(); - return static_cast(const_cast(this)->upperBound(akey)); + Node *ub = d->root()->upperBound(akey); + if (!ub) + ub = d->end(); + return iterator(ub); } template @@ -907,14 +943,12 @@ Q_OUTOFLINE_TEMPLATE bool QMap::operator==(const QMap &other) co template Q_OUTOFLINE_TEMPLATE QMap::QMap(const std::map &other) { - d = QMapData::createData(alignment()); - d->insertInOrder = true; + d = QMapData::create(); typename std::map::const_iterator it = other.end(); while (it != other.begin()) { --it; insert((*it).first, (*it).second); } - d->insertInOrder = false; } template -- cgit v1.2.3