diff options
author | Lars Knoll <lars.knoll@qt.io> | 2020-11-04 22:59:09 +0100 |
---|---|---|
committer | Lars Knoll <lars.knoll@qt.io> | 2020-11-17 11:45:46 +0100 |
commit | 6be39809b038768a665b0e29a3a3668fdc424d9a (patch) | |
tree | 51b29213d4beed589e89a6bcae34874d5f63c593 /src | |
parent | 20883c9bcc7882b79db438ed0959530f82c8ee0a (diff) |
Simplify reallocation handling in QList
Have one generic method for detaching and reallocations.
Use that method throughout QList to avoid duplicated
instantiations of code paths that are rarely used.
Change-Id: I5b9add3be5f17b387e2d34028b72c8f52db68444
Reviewed-by: Andrei Golubev <andrei.golubev@qt.io>
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
Diffstat (limited to 'src')
-rw-r--r-- | src/corelib/tools/qarraydataops.h | 77 | ||||
-rw-r--r-- | src/corelib/tools/qarraydatapointer.h | 88 | ||||
-rw-r--r-- | src/corelib/tools/qlist.h | 99 |
3 files changed, 102 insertions, 162 deletions
diff --git a/src/corelib/tools/qarraydataops.h b/src/corelib/tools/qarraydataops.h index d7e7b4bf07..3548424b53 100644 --- a/src/corelib/tools/qarraydataops.h +++ b/src/corelib/tools/qarraydataops.h @@ -1311,60 +1311,37 @@ public: public: void insert(qsizetype i, qsizetype n, parameter_type t) { - if (this->needsDetach() || (n > this->freeSpaceAtBegin() && n > this->freeSpaceAtEnd())) { - typename Data::GrowthPosition pos = Data::GrowsAtEnd; - if (this->size != 0 && i <= (this->size >> 1)) - pos = Data::GrowsAtBeginning; - - DataPointer detached(DataPointer::allocateGrow(*this, n, pos)); - const_iterator where = this->constBegin() + i; - detached->copyAppend(this->constBegin(), where); - detached->copyAppend(n, t); - detached->copyAppend(where, this->constEnd()); - this->swap(detached); - } else { - T copy(t); - // Insert elements based on the divided distance. Good case: only 1 - // insert happens (either to the front part or to the back part). Bad - // case: both inserts happen, meaning that we touch all N elements in - // the container (this should be handled "outside" by ensuring enough - // free space by reallocating more frequently) - T *where = this->begin() + i; - const auto beginSize = sizeToInsertAtBegin(where, n); - if (beginSize) - Base::insert(GrowsBackwardsTag{}, where, beginSize, copy); - if (n - beginSize) - Base::insert(GrowsForwardTag{}, where, n - beginSize, copy); - } + T copy(t); + + typename Data::GrowthPosition pos = Data::GrowsAtEnd; + if (this->size != 0 && i <= (this->size >> 1)) + pos = Data::GrowsAtBeginning; + this->detachAndGrow(pos, n); + Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) || + (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n)); + + T *where = this->begin() + i; + if (pos == QArrayData::GrowsAtBeginning) + Base::insert(GrowsBackwardsTag{}, where, n, copy); + else + Base::insert(GrowsForwardTag{}, where, n, copy); } void insert(qsizetype i, const T *data, qsizetype n) { - if (this->needsDetach() || (n > this->freeSpaceAtBegin() && n > this->freeSpaceAtEnd())) { - typename Data::GrowthPosition pos = Data::GrowsAtEnd; - if (this->size != 0 && i <= (this->size >> 1)) - pos = Data::GrowsAtBeginning; - - DataPointer detached(DataPointer::allocateGrow(*this, n, pos)); - auto where = this->constBegin() + i; - detached->copyAppend(this->constBegin(), where); - detached->copyAppend(data, data + n); - detached->copyAppend(where, this->constEnd()); - this->swap(detached); - } else { - // Insert elements based on the divided distance. Good case: only 1 - // insert happens (either to the front part or to the back part). Bad - // case: both inserts happen, meaning that we touch all N elements in - // the container (this should be handled "outside" by ensuring enough - // free space by reallocating more frequently) - T *where = this->begin() + i; - const auto k = sizeToInsertAtBegin(where, n); - if (k) - Base::insert(GrowsBackwardsTag{}, where, data, data + k); - if (k != n) - Base::insert(GrowsForwardTag{}, where, data + k, data + n); - } - + typename Data::GrowthPosition pos = Data::GrowsAtEnd; + if (this->size != 0 && i <= (this->size >> 1)) + pos = Data::GrowsAtBeginning; + DataPointer oldData; + this->detachAndGrow(pos, n, &oldData); + Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) || + (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n)); + + T *where = this->begin() + i; + if (pos == QArrayData::GrowsAtBeginning) + Base::insert(GrowsBackwardsTag{}, where, data, data + n); + else + Base::insert(GrowsForwardTag{}, where, data, data + n); } template<typename... Args> diff --git a/src/corelib/tools/qarraydatapointer.h b/src/corelib/tools/qarraydatapointer.h index 26e8f934ee..1aa9a670e7 100644 --- a/src/corelib/tools/qarraydatapointer.h +++ b/src/corelib/tools/qarraydatapointer.h @@ -162,17 +162,55 @@ public: swap(tmp); } - QArrayDataPointer detach() + void detach(QArrayDataPointer *old = nullptr) { - if (needsDetach()) { - QPair<Data *, T *> copy = clone(); - QArrayDataPointer old(d, ptr, size); - d = copy.first; - ptr = copy.second; - return old; + if (needsDetach()) + 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) + { + if (!needsDetach()) { + if (!n || + (where == QArrayData::GrowsAtBeginning && freeSpaceAtBegin() >= n) || + (where == QArrayData::GrowsAtEnd && freeSpaceAtEnd() >= n)) + return; + } + reallocateAndGrow(where, n, old); + } + + 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) { + (*this)->reallocate(constAllocatedCapacity() - freeSpaceAtEnd() + n, QArrayData::Grow); // fast path + return; + } + } + + QArrayDataPointer dp(allocateGrow(*this, n, where)); + if (where == QArrayData::GrowsAtBeginning) { + dp.ptr += n; + Q_ASSERT(dp.freeSpaceAtBegin() >= n); + } else { + Q_ASSERT(dp.freeSpaceAtEnd() >= n); + } + if (size) { + qsizetype toCopy = size; + if (n < 0) + toCopy += n; + if (needsDetach() || old) + dp->copyAppend(begin(), begin() + toCopy); + else + dp->moveAppend(begin(), begin() + toCopy); + dp.d->flags = flags(); + Q_ASSERT(dp.size == toCopy); } - return QArrayDataPointer(); + swap(dp); + if (old) + old->swap(dp); } // forwards from QArrayData @@ -244,40 +282,6 @@ public: return lhs.data() != rhs.data() || lhs.size != rhs.size; } - static void reallocateGrow(QArrayDataPointer &from, qsizetype n) - { - Q_ASSERT(n > 0); - - if constexpr (!QTypeInfo<T>::isRelocatable || alignof(T) > alignof(std::max_align_t)) { - QArrayDataPointer dd(allocateGrow(from, n, QArrayData::GrowsAtEnd)); - dd->copyAppend(from.data(), from.data() + from.size); - from.swap(dd); - } else { - if (from.needsDetach()) { - QArrayDataPointer dd(allocateGrow(from, n, QArrayData::GrowsAtEnd)); - dd->copyAppend(from.data(), from.data() + from.size); - from.swap(dd); - } else { - from->reallocate(from.constAllocatedCapacity() - from.freeSpaceAtEnd() + n, QArrayData::Grow); // fast path - } - } - } - -private: - [[nodiscard]] QPair<Data *, T *> clone() const - { - QPair<Data *, T *> pair = Data::allocate(detachCapacity(size), QArrayData::KeepSize); - QArrayDataPointer copy(pair.first, pair.second, 0); - if (size) - copy->copyAppend(begin(), end()); - - if (pair.first) - pair.first->flags = flags(); - copy.d = nullptr; - copy.ptr = nullptr; - return pair; - } - protected: Data *d; T *ptr; diff --git a/src/corelib/tools/qlist.h b/src/corelib/tools/qlist.h index 85c8ee76bf..a5cb560dc0 100644 --- a/src/corelib/tools/qlist.h +++ b/src/corelib/tools/qlist.h @@ -385,7 +385,8 @@ public: void replace(qsizetype i, parameter_type t) { Q_ASSERT_X(i >= 0 && i < d->size, "QList<T>::replace", "index out of range"); - auto oldData = d.detach(); + DataPointer oldData; + d.detach(&oldData); d.data()[i] = t; } void replace(qsizetype i, rvalue_ref t) @@ -395,7 +396,8 @@ public: Q_UNUSED(t); } else { Q_ASSERT_X(i >= 0 && i < d->size, "QList<T>::replace", "index out of range"); - auto oldData = d.detach(); + DataPointer oldData; + d.detach(&oldData); d.data()[i] = std::move(t); } } @@ -603,15 +605,8 @@ inline void QList<T>::resize_internal(qsizetype newSize) Q_ASSERT(newSize >= 0); if (d->needsDetach() || newSize > capacity() - d.freeSpaceAtBegin()) { - // must allocate memory - DataPointer detached(Data::allocate(d->detachCapacity(newSize))); - qsizetype toCopy = qMin(size(), newSize); - if (toCopy) - detached->copyAppend(constBegin(), constBegin() + toCopy); - d.swap(detached); - } - - if (newSize < size()) + d.reallocateAndGrow(QArrayData::GrowsAtEnd, newSize - d.size); + } else if (newSize < size()) d->truncate(newSize); } @@ -645,7 +640,10 @@ inline void QList<T>::squeeze() // must allocate memory DataPointer detached(Data::allocate(size())); if (size()) { - detached->copyAppend(constBegin(), constEnd()); + if (d.needsDetach()) + detached->copyAppend(constBegin(), constEnd()); + else + detached->moveAppend(d.data(), d.data() + d.size); } d.swap(detached); } @@ -662,9 +660,7 @@ inline void QList<T>::remove(qsizetype i, qsizetype n) if (n == 0) return; - if (d->needsDetach()) - d.detach(); - + d.detach(); d->erase(d->begin() + i, d->begin() + i + n); } @@ -672,8 +668,7 @@ template <typename T> inline void QList<T>::removeFirst() { Q_ASSERT(!isEmpty()); - if (d->needsDetach()) - d.detach(); + d.detach(); d->eraseFirst(); } @@ -681,8 +676,7 @@ template <typename T> inline void QList<T>::removeLast() { Q_ASSERT(!isEmpty()); - if (d->needsDetach()) - detach(); + d.detach(); d->eraseLast(); } @@ -699,39 +693,22 @@ inline void QList<T>::append(const_iterator i1, const_iterator i2) if (i1 == i2) return; const auto distance = std::distance(i1, i2); - if (d->needsDetach() || distance > d.freeSpaceAtEnd()) { - DataPointer detached(DataPointer::allocateGrow(d, distance, QArrayData::GrowsAtEnd)); - detached->copyAppend(constBegin(), constEnd()); - detached->copyAppend(i1, i2); - d.swap(detached); - } else { - // we're detached and we can just move data around - d->copyAppend(i1, i2); - } + DataPointer oldData; + d.detachAndGrow(QArrayData::GrowsAtEnd, distance, &oldData); + d->copyAppend(i1, i2); } template <typename T> inline void QList<T>::append(QList<T> &&other) { + Q_ASSERT(&other != this); if (other.isEmpty()) return; if (other.d->needsDetach() || !std::is_nothrow_move_constructible_v<T>) return append(other); - if (d->needsDetach() || other.size() > d.freeSpaceAtEnd()) { - DataPointer detached(DataPointer::allocateGrow(d, other.size(), QArrayData::GrowsAtEnd)); - - if (!d->needsDetach()) - detached->moveAppend(begin(), end()); - else - detached->copyAppend(cbegin(), cend()); - detached->moveAppend(other.begin(), other.end()); - - d.swap(detached); - } else { - // we're detached and we can just move data around - d->moveAppend(other.begin(), other.end()); - } + d.detachAndGrow(QArrayData::GrowsAtEnd, other.size()); + d->moveAppend(other.begin(), other.end()); } template<typename T> @@ -739,14 +716,10 @@ template<typename... Args> inline typename QList<T>::reference QList<T>::emplaceFront(Args &&... args) { if (d->needsDetach() || !d.freeSpaceAtBegin()) { - DataPointer detached(DataPointer::allocateGrow(d, 1, QArrayData::GrowsAtBeginning)); - - detached->emplaceBack(std::forward<Args>(args)...); - if (!d.needsDetach()) - detached->moveAppend(d.begin(), d.end()); - else - detached->copyAppend(constBegin(), constEnd()); - d.swap(detached); + // protect against args being an element of the container + T tmp(std::forward<Args>(args)...); + d.reallocateAndGrow(QArrayData::GrowsAtBeginning, 1); + d->emplaceFront(std::move(tmp)); } else { d->emplaceFront(std::forward<Args>(args)...); } @@ -778,10 +751,8 @@ QList<T>::emplace(qsizetype i, Args&&... args) DataPointer detached(DataPointer::allocateGrow(d, 1, pos)); const_iterator where = constBegin() + i; - // Create an element here to handle cases when a user moves the element - // from a container to the same container. This is a critical step for - // COW types (e.g. Qt types) since copyAppend() done before emplace() - // would shallow-copy the passed element and ruin the move + + // protect against args being an element of the container T tmp(std::forward<Args>(args)...); detached->copyAppend(constBegin(), where); @@ -799,22 +770,10 @@ template<typename... Args> inline typename QList<T>::reference QList<T>::emplaceBack(Args &&... args) { if (d->needsDetach() || !d.freeSpaceAtEnd()) { - // condition below should follow the condition in QArrayDataPointer::reallocateGrow() - if constexpr (!QTypeInfo<T>::isRelocatable || alignof(T) > alignof(std::max_align_t)) { - // avoid taking a temporary copy of Args - DataPointer detached(DataPointer::allocateGrow(d, 1, QArrayData::GrowsAtEnd)); - detached->copyAppend(constBegin(), constEnd()); - detached->emplace(detached.end(), std::forward<Args>(args)...); - d.swap(detached); - } else { - // Create an element here to handle cases when a user moves the element - // from a container to the same container. This is required as we call - // reallocate, which could delete the data args points to. - // This should be optimised to only take the copy when really required. - T tmp(std::forward<Args>(args)...); - DataPointer::reallocateGrow(d, 1); - d->emplace(d.end(), std::move(tmp)); - } + // protect against args being an element of the container + T tmp(std::forward<Args>(args)...); + d.reallocateAndGrow(QArrayData::GrowsAtEnd, 1); + d->emplaceBack(std::move(tmp)); } else { d->emplaceBack(std::forward<Args>(args)...); } |