QCborArray & Map: implement efficient take() / extract()

Questions:
 1) should QCborMap::extract return value_type (a pair) instead of just
    the value?
 2) should the both return the iterator to the next element too, like
    erase()?

Change-Id: I052407b777ec43f78378fffd15302a9c14468db3
Reviewed-by: Edward Welbourne <edward.welbourne@qt.io>
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>

7 files changed, 197 insertions, 10 deletions

diff --git a/src/corelib/serialization/qcborarray.cpp b/src/corelib/serialization/qcborarray.cpp
index 020841d604..a1b0d1573c 100644
--- a/src/corelib/serialization/qcborarray.cpp
+++ b/src/corelib/serialization/qcborarray.cpp
@@ -42,6 +42,8 @@
 
 QT_BEGIN_NAMESPACE
 
+using namespace QtCbor;
+
 /*!
     \class QCborArray
     \inmodule QtCore
@@ -300,7 +302,7 @@ QCborValue QCborArray::at(qsizetype i) const
     must have at least \a i elements before the insertion.
 
     \sa at(), operator[](), first(), last(), prepend(), append(),
-        removeAt(), takeAt()
+        removeAt(), takeAt(), extract()
  */
 void QCborArray::insert(qsizetype i, const QCborValue &value)
 {
@@ -312,6 +314,21 @@ void QCborArray::insert(qsizetype i, const QCborValue &value)
 }
 
 /*!
+    Extracts a value from the array at the position indicated by iterator \a it
+    and returns the value so extracted.
+
+    \sa insert(), erase(), takeAt(), removeAt()
+ */
+QCborValue QCborArray::extract(iterator it)
+{
+    detach();
+
+    QCborValue v = d->extractAt(it.item.i);
+    d->removeAt(it.item.i);
+    return v;
+}
+
+/*!
     \fn void QCborArray::prepend(const QCborValue &value)
 
     Prepends \a value into the array before any other elements it may already
diff --git a/src/corelib/serialization/qcborarray.h b/src/corelib/serialization/qcborarray.h
index f10fcac2cb..0be362480c 100644
--- a/src/corelib/serialization/qcborarray.h
+++ b/src/corelib/serialization/qcborarray.h
@@ -192,8 +192,9 @@ public:
     void insert(qsizetype i, const QCborValue &value);
     void prepend(const QCborValue &value) { insert(0, value); }
     void append(const QCborValue &value) { insert(-1, value); }
+    QCborValue extract(Iterator it);
     void removeAt(qsizetype i);
-    QCborValue takeAt(qsizetype i) { QCborValue v = at(i); removeAt(i); return v; }
+    QCborValue takeAt(qsizetype i) { Q_ASSERT(i < size()); return extract(begin() + i); }
     void removeFirst() { removeAt(0); }
     void removeLast() { removeAt(size() - 1); }
     QCborValue takeFirst() { return takeAt(0); }
diff --git a/src/corelib/serialization/qcbormap.cpp b/src/corelib/serialization/qcbormap.cpp
index 46ac9c1ec8..6b6a56c389 100644
--- a/src/corelib/serialization/qcbormap.cpp
+++ b/src/corelib/serialization/qcbormap.cpp
@@ -42,6 +42,8 @@
 
 QT_BEGIN_NAMESPACE
 
+using namespace QtCbor;
+
 /*!
     \class QCborMap
     \inmodule QtCore
@@ -342,6 +344,22 @@ QVector<QCborValue> QCborMap::keys() const
  */
 
 /*!
+    \fn QCborValue QCborArray::take(qint64 key)
+
+    Removes the key \a key and the corresponding value from the map and returns
+    the value, if it is found. If the map contains no such key, this function does nothing.
+
+    If the map contains more than one key equal to \a key, it is undefined
+    which one this function will remove. QCborMap does not allow inserting
+    duplicate keys, but it is possible to create such a map by decoding a CBOR
+    stream with them. They are usually not permitted and having duplicate keys
+    is usually an indication of a problem in the sender.
+
+    \sa value(qint64), operator[](qint64), find(qint64), contains(qint64),
+      take(QLatin1String), take(const QString &), take(const QCborValue &), insert()
+ */
+
+/*!
     \fn void QCborMap::remove(qint64 key)
 
     Removes the key \a key and the corresponding value from the map, if it is
@@ -451,6 +469,22 @@ QCborValueRef QCborMap::operator[](qint64 key)
  */
 
 /*!
+    \fn QCborValue QCborArray::take(QLatin1String key)
+
+    Removes the key \a key and the corresponding value from the map and returns
+    the value, if it is found. If the map contains no such key, this function does nothing.
+
+    If the map contains more than one key equal to \a key, it is undefined
+    which one this function will remove. QCborMap does not allow inserting
+    duplicate keys, but it is possible to create such a map by decoding a CBOR
+    stream with them. They are usually not permitted and having duplicate keys
+    is usually an indication of a problem in the sender.
+
+    \sa value(QLatin1String), operator[](QLatin1String), find(QLatin1String), contains(QLatin1String),
+      take(qint64), take(const QString &), take(const QCborValue &), insert()
+ */
+
+/*!
     \fn void QCborMap::remove(QLatin1String key)
     \overload
 
@@ -562,6 +596,22 @@ QCborValueRef QCborMap::operator[](QLatin1String key)
  */
 
 /*!
+    \fn QCborValue QCborArray::take(const QString &key)
+
+    Removes the key \a key and the corresponding value from the map and returns
+    the value, if it is found. If the map contains no such key, this function does nothing.
+
+    If the map contains more than one key equal to \a key, it is undefined
+    which one this function will remove. QCborMap does not allow inserting
+    duplicate keys, but it is possible to create such a map by decoding a CBOR
+    stream with them. They are usually not permitted and having duplicate keys
+    is usually an indication of a problem in the sender.
+
+    \sa value(const QString &), operator[](const QString &), find(const QString &), contains(const QString &),
+      take(QLatin1String), take(qint64), take(const QCborValue &), insert()
+ */
+
+/*!
     \fn void QCborMap::remove(const QString &key)
     \overload
 
@@ -673,6 +723,22 @@ QCborValueRef QCborMap::operator[](const QString & key)
  */
 
 /*!
+    \fn QCborValue QCborArray::take(const QCborValue &key)
+
+    Removes the key \a key and the corresponding value from the map and returns
+    the value, if it is found. If the map contains no such key, this function does nothing.
+
+    If the map contains more than one key equal to \a key, it is undefined
+    which one this function will remove. QCborMap does not allow inserting
+    duplicate keys, but it is possible to create such a map by decoding a CBOR
+    stream with them. They are usually not permitted and having duplicate keys
+    is usually an indication of a problem in the sender.
+
+    \sa value(const QCborValue &), operator[](const QCborValue &), find(const QCborValue &), contains(const QCborValue &),
+      take(QLatin1String), take(const QString &), take(qint64), insert()
+ */
+
+/*!
     \fn void QCborMap::remove(const QCborValue &key)
 
     Removes the key \a key and the corresponding value from the map, if it is
@@ -946,7 +1012,7 @@ QCborMap::const_iterator QCborMap::constFind(const QCborValue &key) const
     by \a value.
 
     \sa erase(), remove(qint64), value(qint64), operator[](qint64), find(qint64),
-        contains(qint64)
+        contains(qint64), take(qint64), extract()
  */
 
 /*!
@@ -960,7 +1026,7 @@ QCborMap::const_iterator QCborMap::constFind(const QCborValue &key) const
     by \a value.
 
     \sa erase(), remove(QLatin1String), value(QLatin1String), operator[](QLatin1String),
-        find(QLatin1String), contains(QLatin1String)
+        find(QLatin1String), contains(QLatin1String), take(QLatin1String), extract()
  */
 
 /*!
@@ -974,7 +1040,7 @@ QCborMap::const_iterator QCborMap::constFind(const QCborValue &key) const
     by \a value.
 
     \sa erase(), remove(const QString &), value(const QString &), operator[](const QString &),
-        find(const QString &), contains(const QString &)
+        find(const QString &), contains(const QString &), take(const QString &), extract()
  */
 
 /*!
@@ -988,7 +1054,7 @@ QCborMap::const_iterator QCborMap::constFind(const QCborValue &key) const
     by \a value.
 
     \sa erase(), remove(const QCborValue &), value(const QCborValue &), operator[](const QCborValue &),
-        find(const QCborValue &), contains(const QCborValue &)
+        find(const QCborValue &), contains(const QCborValue &), take(const QCborValue &), extract()
  */
 
 /*!
@@ -1001,7 +1067,7 @@ QCborMap::const_iterator QCborMap::constFind(const QCborValue &key) const
     If the map already had a key equal to \c{v.first}, its value will be
     overwritten by \c{v.second}.
 
-    \sa operator[], erase()
+    \sa operator[], erase(), extract()
  */
 
 
