From f0533ba8c22d6366f9d4fb8e8ce18554cd0d01e9 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Thorbj=C3=B8rn=20Martsum?= <tmartsum@gmail.com>
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 <thiago.macieira@intel.com>
---
 src/corelib/tools/qmap.h | 54 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 54 insertions(+)

(limited to 'src/corelib/tools/qmap.h')

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
@@ -746,6 +747,57 @@ Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(cons
     return iterator(z);
 }
 
+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
 {
@@ -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; }
-- 
cgit v1.2.3