From 2bb44414ff456873c885391e4a03afb67e7306da Mon Sep 17 00:00:00 2001 From: Thiago Macieira Date: Sat, 19 May 2018 14:58:43 -0700 Subject: 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 Reviewed-by: Thiago Macieira --- src/corelib/serialization/qcborarray.cpp | 19 ++++++- src/corelib/serialization/qcborarray.h | 3 +- src/corelib/serialization/qcbormap.cpp | 96 ++++++++++++++++++++++++++++++-- src/corelib/serialization/qcbormap.h | 10 ++++ src/corelib/serialization/qcborvalue.cpp | 23 ++++++++ src/corelib/serialization/qcborvalue_p.h | 25 ++++++++- 6 files changed, 166 insertions(+), 10 deletions(-) (limited to 'src') 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) { @@ -311,6 +313,21 @@ void QCborArray::insert(qsizetype i, const QCborValue &value) d->insertAt(i, 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) 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 @@ -341,6 +343,22 @@ QVector QCborMap::keys() const operator[](QLatin1String), operator[](const QString &), operator[](const QCborOperator[] &) */ +/*! + \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) @@ -450,6 +468,22 @@ QCborValueRef QCborMap::operator[](qint64 key) operator[](qint64), operator[](const QString &), operator[](const QCborOperator[] &) */ +/*! + \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 @@ -561,6 +595,22 @@ QCborValueRef QCborMap::operator[](QLatin1String key) operator[](qint64), operator[](QLatin1String), operator[](const QCborOperator[] &) */ +/*! + \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 @@ -672,6 +722,22 @@ QCborValueRef QCborMap::operator[](const QString & key) operator[](qint64), operator[](QLatin1String), operator[](const QCborOperator[] &) */ +/*! + \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) @@ -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() */ /*! @@ -1033,6 +1099,24 @@ QCborMap::iterator QCborMap::erase(QCborMap::iterator it) return 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 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 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) { -- cgit v1.2.3