diff options
| author | Andrei Golubev <andrei.golubev@qt.io> | 2020-07-31 15:27:08 +0200 |
|---|---|---|
| committer | Andrei Golubev <andrei.golubev@qt.io> | 2020-08-27 18:58:20 +0200 |
| commit | e35d0ae0ccdb72a1fe4347b3985fd6a69886e0bb (patch) | |
| tree | 576c977e177c8a2e0d62f522269ea93b53f68207 /src/corelib/tools/qarraydataops.h | |
| parent | 4b2f5371d9ba7b8d2dc068223866bbb3c8242beb (diff) | |
Support GrowsBackwards flag in QArrayDataPointer
Introduced allocation function in QArrayDataPointer with
interface similar to QArrayData::allocate that supports growing
strategies. This func is used instead of the original in cases
when prepend-aware storage is needed. Tried to follow Qt5 QList
policy in terms of space reservation
Updated QPodArrayOps::reallocate to be aware of growing
shenanigans. It doesn't look like a perfect solution but it is
rather close and similar to what Qt6 QList is doing when not
growing (e.g. reserve/squeeze)
Added initial QCommonArrayOps with helper function that tells
when reallocation is preferable over just using the insert-like
operation. This comes up later on when GrowsBackwards policy is
properly supported in operations
Essentially, 2/3 main data management blocks for prepend optimization
are introduced here. The last one being a generalized data move that
is done instead of reallocation when existing free space is not enough
Task-number: QTBUG-84320
Change-Id: I9a2bac62ad600613a6d7c5348325e0e54aadb73d
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
Diffstat (limited to 'src/corelib/tools/qarraydataops.h')
| -rw-r--r-- | src/corelib/tools/qarraydataops.h | 59 |
1 files changed, 58 insertions, 1 deletions
diff --git a/src/corelib/tools/qarraydataops.h b/src/corelib/tools/qarraydataops.h index f6384ca9986..8c0ca8f2f41 100644 --- a/src/corelib/tools/qarraydataops.h +++ b/src/corelib/tools/qarraydataops.h @@ -465,6 +465,19 @@ public: void reallocate(qsizetype alloc, typename Data::ArrayOptions options) { + // when reallocating, take care of the situation when no growth is + // happening - need to move the data in this case, unfortunately + const bool grows = options & (Data::GrowsForward | Data::GrowsBackwards); + + // ### optimize me: there may be cases when moving is not obligatory + if (this->d && !grows) { + const auto gap = this->freeSpaceAtBegin(); + auto oldBegin = this->begin(); + this->ptr -= gap; + ::memmove(static_cast<void *>(this->begin()), static_cast<void *>(oldBegin), + this->size * sizeof(T)); + } + auto pair = Data::reallocateUnaligned(this->d, this->ptr, alloc, options); this->d = pair.first; this->ptr = pair.second; @@ -1033,11 +1046,55 @@ struct QArrayOpsSelector<T, typedef QMovableArrayOps<T> Type; }; +template <class T> +struct QCommonArrayOps : QArrayOpsSelector<T>::Type +{ + using Base = typename QArrayOpsSelector<T>::Type; + using parameter_type = typename Base::parameter_type; + using iterator = typename Base::iterator; + using const_iterator = typename Base::const_iterator; + + // Returns whether reallocation is desirable before adding more elements + // into the container. This is a helper function that one can use to + // theoretically improve average operations performance. Ignoring this + // function does not affect the correctness of the array operations. + bool shouldGrowBeforeInsert(const_iterator where, qsizetype n) const noexcept + { + if (this->d == nullptr) + return true; + if (this->d->flags & QArrayData::CapacityReserved) + return false; + if (!(this->d->flags & (QArrayData::GrowsForward | QArrayData::GrowsBackwards))) + return false; + Q_ASSERT(where >= this->begin() && where <= this->end()); // in range + + const qsizetype freeAtBegin = this->freeSpaceAtBegin(); + const qsizetype freeAtEnd = this->freeSpaceAtEnd(); + const qsizetype capacity = this->constAllocatedCapacity(); + + if (where == this->begin()) { // prepend + // Qt5 QList in prepend: not enough space at begin && 33% full + // Now (below): + return freeAtBegin < n && (this->size >= (capacity / 3)); + } + + if (where == this->end()) { // append + // Qt5 QList in append: not enough space at end && less than 66% free space at front + // Now (below): + return freeAtEnd < n && !((freeAtBegin - n) >= (2 * capacity / 3)); + } + + // Qt5 QList in insert: no free space + // Now: no free space OR not enough space on either of the sides (bad perf. case) + return (freeAtBegin + freeAtEnd) < n || (freeAtBegin < n && freeAtEnd < n); + } +}; + } // namespace QtPrivate template <class T> struct QArrayDataOps - : QtPrivate::QArrayOpsSelector<T>::Type + : QtPrivate::QCommonArrayOps<T> { }; |