diff options
author | Andrei Golubev <andrei.golubev@qt.io> | 2021-03-24 16:47:33 +0100 |
---|---|---|
committer | Andrei Golubev <andrei.golubev@qt.io> | 2021-04-26 17:07:07 +0200 |
commit | a0253f5f0249024580050e4ec22d50cb139ef8d9 (patch) | |
tree | 43a61a5f66f94ed3af4c8fbd06814c05c71c39ce | |
parent | 10b46e7f0faecc42a94cc2e25ad3edd08ae28083 (diff) |
Resurrect data moves in QList
Use the data moves to readjust the free space in the QList,
which ultimately fixes the out-of-memory issues caused by
cases like:
forever {
list.prepend(list.back());
list.removeLast();
}
Task-number: QTBUG-91801
Task-number: QTBUG-91360
Task-number: QTBUG-93019
Pick-to: dev 6.0 6.1
Change-Id: Iacff69cbf36b8b5b176bb2663df635ec972c875c
Reviewed-by: Lars Knoll <lars.knoll@qt.io>
-rw-r--r-- | src/corelib/text/qbytearray.cpp | 19 | ||||
-rw-r--r-- | src/corelib/text/qstring.cpp | 49 | ||||
-rw-r--r-- | src/corelib/tools/qarraydataops.h | 56 | ||||
-rw-r--r-- | src/corelib/tools/qarraydatapointer.h | 134 | ||||
-rw-r--r-- | src/corelib/tools/qcontainertools_impl.h | 111 | ||||
-rw-r--r-- | src/corelib/tools/qlist.h | 21 | ||||
-rw-r--r-- | tests/auto/corelib/tools/qarraydata/simplevector.h | 17 | ||||
-rw-r--r-- | tests/auto/corelib/tools/qlist/tst_qlist.cpp | 59 |
8 files changed, 366 insertions, 100 deletions
diff --git a/src/corelib/text/qbytearray.cpp b/src/corelib/text/qbytearray.cpp index 6a7d8b2657..a710c6ecba 100644 --- a/src/corelib/text/qbytearray.cpp +++ b/src/corelib/text/qbytearray.cpp @@ -1971,8 +1971,7 @@ QByteArray &QByteArray::append(const QByteArray &ba) QByteArray& QByteArray::append(char ch) { - if (d->needsDetach() || !d->freeSpaceAtEnd()) - reallocGrowData(1); + d.detachAndGrow(QArrayData::GrowsAtEnd, 1, nullptr, nullptr); d->copyAppend(1, ch); d.data()[d.size] = '\0'; return *this; @@ -2012,12 +2011,8 @@ QByteArray &QByteArray::insert(qsizetype i, QByteArrayView data) // defer a call to free() so that it comes after we copied the data from // the old memory: DataPointer detached{}; // construction is free - if (d->needsDetach() || i + size - d->size > d.freeSpaceAtEnd()) { - detached = DataPointer::allocateGrow(d, i + size - d->size, Data::GrowsAtEnd); - Q_CHECK_PTR(detached.data()); - detached->copyAppend(d.constBegin(), d.constEnd()); - d.swap(detached); - } + d.detachAndGrow(Data::GrowsAtEnd, (i - d.size) + size, &str, &detached); + Q_CHECK_PTR(d.data()); d->copyAppend(i - d->size, ' '); d->copyAppend(str, str + size); d.data()[d.size] = '\0'; @@ -2094,12 +2089,8 @@ QByteArray &QByteArray::insert(qsizetype i, qsizetype count, char ch) if (i >= d->size) { // handle this specially, as QArrayDataOps::insert() doesn't handle out of bounds positions - if (d->needsDetach() || i + count - d->size > d.freeSpaceAtEnd()) { - DataPointer detached(DataPointer::allocateGrow(d, i + count - d->size, Data::GrowsAtEnd)); - Q_CHECK_PTR(detached.data()); - detached->copyAppend(d.constBegin(), d.constEnd()); - d.swap(detached); - } + d.detachAndGrow(Data::GrowsAtEnd, (i - d.size) + count, nullptr, nullptr); + Q_CHECK_PTR(d.data()); d->copyAppend(i - d->size, ' '); d->copyAppend(count, ch); d.data()[d.size] = '\0'; diff --git a/src/corelib/text/qstring.cpp b/src/corelib/text/qstring.cpp index a86ba03932..b23c88cbb8 100644 --- a/src/corelib/text/qstring.cpp +++ b/src/corelib/text/qstring.cpp @@ -2770,13 +2770,17 @@ QString &QString::insert(qsizetype i, QLatin1String str) return *this; qsizetype len = str.size(); + qsizetype difference = 0; if (Q_UNLIKELY(i > size())) - resize(i + len, QLatin1Char(' ')); - else - resize(size() + len); + difference = i - size(); + d.detachAndGrow(Data::GrowsAtEnd, difference + len, nullptr, nullptr); + Q_CHECK_PTR(d.data()); + d->copyAppend(difference, u' '); + d.size += len; ::memmove(d.data() + i + len, d.data() + i, (d.size - i - len) * sizeof(QChar)); qt_from_latin1(d.data() + i, s, size_t(len)); + d.data()[d.size] = u'\0'; return *this; } @@ -2797,7 +2801,7 @@ QString& QString::insert(qsizetype i, const QChar *unicode, qsizetype size) if (i < 0 || size <= 0) return *this; - const auto s = reinterpret_cast<const char16_t *>(unicode); + const char16_t *s = reinterpret_cast<const char16_t *>(unicode); // handle this specially, as QArrayDataOps::insert() doesn't handle out of // bounds positions @@ -2806,12 +2810,8 @@ QString& QString::insert(qsizetype i, const QChar *unicode, qsizetype size) // defer a call to free() so that it comes after we copied the data from // the old memory: DataPointer detached{}; // construction is free - if (d->needsDetach() || i + size - d->size > d.freeSpaceAtEnd()) { - detached = DataPointer::allocateGrow(d, i + size - d->size, Data::GrowsAtEnd); - Q_CHECK_PTR(detached.data()); - detached->copyAppend(d.constBegin(), d.constEnd()); - d.swap(detached); - } + d.detachAndGrow(Data::GrowsAtEnd, (i - d.size) + size, &s, &detached); + Q_CHECK_PTR(d.data()); d->copyAppend(i - d->size, u' '); d->copyAppend(s, s + size); d.data()[d.size] = u'\0'; @@ -2867,11 +2867,8 @@ QString &QString::append(const QString &str) if (!str.isNull()) { if (isNull()) { operator=(str); - } else { - if (d->needsDetach() || str.size() > d->freeSpaceAtEnd()) - reallocGrowData(str.size()); - d->copyAppend(str.d.data(), str.d.data() + str.d.size); - d.data()[d.size] = '\0'; + } else if (str.size()) { + append(str.constData(), str.size()); } } return *this; @@ -2886,13 +2883,11 @@ QString &QString::append(const QString &str) QString &QString::append(const QChar *str, qsizetype len) { if (str && len > 0) { - if (d->needsDetach() || len > d->freeSpaceAtEnd()) - reallocGrowData(len); static_assert(sizeof(QChar) == sizeof(char16_t), "Unexpected difference in sizes"); // the following should be safe as QChar uses char16_t as underlying data const char16_t *char16String = reinterpret_cast<const char16_t *>(str); - d->copyAppend(char16String, char16String + len); - d.data()[d.size] = '\0'; + d->growAppend(char16String, char16String + len); + d.data()[d.size] = u'\0'; } return *this; } @@ -2905,16 +2900,17 @@ QString &QString::append(const QChar *str, qsizetype len) QString &QString::append(QLatin1String str) { const char *s = str.latin1(); - if (s) { - qsizetype len = str.size(); - if (d->needsDetach() || str.size() > d->freeSpaceAtEnd()) - reallocGrowData(len); - - Q_ASSERT(str.size() <= d->freeSpaceAtEnd()); + const qsizetype len = str.size(); + if (s && len > 0) { + d.detachAndGrow(Data::GrowsAtEnd, len, nullptr, nullptr); + Q_CHECK_PTR(d.data()); + Q_ASSERT(len <= d->freeSpaceAtEnd()); char16_t *i = d.data() + d.size; qt_from_latin1(i, s, size_t(len)); d.size += len; d.data()[d.size] = '\0'; + } else if (d.isNull() && !str.isNull()) { // special case + d = DataPointer::fromRawData(&_empty, 0); } return *this; } @@ -2952,8 +2948,7 @@ QString &QString::append(QLatin1String str) */ QString &QString::append(QChar ch) { - if (d->needsDetach() || !d->freeSpaceAtEnd()) - reallocGrowData(1); + d.detachAndGrow(QArrayData::GrowsAtEnd, 1, nullptr, nullptr); d->copyAppend(1, ch.unicode()); d.data()[d.size] = '\0'; return *this; diff --git a/src/corelib/tools/qarraydataops.h b/src/corelib/tools/qarraydataops.h index 0c7703c588..02609a369e 100644 --- a/src/corelib/tools/qarraydataops.h +++ b/src/corelib/tools/qarraydataops.h @@ -164,8 +164,9 @@ public: typename Data::GrowthPosition pos = Data::GrowsAtEnd; if (this->size != 0 && i <= (this->size >> 1)) pos = Data::GrowsAtBeginning; + DataPointer oldData; - this->detachAndGrow(pos, n, &oldData); + this->detachAndGrow(pos, n, &data, &oldData); Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) || (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n)); @@ -180,7 +181,8 @@ public: typename Data::GrowthPosition pos = Data::GrowsAtEnd; if (this->size != 0 && i <= (this->size >> 1)) pos = Data::GrowsAtBeginning; - this->detachAndGrow(pos, n); + + this->detachAndGrow(pos, n, nullptr, nullptr); Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) || (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n)); @@ -210,10 +212,8 @@ public: typename QArrayData::GrowthPosition pos = QArrayData::GrowsAtEnd; if (this->size != 0 && i <= (this->size >> 1)) pos = QArrayData::GrowsAtBeginning; - if (detach || - (pos == QArrayData::GrowsAtBeginning && !this->freeSpaceAtBegin()) || - (pos == QArrayData::GrowsAtEnd && !this->freeSpaceAtEnd())) - this->reallocateAndGrow(pos, 1); + + this->detachAndGrow(pos, 1, nullptr, nullptr); T *where = createHole(pos, i, 1); new (where) T(std::move(tmp)); @@ -547,8 +547,9 @@ public: typename Data::GrowthPosition pos = Data::GrowsAtEnd; if (this->size != 0 && i <= (this->size >> 1)) pos = Data::GrowsAtBeginning; + DataPointer oldData; - this->detachAndGrow(pos, n, &oldData); + this->detachAndGrow(pos, n, &data, &oldData); Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) || (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n)); @@ -562,7 +563,8 @@ public: typename Data::GrowthPosition pos = Data::GrowsAtEnd; if (this->size != 0 && i <= (this->size >> 1)) pos = Data::GrowsAtBeginning; - this->detachAndGrow(pos, n); + + this->detachAndGrow(pos, n, nullptr, nullptr); Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) || (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n)); @@ -590,10 +592,8 @@ public: typename QArrayData::GrowthPosition pos = QArrayData::GrowsAtEnd; if (this->size != 0 && i <= (this->size >> 1)) pos = QArrayData::GrowsAtBeginning; - if (detach || - (pos == QArrayData::GrowsAtBeginning && !this->freeSpaceAtBegin()) || - (pos == QArrayData::GrowsAtEnd && !this->freeSpaceAtEnd())) - this->reallocateAndGrow(pos, 1); + + this->detachAndGrow(pos, 1, nullptr, nullptr); Inserter(this, pos).insertOne(i, std::move(tmp)); } @@ -773,8 +773,9 @@ public: typename Data::GrowthPosition pos = Data::GrowsAtEnd; if (this->size != 0 && i <= (this->size >> 1)) pos = Data::GrowsAtBeginning; + DataPointer oldData; - this->detachAndGrow(pos, n, &oldData); + this->detachAndGrow(pos, n, &data, &oldData); Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) || (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n)); @@ -788,7 +789,8 @@ public: typename Data::GrowthPosition pos = Data::GrowsAtEnd; if (this->size != 0 && i <= (this->size >> 1)) pos = Data::GrowsAtBeginning; - this->detachAndGrow(pos, n); + + this->detachAndGrow(pos, n, nullptr, nullptr); Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) || (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n)); @@ -816,10 +818,8 @@ public: typename QArrayData::GrowthPosition pos = QArrayData::GrowsAtEnd; if (this->size != 0 && i <= (this->size >> 1)) pos = QArrayData::GrowsAtBeginning; - if (detach || - (pos == QArrayData::GrowsAtBeginning && !this->freeSpaceAtBegin()) || - (pos == QArrayData::GrowsAtEnd && !this->freeSpaceAtEnd())) - this->reallocateAndGrow(pos, 1); + + this->detachAndGrow(pos, 1, nullptr, nullptr); Inserter(this, pos).insertOne(i, std::move(tmp)); } @@ -913,6 +913,26 @@ public: ++this->size; } } + + // slightly higher level API than copyAppend() that also preallocates space + void growAppend(const T *b, const T *e) + { + if (b == e) + return; + Q_ASSERT(b < e); + const qsizetype n = e - b; + DataPointer old; + + // points into range: + if (QtPrivate::q_points_into_range(b, this->begin(), this->end())) { + this->detachAndGrow(QArrayData::GrowsAtEnd, n, &b, &old); + } else { + this->detachAndGrow(QArrayData::GrowsAtEnd, n, nullptr, nullptr); + } + Q_ASSERT(this->freeSpaceAtEnd() >= n); + // b might be updated so use [b, n) + this->copyAppend(b, b + n); + } }; } // namespace QtPrivate diff --git a/src/corelib/tools/qarraydatapointer.h b/src/corelib/tools/qarraydatapointer.h index f6aabeee65..af60a105fe 100644 --- a/src/corelib/tools/qarraydatapointer.h +++ b/src/corelib/tools/qarraydatapointer.h @@ -166,19 +166,56 @@ public: reallocateAndGrow(QArrayData::GrowsAtEnd, 0, old); } - // pass in a pointer to a default constructed QADP, to keep it alive beyond the detach() call - void detachAndGrow(QArrayData::GrowthPosition where, qsizetype n, QArrayDataPointer *old = nullptr) + /*! \internal + + Detaches this (optionally) and grows to accommodate the free space for + \a n elements at the required side. The side is determined from \a pos. + + \a data pointer can be provided when the caller knows that \a data + points into range [this->begin(), this->end()). In case it is, *data + would be updated so that it continues to point to the element it was + pointing to before the data move. if \a data does not point into range, + one can/should pass \c nullptr. + + Similarly to \a data, \a old, pointer to a default-constructed QADP, can + be provided when the caller expects to e.g. copy the data from this to + itself: + \code + QList<T> list(5); + qsizetype pos = getArbitraryPos(); + list.insert(pos, list.begin(), list.end()); + \endcode + + The default rule would be: \a data and \a old must either both be valid + pointers, or both equal to \c nullptr. + */ + void detachAndGrow(QArrayData::GrowthPosition where, qsizetype n, const T **data, + QArrayDataPointer *old) { - if (!needsDetach()) { - if (!n || - (where == QArrayData::GrowsAtBeginning && freeSpaceAtBegin() >= n) || - (where == QArrayData::GrowsAtEnd && freeSpaceAtEnd() >= n)) + const bool detach = needsDetach(); + bool readjusted = false; + if (!detach) { + if (!n || (where == QArrayData::GrowsAtBeginning && freeSpaceAtBegin() >= n) + || (where == QArrayData::GrowsAtEnd && freeSpaceAtEnd() >= n)) return; + readjusted = tryReadjustFreeSpace(where, n, data); + Q_ASSERT(!readjusted + || (where == QArrayData::GrowsAtBeginning && freeSpaceAtBegin() >= n) + || (where == QArrayData::GrowsAtEnd && freeSpaceAtEnd() >= n)); } - reallocateAndGrow(where, n, old); + + if (!readjusted) + reallocateAndGrow(where, n, old); } - Q_NEVER_INLINE void reallocateAndGrow(QArrayData::GrowthPosition where, qsizetype n, QArrayDataPointer *old = nullptr) + /*! \internal + + Reallocates to accommodate the free space for \a n elements at the + required side. The side is determined from \a pos. Might also shrink + when n < 0. + */ + Q_NEVER_INLINE void reallocateAndGrow(QArrayData::GrowthPosition where, qsizetype n, + QArrayDataPointer *old = nullptr) { if constexpr (QTypeInfo<T>::isRelocatable && alignof(T) <= alignof(std::max_align_t)) { if (where == QArrayData::GrowsAtEnd && !old && !needsDetach() && n > 0) { @@ -188,9 +225,10 @@ public: } QArrayDataPointer dp(allocateGrow(*this, n, where)); + if (n > 0) + Q_CHECK_PTR(dp.data()); if (where == QArrayData::GrowsAtBeginning) { Q_ASSERT(dp.ptr); - dp.ptr += n; Q_ASSERT(dp.freeSpaceAtBegin() >= n); } else { Q_ASSERT(dp.freeSpaceAtEnd() >= n); @@ -211,6 +249,77 @@ public: old->swap(dp); } + /*! \internal + + Attempts to relocate [begin(), end()) to accommodate the free space for + \a n elements at the required side. The side is determined from \a pos. + + Returns \c true if the internal data is moved. Returns \c false when + there is no point in moving the data or the move is impossible. If \c + false is returned, it is the responsibility of the caller to figure out + how to accommodate the free space for \a n elements at \a pos. + + This function expects that certain preconditions are met, e.g. the + detach is not needed, n > 0 and so on. This is intentional to reduce the + number of if-statements when the caller knows that preconditions would + be satisfied. + + \sa reallocateAndGrow + */ + bool tryReadjustFreeSpace(QArrayData::GrowthPosition pos, qsizetype n, const T **data = nullptr) + { + Q_ASSERT(!this->needsDetach()); + Q_ASSERT(n > 0); + Q_ASSERT((pos == QArrayData::GrowsAtEnd && this->freeSpaceAtEnd() < n) + || (pos == QArrayData::GrowsAtBeginning && this->freeSpaceAtBegin() < n)); + + const qsizetype capacity = this->constAllocatedCapacity(); + const qsizetype freeAtBegin = this->freeSpaceAtBegin(); + const qsizetype freeAtEnd = this->freeSpaceAtEnd(); + + qsizetype dataStartOffset = 0; + // algorithm: + // a. GrowsAtEnd: relocate if space at begin AND size < (capacity * 2) / 3 + // [all goes to free space at end]: + // new free space at begin = 0 + // + // b. GrowsAtBeginning: relocate if space at end AND size < capacity / 3 + // [balance the free space]: + // new free space at begin = n + (total free space - n) / 2 + if (pos == QArrayData::GrowsAtEnd && freeAtBegin >= n + && ((3 * this->size) < (2 * capacity))) { + // dataStartOffset = 0; - done in declaration + } else if (pos == QArrayData::GrowsAtBeginning && freeAtEnd >= n + && ((3 * this->size) < capacity)) { + // total free space == capacity - size + dataStartOffset = n + qMax(0, (capacity - this->size - n) / 2); + } else { + // nothing to do otherwise + return false; + } + + relocate(dataStartOffset - freeAtBegin, data); + + Q_ASSERT((pos == QArrayData::GrowsAtEnd && this->freeSpaceAtEnd() >= n) + || (pos == QArrayData::GrowsAtBeginning && this->freeSpaceAtBegin() >= n)); + return true; + } + + /*! \internal + + Relocates [begin(), end()) by \a offset and updates \a data if it is not + \c nullptr and points into [begin(), end()). + */ + void relocate(qsizetype offset, const T **data = nullptr) + { + T *res = this->ptr + offset; + QtPrivate::q_relocate_overlap_n(this->ptr, this->size, res); + // first update data pointer, then this->ptr + if (data && QtPrivate::q_points_into_range(*data, this->begin(), this->end())) + *data += offset; + this->ptr = res; + } + // forwards from QArrayData qsizetype allocatedCapacity() noexcept { return d ? d->allocatedCapacity() : 0; } qsizetype constAllocatedCapacity() const noexcept { return d ? d->constAllocatedCapacity() : 0; } @@ -262,10 +371,9 @@ public: // Idea: * when growing backwards, adjust pointer to prepare free space at the beginning // * when growing forward, adjust by the previous data pointer offset - - // TODO: what's with CapacityReserved? - dataPtr += (position == QArrayData::GrowsAtBeginning) ? qMax(0, (header->alloc - from.size - n) / 2) - : from.freeSpaceAtBegin(); + dataPtr += (position == QArrayData::GrowsAtBeginning) + ? n + qMax(0, (header->alloc - from.size - n) / 2) + : from.freeSpaceAtBegin(); header->flags = from.flags(); return QArrayDataPointer(header, dataPtr); } diff --git a/src/corelib/tools/qcontainertools_impl.h b/src/corelib/tools/qcontainertools_impl.h index 465ea5c544..2053de6408 100644 --- a/src/corelib/tools/qcontainertools_impl.h +++ b/src/corelib/tools/qcontainertools_impl.h @@ -53,6 +53,7 @@ #include <cstring> #include <iterator> #include <memory> +#include <algorithm> QT_BEGIN_NAMESPACE @@ -88,6 +89,116 @@ void q_uninitialized_relocate_n(T* first, N n, T* out) } } +template<typename iterator, typename N> +void q_relocate_overlap_n_left_move(iterator first, N n, iterator d_first) +{ + // requires: [first, n) is a valid range + // requires: d_first + n is reachable from d_first + // requires: iterator is at least a random access iterator + // requires: value_type(iterator) has a non-throwing destructor + + Q_ASSERT(n); + Q_ASSERT(d_first < first); // only allow moves to the "left" + using T = typename std::iterator_traits<iterator>::value_type; + + // Watches passed iterator. Unless commit() is called, all the elements that + // the watched iterator passes through are deleted at the end of object + // lifetime. freeze() could be used to stop watching the passed iterator and + // remain at current place. + // + // requires: the iterator is expected to always point to an invalid object + // (to uninitialized memory) + struct Destructor + { + iterator *iter; + iterator end; + iterator intermediate; + + Destructor(iterator &it) noexcept : iter(std::addressof(it)), end(it) { } + void commit() noexcept { iter = std::addressof(end); } + void freeze() noexcept + { + intermediate = *iter; + iter = std::addressof(intermediate); + } + ~Destructor() noexcept + { + for (const int step = *iter < end ? 1 : -1; *iter != end;) { + std::advance(*iter, step); + (*iter)->~T(); + } + } + } destroyer(d_first); + + const iterator d_last = d_first + n; + // Note: use pair and explicitly copy iterators from it to prevent + // accidental reference semantics instead of copy. equivalent to: + // + // auto [overlapBegin, overlapEnd] = std::minmax(d_last, first); + auto pair = std::minmax(d_last, first); + + // overlap area between [d_first, d_first + n) and [first, first + n) or an + // uninitialized memory area between the two ranges + iterator overlapBegin = pair.first; + iterator overlapEnd = pair.second; + + // move construct elements in uninitialized region + while (d_first != overlapBegin) { + // account for std::reverse_iterator, cannot use new(d_first) directly + new (std::addressof(*d_first)) T(std::move_if_noexcept(*first)); + ++d_first; + ++first; + } + + // cannot commit but have to stop - there might be an overlap region + // which we don't want to delete (because it's part of existing data) + destroyer.freeze(); + + // move assign elements in overlap region + while (d_first != d_last) { + *d_first = std::move_if_noexcept(*first); + ++d_first; + ++first; + } + + Q_ASSERT(d_first == destroyer.end + n); + destroyer.commit(); // can commit here as ~T() below does not throw + + while (first != overlapEnd) + (--first)->~T(); +} + +/*! + \internal + + Relocates a range [first, n) to [d_first, n) taking care of potential memory + overlaps. This is a generic equivalent of memmove. + + If an exception is thrown during the relocation, all the relocated elements + are destroyed and [first, n) may contain valid but unspecified values, + including moved-from values (basic exception safety). +*/ +template<typename T, typename N> +void q_relocate_overlap_n(T *first, N n, T *d_first) +{ + static_assert(std::is_nothrow_destructible_v<T>, + "This algorithm requires that T has a non-throwing destructor"); + + if (n == N(0) || first == d_first || first == nullptr || d_first == nullptr) + return; + + if constexpr (QTypeInfo<T>::isRelocatable) { + std::memmove(static_cast<void *>(d_first), static_cast<const void *>(first), n * sizeof(T)); + } else { // generic version has to be used + if (d_first < first) { + q_relocate_overlap_n_left_move(first, n, d_first); + } else { // first < d_first + auto rfirst = std::make_reverse_iterator(first + n); + auto rd_first = std::make_reverse_iterator(d_first + n); + q_relocate_overlap_n_left_move(rfirst, n, rd_first); + } + } +} template <typename Iterator> using IfIsInputIterator = typename std::enable_if< diff --git a/src/corelib/tools/qlist.h b/src/corelib/tools/qlist.h index b50cd9090f..2811688e4b 100644 --- a/src/corelib/tools/qlist.h +++ b/src/corelib/tools/qlist.h @@ -663,9 +663,10 @@ inline void QList<T>::resize_internal(qsizetype newSize) Q_ASSERT(newSize >= 0); if (d->needsDetach() || newSize > capacity() - d.freeSpaceAtBegin()) { - d.reallocateAndGrow(QArrayData::GrowsAtEnd, newSize - d.size); - } else if (newSize < size()) + d.detachAndGrow(QArrayData::GrowsAtEnd, newSize - d.size, nullptr, nullptr); + } else if (newSize < size()) { d->truncate(newSize); + } } template <typename T> @@ -748,12 +749,7 @@ inline T QList<T>::value(qsizetype i, parameter_type defaultValue) const template <typename T> inline void QList<T>::append(const_iterator i1, const_iterator i2) { - if (i1 == i2) - return; - const auto distance = std::distance(i1, i2); - DataPointer oldData; - d.detachAndGrow(QArrayData::GrowsAtEnd, distance, &oldData); - d->copyAppend(i1, i2); + d->growAppend(i1, i2); } template <typename T> @@ -765,7 +761,9 @@ inline void QList<T>::append(QList<T> &&other) if (other.d->needsDetach() || !std::is_nothrow_move_constructible_v<T>) return append(other); - d.detachAndGrow(QArrayData::GrowsAtEnd, other.size()); + // due to precondition &other != this, we can unconditionally modify 'this' + d.detachAndGrow(QArrayData::GrowsAtEnd, other.size(), nullptr, nullptr); + Q_ASSERT(d.freeSpaceAtEnd() >= other.size()); d->moveAppend(other.begin(), other.end()); } @@ -783,8 +781,9 @@ inline typename QList<T>::iterator QList<T>::insert(qsizetype i, qsizetype n, parameter_type t) { Q_ASSERT_X(size_t(i) <= size_t(d->size), "QList<T>::insert", "index out of range"); - - d->insert(i, n, t); + Q_ASSERT_X(n >= 0, "QList::insert", "invalid count"); + if (Q_LIKELY(n)) + d->insert(i, n, t); return d.begin() + i; } diff --git a/tests/auto/corelib/tools/qarraydata/simplevector.h b/tests/auto/corelib/tools/qarraydata/simplevector.h index 747af3d422..1fc5e9b8e1 100644 --- a/tests/auto/corelib/tools/qarraydata/simplevector.h +++ b/tests/auto/corelib/tools/qarraydata/simplevector.h @@ -209,22 +209,7 @@ public: d->insert(0, first, last - first); } - void append(const_iterator first, const_iterator last) - { - if (first == last) - return; - - auto requiredSize = qsizetype(last - first); - if (d->needsDetach() || d.freeSpaceAtEnd() < requiredSize) { - DataPointer oldData; - d.reallocateAndGrow(QArrayData::GrowsAtEnd, requiredSize, &oldData); - - d->copyAppend(first, last); - return; - } - - d->copyAppend(first, last); - } + void append(const_iterator first, const_iterator last) { d->growAppend(first, last); } void insert(int position, const_iterator first, const_iterator last) { diff --git a/tests/auto/corelib/tools/qlist/tst_qlist.cpp b/tests/auto/corelib/tools/qlist/tst_qlist.cpp index 80adb0f6a1..14c679562f 100644 --- a/tests/auto/corelib/tools/qlist/tst_qlist.cpp +++ b/tests/auto/corelib/tools/qlist/tst_qlist.cpp @@ -348,8 +348,13 @@ private slots: void emplaceWithElementFromTheSameContainer_data(); void fromReadOnlyData() const; - void qtbug_90359() const; + void reinsertToBeginInt_qtbug91360() const { reinsertToBegin<int>(); } + void reinsertToBeginMovable_qtbug91360() const { reinsertToBegin<Movable>(); } + void reinsertToBeginCustom_qtbug91360() const { reinsertToBegin<Custom>(); } + void reinsertToEndInt_qtbug91360() const { reinsertToEnd<int>(); } + void reinsertToEndMovable_qtbug91360() const { reinsertToEnd<Movable>(); } + void reinsertToEndCustom_qtbug91360() const { reinsertToEnd<Custom>(); } private: template<typename T> void copyConstructor() const; @@ -379,6 +384,10 @@ private: template<typename T> void detachThreadSafety() const; template<typename T> void emplaceImpl() const; template<typename T> void emplaceConsistentWithStdVectorImpl() const; + template<typename T> + void reinsertToBegin() const; + template<typename T> + void reinsertToEnd() const; }; @@ -3265,5 +3274,53 @@ void tst_QList::qtbug_90359() const QCOMPARE(actual, expected); } +template<typename T> +void tst_QList::reinsertToBegin() const +{ + QList<T> list(1); + const auto reinsert = [](QList<T> &list) { + list.prepend(list.back()); + list.removeLast(); + }; + + // this constant is big enough for the QList to stop reallocating, after + // all, size is always less than 3 + const int maxIters = 128; + for (int i = 0; i < maxIters; ++i) { + reinsert(list); + } + + // if QList continues to grow, it's an error + qsizetype capacity = list.capacity(); + for (int i = 0, enoughIters = int(capacity) * 2; i < enoughIters; ++i) { + reinsert(list); + QCOMPARE(capacity, list.capacity()); + } +} + +template<typename T> +void tst_QList::reinsertToEnd() const +{ + QList<T> list(1); + const auto reinsert = [](QList<T> &list) { + list.append(list.front()); + list.removeFirst(); + }; + + // this constant is big enough for the QList to stop reallocating, after + // all, size is always less than 3 + const int maxIters = 128; + for (int i = 0; i < maxIters; ++i) { + reinsert(list); + } + + // if QList continues to grow, it's an error + qsizetype capacity = list.capacity(); + for (int i = 0, enoughIters = int(capacity) * 2; i < enoughIters; ++i) { + reinsert(list); + QCOMPARE(capacity, list.capacity()); + } +} + QTEST_MAIN(tst_QList) #include "tst_qlist.moc" |