From 5cb0368516abd293daf67711a36bbacc99422e9a Mon Sep 17 00:00:00 2001 From: Lars Knoll Date: Mon, 19 Mar 2012 20:53:20 +0100 Subject: Rewrite QMap to use a RB tree QMap used to use a skiplist in Qt 4.x, which has variable sized nodes and we can thus not optimise using custom allocators. The rewrite now uses a red-black tree, and all allocations and tree operations happen in the cpp file. This will allow us to introduce custom allocation schemes in later versions of Qt. Added some more tests and a benchmark. Memory consumption of the new QMap implementation is pretty much the same as before. Performance of insertion and lookup has increased by 10-30%. iteration is slower, but still extremely fast and should not matter compared to the work usually done when iterating. Change-Id: I8796c0e4b207d01111e2ead7ae55afb464dd88f5 Reviewed-by: Thiago Macieira --- src/corelib/tools/qmap.cpp | 445 +++++++++++++++++++++++++++++---------------- 1 file changed, 287 insertions(+), 158 deletions(-) (limited to 'src/corelib/tools/qmap.cpp') 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 -- cgit v1.2.3