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/io/qdatastream.h | 2 - src/corelib/tools/qmap.cpp | 445 ++++++++++----- src/corelib/tools/qmap.h | 822 ++++++++++++++------------- tests/auto/corelib/tools/qmap/tst_qmap.cpp | 166 +++++- tests/benchmarks/corelib/tools/qmap/main.cpp | 165 ++++++ tests/benchmarks/corelib/tools/qmap/qmap.pro | 5 + tests/benchmarks/corelib/tools/tools.pro | 1 + 7 files changed, 1048 insertions(+), 558 deletions(-) create mode 100644 tests/benchmarks/corelib/tools/qmap/main.cpp create mode 100644 tests/benchmarks/corelib/tools/qmap/qmap.pro diff --git a/src/corelib/io/qdatastream.h b/src/corelib/io/qdatastream.h index 451a7ab959..533911974a 100644 --- a/src/corelib/io/qdatastream.h +++ b/src/corelib/io/qdatastream.h @@ -385,7 +385,6 @@ Q_OUTOFLINE_TEMPLATE QDataStream &operator>>(QDataStream &in, QMap &ma in >> n; map.detach(); - map.setInsertInOrder(true); for (quint32 i = 0; i < n; ++i) { if (in.status() != QDataStream::Ok) break; @@ -395,7 +394,6 @@ Q_OUTOFLINE_TEMPLATE QDataStream &operator>>(QDataStream &in, QMap &ma in >> key >> value; map.insertMulti(key, value); } - map.setInsertInOrder(false); if (in.status() != QDataStream::Ok) map.clear(); if (oldStatus != QDataStream::Ok) diff --git a/src/corelib/tools/qmap.cpp b/src/corelib/tools/qmap.cpp index b585bdbbc8..90521d343c 100644 --- a/src/corelib/tools/qmap.cpp +++ b/src/corelib/tools/qmap.cpp @@ -50,170 +50,316 @@ QT_BEGIN_NAMESPACE -const QMapData QMapData::shared_null = { - const_cast(&shared_null), - { const_cast(&shared_null), 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, - Q_REFCOUNT_INITIALIZE_STATIC, 0, 0, 0, false, true, false, 0 -}; +const QMapDataBase QMapDataBase::shared_null = { Q_REFCOUNT_INITIALIZE_STATIC, 0, { 0, 0, 0 } }; -QMapData *QMapData::createData(int alignment) +const QMapNodeBase *QMapNodeBase::nextNode() const { - QMapData *d = new QMapData; - Q_CHECK_PTR(d); - Node *e = reinterpret_cast(d); - e->backward = e; - e->forward[0] = e; - d->ref.initializeOwned(); - d->topLevel = 0; - d->size = 0; - d->randomBits = 0; - d->insertInOrder = false; - d->sharable = true; - d->strictAlignment = alignment > 8; - d->reserved = 0; - return d; + const QMapNodeBase *n = this; + if (n->right) { + n = n->right; + while (n->left) + n = n->left; + } else { + const QMapNodeBase *y = n->parent(); + while (y && n == y->right) { + n = y; + y = n->parent(); + } + n = y; + } + return n; } -void QMapData::continueFreeData(int offset) +const QMapNodeBase *QMapNodeBase::previousNode() const { - Node *e = reinterpret_cast(this); - Node *cur = e->forward[0]; - Node *prev; - while (cur != e) { - prev = cur; - cur = cur->forward[0]; - if (strictAlignment) - qFreeAligned(reinterpret_cast(prev) - offset); - else - free(reinterpret_cast(prev) - offset); + const QMapNodeBase *n = this; + if (n->left) { + n = n->left; + while (n->right) + n = n->right; + } else { + const QMapNodeBase *y = n->parent(); + while (y && n == y->left) { + n = y; + y = n->parent(); + } + n = y; } - delete this; + return n; } -/*! - Creates a new node inside the data structure. - - \a update is an array with pointers to the node after which the new node - should be inserted. Because of the strange skip list data structure there - could be several pointers to this node on different levels. - \a offset is an amount of bytes that needs to reserved just before the - QMapData::Node structure. - - \a alignment dictates the alignment for the data. - \internal - \since 4.6 -*/ -QMapData::Node *QMapData::node_create(Node *update[], int offset, int alignment) +void QMapDataBase::rotateLeft(QMapNodeBase *x) { - int level = 0; - uint mask = (1 << Sparseness) - 1; - - while ((randomBits & mask) == mask && level < LastLevel) { - ++level; - mask <<= Sparseness; - } - - if (level > topLevel) { - Node *e = reinterpret_cast(this); - level = ++topLevel; - e->forward[level] = e; - update[level] = e; - } - - ++randomBits; - if (level == 3 && !insertInOrder) - randomBits = qrand(); + QMapNodeBase *&root = header.left; + QMapNodeBase *y = x->right; + x->right = y->left; + if (y->left != 0) + y->left->setParent(x); + y->setParent(x->parent()); + if (x == root) + root = y; + else if (x == x->parent()->left) + x->parent()->left = y; + else + x->parent()->right = y; + y->left = x; + x->setParent(y); +} - void *concreteNode = strictAlignment ? - qMallocAligned(offset + sizeof(Node) + level * sizeof(Node *), alignment) : - malloc(offset + sizeof(Node) + level * sizeof(Node *)); - Q_CHECK_PTR(concreteNode); - Node *abstractNode = reinterpret_cast(reinterpret_cast(concreteNode) + offset); +void QMapDataBase::rotateRight(QMapNodeBase *x) +{ + QMapNodeBase *&root = header.left; + QMapNodeBase *y = x->left; + x->left = y->right; + if (y->right != 0) + y->right->setParent(x); + y->setParent(x->parent()); + if (x == root) + root = y; + else if (x == x->parent()->right) + x->parent()->right = y; + else + x->parent()->left = y; + y->right = x; + x->setParent(y); +} - abstractNode->backward = update[0]; - update[0]->forward[0]->backward = abstractNode; - for (int i = level; i >= 0; i--) { - abstractNode->forward[i] = update[i]->forward[i]; - update[i]->forward[i] = abstractNode; - update[i] = abstractNode; +void QMapDataBase::rebalance(QMapNodeBase *x) +{ + QMapNodeBase *&root = header.left; + x->setColor(QMapNodeBase::Red); + while (x != root && x->parent()->color() == QMapNodeBase::Red) { + if (x->parent() == x->parent()->parent()->left) { + QMapNodeBase *y = x->parent()->parent()->right; + if (y && y->color() == QMapNodeBase::Red) { + x->parent()->setColor(QMapNodeBase::Black); + y->setColor(QMapNodeBase::Black); + x->parent()->parent()->setColor(QMapNodeBase::Red); + x = x->parent()->parent(); + } else { + if (x == x->parent()->right) { + x = x->parent(); + rotateLeft(x); + } + x->parent()->setColor(QMapNodeBase::Black); + x->parent()->parent()->setColor(QMapNodeBase::Red); + rotateRight (x->parent()->parent()); + } + } else { + QMapNodeBase *y = x->parent()->parent()->left; + if (y && y->color() == QMapNodeBase::Red) { + x->parent()->setColor(QMapNodeBase::Black); + y->setColor(QMapNodeBase::Black); + x->parent()->parent()->setColor(QMapNodeBase::Red); + x = x->parent()->parent(); + } else { + if (x == x->parent()->left) { + x = x->parent(); + rotateRight(x); + } + x->parent()->setColor(QMapNodeBase::Black); + x->parent()->parent()->setColor(QMapNodeBase::Red); + rotateLeft(x->parent()->parent()); + } + } } - ++size; - return abstractNode; + root->setColor(QMapNodeBase::Black); } -void QMapData::node_delete(Node *update[], int offset, Node *node) +void QMapDataBase::freeNodeAndRebalance(QMapNodeBase *z) { - node->forward[0]->backward = node->backward; - - for (int i = 0; i <= topLevel; ++i) { - if (update[i]->forward[i] != node) - break; - update[i]->forward[i] = node->forward[i]; + QMapNodeBase *&root = header.left; + QMapNodeBase *y = z; + QMapNodeBase *x; + QMapNodeBase *x_parent; + if (y->left == 0) { + x = y->right; + } else { + if (y->right == 0) { + x = y->left; + } else { + y = y->right; + while (y->left != 0) + y = y->left; + x = y->right; + } } + if (y != z) { + z->left->setParent(y); + y->left = z->left; + if (y != z->right) { + x_parent = y->parent(); + if (x) + x->setParent(y->parent()); + y->parent()->left = x; + y->right = z->right; + z->right->setParent(y); + } else { + x_parent = y; + } + if (root == z) + root = y; + else if (z->parent()->left == z) + z->parent()->left = y; + else + z->parent()->right = y; + y->setParent(z->parent()); + // Swap the colors + QMapNodeBase::Color c = y->color(); + y->setColor(z->color()); + z->setColor(c); + y = z; + } else { + x_parent = y->parent(); + if (x) + x->setParent(y->parent()); + if (root == z) + root = x; + else if (z->parent()->left == z) + z->parent()->left = x; + else + z->parent()->right = x; + } + if (y->color() != QMapNodeBase::Red) { + while (x != root && (x == 0 || x->color() == QMapNodeBase::Black)) { + if (x == x_parent->left) { + QMapNodeBase *w = x_parent->right; + if (w->color() == QMapNodeBase::Red) { + w->setColor(QMapNodeBase::Black); + x_parent->setColor(QMapNodeBase::Red); + rotateLeft(x_parent); + w = x_parent->right; + } + if ((w->left == 0 || w->left->color() == QMapNodeBase::Black) && + (w->right == 0 || w->right->color() == QMapNodeBase::Black)) { + w->setColor(QMapNodeBase::Red); + x = x_parent; + x_parent = x_parent->parent(); + } else { + if (w->right == 0 || w->right->color() == QMapNodeBase::Black) { + if (w->left) + w->left->setColor(QMapNodeBase::Black); + w->setColor(QMapNodeBase::Red); + rotateRight(w); + w = x_parent->right; + } + w->setColor(x_parent->color()); + x_parent->setColor(QMapNodeBase::Black); + if (w->right) + w->right->setColor(QMapNodeBase::Black); + rotateLeft(x_parent); + break; + } + } else { + QMapNodeBase *w = x_parent->left; + if (w->color() == QMapNodeBase::Red) { + w->setColor(QMapNodeBase::Black); + x_parent->setColor(QMapNodeBase::Red); + rotateRight(x_parent); + w = x_parent->left; + } + if ((w->right == 0 || w->right->color() == QMapNodeBase::Black) && + (w->left == 0 || w->left->color() == QMapNodeBase::Black)) { + w->setColor(QMapNodeBase::Red); + x = x_parent; + x_parent = x_parent->parent(); + } else { + if (w->left == 0 || w->left->color() == QMapNodeBase::Black) { + if (w->right) + w->right->setColor(QMapNodeBase::Black); + w->setColor(QMapNodeBase::Red); + rotateLeft(w); + w = x_parent->left; + } + w->setColor(x_parent->color()); + x_parent->setColor(QMapNodeBase::Black); + if (w->left) + w->left->setColor(QMapNodeBase::Black); + rotateRight(x_parent); + break; + } + } + } + if (x) + x->setColor(QMapNodeBase::Black); + } + free(y); --size; - if (strictAlignment) - qFreeAligned(reinterpret_cast(node) - offset); - else - free(reinterpret_cast(node) - offset); } -#ifdef QT_QMAP_DEBUG +static inline int qMapAlignmentThreshold() +{ + // malloc on 32-bit platforms should return pointers that are 8-byte + // aligned or more while on 64-bit platforms they should be 16-byte aligned + // or more + return 2 * sizeof(void*); +} -uint QMapData::adjust_ptr(Node *node) +static inline void *qMapAllocate(int alloc, int alignment) { - if (node == reinterpret_cast(this)) { - return (uint)0xDEADBEEF; - } else { - return (uint)node; - } + return alignment > qMapAlignmentThreshold() + ? qMallocAligned(alloc, alignment) + : ::malloc(alloc); } -void QMapData::dump() +static inline void qMapDeallocate(QMapNodeBase *node, int alignment) { - qDebug("Map data (ref = %d, size = %d, randomBits = %#.8x)", int(ref), size, randomBits); + if (alignment > qMapAlignmentThreshold()) + qFreeAligned(node); + else + ::free(node); +} - QString preOutput; - QVector output(topLevel + 1); - Node *e = reinterpret_cast(this); +QMapNodeBase *QMapDataBase::createNode(int alloc, int alignment, QMapNodeBase *parent, bool left) +{ + QMapNodeBase *node = static_cast(qMapAllocate(alloc, alignment)); + Q_CHECK_PTR(node); - QString str; - str.sprintf(" %.8x", adjust_ptr(reinterpret_cast(this))); - preOutput += str; + memset(node, 0, alloc); + ++size; - Node *update[LastLevel + 1]; - for (int i = 0; i <= topLevel; ++i) { - str.sprintf("%d: [%.8x] -", i, adjust_ptr(reinterpret_cast(forward[i]))); - output[i] += str; - update[i] = reinterpret_cast(forward[i]); + if (parent) { + if (left) { + parent->left = node; + } else { + parent->right = node; + } + node->setParent(parent); + rebalance(node); } + return node; +} + +void QMapDataBase::freeTree(QMapNodeBase *root, int alignment) +{ + if (root->left) + freeTree(root->left, alignment); + if (root->right) + freeTree(root->right, alignment); + qMapDeallocate(root, alignment); +} - Node *node = reinterpret_cast(forward[0]); - while (node != e) { - int level = 0; - while (level < topLevel && update[level + 1] == node) - ++level; +QMapDataBase *QMapDataBase::createData() +{ + QMapDataBase *d = new QMapDataBase; + + d->ref.initializeOwned(); + d->size = 0; - str.sprintf(" %.8x", adjust_ptr(node)); - preOutput += str; + d->header.p = 0; + d->header.left = 0; + d->header.right = 0; - for (int i = 0; i <= level; ++i) { - str.sprintf("-> [%.8x] -", adjust_ptr(node->forward[i])); - output[i] += str; - update[i] = node->forward[i]; - } - for (int j = level + 1; j <= topLevel; ++j) - output[j] += QLatin1String("---------------"); - node = node->forward[0]; - } + return d; +} - qDebug("%s", preOutput.ascii()); - for (int i = 0; i <= topLevel; ++i) - qDebug("%s", output[i].ascii()); +void QMapDataBase::freeData(QMapDataBase *d) +{ + delete d; } -#endif /*! \class QMap @@ -482,11 +628,6 @@ void QMapData::dump() \internal */ -/*! \fn void QMap::setInsertInOrder(bool sharable) - - \internal -*/ - /*! \fn void QMap::clear() Removes all items from the map. @@ -529,22 +670,21 @@ void QMapData::dump() /*! \fn const T QMap::value(const Key &key) const - Returns the value associated with the key \a key. - - If the map contains no item with key \a key, the function - returns a \l{default-constructed value}. If there are multiple - items for \a key in the map, the value of the most recently - inserted one is returned. - - \sa key(), values(), contains(), operator[]() */ /*! \fn const T QMap::value(const Key &key, const T &defaultValue) const \overload + Returns the value associated with the key \a key. + If the map contains no item with key \a key, the function returns - \a defaultValue. + \a defaultValue. If no \a defaultValue is specified, the function + returns a \l{default-constructed value}. If there are multiple + items for \a key in the map, the value of the most recently + inserted one is returned. + + \sa key(), values(), contains(), operator[]() */ /*! \fn T &QMap::operator[](const Key &key) @@ -606,32 +746,21 @@ void QMapData::dump() by value. */ -/*! \fn Key QMap::key(const T &value) const - - Returns the first key with value \a value. - - If the map contains no item with value \a value, the function - returns a \link {default-constructed value} default-constructed - key \endlink. - - This function can be slow (\l{linear time}), because QMap's - internal data structure is optimized for fast lookup by key, not - by value. - - \sa value(), keys() -*/ - /*! \fn Key QMap::key(const T &value, const Key &defaultKey) const \since 4.3 \overload Returns the first key with value \a value, or \a defaultKey if - the map contains no item with value \a value. + the map contains no item with value \a value. If no \a defaultKey + is provided the function returns a \link {default-constructed value} + default-constructed key \endlink. This function can be slow (\l{linear time}), because QMap's internal data structure is optimized for fast lookup by key, not by value. + + \sa value(), keys() */ /*! \fn QList QMap::values() const 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 diff --git a/tests/auto/corelib/tools/qmap/tst_qmap.cpp b/tests/auto/corelib/tools/qmap/tst_qmap.cpp index 7d0ef7d7e4..ac75c0e5bd 100644 --- a/tests/auto/corelib/tools/qmap/tst_qmap.cpp +++ b/tests/auto/corelib/tools/qmap/tst_qmap.cpp @@ -41,10 +41,10 @@ #define QT_STRICT_ITERATORS +#include #include #include -#include class tst_QMap : public QObject { @@ -74,6 +74,11 @@ private slots: void qmultimap_specific(); void const_shared_null(); + + void equal_range(); + void setSharable(); + + void insert(); }; typedef QMap StringMap; @@ -105,6 +110,11 @@ int MyClass::count = 0; typedef QMap MyMap; +QDebug operator << (QDebug d, const MyClass &c) { + d << c.str; + return d; +} + void tst_QMap::init() { MyClass::count = 0; @@ -152,6 +162,7 @@ void tst_QMap::count() map.insert( "Paul", MyClass("Tvete 6") ); QCOMPARE( map.count(), 9 ); + QCOMPARE( map.count("Paul"), 1 ); #ifndef Q_CC_SUN QCOMPARE( MyClass::count, 9 ); #endif @@ -519,6 +530,7 @@ void tst_QMap::find() for(i = 3; i < 10; ++i) { compareString = testString.arg(i); map1.insertMulti(4, compareString); + QCOMPARE(map1.count(4), i - 2); } QMap::const_iterator it=map1.constFind(4); @@ -588,6 +600,33 @@ void tst_QMap::lowerUpperBound() QCOMPARE(map1.lowerBound(2).key(), 5); // returns iterator to (5, "five") QCOMPARE(map1.lowerBound(10).key(), 10); // returns iterator to (10, "ten") QVERIFY(map1.lowerBound(999) == map1.end()); // returns end() + + map1.insert(3, "three"); + map1.insert(7, "seven"); + map1.insertMulti(7, "seven_2"); + + QCOMPARE(map1.upperBound(0).key(), 1); + QCOMPARE(map1.upperBound(1).key(), 3); + QCOMPARE(map1.upperBound(2).key(), 3); + QCOMPARE(map1.upperBound(3).key(), 5); + QCOMPARE(map1.upperBound(7).key(), 10); + QVERIFY(map1.upperBound(10) == map1.end()); + QVERIFY(map1.upperBound(999) == map1.end()); + + QCOMPARE(map1.lowerBound(0).key(), 1); + QCOMPARE(map1.lowerBound(1).key(), 1); + QCOMPARE(map1.lowerBound(2).key(), 3); + QCOMPARE(map1.lowerBound(3).key(), 3); + QCOMPARE(map1.lowerBound(4).key(), 5); + QCOMPARE(map1.lowerBound(5).key(), 5); + QCOMPARE(map1.lowerBound(6).key(), 7); + QCOMPARE(map1.lowerBound(7).key(), 7); + QCOMPARE(map1.lowerBound(6).value(), QString("seven_2")); + QCOMPARE(map1.lowerBound(7).value(), QString("seven_2")); + QCOMPARE((++map1.lowerBound(6)).value(), QString("seven")); + QCOMPARE((++map1.lowerBound(7)).value(), QString("seven")); + QCOMPARE(map1.lowerBound(10).key(), 10); + QVERIFY(map1.lowerBound(999) == map1.end()); } void tst_QMap::mergeCompare() @@ -846,10 +885,129 @@ void tst_QMap::const_shared_null() QMap map2; map2.setSharable(true); QVERIFY(!map2.isDetached()); +} + +void tst_QMap::equal_range() +{ + QMap map; + + QPair::iterator, QMap::iterator> result = map.equal_range(0); + QCOMPARE(result.first, map.end()); + QCOMPARE(result.second, map.end()); + + map.insert(1, "one"); + + result = map.equal_range(0); + QCOMPARE(result.first, map.find(1)); + QCOMPARE(result.second, map.find(1)); - QMap map3; - map3.setInsertInOrder(true); - map3.setInsertInOrder(false); + result = map.equal_range(1); + QCOMPARE(result.first, map.find(1)); + QCOMPARE(result.second, map.end()); + + result = map.equal_range(2); + QCOMPARE(result.first, map.end()); + QCOMPARE(result.second, map.end()); + + for (int i = -10; i < 10; i += 2) + map.insert(i, QString("%1").arg(i)); + + result = map.equal_range(0); + QCOMPARE(result.first, map.find(0)); + QCOMPARE(result.second, map.find(1)); + + result = map.equal_range(1); + QCOMPARE(result.first, map.find(1)); + QCOMPARE(result.second, map.find(2)); + + result = map.equal_range(2); + QCOMPARE(result.first, map.find(2)); + QCOMPARE(result.second, map.find(4)); + + map.insertMulti(1, "another one"); + result = map.equal_range(1); + QCOMPARE(result.first, map.find(1)); + QCOMPARE(result.second, map.find(2)); + + QCOMPARE(map.count(1), 2); +} + +template +const T &const_(const T &t) +{ + return t; +} + +void tst_QMap::setSharable() +{ + QMap map; + + map.insert(1, "um"); + map.insert(2, "dois"); + map.insert(4, "quatro"); + map.insert(5, "cinco"); + + map.setSharable(true); + QCOMPARE(map.size(), 4); + QCOMPARE(const_(map)[4], QString("quatro")); + + { + QMap copy(map); + + QVERIFY(!map.isDetached()); + QVERIFY(copy.isSharedWith(map)); + } + + map.setSharable(false); + QVERIFY(map.isDetached()); + QCOMPARE(map.size(), 4); + QCOMPARE(const_(map)[4], QString("quatro")); + + { + QMap copy(map); + + QVERIFY(map.isDetached()); + QVERIFY(copy.isDetached()); + + QCOMPARE(copy.size(), 4); + QCOMPARE(const_(copy)[4], QString("quatro")); + + QCOMPARE(map, copy); + } + + map.setSharable(true); + QCOMPARE(map.size(), 4); + QCOMPARE(const_(map)[4], QString("quatro")); + + { + QMap copy(map); + + QVERIFY(!map.isDetached()); + QVERIFY(copy.isSharedWith(map)); + } +} + +void tst_QMap::insert() +{ + QMap map; + map.insert("cs/key1", 1); + map.insert("cs/key2", 2); + map.insert("cs/key1", 3); + QCOMPARE(map.count(), 2); + + QMap intMap; + for (int i = 0; i < 1000; ++i) { + intMap.insert(i, i); + } + + QCOMPARE(intMap.size(), 1000); + + for (int i = 0; i < 1000; ++i) { + QCOMPARE(intMap.value(i), i); + intMap.insert(i, -1); + QCOMPARE(intMap.size(), 1000); + QCOMPARE(intMap.value(i), -1); + } } QTEST_APPLESS_MAIN(tst_QMap) diff --git a/tests/benchmarks/corelib/tools/qmap/main.cpp b/tests/benchmarks/corelib/tools/qmap/main.cpp new file mode 100644 index 0000000000..e68ea685a3 --- /dev/null +++ b/tests/benchmarks/corelib/tools/qmap/main.cpp @@ -0,0 +1,165 @@ +/**************************************************************************** +** +** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies). +** Contact: http://www.qt-project.org/ +** +** This file is part of the test suite of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** GNU Lesser General Public License Usage +** This file may be used under the terms of the GNU Lesser General Public +** License version 2.1 as published by the Free Software Foundation and +** appearing in the file LICENSE.LGPL included in the packaging of this +** file. Please review the following information to ensure the GNU Lesser +** General Public License version 2.1 requirements will be met: +** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain additional +** rights. These rights are described in the Nokia Qt LGPL Exception +** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU General +** Public License version 3.0 as published by the Free Software Foundation +** and appearing in the file LICENSE.GPL included in the packaging of this +** file. Please review the following information to ensure the GNU General +** Public License version 3.0 requirements will be met: +** http://www.gnu.org/copyleft/gpl.html. +** +** Other Usage +** Alternatively, this file may be used in accordance with the terms and +** conditions contained in a signed written agreement between you and Nokia. +** +** +** +** +** +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include +#include +#include +#include +#include + + +class tst_QMap : public QObject +{ + Q_OBJECT + +private slots: + void insertion_int_int(); + void insertion_int_string(); + void insertion_string_int(); + + void lookup_int_int(); + void lookup_int_string(); + void lookup_string_int(); + + void iteration(); +}; + + +void tst_QMap::insertion_int_int() +{ + QMap map; + QBENCHMARK { + for (int i = 0; i < 100000; ++i) + map.insert(i, i); + } +} + +void tst_QMap::insertion_int_string() +{ + QMap map; + QString str("Hello World"); + QBENCHMARK { + for (int i = 0; i < 100000; ++i) + map.insert(i, str); + } +} + +void tst_QMap::insertion_string_int() +{ + QMap map; + QString str("Hello World"); + QBENCHMARK { + for (int i = 1; i < 100000; ++i) { + str[0] = QChar(i); + map.insert(str, i); + } + } +} + + +void tst_QMap::lookup_int_int() +{ + QMap map; + for (int i = 0; i < 100000; ++i) + map.insert(i, i); + + int sum = 0; + QBENCHMARK { + for (int i = 0; i < 100000; ++i) + sum += map.value(i); + } +} + +void tst_QMap::lookup_int_string() +{ + QMap map; + QString str("Hello World"); + for (int i = 0; i < 100000; ++i) + map.insert(i, str); + + QBENCHMARK { + for (int i = 0; i < 100000; ++i) + str += map.value(i); + } +} + +void tst_QMap::lookup_string_int() +{ + QMap map; + QString str("Hello World"); + for (int i = 1; i < 100000; ++i) { + str[0] = QChar(i); + map.insert(str, i); + } + + int sum = 0; + QBENCHMARK { + for (int i = 1; i < 100000; ++i) { + str[0] = QChar(i); + sum += map.value(str); + } + } +} + +// iteration speed doesn't depend on the type of the map. +void tst_QMap::iteration() +{ + QMap map; + for (int i = 0; i < 100000; ++i) + map.insert(i, i); + + int j = 0; + QBENCHMARK { + for (int i = 0; i < 100; ++i) { + QMap::const_iterator it = map.constBegin(); + QMap::const_iterator end = map.constEnd(); + while (it != end) { + j += *it; + ++it; + } + } + } +} + + +QTEST_MAIN(tst_QMap) + +#include "main.moc" diff --git a/tests/benchmarks/corelib/tools/qmap/qmap.pro b/tests/benchmarks/corelib/tools/qmap/qmap.pro new file mode 100644 index 0000000000..6a0c8d62bd --- /dev/null +++ b/tests/benchmarks/corelib/tools/qmap/qmap.pro @@ -0,0 +1,5 @@ +TARGET = tst_qmap +QT = core testlib +INCLUDEPATH += . +SOURCES += main.cpp +CONFIG += release diff --git a/tests/benchmarks/corelib/tools/tools.pro b/tests/benchmarks/corelib/tools/tools.pro index ea9059e759..7565b1a167 100644 --- a/tests/benchmarks/corelib/tools/tools.pro +++ b/tests/benchmarks/corelib/tools/tools.pro @@ -5,6 +5,7 @@ SUBDIRS = \ qbytearray \ qcontiguouscache \ qlist \ + qmap \ qrect \ qregexp \ qstring \ -- cgit v1.2.3