1/****************************************************************************
2**
3** Copyright (C) 2020 The Qt Company Ltd.
4** Contact: https://www.qt.io/licensing/
5**
6** This file is part of the QtCore module of the Qt Toolkit.
7**
8** $QT_BEGIN_LICENSE:LGPL$
9** Commercial License Usage
10** Licensees holding valid commercial Qt licenses may use this file in
11** accordance with the commercial license agreement provided with the
12** Software or, alternatively, in accordance with the terms contained in
13** a written agreement between you and The Qt Company. For licensing terms
14** and conditions see https://www.qt.io/terms-conditions. For further
15** information use the contact form at https://www.qt.io/contact-us.
16**
17** GNU Lesser General Public License Usage
18** Alternatively, this file may be used under the terms of the GNU Lesser
19** General Public License version 3 as published by the Free Software
20** Foundation and appearing in the file LICENSE.LGPL3 included in the
21** packaging of this file. Please review the following information to
22** ensure the GNU Lesser General Public License version 3 requirements
23** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24**
25** GNU General Public License Usage
26** Alternatively, this file may be used under the terms of the GNU
27** General Public License version 2.0 or (at your option) the GNU General
28** Public license version 3 or any later version approved by the KDE Free
29** Qt Foundation. The licenses are as published by the Free Software
30** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31** included in the packaging of this file. Please review the following
32** information to ensure the GNU General Public License requirements will
33** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34** https://www.gnu.org/licenses/gpl-3.0.html.
35**
36** $QT_END_LICENSE$
37**
38****************************************************************************/
39
40#ifndef QARRAYDATAPOINTER_H
41#define QARRAYDATAPOINTER_H
42
43#include <QtCore/qarraydataops.h>
44#include <QtCore/qcontainertools_impl.h>
45
46QT_BEGIN_NAMESPACE
47
48template <class T>
49struct QArrayDataPointer
50{
51private:
52 typedef QTypedArrayData<T> Data;
53 typedef QArrayDataOps<T> DataOps;
54
55public:
56 enum {
57 pass_parameter_by_value =
58 std::is_arithmetic<T>::value || std::is_pointer<T>::value || std::is_enum<T>::value
59 };
60
61 typedef typename std::conditional<pass_parameter_by_value, T, const T &>::type parameter_type;
62
63 constexpr QArrayDataPointer() noexcept
64 : d(nullptr), ptr(nullptr), size(0)
65 {
66 }
67
68 QArrayDataPointer(const QArrayDataPointer &other) noexcept
69 : d(other.d), ptr(other.ptr), size(other.size)
70 {
71 ref();
72 }
73
74 constexpr QArrayDataPointer(Data *header, T *adata, qsizetype n = 0) noexcept
75 : d(header), ptr(adata), size(n)
76 {
77 }
78
79 explicit QArrayDataPointer(QPair<QTypedArrayData<T> *, T *> adata, qsizetype n = 0) noexcept
80 : d(adata.first), ptr(adata.second), size(n)
81 {
82 }
83
84 static QArrayDataPointer fromRawData(const T *rawData, qsizetype length) noexcept
85 {
86 Q_ASSERT(rawData || !length);
87 return { nullptr, const_cast<T *>(rawData), length };
88 }
89
90 QArrayDataPointer &operator=(const QArrayDataPointer &other) noexcept
91 {
92 QArrayDataPointer tmp(other);
93 this->swap(tmp);
94 return *this;
95 }
96
97 QArrayDataPointer(QArrayDataPointer &&other) noexcept
98 : d(other.d), ptr(other.ptr), size(other.size)
99 {
100 other.d = nullptr;
101 other.ptr = nullptr;
102 other.size = 0;
103 }
104
105 QT_MOVE_ASSIGNMENT_OPERATOR_IMPL_VIA_MOVE_AND_SWAP(QArrayDataPointer)
106
107 DataOps &operator*() noexcept
108 {
109 return *static_cast<DataOps *>(this);
110 }
111
112 DataOps *operator->() noexcept
113 {
114 return static_cast<DataOps *>(this);
115 }
116
117 const DataOps &operator*() const noexcept
118 {
119 return *static_cast<const DataOps *>(this);
120 }
121
122 const DataOps *operator->() const noexcept
123 {
124 return static_cast<const DataOps *>(this);
125 }
126
127 ~QArrayDataPointer()
128 {
129 if (!deref()) {
130 (*this)->destroyAll();
131 Data::deallocate(d);
132 }
133 }
134
135 bool isNull() const noexcept
136 {
137 return !ptr;
138 }
139
140 T *data() noexcept { return ptr; }
141 const T *data() const noexcept { return ptr; }
142
143 T *begin() noexcept { return data(); }
144 T *end() noexcept { return data() + size; }
145 const T *begin() const noexcept { return data(); }
146 const T *end() const noexcept { return data() + size; }
147 const T *constBegin() const noexcept { return data(); }
148 const T *constEnd() const noexcept { return data() + size; }
149
150 void swap(QArrayDataPointer &other) noexcept
151 {
152 qSwap(d, other.d);
153 qSwap(ptr, other.ptr);
154 qSwap(size, other.size);
155 }
156
157 void clear() noexcept(std::is_nothrow_destructible<T>::value)
158 {
159 QArrayDataPointer tmp;
160 swap(tmp);
161 }
162
163 void detach(QArrayDataPointer *old = nullptr)
164 {
165 if (needsDetach())
166 reallocateAndGrow(QArrayData::GrowsAtEnd, 0, old);
167 }
168
169 // pass in a pointer to a default constructed QADP, to keep it alive beyond the detach() call
170 void detachAndGrow(QArrayData::GrowthPosition where, qsizetype n, QArrayDataPointer *old = nullptr)
171 {
172 if (!needsDetach()) {
173 if (!n ||
174 (where == QArrayData::GrowsAtBeginning && freeSpaceAtBegin() >= n) ||
175 (where == QArrayData::GrowsAtEnd && freeSpaceAtEnd() >= n))
176 return;
177 }
178 reallocateAndGrow(where, n, old);
179 }
180
181 Q_NEVER_INLINE void reallocateAndGrow(QArrayData::GrowthPosition where, qsizetype n, QArrayDataPointer *old = nullptr)
182 {
183 if constexpr (QTypeInfo<T>::isRelocatable && alignof(T) <= alignof(std::max_align_t)) {
184 if (where == QArrayData::GrowsAtEnd && !old && !needsDetach() && n > 0) {
185 (*this)->reallocate(constAllocatedCapacity() - freeSpaceAtEnd() + n, QArrayData::Grow); // fast path
186 return;
187 }
188 }
189
190 QArrayDataPointer dp(allocateGrow(*this, n, where));
191 if (where == QArrayData::GrowsAtBeginning) {
192 Q_ASSERT(dp.ptr);
193 dp.ptr += n;
194 Q_ASSERT(dp.freeSpaceAtBegin() >= n);
195 } else {
196 Q_ASSERT(dp.freeSpaceAtEnd() >= n);
197 }
198 if (size) {
199 qsizetype toCopy = size;
200 if (n < 0)
201 toCopy += n;
202 if (needsDetach() || old)
203 dp->copyAppend(begin(), begin() + toCopy);
204 else
205 dp->moveAppend(begin(), begin() + toCopy);
206 Q_ASSERT(dp.size == toCopy);
207 }
208
209 swap(dp);
210 if (old)
211 old->swap(dp);
212 }
213
214 // forwards from QArrayData
215 qsizetype allocatedCapacity() noexcept { return d ? d->allocatedCapacity() : 0; }
216 qsizetype constAllocatedCapacity() const noexcept { return d ? d->constAllocatedCapacity() : 0; }
217 void ref() noexcept { if (d) d->ref(); }
218 bool deref() noexcept { return !d || d->deref(); }
219 bool isMutable() const noexcept { return d; }
220 bool isShared() const noexcept { return !d || d->isShared(); }
221 bool isSharedWith(const QArrayDataPointer &other) const noexcept { return d && d == other.d; }
222 bool needsDetach() const noexcept { return !d || d->needsDetach(); }
223 qsizetype detachCapacity(qsizetype newSize) const noexcept { return d ? d->detachCapacity(newSize) : newSize; }
224 const typename Data::ArrayOptions flags() const noexcept { return d ? typename Data::ArrayOption(d->flags) : Data::ArrayOptionDefault; }
225 void setFlag(typename Data::ArrayOptions f) noexcept { Q_ASSERT(d); d->flags |= f; }
226 void clearFlag(typename Data::ArrayOptions f) noexcept { if (d) d->flags &= ~f; }
227
228 Data *d_ptr() noexcept { return d; }
229 void setBegin(T *begin) noexcept { ptr = begin; }
230
231 qsizetype freeSpaceAtBegin() const noexcept
232 {
233 if (d == nullptr)
234 return 0;
235 return this->ptr - Data::dataStart(d, alignof(typename Data::AlignmentDummy));
236 }
237
238 qsizetype freeSpaceAtEnd() const noexcept
239 {
240 if (d == nullptr)
241 return 0;
242 return d->constAllocatedCapacity() - freeSpaceAtBegin() - this->size;
243 }
244
245 // allocate and grow. Ensure that at the minimum requiredSpace is available at the requested end
246 static QArrayDataPointer allocateGrow(const QArrayDataPointer &from, qsizetype n, QArrayData::GrowthPosition position)
247 {
248 // calculate new capacity. We keep the free capacity at the side that does not have to grow
249 // to avoid quadratic behavior with mixed append/prepend cases
250
251 // use qMax below, because constAllocatedCapacity() can be 0 when using fromRawData()
252 qsizetype minimalCapacity = qMax(from.size, from.constAllocatedCapacity()) + n;
253 // subtract the free space at the side we want to allocate. This ensures that the total size requested is
254 // the existing allocation at the other side + size + n.
255 minimalCapacity -= (position == QArrayData::GrowsAtEnd) ? from.freeSpaceAtEnd() : from.freeSpaceAtBegin();
256 qsizetype capacity = from.detachCapacity(minimalCapacity);
257 const bool grows = capacity > from.constAllocatedCapacity();
258 auto [header, dataPtr] = Data::allocate(capacity, grows ? QArrayData::Grow : QArrayData::KeepSize);
259 const bool valid = header != nullptr && dataPtr != nullptr;
260 if (!valid)
261 return QArrayDataPointer(header, dataPtr);
262
263 // Idea: * when growing backwards, adjust pointer to prepare free space at the beginning
264 // * when growing forward, adjust by the previous data pointer offset
265
266 // TODO: what's with CapacityReserved?
267 dataPtr += (position == QArrayData::GrowsAtBeginning) ? qMax(0, (header->alloc - from.size - n) / 2)
268 : from.freeSpaceAtBegin();
269 header->flags = from.flags();
270 return QArrayDataPointer(header, dataPtr);
271 }
272
273 friend bool operator==(const QArrayDataPointer &lhs, const QArrayDataPointer &rhs) noexcept
274 {
275 return lhs.data() == rhs.data() && lhs.size == rhs.size;
276 }
277
278 friend bool operator!=(const QArrayDataPointer &lhs, const QArrayDataPointer &rhs) noexcept
279 {
280 return lhs.data() != rhs.data() || lhs.size != rhs.size;
281 }
282
283 Data *d;
284 T *ptr;
285 qsizetype size;
286};
287
288template <class T>
289inline void qSwap(QArrayDataPointer<T> &p1, QArrayDataPointer<T> &p2) noexcept
290{
291 p1.swap(p2);
292}
293
294////////////////////////////////////////////////////////////////////////////////
295// Q_ARRAY_LITERAL
296
297// The idea here is to place a (read-only) copy of header and array data in an
298// mmappable portion of the executable (typically, .rodata section).
299
300// Hide array inside a lambda
301#define Q_ARRAY_LITERAL(Type, ...) \
302 ([]() -> QArrayDataPointer<Type> { \
303 static Type const data[] = { __VA_ARGS__ }; \
304 return QArrayDataPointer<Type>::fromRawData(const_cast<Type *>(data), std::size(data)); \
305 }())
306/**/
307
308QT_END_NAMESPACE
309
310#endif // include guard
311