summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/corelib/io/qdatastream.h2
-rw-r--r--src/corelib/tools/qmap.cpp445
-rw-r--r--src/corelib/tools/qmap.h822
-rw-r--r--tests/auto/corelib/tools/qmap/tst_qmap.cpp166
-rw-r--r--tests/benchmarks/corelib/tools/qmap/main.cpp165
-rw-r--r--tests/benchmarks/corelib/tools/qmap/qmap.pro5
-rw-r--r--tests/benchmarks/corelib/tools/tools.pro1
7 files changed, 1048 insertions, 558 deletions
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<aKey, aT> &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<aKey, aT> &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<QMapData *>(&shared_null),
- { const_cast<QMapData *>(&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<Node *>(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<Node *>(this);
- Node *cur = e->forward[0];
- Node *prev;
- while (cur != e) {
- prev = cur;
- cur = cur->forward[0];
- if (strictAlignment)
- qFreeAligned(reinterpret_cast<char *>(prev) - offset);
- else
- free(reinterpret_cast<char *>(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<Node *>(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<Node *>(reinterpret_cast<char *>(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<char *>(node) - offset);
- else
- free(reinterpret_cast<char *>(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<Node *>(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<QString> output(topLevel + 1);
- Node *e = reinterpret_cast<Node *>(this);
+QMapNodeBase *QMapDataBase::createNode(int alloc, int alignment, QMapNodeBase *parent, bool left)
+{
+ QMapNodeBase *node = static_cast<QMapNodeBase *>(qMapAllocate(alloc, alignment));
+ Q_CHECK_PTR(node);
- QString str;
- str.sprintf(" %.8x", adjust_ptr(reinterpret_cast<Node *>(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<Node *>(forward[i])));
- output[i] += str;
- update[i] = reinterpret_cast<Node *>(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<Node *>(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<T> 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 <QtCore/qiterator.h>
#include <QtCore/qlist.h>
#include <QtCore/qrefcount.h>
+#include <QtCore/qpair.h>
+
+#ifdef Q_MAP_DEBUG
+#include <QtCore/qdebug.h>
+#endif
#ifndef QT_NO_STL
#include <map>
@@ -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 <class Key> inline bool qMapLessThanKey(const Key &key1, const Key &key
return key1 < key2;
}
-template <class Ptr> inline bool qMapLessThanKey(Ptr *key1, Ptr *key2)
+template <class Ptr> 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 <class Ptr> inline bool qMapLessThanKey(const Ptr *key1, const Ptr *key2)
+struct QMapDataBase;
+template <class Key, class T> 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<QMapNodeBase *>(const_cast<const QMapNodeBase *>(this)->nextNode()); }
+ const QMapNodeBase *previousNode() const;
+ QMapNodeBase *previousNode() { return const_cast<QMapNodeBase *>(const_cast<const QMapNodeBase *>(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<QMapNodeBase *>(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 <class Key, class T>
-struct QMapNode {
+struct QMapNode : public QMapNodeBase
+{
Key key;
T value;
+ inline QMapNode *leftNode() const { return static_cast<QMapNode *>(left); }
+ inline QMapNode *rightNode() const { return static_cast<QMapNode *>(right); }
+
+ inline const QMapNode *nextNode() const { return static_cast<const QMapNode *>(QMapNodeBase::nextNode()); }
+ inline const QMapNode *previousNode() const { return static_cast<const QMapNode *>(QMapNodeBase::previousNode()); }
+ inline QMapNode *nextNode() { return static_cast<QMapNode *>(QMapNodeBase::nextNode()); }
+ inline QMapNode *previousNode() { return static_cast<QMapNode *>(QMapNodeBase::previousNode()); }
+
+ QMapNode *minimumNode() { return static_cast<QMapNode *>(QMapNodeBase::minimumNode()); }
+ QMapNode *maximumNode() { return static_cast<QMapNode *>(QMapNodeBase::maximumNode()); }
+ const QMapNode *minimumNode() const { return static_cast<QMapNode *>(QMapNodeBase::minimumNode()); }
+ const QMapNode *maximumNode() const { return static_cast<QMapNode *>(QMapNodeBase::maximumNode()); }
+
+ QMapNode<Key, T> *copy(QMapData<Key, T> *d) const;
+
+ void destroySubTree();
+
+ QMapNode<Key, T> *lowerBound(const Key &key);
+ QMapNode<Key, T> *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 <class Key, class T>
-struct QMapPayloadNode
+inline QMapNode<Key, T> *QMapNode<Key, T>::lowerBound(const Key &akey)
{
- Key key;
- T value;
+ QMapNode<Key, T> *n = this;
+ QMapNode<Key, T> *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 <class Key, class T>
+inline QMapNode<Key, T> *QMapNode<Key, T>::upperBound(const Key &akey)
+{
+ QMapNode<Key, T> *n = this;
+ QMapNode<Key, T> *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 Key, class T>
-class QMap
+struct QMapData : public QMapDataBase
{
typedef QMapNode<Key, T> Node;
- typedef QMapPayloadNode<Key, T> PayloadNode;
- union {
- QMapData *d;
- QMapData::Node *e;
- };
+ Node *root() const { return static_cast<Node *>(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<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(); }
+
+ 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<Node *>(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<Node *>(reinterpret_cast<char *>(node) - payload());
+
+ static QMapData *create() {
+ return static_cast<QMapData *>(createData());
}
+ void free() {
+ if (root()) {
+ root()->destroySubTree();
+ freeTree(header.left, Q_ALIGNOF(Node));
+ }
+ freeData(this);
+ }
+};
+
+template <class Key, class T>
+QMapNode<Key, T> *QMapNode<Key, T>::copy(QMapData<Key, T> *d) const
+{
+ QMapNode<Key, T> *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 <class Key, class T>
+void QMapNode<Key, T>::destroySubTree()
+{
+ if (QTypeInfo<Key>::isComplex)
+ key.~Key();
+ if (QTypeInfo<T>::isComplex)
+ value.~T();
+ if (QTypeInfo<Key>::isComplex || QTypeInfo<T>::isComplex) {
+ if (left)
+ leftNode()->destroySubTree();
+ if (right)
+ rightNode()->destroySubTree();
+ }
+}
+
+template <class Key, class T>
+void QMapData<Key, T>::deleteNode(QMapNode<Key, T> *z)
+{
+ if (QTypeInfo<Key>::isComplex)
+ z->key.~Key();
+ if (QTypeInfo<T>::isComplex)
+ z->value.~T();
+ freeNodeAndRebalance(z);
+}
+
+template <class Key, class T>
+QMapNode<Key, T> *QMapData<Key, T>::findNode(const Key &akey) const
+{
+ Node *lb = root()->lowerBound(akey);
+ if (lb && !qMapLessThanKey(akey, lb->key))
+ return lb;
+ return 0;
+}
+
+
+template <class Key, class T>
+void QMapData<Key, T>::nodeRange(const Key &akey, QMapNode<Key, T> **first, QMapNode<Key, T> **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 Key, class T>
+class QMap
+{
+ typedef QMapNode<Key, T> Node;
+
+ QMapData<Key, T> *d;
+
public:
- inline QMap() : d(const_cast<QMapData *>(&QMapData::shared_null)) { }
- inline QMap(const QMap<Key, T> &other) : d(other.d)
- { d->ref.ref(); if (!d->sharable) detach(); }
- inline ~QMap() { if (!d->ref.deref()) freeData(d); }
+ inline QMap() : d(static_cast<QMapData<Key, T> *>(const_cast<QMapDataBase *>(&QMapDataBase::shared_null))) { }
+ QMap(const QMap<Key, T> &other);
+
+ inline ~QMap() { if (!d->ref.deref()) d->free(); }
QMap<Key, T> &operator=(const QMap<Key, T> &other);
#ifdef Q_COMPILER_RVALUE_REFS
+ inline QMap(QMap<Key, T> &&other)
+ : d(other.d)
+ {
+ other.d = static_cast<QMapData<Key, T> *>(
+ const_cast<QMapDataBase *>(&QMapDataBase::shared_null));
+ }
+
inline QMap<Key, T> &operator=(QMap<Key, T> &&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<Key, T> &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<Key, T>;
};
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<Key, T>;
};
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<iterator, iterator> 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 <class Key, class T>
-Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::operator=(const QMap<Key, T> &other)
+inline QMap<Key, T>::QMap(const QMap<Key, T> &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 <class Key, class T>
-Q_INLINE_TEMPLATE void QMap<Key, T>::clear()
-{
- *this = QMap<Key, T>();
-}
-
-template <class Key, class T>
-Q_INLINE_TEMPLATE typename QMapData::Node *
-QMap<Key, T>::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<Key, T>::create();
+ if (other.d->header.left) {
+ d->header.left = static_cast<Node *>(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<QMapData::Node *>(adt) || aupdate[i]->forward[i] != abstractNode)
- break;
- aupdate[i] = abstractNode;
- }
-*/
-
- return abstractNode;
}
template <class Key, class T>
-Q_INLINE_TEMPLATE QMapData::Node *QMap<Key, T>::findNode(const Key &akey) const
+Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::operator=(const QMap<Key, T> &other)
{
- QMapData::Node *cur = e;
- QMapData::Node *next = e;
-
- for (int i = d->topLevel; i >= 0; i--) {
- while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))
- cur = next;
- }
-
- if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
- return next;
- } else {
- return e;
+ if (d != other.d) {
+ QMap<Key, T> tmp(other);
+ tmp.swap(*this);
}
+ return *this;
}
template <class Key, class T>
-Q_INLINE_TEMPLATE const T QMap<Key, T>::value(const Key &akey) const
+Q_INLINE_TEMPLATE void QMap<Key, T>::clear()
{
- QMapData::Node *node;
- if (d->size == 0 || (node = findNode(akey)) == e) {
- return T();
- } else {
- return concrete(node)->value;
- }
+ *this = QMap<Key, T>();
}
+
template <class Key, class T>
Q_INLINE_TEMPLATE const T QMap<Key, T>::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 <class Key, class T>
@@ -510,24 +604,25 @@ template <class Key, class T>
Q_INLINE_TEMPLATE T &QMap<Key, T>::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 <class Key, class T>
Q_INLINE_TEMPLATE int QMap<Key, T>::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<Key>(akey, concrete(node)->key));
+ while (first != last) {
+ ++cnt;
+ ++first;
}
return cnt;
}
@@ -535,23 +630,34 @@ Q_INLINE_TEMPLATE int QMap<Key, T>::count(const Key &akey) const
template <class Key, class T>
Q_INLINE_TEMPLATE bool QMap<Key, T>::contains(const Key &akey) const
{
- return findNode(akey) != e;
+ return d->findNode(akey) != 0;
}
template <class Key, class T>
-Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insert(const Key &akey,
- const T &avalue)
+Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::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 <class Key, class T>
@@ -559,29 +665,37 @@ Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::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<Node *>(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 <class Key, class T>
-Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::find(const Key &akey) const
+Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::constFind(const Key &akey) const
{
- return const_iterator(findNode(akey));
+ Node *n = d->findNode(akey);
+ return const_iterator(n ? n : d->end());
}
template <class Key, class T>
-Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::constFind(const Key &akey) const
+Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::find(const Key &akey) const
{
- return const_iterator(findNode(akey));
+ return constFind(akey);
}
template <class Key, class T>
Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::find(const Key &akey)
{
detach();
- return iterator(findNode(akey));
+ Node *n = d->findNode(akey);
+ return iterator(n ? n : d->end());
}
template <class Key, class T>
@@ -598,56 +712,46 @@ Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::unite(const QMap<Key, T> &other)
}
template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE void QMap<Key, T>::freeData(QMapData *x)
+QPair<typename QMap<Key, T>::iterator, typename QMap<Key, T>::iterator> QMap<Key, T>::equal_range(const Key &akey)
{
- if (QTypeInfo<Key>::isComplex || QTypeInfo<T>::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<QMapData::Node *>(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, iterator>(iterator(first), iterator(last));
+}
+
+#ifdef Q_MAP_DEBUG
+template <class Key, class T>
+void QMap<Key, T>::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 <class Key, class T>
Q_OUTOFLINE_TEMPLATE int QMap<Key, T>::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<Key>(concrete(next)->key, akey))
- cur = next;
- update[i] = cur;
- }
-
- if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
- bool deleteNext = true;
- do {
- cur = next;
- next = cur->forward[0];
- deleteNext = (next != e && !qMapLessThanKey<Key>(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 <class Key, class T>
@@ -655,21 +759,10 @@ Q_OUTOFLINE_TEMPLATE T QMap<Key, T>::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<Key>(concrete(next)->key, akey))
- cur = next;
- update[i] = cur;
- }
-
- if (next != e && !qMapLessThanKey<Key>(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<Key, T>::take(const Key &akey)
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::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<Key>(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 <class Key, class T>
Q_OUTOFLINE_TEMPLATE void QMap<Key, T>::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<Key, T> *x = QMapData<Key, T>::create();
+ if (d->header.left) {
+ x->header.left = static_cast<Node *>(d->header.left)->copy(x);
+ x->header.left->setParent(&x->header);
}
if (!d->ref.deref())
- freeData(d);
- d = x.d;
-}
-
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE QMapData::Node *QMap<Key, T>::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<Key>(concrete(next)->key, akey))
- cur = next;
- aupdate[i] = cur;
- }
- if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
- return next;
- } else {
- return e;
- }
+ d->free();
+ d = x;
}
template <class Key, class T>
@@ -769,7 +806,7 @@ Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::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:
@@ -803,12 +840,6 @@ Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys(const T &avalue) const
}
template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE const Key QMap<Key, T>::key(const T &avalue) const
-{
- return key(avalue, Key());
-}
-
-template <class Key, class T>
Q_OUTOFLINE_TEMPLATE const Key QMap<Key, T>::key(const T &avalue, const Key &defaultKey) const
{
const_iterator i = begin();
@@ -838,49 +869,54 @@ template <class Key, class T>
Q_OUTOFLINE_TEMPLATE QList<T> QMap<Key, T>::values(const Key &akey) const
{
QList<T> 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<Key>(akey, concrete(node)->key));
+ res.append(*it);
+ ++it;
+ } while (it != constEnd() && !qMapLessThanKey<Key>(akey, it.key()));
}
return res;
}
template <class Key, class T>
-Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator
-QMap<Key, T>::lowerBound(const Key &akey) const
+Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::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 <class Key, class T>
Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::lowerBound(const Key &akey)
{
detach();
- return static_cast<QMapData::Node *>(const_cast<const QMap *>(this)->lowerBound(akey));
+ Node *lb = d->root()->lowerBound(akey);
+ if (!lb)
+ lb = d->end();
+ return iterator(lb);
}
template <class Key, class T>
Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator
QMap<Key, T>::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<Key>(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 <class Key, class T>
Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::upperBound(const Key &akey)
{
detach();
- return static_cast<QMapData::Node *>(const_cast<const QMap *>(this)->upperBound(akey));
+ Node *ub = d->root()->upperBound(akey);
+ if (!ub)
+ ub = d->end();
+ return iterator(ub);
}
template <class Key, class T>
@@ -907,14 +943,12 @@ Q_OUTOFLINE_TEMPLATE bool QMap<Key, T>::operator==(const QMap<Key, T> &other) co
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE QMap<Key, T>::QMap(const std::map<Key, T> &other)
{
- d = QMapData::createData(alignment());
- d->insertInOrder = true;
+ d = QMapData<Key, T>::create();
typename std::map<Key,T>::const_iterator it = other.end();
while (it != other.begin()) {
--it;
insert((*it).first, (*it).second);
}
- d->insertInOrder = false;
}
template <class Key, class T>
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 <qmap.h>
#include <QtTest/QtTest>
#include <QDebug>
-#include <qmap.h>
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<QString, QString> StringMap;
@@ -105,6 +110,11 @@ int MyClass::count = 0;
typedef QMap<QString, MyClass> 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<int, QString>::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<int, QString> map2;
map2.setSharable(true);
QVERIFY(!map2.isDetached());
+}
+
+void tst_QMap::equal_range()
+{
+ QMap<int, QString> map;
+
+ QPair<QMap<int, QString>::iterator, QMap<int, QString>::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<int, QString> 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 <class T>
+const T &const_(const T &t)
+{
+ return t;
+}
+
+void tst_QMap::setSharable()
+{
+ QMap<int, QString> 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<int, QString> 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<int, QString> 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<int, QString> copy(map);
+
+ QVERIFY(!map.isDetached());
+ QVERIFY(copy.isSharedWith(map));
+ }
+}
+
+void tst_QMap::insert()
+{
+ QMap<QString, float> map;
+ map.insert("cs/key1", 1);
+ map.insert("cs/key2", 2);
+ map.insert("cs/key1", 3);
+ QCOMPARE(map.count(), 2);
+
+ QMap<int, int> 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 <QFile>
+#include <QMap>
+#include <QString>
+#include <QTest>
+#include <qdebug.h>
+
+
+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<int, int> map;
+ QBENCHMARK {
+ for (int i = 0; i < 100000; ++i)
+ map.insert(i, i);
+ }
+}
+
+void tst_QMap::insertion_int_string()
+{
+ QMap<int, QString> map;
+ QString str("Hello World");
+ QBENCHMARK {
+ for (int i = 0; i < 100000; ++i)
+ map.insert(i, str);
+ }
+}
+
+void tst_QMap::insertion_string_int()
+{
+ QMap<QString, int> 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<int, int> 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<int, QString> 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<QString, int> 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<int, int> map;
+ for (int i = 0; i < 100000; ++i)
+ map.insert(i, i);
+
+ int j = 0;
+ QBENCHMARK {
+ for (int i = 0; i < 100; ++i) {
+ QMap<int, int>::const_iterator it = map.constBegin();
+ QMap<int, int>::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 \
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-10 21:23:28 +0000