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 <thiago.macieira@intel.com>

3 files changed, 157 insertions, 0 deletions

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<Key, T> &QMap::unite(const QMap<Key, T> &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<Key, T>::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<Key, T> &unite(const QMap<Key, T> &other);
 
     // STL compatibility
@@ -747,6 +748,57 @@ Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(cons
 }
 
 template <class Key, class T>
+typename QMap<Key, T>::iterator QMap<Key, T>::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<Node *>(pos.i->left);
+        if (n) {
+            while (n->right)
+                n = static_cast<Node *>(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<Node*>(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<Node*>(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 <class Key, class T>
 Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::constFind(const Key &akey) const
 {
     Node *n = d->findNode(akey);
@@ -1051,6 +1103,8 @@ public:
     { return QMap<Key, T>::insert(key, value); }
     inline typename QMap<Key, T>::iterator insert(const Key &key, const T &value)
     { return QMap<Key, T>::insertMulti(key, value); }
+    inline typename QMap<Key, T>::iterator insert(typename QMap<Key, T>::const_iterator pos, const Key &key, const T &value)
+    { return QMap<Key, T>::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<QString, QString> 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<int, int> map;
+    map.setSharable(false);
+
+    typedef QMap<int, int>::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<int, int>::iterator i = map.insertMulti(map.constBegin(), 256, 259); // wrong hint
+    sanityCheckTree(map, __LINE__);
+    QCOMPARE(map.size(), 7);
+
+    QMap<int, int>::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"