From ca6a4258d0816b3608295eb40ac89cfd82bab5bd Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Thorbj=C3=B8rn=20Lund=20Martsum?= Date: Fri, 5 Oct 2012 15:58:56 +0200 Subject: QMap - add insert overload that provide a hint This adds a fast insert on QMap when providing a correct hint. Change-Id: I256bba342932c1d4f24c6e65074e1bf47b519537 Reviewed-by: Thiago Macieira Reviewed-by: Lars Knoll --- src/corelib/tools/qmap.cpp | 26 ++++++++++ src/corelib/tools/qmap.h | 67 ++++++++++++++++++++++++ tests/auto/corelib/tools/qmap/tst_qmap.cpp | 65 +++++++++++++++++++++++ tests/benchmarks/corelib/tools/qmap/main.cpp | 78 ++++++++++++++++++++++++++++ 4 files changed, 236 insertions(+) diff --git a/src/corelib/tools/qmap.cpp b/src/corelib/tools/qmap.cpp index a4c28b5bd4..21ac059a01 100644 --- a/src/corelib/tools/qmap.cpp +++ b/src/corelib/tools/qmap.cpp @@ -981,6 +981,32 @@ void QMapDataBase::freeData(QMapDataBase *d) \sa insertMulti() */ +/*! \fn QMap::iterator QMap::insert(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 (strictly) 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 key \a key, that item's value + is replaced with \a value. + + If there are multiple items with the key \a key, then exactly one of them + is replaced with \a value. + + When creating a map from sorted data inserting the largest key first with constBegin() + is faster than inserting in sorted order with constEnd() + + \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 insertMulti() +*/ + /*! \fn QMap::iterator QMap::insertMulti(const Key &key, const T &value) Inserts a new item with the key \a key and a value of \a value. diff --git a/src/corelib/tools/qmap.h b/src/corelib/tools/qmap.h index 280696c534..31a891b0c2 100644 --- a/src/corelib/tools/qmap.h +++ b/src/corelib/tools/qmap.h @@ -538,6 +538,7 @@ public: iterator upperBound(const Key &key); const_iterator upperBound(const Key &key) const; 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); QMap &unite(const QMap &other); @@ -662,6 +663,72 @@ Q_INLINE_TEMPLATE typename QMap::iterator QMap::insert(const Key return iterator(z); } +template +typename QMap::iterator QMap::insert(const_iterator pos, const Key &akey, const T &avalue) +{ + if (d->ref.isShared()) + return this->insert(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->insert(akey, avalue); // ignore hint + // This can be optimized by checking equal too. + // we can overwrite if previous node key is strictly smaller + // (or there is no previous node) + + Node *z = d->createNode(akey, avalue, n, false); // insert right most + return iterator(z); + } + return this->insert(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->insert(akey, avalue); // ignore hint + + if (pos == constBegin()) { + // There is no previous value + // Maybe overwrite left most value + if (!qMapLessThanKey(akey, next->key)) { + next->value = avalue; // overwrite current iterator + return iterator(next); + } + // 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->insert(akey, avalue); // ignore hint + } + // Hint is ok + if (!qMapLessThanKey(akey, next->key)) { + next->value = avalue; // overwrite current iterator + return iterator(next); + } + + // we need to insert (not overwrite) + 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->insert(akey, avalue); + } + } +} + template Q_INLINE_TEMPLATE typename QMap::iterator QMap::insertMulti(const Key &akey, const T &avalue) diff --git a/tests/auto/corelib/tools/qmap/tst_qmap.cpp b/tests/auto/corelib/tools/qmap/tst_qmap.cpp index 801656e1c3..66063d0262 100644 --- a/tests/auto/corelib/tools/qmap/tst_qmap.cpp +++ b/tests/auto/corelib/tools/qmap/tst_qmap.cpp @@ -85,6 +85,7 @@ private slots: void insert(); void checkMostLeftNode(); void initializerList(); + void testInsertWithHint(); }; typedef QMap StringMap; @@ -1159,5 +1160,69 @@ void tst_QMap::initializerList() #endif } +void tst_QMap::testInsertWithHint() +{ + QMap map; + map.setSharable(false); + + // Check with end hint(); + map.insert(map.constEnd(), 3, 1); // size == 1 + sanityCheckTree(map, __LINE__); + map.insert(map.constEnd(), 5, 1); // size = 2 + sanityCheckTree(map, __LINE__); + map.insert(map.constEnd(), 50, 1); // size = 3 + sanityCheckTree(map, __LINE__); + QMap::const_iterator key75(map.insert(map.constEnd(), 75, 1)); // size = 4 + sanityCheckTree(map, __LINE__); + map.insert(map.constEnd(), 100, 1); // size = 5 + sanityCheckTree(map, __LINE__); + map.insert(map.constEnd(), 105, 1); // size = 6 + sanityCheckTree(map, __LINE__); + map.insert(map.constEnd(), 10, 5); // invalid hint and size = 7 + sanityCheckTree(map, __LINE__); + QMap::iterator lastkey = map.insert(map.constEnd(), 105, 12); // overwrite + sanityCheckTree(map, __LINE__); + QCOMPARE(lastkey.value(), 12); + QCOMPARE(lastkey.key(), 105); + QCOMPARE(map.size(), 7); + + // With regular hint + map.insert(key75, 75, 100); // overwrite current key + sanityCheckTree(map, __LINE__); + QCOMPARE(map.size(), 7); + QCOMPARE(key75.key(), 75); + QCOMPARE(key75.value(), 100); + + map.insert(key75, 50, 101); // overwrite previous value + QMap::const_iterator key50(key75); + --key50; + QCOMPARE(map.size(), 7); + QCOMPARE(key50.key(), 50); + QCOMPARE(key50.value(), 101); + + map.insert(key75, 17, 125); // invalid hint - size 8 + sanityCheckTree(map, __LINE__); + QCOMPARE(map.size(), 8); + + // begin + map.insert(map.constBegin(), 1, 1); // size 9 + sanityCheckTree(map, __LINE__); + QCOMPARE(map.size(), 9); + + map.insert(map.constBegin(), 1, 10); // overwrite existing (leftmost) value + QCOMPARE(map.constBegin().value(), 10); + + map.insert(map.constBegin(), 47, 47); // wrong hint - size 10 + sanityCheckTree(map, __LINE__); + QCOMPARE(map.size(), 10); + + // insert with right == 0 + QMap::const_iterator i1 (map.insert(key75, 70, 12)); // overwrite + map.insert(i1, 69, 12); // size 12 + + sanityCheckTree(map, __LINE__); + QCOMPARE(map.size(), 12); +} + QTEST_APPLESS_MAIN(tst_QMap) #include "tst_qmap.moc" diff --git a/tests/benchmarks/corelib/tools/qmap/main.cpp b/tests/benchmarks/corelib/tools/qmap/main.cpp index e0bd994967..53b2a90fab 100644 --- a/tests/benchmarks/corelib/tools/qmap/main.cpp +++ b/tests/benchmarks/corelib/tools/qmap/main.cpp @@ -64,6 +64,14 @@ private slots: void iterator_begin(); void ctorStdMap(); + + void insertion_int_intx(); + void insertion_int_int_with_hint1(); + void insertion_int_int2(); + void insertion_int_int_with_hint2(); + + void insertion_string_int2(); + void insertion_string_int2_hint(); }; @@ -76,6 +84,44 @@ void tst_QMap::insertion_int_int() } } +void tst_QMap::insertion_int_intx() +{ + // This is the same test - but executed later. + // The results in the beginning of the test seems to be a somewhat inaccurate. + QMap map; + QBENCHMARK { + for (int i = 0; i < 100000; ++i) + map.insert(i, i); + } +} + +void tst_QMap::insertion_int_int_with_hint1() +{ + QMap map; + QBENCHMARK { + for (int i = 0; i < 100000; ++i) + map.insert(map.constEnd(), i, i); + } +} + +void tst_QMap::insertion_int_int2() +{ + QMap map; + QBENCHMARK { + for (int i = 100000; i >= 0; --i) + map.insert(i, i); + } +} + +void tst_QMap::insertion_int_int_with_hint2() +{ + QMap map; + QBENCHMARK { + for (int i = 100000; i >= 0; --i) + map.insert(map.constBegin(), i, i); + } +} + void tst_QMap::insertion_int_string() { QMap map; @@ -203,6 +249,38 @@ void tst_QMap::ctorStdMap() } } +class XString : public QString +{ +public: + bool operator < (const XString& x) const // an expensive operator < + { + return toInt() < x.toInt(); + } +}; + +void tst_QMap::insertion_string_int2() +{ + QMap map; + QBENCHMARK { + for (int i = 1; i < 5000; ++i) { + XString str; + str.setNum(i); + map.insert(str, i); + } + } +} + +void tst_QMap::insertion_string_int2_hint() +{ + QMap map; + QBENCHMARK { + for (int i = 1; i < 5000; ++i) { + XString str; + str.setNum(i); + map.insert(map.end(), str, i); + } + } +} QTEST_MAIN(tst_QMap) -- cgit v1.2.3