Revision control
Copy as Markdown
// Copyright (C) 2020 The Qt Company Ltd.
// Copyright (C) 2016 Intel Corporation.
// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
// Qt-Security score:significant reason:default
#ifndef QARRAYDATAOPS_H
#define QARRAYDATAOPS_H
#include <QtCore/qarraydata.h>
#include <QtCore/qcontainertools_impl.h>
#include <QtCore/qnamespace.h>
#include <QtCore/q20functional.h>
#include <QtCore/q20memory.h>
#include <new>
#include <string.h>
#include <utility>
#include <iterator>
#include <type_traits>
QT_BEGIN_NAMESPACE
template <class T> struct QArrayDataPointer;
namespace QtPrivate {
template <class T>
struct QPodArrayOps
{
static_assert (std::is_nothrow_destructible_v<T>, "Types with throwing destructors are not supported in Qt containers.");
protected:
typedef QTypedArrayData<T> Data;
using DataPointer = QArrayDataPointer<T>;
private:
DataPointer *m_ptr;
public:
explicit QPodArrayOps(DataPointer &dp) : m_ptr{&dp} {}
DataPointer *that()
{ return m_ptr; }
const DataPointer *that() const
{ return m_ptr; }
typedef typename QArrayDataPointer<T>::parameter_type parameter_type;
void copyAppend(const T *b, const T *e) noexcept
{
Q_ASSERT(that()->isMutable() || b == e);
Q_ASSERT(!that()->isShared() || b == e);
Q_ASSERT(b <= e);
Q_ASSERT((e - b) <= that()->freeSpaceAtEnd());
if (b == e)
return;
::memcpy(static_cast<void *>(that()->end()), static_cast<const void *>(b), (e - b) * sizeof(T));
that()->size += (e - b);
}
void copyAppend(qsizetype n, parameter_type t) noexcept
{
Q_ASSERT(!that()->isShared() || n == 0);
Q_ASSERT(that()->freeSpaceAtEnd() >= n);
if (!n)
return;
T *where = that()->end();
that()->size += qsizetype(n);
while (n--)
*where++ = t;
}
void moveAppend(T *b, T *e) noexcept
{
copyAppend(b, e);
}
void truncate(size_t newSize) noexcept
{
Q_ASSERT(that()->isMutable());
Q_ASSERT(!that()->isShared());
Q_ASSERT(newSize <= size_t(that()->size));
that()->size = qsizetype(newSize);
}
void destroyAll() noexcept // Call from destructors, ONLY!
{
Q_ASSERT(that()->d);
Q_ASSERT(that()->d->ref_.loadRelaxed() == 0);
// As this is to be called only from destructor, it doesn't need to be
// exception safe; size not updated.
}
T *createHole(QArrayData::GrowthPosition pos, qsizetype where, qsizetype n)
{
Q_ASSERT((pos == QArrayData::GrowsAtBeginning && n <= that()->freeSpaceAtBegin()) ||
(pos == QArrayData::GrowsAtEnd && n <= that()->freeSpaceAtEnd()));
T *insertionPoint = that()->ptr + where;
if (pos == QArrayData::GrowsAtEnd) {
if (where < that()->size)
::memmove(static_cast<void *>(insertionPoint + n), static_cast<void *>(insertionPoint), (that()->size - where) * sizeof(T));
} else {
Q_ASSERT(where == 0);
that()->ptr -= n;
insertionPoint -= n;
}
that()->size += n;
return insertionPoint;
}
void insert(qsizetype i, const T *data, qsizetype n)
{
typename Data::GrowthPosition pos = Data::GrowsAtEnd;
if (that()->size != 0 && i == 0)
pos = Data::GrowsAtBeginning;
DataPointer oldData;
that()->detachAndGrow(pos, n, &data, &oldData);
Q_ASSERT((pos == Data::GrowsAtBeginning && that()->freeSpaceAtBegin() >= n) ||
(pos == Data::GrowsAtEnd && that()->freeSpaceAtEnd() >= n));
T *where = createHole(pos, i, n);
::memcpy(static_cast<void *>(where), static_cast<const void *>(data), n * sizeof(T));
}
void insert(qsizetype i, qsizetype n, parameter_type t)
{
T copy(t);
typename Data::GrowthPosition pos = Data::GrowsAtEnd;
if (that()->size != 0 && i == 0)
pos = Data::GrowsAtBeginning;
that()->detachAndGrow(pos, n, nullptr, nullptr);
Q_ASSERT((pos == Data::GrowsAtBeginning && that()->freeSpaceAtBegin() >= n) ||
(pos == Data::GrowsAtEnd && that()->freeSpaceAtEnd() >= n));
T *where = createHole(pos, i, n);
while (n--)
*where++ = copy;
}
template<typename... Args>
void emplace(qsizetype i, Args &&... args)
{
bool detach = that()->needsDetach();
if (!detach) {
if (i == that()->size && that()->freeSpaceAtEnd()) {
new (that()->end()) T(std::forward<Args>(args)...);
++that()->size;
return;
}
if (i == 0 && that()->freeSpaceAtBegin()) {
new (that()->begin() - 1) T(std::forward<Args>(args)...);
--that()->ptr;
++that()->size;
return;
}
}
T tmp(std::forward<Args>(args)...);
typename QArrayData::GrowthPosition pos = QArrayData::GrowsAtEnd;
if (that()->size != 0 && i == 0)
pos = QArrayData::GrowsAtBeginning;
that()->detachAndGrow(pos, 1, nullptr, nullptr);
T *where = createHole(pos, i, 1);
new (where) T(std::move(tmp));
}
void erase(T *b, qsizetype n)
{
T *e = b + n;
Q_ASSERT(that()->isMutable());
Q_ASSERT(b < e);
Q_ASSERT(b >= that()->begin() && b < that()->end());
Q_ASSERT(e > that()->begin() && e <= that()->end());
// Comply with std::vector::erase(): erased elements and all after them
// are invalidated. However, erasing from the beginning effectively
// means that all iterators are invalidated. We can use this freedom to
// erase by moving towards the end.
if (b == that()->begin() && e != that()->end()) {
that()->ptr = e;
} else if (e != that()->end()) {
::memmove(static_cast<void *>(b), static_cast<void *>(e),
(static_cast<T *>(that()->end()) - e) * sizeof(T));
}
that()->size -= n;
}
void eraseFirst() noexcept
{
Q_ASSERT(that()->isMutable());
Q_ASSERT(that()->size);
++that()->ptr;
--that()->size;
}
void eraseLast() noexcept
{
Q_ASSERT(that()->isMutable());
Q_ASSERT(that()->size);
--that()->size;
}
template <typename Predicate>
qsizetype eraseIf(Predicate pred)
{
qsizetype result = 0;
if (that()->size == 0)
return result;
if (!that()->needsDetach()) {
auto end = that()->end();
auto it = std::remove_if(that()->begin(), end, pred);
if (it != end) {
result = std::distance(it, end);
erase(it, result);
}
} else {
const auto begin = that()->begin();
const auto end = that()->end();
auto it = std::find_if(begin, end, pred);
if (it == end)
return result;
QArrayDataPointer<T> other(that()->size);
Q_CHECK_PTR(other.data());
auto dest = other.begin();
// std::uninitialized_copy will fallback to ::memcpy/memmove()
dest = std::uninitialized_copy(begin, it, dest);
dest = q_uninitialized_remove_copy_if(std::next(it), end, dest, pred);
other.size = std::distance(other.data(), dest);
result = that()->size - other.size;
that()->swap(other);
}
return result;
}
struct Span { T *begin; T *end; };
void copyRanges(std::initializer_list<Span> ranges)
{
auto it = that()->begin();
std::for_each(ranges.begin(), ranges.end(), [&it](const auto &span) {
it = std::copy(span.begin, span.end, it);
});
that()->size = std::distance(that()->begin(), it);
}
void assign(T *b, T *e, parameter_type t) noexcept
{
Q_ASSERT(b <= e);
Q_ASSERT(b >= that()->begin() && e <= that()->end());
while (b != e)
::memcpy(static_cast<void *>(b++), static_cast<const void *>(&t), sizeof(T));
}
void reallocate(qsizetype alloc, QArrayData::AllocationOption option)
{
auto pair = Data::reallocateUnaligned(that()->d, that()->ptr, alloc, option);
Q_CHECK_PTR(pair.ptr);
Q_ASSERT(pair.header != nullptr);
that()->d = pair.header;
that()->ptr = pair.ptr;
}
};
template <class T>
struct QGenericArrayOps
{
static_assert (std::is_nothrow_destructible_v<T>, "Types with throwing destructors are not supported in Qt containers.");
protected:
typedef QTypedArrayData<T> Data;
using DataPointer = QArrayDataPointer<T>;
private:
DataPointer *m_ptr;
public:
explicit QGenericArrayOps(DataPointer &dp) : m_ptr{&dp} {}
DataPointer *that()
{ return m_ptr; }
const DataPointer *that() const
{ return m_ptr; }
typedef typename QArrayDataPointer<T>::parameter_type parameter_type;
void copyAppend(const T *b, const T *e)
{
Q_ASSERT(that()->isMutable() || b == e);
Q_ASSERT(!that()->isShared() || b == e);
Q_ASSERT(b <= e);
Q_ASSERT((e - b) <= that()->freeSpaceAtEnd());
if (b == e) // short-cut and handling the case b and e == nullptr
return;
T *data = that()->begin();
while (b < e) {
new (data + that()->size) T(*b);
++b;
++that()->size;
}
}
void copyAppend(qsizetype n, parameter_type t)
{
Q_ASSERT(!that()->isShared() || n == 0);
Q_ASSERT(that()->freeSpaceAtEnd() >= n);
if (!n)
return;
T *data = that()->begin();
while (n--) {
new (data + that()->size) T(t);
++that()->size;
}
}
void moveAppend(T *b, T *e)
{
Q_ASSERT(that()->isMutable() || b == e);
Q_ASSERT(!that()->isShared() || b == e);
Q_ASSERT(b <= e);
Q_ASSERT((e - b) <= that()->freeSpaceAtEnd());
if (b == e)
return;
T *data = that()->begin();
while (b < e) {
new (data + that()->size) T(std::move(*b));
++b;
++that()->size;
}
}
void truncate(size_t newSize)
{
Q_ASSERT(that()->isMutable());
Q_ASSERT(!that()->isShared());
Q_ASSERT(newSize <= size_t(that()->size));
std::destroy(that()->begin() + newSize, that()->end());
that()->size = newSize;
}
void destroyAll() // Call from destructors, ONLY
{
Q_ASSERT(that()->d);
// As this is to be called only from destructor, it doesn't need to be
// exception safe; size not updated.
Q_ASSERT(that()->d->ref_.loadRelaxed() == 0);
std::destroy(that()->begin(), that()->end());
}
struct Inserter
{
QArrayDataPointer<T> *data;
T *begin;
qsizetype size;
qsizetype sourceCopyConstruct = 0, nSource = 0, move = 0, sourceCopyAssign = 0;
T *end = nullptr, *last = nullptr, *where = nullptr;
Inserter(QArrayDataPointer<T> *d) : data(d)
{
begin = d->ptr;
size = d->size;
}
~Inserter() {
data->ptr = begin;
data->size = size;
}
Q_DISABLE_COPY(Inserter)
void setup(qsizetype pos, qsizetype n)
{
end = begin + size;
last = end - 1;
where = begin + pos;
qsizetype dist = size - pos;
sourceCopyConstruct = 0;
nSource = n;
move = n - dist; // smaller 0
sourceCopyAssign = n;
if (n > dist) {
sourceCopyConstruct = n - dist;
move = 0;
sourceCopyAssign -= sourceCopyConstruct;
}
}
void insert(qsizetype pos, const T *source, qsizetype n)
{
qsizetype oldSize = size;
Q_UNUSED(oldSize);
setup(pos, n);
// first create new elements at the end, by copying from elements
// to be inserted (if they extend past the current end of the array)
for (qsizetype i = 0; i != sourceCopyConstruct; ++i) {
new (end + i) T(source[nSource - sourceCopyConstruct + i]);
++size;
}
Q_ASSERT(size <= oldSize + n);
// now move construct new elements at the end from existing elements inside
// the array.
for (qsizetype i = sourceCopyConstruct; i != nSource; ++i) {
new (end + i) T(std::move(*(end + i - nSource)));
++size;
}
// array has the new size now!
Q_ASSERT(size == oldSize + n);
// now move assign existing elements towards the end
for (qsizetype i = 0; i != move; --i)
last[i] = std::move(last[i - nSource]);
// finally copy the remaining elements from source over
for (qsizetype i = 0; i != sourceCopyAssign; ++i)
where[i] = source[i];
}
void insert(qsizetype pos, const T &t, qsizetype n)
{
const qsizetype oldSize = size;
Q_UNUSED(oldSize);
setup(pos, n);
// first create new elements at the end, by copying from elements
// to be inserted (if they extend past the current end of the array)
for (qsizetype i = 0; i != sourceCopyConstruct; ++i) {
new (end + i) T(t);
++size;
}
Q_ASSERT(size <= oldSize + n);
// now move construct new elements at the end from existing elements inside
// the array.
for (qsizetype i = sourceCopyConstruct; i != nSource; ++i) {
new (end + i) T(std::move(*(end + i - nSource)));
++size;
}
// array has the new size now!
Q_ASSERT(size == oldSize + n);
// now move assign existing elements towards the end
for (qsizetype i = 0; i != move; --i)
last[i] = std::move(last[i - nSource]);
// finally copy the remaining elements from source over
for (qsizetype i = 0; i != sourceCopyAssign; ++i)
where[i] = t;
}
void insertOne(qsizetype pos, T &&t)
{
setup(pos, 1);
if (sourceCopyConstruct) {
Q_ASSERT(sourceCopyConstruct == 1);
new (end) T(std::move(t));
++size;
} else {
// create a new element at the end by move constructing one existing element
// inside the array.
new (end) T(std::move(*(end - 1)));
++size;
// now move assign existing elements towards the end
for (qsizetype i = 0; i != move; --i)
last[i] = std::move(last[i - 1]);
// and move the new item into place
*where = std::move(t);
}
}
};
void insert(qsizetype i, const T *data, qsizetype n)
{
const bool growsAtBegin = that()->size != 0 && i == 0;
const auto pos = growsAtBegin ? Data::GrowsAtBeginning : Data::GrowsAtEnd;
DataPointer oldData;
that()->detachAndGrow(pos, n, &data, &oldData);
Q_ASSERT((pos == Data::GrowsAtBeginning && that()->freeSpaceAtBegin() >= n) ||
(pos == Data::GrowsAtEnd && that()->freeSpaceAtEnd() >= n));
if (growsAtBegin) {
// copy construct items in reverse order at the begin
Q_ASSERT(that()->freeSpaceAtBegin() >= n);
while (n) {
--n;
new (that()->begin() - 1) T(data[n]);
--that()->ptr;
++that()->size;
}
} else {
Inserter{that()}.insert(i, data, n);
}
}
void insert(qsizetype i, qsizetype n, parameter_type t)
{
Q_DECL_UNINITIALIZED
T copy(t);
const bool growsAtBegin = that()->size != 0 && i == 0;
const auto pos = growsAtBegin ? Data::GrowsAtBeginning : Data::GrowsAtEnd;
that()->detachAndGrow(pos, n, nullptr, nullptr);
Q_ASSERT((pos == Data::GrowsAtBeginning && that()->freeSpaceAtBegin() >= n) ||
(pos == Data::GrowsAtEnd && that()->freeSpaceAtEnd() >= n));
if (growsAtBegin) {
// copy construct items in reverse order at the begin
Q_ASSERT(that()->freeSpaceAtBegin() >= n);
while (n--) {
new (that()->begin() - 1) T(copy);
--that()->ptr;
++that()->size;
}
} else {
Inserter{that()}.insert(i, copy, n);
}
}
template<typename... Args>
void emplace(qsizetype i, Args &&... args)
{
bool detach = that()->needsDetach();
if (!detach) {
if (i == that()->size && that()->freeSpaceAtEnd()) {
new (that()->end()) T(std::forward<Args>(args)...);
++that()->size;
return;
}
if (i == 0 && that()->freeSpaceAtBegin()) {
new (that()->begin() - 1) T(std::forward<Args>(args)...);
--that()->ptr;
++that()->size;
return;
}
}
Q_DECL_UNINITIALIZED
T tmp(std::forward<Args>(args)...);
const bool growsAtBegin = that()->size != 0 && i == 0;
const auto pos = growsAtBegin ? Data::GrowsAtBeginning : Data::GrowsAtEnd;
that()->detachAndGrow(pos, 1, nullptr, nullptr);
if (growsAtBegin) {
Q_ASSERT(that()->freeSpaceAtBegin());
new (that()->begin() - 1) T(std::move(tmp));
--that()->ptr;
++that()->size;
} else {
Inserter{that()}.insertOne(i, std::move(tmp));
}
}
void erase(T *b, qsizetype n)
{
T *e = b + n;
Q_ASSERT(that()->isMutable());
Q_ASSERT(b < e);
Q_ASSERT(b >= that()->begin() && b < that()->end());
Q_ASSERT(e > that()->begin() && e <= that()->end());
// Comply with std::vector::erase(): erased elements and all after them
// are invalidated. However, erasing from the beginning effectively
// means that all iterators are invalidated. We can use this freedom to
// erase by moving towards the end.
if (b == that()->begin() && e != that()->end()) {
that()->ptr = e;
} else {
const T *const end = that()->end();
// move (by assignment) the elements from e to end
// onto b to the new end
while (e != end) {
*b = std::move(*e);
++b;
++e;
}
}
that()->size -= n;
std::destroy(b, e);
}
void eraseFirst() noexcept
{
Q_ASSERT(that()->isMutable());
Q_ASSERT(that()->size);
that()->begin()->~T();
++that()->ptr;
--that()->size;
}
void eraseLast() noexcept
{
Q_ASSERT(that()->isMutable());
Q_ASSERT(that()->size);
(that()->end() - 1)->~T();
--that()->size;
}
void assign(T *b, T *e, parameter_type t)
{
Q_ASSERT(b <= e);
Q_ASSERT(b >= that()->begin() && e <= that()->end());
while (b != e)
*b++ = t;
}
};
template <class T>
struct QMovableArrayOps
: QGenericArrayOps<T>
{
using Base = QGenericArrayOps<T>;
static_assert (std::is_nothrow_destructible_v<T>, "Types with throwing destructors are not supported in Qt containers.");
protected:
typedef QTypedArrayData<T> Data;
using DataPointer = QArrayDataPointer<T>;
public:
explicit QMovableArrayOps(DataPointer &dp) : Base(dp) {}
DataPointer *that()
{ return Base::that(); }
const DataPointer *that() const
{ return Base::that(); }
// using QGenericArrayOps<T>::copyAppend;
// using QGenericArrayOps<T>::moveAppend;
// using QGenericArrayOps<T>::truncate;
// using QGenericArrayOps<T>::destroyAll;
typedef typename QGenericArrayOps<T>::parameter_type parameter_type;
struct Inserter
{
QArrayDataPointer<T> * const data;
T *displaceFrom;
T * const displaceTo;
const qsizetype nInserts = 0;
const size_t bytes;
void verifyPost()
{ Q_ASSERT(displaceFrom == displaceTo); }
explicit Inserter(QArrayDataPointer<T> *d, qsizetype pos, qsizetype n)
: data{d},
displaceFrom{d->ptr + pos},
displaceTo{displaceFrom + n},
nInserts{n},
bytes{(data->size - pos) * sizeof(T)}
{
::memmove(static_cast<void *>(displaceTo), static_cast<void *>(displaceFrom), bytes);
}
~Inserter() {
auto inserts = nInserts;
if constexpr (!std::is_nothrow_copy_constructible_v<T>) {
if (displaceFrom != displaceTo) {
::memmove(static_cast<void *>(displaceFrom), static_cast<void *>(displaceTo), bytes);
inserts -= qAbs(displaceFrom - displaceTo);
}
}
data->size += inserts;
}
Q_DISABLE_COPY(Inserter)
void insertRange(const T *source, qsizetype n)
{
while (n--) {
new (displaceFrom) T(*source);
++source;
++displaceFrom;
}
verifyPost();
}
void insertFill(const T &t, qsizetype n)
{
while (n--) {
new (displaceFrom) T(t);
++displaceFrom;
}
verifyPost();
}
void insertOne(T &&t)
{
new (displaceFrom) T(std::move(t));
++displaceFrom;
verifyPost();
}
};
void insert(qsizetype i, const T *data, qsizetype n)
{
const bool growsAtBegin = that()->size != 0 && i == 0;
const auto pos = growsAtBegin ? Data::GrowsAtBeginning : Data::GrowsAtEnd;
DataPointer oldData;
that()->detachAndGrow(pos, n, &data, &oldData);
Q_ASSERT((pos == Data::GrowsAtBeginning && that()->freeSpaceAtBegin() >= n) ||
(pos == Data::GrowsAtEnd && that()->freeSpaceAtEnd() >= n));
if (growsAtBegin) {
// copy construct items in reverse order at the begin
Q_ASSERT(that()->freeSpaceAtBegin() >= n);
while (n) {
--n;
new (that()->begin() - 1) T(data[n]);
--that()->ptr;
++that()->size;
}
} else {
Inserter{that(), i, n}.insertRange(data, n);
}
}
void insert(qsizetype i, qsizetype n, parameter_type t)
{
Q_DECL_UNINITIALIZED
T copy(t);
const bool growsAtBegin = that()->size != 0 && i == 0;
const auto pos = growsAtBegin ? Data::GrowsAtBeginning : Data::GrowsAtEnd;
that()->detachAndGrow(pos, n, nullptr, nullptr);
Q_ASSERT((pos == Data::GrowsAtBeginning && that()->freeSpaceAtBegin() >= n) ||
(pos == Data::GrowsAtEnd && that()->freeSpaceAtEnd() >= n));
if (growsAtBegin) {
// copy construct items in reverse order at the begin
Q_ASSERT(that()->freeSpaceAtBegin() >= n);
while (n--) {
new (that()->begin() - 1) T(copy);
--that()->ptr;
++that()->size;
}
} else {
Inserter{that(), i, n}.insertFill(copy, n);
}
}
template<typename... Args>
void emplace(qsizetype i, Args &&... args)
{
bool detach = that()->needsDetach();
if (!detach) {
if (i == that()->size && that()->freeSpaceAtEnd()) {
new (that()->end()) T(std::forward<Args>(args)...);
++that()->size;
return;
}
if (i == 0 && that()->freeSpaceAtBegin()) {
new (that()->begin() - 1) T(std::forward<Args>(args)...);
--that()->ptr;
++that()->size;
return;
}
}
Q_DECL_UNINITIALIZED
T tmp(std::forward<Args>(args)...);
const bool growsAtBegin = that()->size != 0 && i == 0;
const auto pos = growsAtBegin ? Data::GrowsAtBeginning : Data::GrowsAtEnd;
that()->detachAndGrow(pos, 1, nullptr, nullptr);
if (growsAtBegin) {
Q_ASSERT(that()->freeSpaceAtBegin());
new (that()->begin() - 1) T(std::move(tmp));
--that()->ptr;
++that()->size;
} else {
Inserter{that(), i, 1}.insertOne(std::move(tmp));
}
}
void erase(T *b, qsizetype n)
{
T *e = b + n;
Q_ASSERT(that()->isMutable());
Q_ASSERT(b < e);
Q_ASSERT(b >= that()->begin() && b < that()->end());
Q_ASSERT(e > that()->begin() && e <= that()->end());
// Comply with std::vector::erase(): erased elements and all after them
// are invalidated. However, erasing from the beginning effectively
// means that all iterators are invalidated. We can use this freedom to
// erase by moving towards the end.
std::destroy(b, e);
if (b == that()->begin() && e != that()->end()) {
that()->ptr = e;
} else if (e != that()->end()) {
memmove(static_cast<void *>(b), static_cast<const void *>(e), (static_cast<const T *>(that()->end()) - e)*sizeof(T));
}
that()->size -= n;
}
void reallocate(qsizetype alloc, QArrayData::AllocationOption option)
{
auto pair = Data::reallocateUnaligned(that()->d, that()->ptr, alloc, option);
Q_CHECK_PTR(pair.ptr);
Q_ASSERT(pair.header != nullptr);
that()->d = pair.header;
that()->ptr = pair.ptr;
}
};
template <class T, class = void>
struct QArrayOpsSelector
{
typedef QGenericArrayOps<T> Type;
};
template <class T>
struct QArrayOpsSelector<T,
typename std::enable_if<
!QTypeInfo<T>::isComplex && QTypeInfo<T>::isRelocatable
>::type>
{
typedef QPodArrayOps<T> Type;
};
template <class T>
struct QArrayOpsSelector<T,
typename std::enable_if<
QTypeInfo<T>::isComplex && QTypeInfo<T>::isRelocatable
>::type>
{
typedef QMovableArrayOps<T> Type;
};
template <class T>
struct QCommonArrayOps : QArrayOpsSelector<T>::Type
{
using Base = typename QArrayOpsSelector<T>::Type;
using Data = QTypedArrayData<T>;
using DataPointer = QArrayDataPointer<T>;
using parameter_type = typename Base::parameter_type;
protected:
using Self = QCommonArrayOps<T>;
public:
using Base::Base;
DataPointer *that()
{ return Base::that(); }
const DataPointer *that() const
{ return Base::that(); }
// using Base::truncate;
// using Base::destroyAll;
template<typename It>
void appendIteratorRange(It b, It e, QtPrivate::IfIsForwardIterator<It> = true)
{
Q_ASSERT(that()->isMutable() || b == e);
Q_ASSERT(!that()->isShared() || b == e);
const qsizetype distance = std::distance(b, e);
Q_ASSERT(distance >= 0 && distance <= that()->allocatedCapacity() - that()->size);
Q_UNUSED(distance);
#if __cplusplus >= 202002L && defined(__cpp_concepts) && defined(__cpp_lib_concepts)
constexpr bool canUseCopyAppend =
std::contiguous_iterator<It> &&
std::is_same_v<
std::remove_cv_t<typename std::iterator_traits<It>::value_type>,
T
>;
if constexpr (canUseCopyAppend) {
Base::copyAppend(std::to_address(b), std::to_address(e));
} else
#endif
{
T *iter = that()->end();
for (; b != e; ++iter, ++b) {
new (iter) T(*b);
++that()->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, *that()))
that()->detachAndGrow(QArrayData::GrowsAtEnd, n, &b, &old);
else
that()->detachAndGrow(QArrayData::GrowsAtEnd, n, nullptr, nullptr);
Q_ASSERT(that()->freeSpaceAtEnd() >= n);
// b might be updated so use [b, n)
Base::copyAppend(b, b + n);
}
void appendUninitialized(qsizetype newSize)
{
Q_ASSERT(that()->isMutable());
Q_ASSERT(!that()->isShared());
Q_ASSERT(newSize > that()->size);
Q_ASSERT(newSize - that()->size <= that()->freeSpaceAtEnd());
T *const b = that()->begin() + that()->size;
T *const e = that()->begin() + newSize;
if constexpr (std::is_constructible_v<T, Qt::Initialization>)
std::uninitialized_fill(b, e, Qt::Uninitialized);
else
std::uninitialized_default_construct(b, e);
that()->size = newSize;
}
using Base::assign;
template <typename InputIterator, typename Projection = q20::identity>
void assign(InputIterator first, InputIterator last, Projection proj = {})
{
// This function only provides the basic exception guarantee.
using Category = typename std::iterator_traits<InputIterator>::iterator_category;
constexpr bool IsFwdIt = std::is_convertible_v<Category, std::forward_iterator_tag>;
const qsizetype n = IsFwdIt ? std::distance(first, last) : 0;
bool undoPrependOptimization = true;
bool needCapacity = n > that()->constAllocatedCapacity();
if (needCapacity || that()->needsDetach()) {
qsizetype newCapacity = that()->detachCapacity(n);
bool wasLastRef = !that()->deref();
if (wasLastRef && needCapacity) {
// free memory we can't reuse
Base::destroyAll();
Data::deallocate(that()->d);
}
if (!needCapacity && wasLastRef) {
// we were the last reference and can reuse the storage
that()->d->ref_.storeRelaxed(1);
} else {
// we must allocate new memory
auto [hdr, p] = Data::allocate(newCapacity);
that()->d = hdr;
that()->ptr = p;
that()->size = 0;
undoPrependOptimization = false;
}
}
if constexpr (!std::is_nothrow_constructible_v<T, decltype(std::invoke(proj, *first))>
|| !std::is_nothrow_invocable_v<Projection, decltype(*first)>)
{
// If construction can throw, and we have freeSpaceAtBegin(),
// it's easiest to just clear the container and start fresh.
// The alternative would be to keep track of two active, disjoint ranges.
if (undoPrependOptimization) {
Base::truncate(0);
that()->setBegin(Data::dataStart(that()->d, alignof(typename Data::AlignmentDummy)));
undoPrependOptimization = false;
}
}
const auto dend = that()->end();
T *dst = that()->begin();
T *capacityBegin = dst;
if (undoPrependOptimization) {
capacityBegin = Data::dataStart(that()->d, alignof(typename Data::AlignmentDummy));
that()->setBegin(capacityBegin); // undo prepend optimization
}
assign_impl(first, last, capacityBegin, dst, dend, proj, Category{});
}
template <typename InputIterator, typename Projection>
void assign_impl(InputIterator first, InputIterator last, T *capacityBegin, T *dst, T *dend,
Projection proj, std::input_iterator_tag)
{
if (qsizetype offset = dst - capacityBegin) {
T *prependBufferEnd = dst;
dst = capacityBegin;
// By construction, the following loop is nothrow!
// (otherwise, we can't reach here)
// Assumes InputIterator operations don't throw.
// (but we can't statically assert that, as these operations
// have preconditons, so typically aren't noexcept)
while (true) {
if (dst == prependBufferEnd) { // ran out of prepend buffer space
that()->size += offset;
// we now have a contiguous buffer, continue with the main loop:
break;
}
if (first == last) { // ran out of elements to assign
std::destroy(prependBufferEnd, dend);
that()->size = dst - that()->begin();
return;
}
// construct element in prepend buffer
q20::construct_at(dst, std::invoke(proj, *first));
++dst;
++first;
}
}
while (true) {
if (first == last) { // ran out of elements to assign
std::destroy(dst, dend);
break;
}
if (dst == dend) { // ran out of existing elements to overwrite
do {
Base::emplace(that()->size, std::invoke(proj, *first));
} while (++first != last);
return; // size() is already correct (and dst invalidated)!
}
*dst = std::invoke(proj, *first); // overwrite existing element
++dst;
++first;
}
that()->size = dst - that()->begin();
}
template <typename InputIterator, typename Projection>
void assign_impl(InputIterator first, InputIterator last, T *capacityBegin, T *dst, T *dend,
Projection proj, std::forward_iterator_tag)
{
constexpr bool IsIdentity = std::is_same_v<Projection, q20::identity>;
const qsizetype n = std::distance(first, last);
if constexpr (IsIdentity && !QTypeInfo<T>::isComplex) {
// For non-complex types, we prefer a single std::copy() -> memcpy()
// call. We can do that because either the default constructor is
// trivial (so the lifetime has started) or the copy constructor is
// (and won't care what the stored value is).
std::copy(first, last, capacityBegin);
} else {
// There are two possibilities:
// 1) fewer elements than the current allocated space
// | prepend buffer | array | destroy |
// 2) more elements than the current allocated space
// | prepend buffer | array | construct |
//
// Both the prepend buffer and the current array may be empty.
// construct elements in the prepend buffer
while (first != last && capacityBegin != dst) {
q20::construct_at(capacityBegin, std::invoke(proj, *first));
++first;
++capacityBegin;
}
// overwrite elements in the existing array
while (first != last && dst != dend) {
*dst = std::invoke(proj, *first); // overwrite existing element
++first;
++dst;
}
// construct new elements in the append buffer
while (first != last) {
q20::construct_at(dst, std::invoke(proj, *first));
++first;
++dst;
}
// or destroy elements from the existing array
if (dst < dend)
std::destroy(dst, dend);
}
that()->size = n;
}
};
} // namespace QtPrivate
template <class T>
struct QArrayDataOps
: QtPrivate::QCommonArrayOps<T>
{
private:
using Base = QtPrivate::QCommonArrayOps<T>;
public:
using Base::Base;
QArrayDataOps *operator->() noexcept { return this; }
const QArrayDataOps *operator->() const noexcept { return this; }
};
QT_END_NAMESPACE
#endif // include guard