From f0533ba8c22d6366f9d4fb8e8ce18554cd0d01e9 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Thorbj=C3=B8rn=20Martsum?= Date: Tue, 15 Jan 2013 16:09:44 +0100 Subject: QMap - add multiInsert with hint This provides a fast multiInsert in QMap (and a fast insert in QMultiMap) when providing a correct hint. Change-Id: I3c864c3a7842765fe63f8ecb4b54d0e8c9fd22d7 Reviewed-by: Thiago Macieira --- src/corelib/tools/qmap.cpp | 37 +++++++++++++++++ src/corelib/tools/qmap.h | 54 ++++++++++++++++++++++++ tests/auto/corelib/tools/qmap/tst_qmap.cpp | 66 ++++++++++++++++++++++++++++++ 3 files changed, 157 insertions(+) diff --git a/src/corelib/tools/qmap.cpp b/src/corelib/tools/qmap.cpp index 21ac059a01..e5de4a1bfd 100644 --- a/src/corelib/tools/qmap.cpp +++ b/src/corelib/tools/qmap.cpp @@ -1019,6 +1019,26 @@ void QMapDataBase::freeData(QMapDataBase *d) \sa insert(), values() */ +/*! \fn QMap::iterator QMap::insertMulti(const_iterator pos, const Key &key, const T &value) + \overload + \since 5.1 + Inserts a new item with the key \a key and value \a value and with hint \a pos + suggesting where to do the insert. + + If constBegin() is used as hint it indicates that the \a key is less than any key in the map + while constEnd() suggests that the \a key is larger than any key in the map. + Otherwise the hint should meet the condition (\a pos - 1).key() < \a key <= pos.key(). + If the hint \a pos is wrong it is ignored and a regular insertMulti is done. + + If there is already an item with the same key in the map, this function will simply create a new one. + + \b {Note:} Be careful with the hint. Providing an iterator from an older shared instance might + crash but there is also a risk that it will silently corrupt both the map and the \a pos map. + + \sa insert() +*/ + + /*! \fn QMap &QMap::unite(const QMap &other) Inserts all the items in the \a other map into this map. If a @@ -1655,6 +1675,23 @@ void QMapDataBase::freeData(QMapDataBase *d) \sa replace() */ +/*! \fn QMultiMap::iterator QMultiMap::insert(QMap::const_iterator pos, const Key &key, const T &value) + + \since 5.1 + Inserts a new item with the key \a key and value \a value and with hint \a pos + suggesting where to do the insert. + + If constBegin() is used as hint it indicates that the \a key is less than any key in the map + while constEnd() suggests that the \a key is larger than any key in the map. + Otherwise the hint should meet the condition (\a pos - 1).key() < \a key <= pos.key(). + If the hint \a pos is wrong it is ignored and a regular insert is done. + + If there is already an item with the same key in the map, this function will simply create a new one. + + \b {Note:} Be careful with the hint. Providing an iterator from an older shared instance might + crash but there is also a risk that it will silently corrupt both the map and the \a pos map. +*/ + /*! \fn QMultiMap &QMultiMap::operator+=(const QMultiMap &other) Inserts all the items in the \a other map into this map and diff --git a/src/corelib/tools/qmap.h b/src/corelib/tools/qmap.h index 31a891b0c2..449fcbca0a 100644 --- a/src/corelib/tools/qmap.h +++ b/src/corelib/tools/qmap.h @@ -540,6 +540,7 @@ public: iterator insert(const Key &key, const T &value); iterator insert(const_iterator pos, const Key &key, const T &value); iterator insertMulti(const Key &key, const T &value); + iterator insertMulti(const_iterator pos, const Key &akey, const T &avalue); QMap &unite(const QMap &other); // STL compatibility @@ -746,6 +747,57 @@ Q_INLINE_TEMPLATE typename QMap::iterator QMap::insertMulti(cons return iterator(z); } +template +typename QMap::iterator QMap::insertMulti(const_iterator pos, const Key &akey, const T &avalue) +{ + if (d->ref.isShared()) + return this->insertMulti(akey, avalue); + + if (pos == constEnd()) { + // Hint is that the Node is larger than (or equal to) the largest value. + Node *n = static_cast(pos.i->left); + if (n) { + while (n->right) + n = static_cast(n->right); + + if (!qMapLessThanKey(n->key, akey)) + return this->insertMulti(akey, avalue); // ignore hint + Node *z = d->createNode(akey, avalue, n, false); // insert right most + return iterator(z); + } + return this->insertMulti(akey, avalue); + } else { + // Hint indicates that the node should be less (or equal to) the hint given + // but larger than the previous value. + Node *next = const_cast(pos.i); + if (qMapLessThanKey(next->key, akey)) + return this->insertMulti(akey, avalue); // ignore hint + + if (pos == constBegin()) { + // There is no previous value (insert left most) + Node *z = d->createNode(akey, avalue, begin().i, true); + return iterator(z); + } else { + Node *prev = const_cast(pos.i->previousNode()); + if (!qMapLessThanKey(prev->key, akey)) + return this->insertMulti(akey, avalue); // ignore hint + + // Hint is ok - do insert + if (prev->right == 0) { + Node *z = d->createNode(akey, avalue, prev, false); + return iterator(z); + } + if (next->left == 0) { + Node *z = d->createNode(akey, avalue, next, true); + return iterator(z); + } + Q_ASSERT(false); // We should have prev->right == 0 or next->left == 0. + return this->insertMulti(akey, avalue); + } + } +} + + template Q_INLINE_TEMPLATE typename QMap::const_iterator QMap::constFind(const Key &akey) const { @@ -1051,6 +1103,8 @@ public: { return QMap::insert(key, value); } inline typename QMap::iterator insert(const Key &key, const T &value) { return QMap::insertMulti(key, value); } + inline typename QMap::iterator insert(typename QMap::const_iterator pos, const Key &key, const T &value) + { return QMap::insertMulti(pos, key, value); } inline QMultiMap &operator+=(const QMultiMap &other) { this->unite(other); return *this; } diff --git a/tests/auto/corelib/tools/qmap/tst_qmap.cpp b/tests/auto/corelib/tools/qmap/tst_qmap.cpp index 66063d0262..0742f19a5e 100644 --- a/tests/auto/corelib/tools/qmap/tst_qmap.cpp +++ b/tests/auto/corelib/tools/qmap/tst_qmap.cpp @@ -86,6 +86,7 @@ private slots: void checkMostLeftNode(); void initializerList(); void testInsertWithHint(); + void testInsertMultiWithHint(); }; typedef QMap StringMap; @@ -939,6 +940,18 @@ void tst_QMap::qmultimap_specific() QVERIFY(map2.remove(42,5)); QVERIFY(map1 == map2); } + + map1.insert(map1.constBegin(), -1, -1); + QCOMPARE(map1.size(), 45); + map1.insert(map1.constBegin(), -1, -1); + QCOMPARE(map1.size(), 46); + map1.insert(map1.constBegin(), -2, -2); + QCOMPARE(map1.size(), 47); + map1.insert(map1.constBegin(), 5, 5); // Invald hint + QCOMPARE(map1.size(), 48); + map1.insert(map1.constBegin(), 5, 5); // Invald hint + QCOMPARE(map1.size(), 49); + sanityCheckTree(map1, __LINE__); } void tst_QMap::const_shared_null() @@ -1224,5 +1237,58 @@ void tst_QMap::testInsertWithHint() QCOMPARE(map.size(), 12); } +void tst_QMap::testInsertMultiWithHint() +{ + QMap map; + map.setSharable(false); + + typedef QMap::const_iterator cite; // Hack since we define QT_STRICT_ITERATORS + map.insertMulti(cite(map.end()), 64, 65); + map[128] = 129; + map[256] = 257; + sanityCheckTree(map, __LINE__); + + map.insertMulti(cite(map.end()), 512, 513); + map.insertMulti(cite(map.end()), 512, 513 * 2); + sanityCheckTree(map, __LINE__); + QCOMPARE(map.size(), 5); + map.insertMulti(cite(map.end()), 256, 258); // wrong hint + sanityCheckTree(map, __LINE__); + QCOMPARE(map.size(), 6); + + QMap::iterator i = map.insertMulti(map.constBegin(), 256, 259); // wrong hint + sanityCheckTree(map, __LINE__); + QCOMPARE(map.size(), 7); + + QMap::iterator j = map.insertMulti(map.constBegin(), 69, 66); + sanityCheckTree(map, __LINE__); + QCOMPARE(map.size(), 8); + + j = map.insertMulti(cite(j), 68, 259); + sanityCheckTree(map, __LINE__); + QCOMPARE(map.size(), 9); + + j = map.insertMulti(cite(j), 67, 67); + sanityCheckTree(map, __LINE__); + QCOMPARE(map.size(), 10); + + i = map.insertMulti(cite(i), 256, 259); + sanityCheckTree(map, __LINE__); + QCOMPARE(map.size(), 11); + + i = map.insertMulti(cite(i), 256, 260); + sanityCheckTree(map, __LINE__); + QCOMPARE(map.size(), 12); + + map.insertMulti(cite(i), 64, 67); + sanityCheckTree(map, __LINE__); + QCOMPARE(map.size(), 13); + + map.insertMulti(map.constBegin(), 20, 20); + sanityCheckTree(map, __LINE__); + QCOMPARE(map.size(), 14); +} + + QTEST_APPLESS_MAIN(tst_QMap) #include "tst_qmap.moc" -- cgit v1.2.3