@@ -1011,7 +1077,7 @@ QCborMap::const_iterator QCborMap::constFind(const QCborValue &key) const
     Removes the key-value pair pointed to by the map iterator \a it and returns a
     pointer to the next element, after removal.
 
-    \sa remove(), begin(), end(), insert()
+    \sa remove(), begin(), end(), insert(), extract()
  */
 
 /*!
@@ -1034,6 +1100,24 @@ QCborMap::iterator QCborMap::erase(QCborMap::iterator it)
 }
 
 /*!
+    Extracts a value from the map at the position indicated by iterator \a it
+    and returns the value so extracted.
+
+    \sa insert(), erase(), take(), remove()
+ */
+QCborValue QCborMap::extract(iterator it)
+{
+    detach();
+    QCborValue v = d->extractAt(it.item.i);
+    // remove both key and value
+    // ### optimize?
+    d->removeAt(it.item.i - 1);
+    d->removeAt(it.item.i - 1);
+
+    return v;
+}
+
+/*!
     \fn bool QCborMap::empty() const
 
     Synonym for isEmpty(). This function is provided for compatibility with
diff --git a/src/corelib/serialization/qcbormap.h b/src/corelib/serialization/qcbormap.h
index 9499f46ace..89de3d6786 100644
--- a/src/corelib/serialization/qcbormap.h
+++ b/src/corelib/serialization/qcbormap.h
@@ -207,6 +207,14 @@ public:
     QCborValueRef operator[](const QString & key);
     QCborValueRef operator[](const QCborValue &key);
 
+    QCborValue take(qint64 key)
+    { iterator it = find(key); if (it != end()) return extract(it); return QCborValue(); }
+    QCborValue take(QLatin1String key)
+    { iterator it = find(key); if (it != end()) return extract(it); return QCborValue(); }
+    QCborValue take(const QString &key)
+    { iterator it = find(key); if (it != end()) return extract(it); return QCborValue(); }
+    QCborValue take(const QCborValue &key)
+    { iterator it = find(key); if (it != end()) return extract(it); return QCborValue(); }
     void remove(qint64 key)
     { iterator it = find(key); if (it != end()) erase(it); }
     void remove(QLatin1String key)
@@ -254,6 +262,8 @@ public:
     const_iterator cend() const { return constEnd(); }
     iterator erase(iterator it);
     iterator erase(const_iterator it) { return erase(iterator{ it.item.d, it.item.i }); }
+    QCborValue extract(iterator it);
+    QCborValue extract(const_iterator it) { return extract(iterator{ it.item.d, it.item.i }); }
     bool empty() const { return isEmpty(); }
 
     iterator find(qint64 key);
diff --git a/src/corelib/serialization/qcborvalue.cpp b/src/corelib/serialization/qcborvalue.cpp
index db5dc938df..d4b7764b49 100644
--- a/src/corelib/serialization/qcborvalue.cpp
+++ b/src/corelib/serialization/qcborvalue.cpp
@@ -1101,6 +1101,29 @@ Q_NEVER_INLINE void QCborContainerPrivate::appendAsciiString(const QString &s)
     qt_to_latin1_unchecked(l, uc, len);
 }
 
+QCborValue QCborContainerPrivate::extractAt_complex(Element e)
+{
+    // create a new container for the returned value, containing the byte data
+    // from this element, if it's worth it
+    Q_ASSERT(e.flags & Element::HasByteData);
+    auto b = byteData(e);
+    auto container = new QCborContainerPrivate;
+
+    if (b->len + qsizetype(sizeof(*b)) < data.size() / 4) {
+        // make a shallow copy of the byte data
+        container->appendByteData(b->byte(), b->len, e.type, e.flags);
+        usedData -= b->len + qsizetype(sizeof(*b));
+        compact(elements.size());
+    } else {
+        // just share with the original byte data
+        container->data = data;
+        container->elements.reserve(1);
+        container->elements.append(e);
+    }
+
+    return makeValue(e.type, 0, container);
+}
+
 QT_WARNING_DISABLE_MSVC(4146)   // unary minus operator applied to unsigned type, result still unsigned
 static int compareContainer(const QCborContainerPrivate *c1, const QCborContainerPrivate *c2);
 static int compareElementNoData(const Element &e1, const Element &e2)
diff --git a/src/corelib/serialization/qcborvalue_p.h b/src/corelib/serialization/qcborvalue_p.h
index c80abd68f5..eb6fe09147 100644
--- a/src/corelib/serialization/qcborvalue_p.h
+++ b/src/corelib/serialization/qcborvalue_p.h
@@ -124,6 +124,8 @@ class QCborContainerPrivate : public QSharedData
     ~QCborContainerPrivate();
 
 public:
+    enum ContainerDisposition { CopyContainer, MoveContainer };
+
     QByteArray::size_type usedData = 0;
     QByteArray data;
     QVector<QtCbor::Element> elements;
@@ -275,12 +277,13 @@ public:
         return data->toUtf8String();
     }
 
-    static QCborValue makeValue(QCborValue::Type type, qint64 n, QCborContainerPrivate *d = nullptr)
+    static QCborValue makeValue(QCborValue::Type type, qint64 n, QCborContainerPrivate *d = nullptr,
+                                ContainerDisposition disp = CopyContainer)
     {
         QCborValue result(type);
         result.n = n;
         result.container = d;
-        if (d)
+        if (d && disp == CopyContainer)
             d->ref.ref();
         return result;
     }
@@ -300,6 +303,24 @@ public:
         }
         return makeValue(e.type, e.value);
     }
+    QCborValue extractAt_complex(QtCbor::Element e);
+    QCborValue extractAt(qsizetype idx)
+    {
+        QtCbor::Element e;
+        qSwap(e, elements[idx]);
+
+        if (e.flags & QtCbor::Element::IsContainer) {
+            if (e.type == QCborValue::Tag && e.container->elements.size() != 2) {
+                // invalid tags can be created due to incomplete parsing
+                e.container->deref();
+                return makeValue(QCborValue::Invalid, 0, nullptr);
+            }
+            return makeValue(e.type, -1, e.container, MoveContainer);
+        } else if (e.flags & QtCbor::Element::HasByteData) {
+            return extractAt_complex(e);
+        }
+        return makeValue(e.type, e.value);
+    }
 
     static QtCbor::Element elementFromValue(const QCborValue &value)
     {
diff --git a/tests/auto/corelib/serialization/qcborvalue/tst_qcborvalue.cpp b/tests/auto/corelib/serialization/qcborvalue/tst_qcborvalue.cpp
index 0cd4c5cca0..7f0007b384 100644
--- a/tests/auto/corelib/serialization/qcborvalue/tst_qcborvalue.cpp
+++ b/tests/auto/corelib/serialization/qcborvalue/tst_qcborvalue.cpp
@@ -781,6 +781,7 @@ void tst_QCborValue::arrayPrepend()
     a.prepend(nullptr);
     QCOMPARE(a.at(1), QCborValue(0));
     QCOMPARE(a.at(0), QCborValue(nullptr));
+    QCOMPARE(a.size(), 2);
 }
 
 void tst_QCborValue::arrayInsertRemove()
@@ -808,6 +809,11 @@ void tst_QCborValue::arrayInsertRemove()
     it = a.erase(it);
     QVERIFY(a.isEmpty());
     QCOMPARE(it, a.end());
+
+    // reinsert the element so we can take it
+    a.append(v);
+    QCOMPARE(a.takeAt(0), v);
+    QVERIFY(a.isEmpty());
 }
 
 void tst_QCborValue::arrayStringElements()
@@ -836,6 +842,10 @@ void tst_QCborValue::arrayStringElements()
     v2 = a.at(1);
     QCOMPARE(v2.toString(), "World");
     QCOMPARE(v2, QCborValue("World"));
+
+    QCOMPARE(a.takeAt(1).toString(), "World");
+    QCOMPARE(a.takeAt(0).toString(), "Hello");
+    QVERIFY(a.isEmpty());
 }
 
 void tst_QCborValue::mapStringValues()
@@ -862,6 +872,10 @@ void tst_QCborValue::mapStringValues()
     v2 = (m.begin() + 1).value();
     QCOMPARE(v2.toString(), "World");
     QCOMPARE(v2, QCborValue("World"));
+
+    QCOMPARE(m.extract(m.begin() + 1).toString(), "World");
+    QCOMPARE(m.take(0).toString(), "Hello");
+    QVERIFY(m.isEmpty());
 }
 
 void tst_QCborValue::mapStringKeys()
@@ -914,6 +928,14 @@ void tst_QCborValue::mapInsertRemove()
     QVERIFY(v == it.value());
     QVERIFY(it.value() == r);
     QVERIFY(r == it.value());
+
+    QCOMPARE(m.extract(it), v);
+    QVERIFY(!m.contains(42));
+
+    m[2] = v;
+    QCOMPARE(m.take(2), v);
+    QVERIFY(m.take(2).isUndefined());
+    QVERIFY(m.isEmpty());
 }
 
 void tst_QCborValue::arrayInsertTagged()
@@ -930,6 +952,9 @@ void tst_QCborValue::arrayInsertTagged()
     QCOMPARE(a.at(1), tagged);
     QCOMPARE(a.at(0).taggedValue(), v);
     QCOMPARE(a.at(1).taggedValue(), v);
+    QCOMPARE(a.takeAt(0).taggedValue(), v);
+    QCOMPARE(a.takeAt(0).taggedValue(), v);
+    QVERIFY(a.isEmpty());
 }
 
 void tst_QCborValue::mapInsertTagged()
@@ -946,6 +971,10 @@ void tst_QCborValue::mapInsertTagged()
     QCOMPARE(m.value(-21), tagged);
     QCOMPARE(m.value(11).taggedValue(), v);
     QCOMPARE((m.end() - 1).value().taggedValue(), v);
+    QCOMPARE(m.extract(m.end() - 1).taggedValue(), v);
+    QVERIFY(!m.contains(-21));
+    QCOMPARE(m.take(11).taggedValue(), v);
+    QVERIFY(m.isEmpty());
 }
 
 void tst_QCborValue::arraySelfAssign()
@@ -1109,6 +1138,8 @@ void tst_QCborValue::mapComplexKeys()
     QVERIFY(m.contains(tagged));
     r = 47;
     QCOMPARE(m[tagged].toInteger(), 47);
+    QCOMPARE(m.take(tagged).toInteger(), 47);
+    QVERIFY(!m.contains(tagged));
 }
 
 void tst_QCborValue::sorting()