1// Copyright (C) 2020 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
3
4#ifndef QARRAYDATAPOINTER_H
5#define QARRAYDATAPOINTER_H
6
7#include <QtCore/qarraydataops.h>
8#include <QtCore/qcontainertools_impl.h>
9
10#include <QtCore/q20functional.h>
11#include <QtCore/q20memory.h>
12
13QT_BEGIN_NAMESPACE
14
15template <class T>
16struct QArrayDataPointer
17{
18private:
19 typedef QTypedArrayData<T> Data;
20 typedef QArrayDataOps<T> DataOps;
21
22public:
23 enum {
24 pass_parameter_by_value =
25 std::is_arithmetic<T>::value || std::is_pointer<T>::value || std::is_enum<T>::value
26 };
27
28 typedef typename std::conditional<pass_parameter_by_value, T, const T &>::type parameter_type;
29
30 Q_NODISCARD_CTOR
31 constexpr QArrayDataPointer() noexcept
32 : d(nullptr), ptr(nullptr), size(0)
33 {
34 }
35
36 Q_NODISCARD_CTOR
37 QArrayDataPointer(const QArrayDataPointer &other) noexcept
38 : d(other.d), ptr(other.ptr), size(other.size)
39 {
40 ref();
41 }
42
43 Q_NODISCARD_CTOR
44 constexpr QArrayDataPointer(Data *header, T *adata, qsizetype n = 0) noexcept
45 : d(header), ptr(adata), size(n)
46 {
47 }
48
49 Q_NODISCARD_CTOR
50 explicit QArrayDataPointer(QPair<QTypedArrayData<T> *, T *> adata, qsizetype n = 0) noexcept
51 : d(adata.first), ptr(adata.second), size(n)
52 {
53 }
54
55 Q_NODISCARD_CTOR
56 static QArrayDataPointer fromRawData(const T *rawData, qsizetype length) noexcept
57 {
58 Q_ASSERT(rawData || !length);
59 return { nullptr, const_cast<T *>(rawData), length };
60 }
61
62 QArrayDataPointer &operator=(const QArrayDataPointer &other) noexcept
63 {
64 QArrayDataPointer tmp(other);
65 this->swap(tmp);
66 return *this;
67 }
68
69 Q_NODISCARD_CTOR
70 QArrayDataPointer(QArrayDataPointer &&other) noexcept
71 : d(other.d), ptr(other.ptr), size(other.size)
72 {
73 other.d = nullptr;
74 other.ptr = nullptr;
75 other.size = 0;
76 }
77
78 QT_MOVE_ASSIGNMENT_OPERATOR_IMPL_VIA_MOVE_AND_SWAP(QArrayDataPointer)
79
80 DataOps &operator*() noexcept
81 {
82 return *static_cast<DataOps *>(this);
83 }
84
85 DataOps *operator->() noexcept
86 {
87 return static_cast<DataOps *>(this);
88 }
89
90 const DataOps &operator*() const noexcept
91 {
92 return *static_cast<const DataOps *>(this);
93 }
94
95 const DataOps *operator->() const noexcept
96 {
97 return static_cast<const DataOps *>(this);
98 }
99
100 ~QArrayDataPointer()
101 {
102 if (!deref()) {
103 (*this)->destroyAll();
104 free(d);
105 }
106 }
107
108 bool isNull() const noexcept
109 {
110 return !ptr;
111 }
112
113 T *data() noexcept { return ptr; }
114 const T *data() const noexcept { return ptr; }
115
116 T *begin() noexcept { return data(); }
117 T *end() noexcept { return data() + size; }
118 const T *begin() const noexcept { return data(); }
119 const T *end() const noexcept { return data() + size; }
120 const T *constBegin() const noexcept { return data(); }
121 const T *constEnd() const noexcept { return data() + size; }
122
123 void swap(QArrayDataPointer &other) noexcept
124 {
125 qt_ptr_swap(d, other.d);
126 qt_ptr_swap(ptr, other.ptr);
127 std::swap(size, other.size);
128 }
129
130 void clear() noexcept(std::is_nothrow_destructible<T>::value)
131 {
132 QArrayDataPointer tmp;
133 swap(other&: tmp);
134 }
135
136 void detach(QArrayDataPointer *old = nullptr)
137 {
138 if (needsDetach())
139 reallocateAndGrow(where: QArrayData::GrowsAtEnd, n: 0, old);
140 }
141
142 /*! \internal
143
144 Reinterprets the data of this QArrayDataPointer to type X. It's the
145 caller's responsibility to ensure that the data contents are valid and
146 properly aligned, particularly if T and X are not trivial types (i.e,
147 don't do that). The current size is kept and the allocated capacity is
148 updated to account for the difference in the element type's size.
149
150 This is used in QString::fromLatin1 to perform in-place conversion of
151 QString to QByteArray.
152 */
153 template <typename X> QArrayDataPointer<X> reinterpreted() &&
154 {
155 if (sizeof(T) != sizeof(X)) {
156 Q_ASSERT(!d->isShared());
157 d->alloc = d->alloc * sizeof(T) / sizeof(X);
158 }
159 auto od = reinterpret_cast<QTypedArrayData<X> *>(std::exchange(d, nullptr));
160 auto optr = reinterpret_cast<X *>(std::exchange(ptr, nullptr));
161 return { od, optr, std::exchange(obj&: size, new_val: 0) };
162 }
163
164 /*! \internal
165
166 Detaches this (optionally) and grows to accommodate the free space for
167 \a n elements at the required side. The side is determined from \a pos.
168
169 \a data pointer can be provided when the caller knows that \a data
170 points into range [this->begin(), this->end()). In case it is, *data
171 would be updated so that it continues to point to the element it was
172 pointing to before the data move. if \a data does not point into range,
173 one can/should pass \c nullptr.
174
175 Similarly to \a data, \a old, pointer to a default-constructed QADP, can
176 be provided when the caller expects to e.g. copy the data from this to
177 itself:
178 \code
179 QList<T> list(5);
180 qsizetype pos = getArbitraryPos();
181 list.insert(pos, list.begin(), list.end());
182 \endcode
183
184 The default rule would be: \a data and \a old must either both be valid
185 pointers, or both equal to \c nullptr.
186 */
187 void detachAndGrow(QArrayData::GrowthPosition where, qsizetype n, const T **data,
188 QArrayDataPointer *old)
189 {
190 const bool detach = needsDetach();
191 bool readjusted = false;
192 if (!detach) {
193 if (!n || (where == QArrayData::GrowsAtBeginning && freeSpaceAtBegin() >= n)
194 || (where == QArrayData::GrowsAtEnd && freeSpaceAtEnd() >= n))
195 return;
196 readjusted = tryReadjustFreeSpace(pos: where, n, data);
197 Q_ASSERT(!readjusted
198 || (where == QArrayData::GrowsAtBeginning && freeSpaceAtBegin() >= n)
199 || (where == QArrayData::GrowsAtEnd && freeSpaceAtEnd() >= n));
200 }
201
202 if (!readjusted)
203 reallocateAndGrow(where, n, old);
204 }
205
206 /*! \internal
207
208 Reallocates to accommodate the free space for \a n elements at the
209 required side. The side is determined from \a pos. Might also shrink
210 when n < 0.
211 */
212 Q_NEVER_INLINE void reallocateAndGrow(QArrayData::GrowthPosition where, qsizetype n,
213 QArrayDataPointer *old = nullptr)
214 {
215 if constexpr (QTypeInfo<T>::isRelocatable && alignof(T) <= alignof(std::max_align_t)) {
216 if (where == QArrayData::GrowsAtEnd && !old && !needsDetach() && n > 0) {
217 (*this)->reallocate(constAllocatedCapacity() - freeSpaceAtEnd() + n, QArrayData::Grow); // fast path
218 return;
219 }
220 }
221
222 QArrayDataPointer dp(allocateGrow(from: *this, n, position: where));
223 if (n > 0)
224 Q_CHECK_PTR(dp.data());
225 if (where == QArrayData::GrowsAtBeginning) {
226 Q_ASSERT(dp.freeSpaceAtBegin() >= n);
227 } else {
228 Q_ASSERT(dp.freeSpaceAtEnd() >= n);
229 }
230 if (size) {
231 qsizetype toCopy = size;
232 if (n < 0)
233 toCopy += n;
234 if (needsDetach() || old)
235 dp->copyAppend(begin(), begin() + toCopy);
236 else
237 dp->moveAppend(begin(), begin() + toCopy);
238 Q_ASSERT(dp.size == toCopy);
239 }
240
241 swap(other&: dp);
242 if (old)
243 old->swap(dp);
244 }
245
246 /*! \internal
247
248 Attempts to relocate [begin(), end()) to accommodate the free space for
249 \a n elements at the required side. The side is determined from \a pos.
250
251 Returns \c true if the internal data is moved. Returns \c false when
252 there is no point in moving the data or the move is impossible. If \c
253 false is returned, it is the responsibility of the caller to figure out
254 how to accommodate the free space for \a n elements at \a pos.
255
256 This function expects that certain preconditions are met, e.g. the
257 detach is not needed, n > 0 and so on. This is intentional to reduce the
258 number of if-statements when the caller knows that preconditions would
259 be satisfied.
260
261 \sa reallocateAndGrow
262 */
263 bool tryReadjustFreeSpace(QArrayData::GrowthPosition pos, qsizetype n, const T **data = nullptr)
264 {
265 Q_ASSERT(!this->needsDetach());
266 Q_ASSERT(n > 0);
267 Q_ASSERT((pos == QArrayData::GrowsAtEnd && this->freeSpaceAtEnd() < n)
268 || (pos == QArrayData::GrowsAtBeginning && this->freeSpaceAtBegin() < n));
269
270 const qsizetype capacity = this->constAllocatedCapacity();
271 const qsizetype freeAtBegin = this->freeSpaceAtBegin();
272 const qsizetype freeAtEnd = this->freeSpaceAtEnd();
273
274 qsizetype dataStartOffset = 0;
275 // algorithm:
276 // a. GrowsAtEnd: relocate if space at begin AND size < (capacity * 2) / 3
277 // [all goes to free space at end]:
278 // new free space at begin = 0
279 //
280 // b. GrowsAtBeginning: relocate if space at end AND size < capacity / 3
281 // [balance the free space]:
282 // new free space at begin = n + (total free space - n) / 2
283 if (pos == QArrayData::GrowsAtEnd && freeAtBegin >= n
284 && ((3 * this->size) < (2 * capacity))) {
285 // dataStartOffset = 0; - done in declaration
286 } else if (pos == QArrayData::GrowsAtBeginning && freeAtEnd >= n
287 && ((3 * this->size) < capacity)) {
288 // total free space == capacity - size
289 dataStartOffset = n + qMax(0, (capacity - this->size - n) / 2);
290 } else {
291 // nothing to do otherwise
292 return false;
293 }
294
295 relocate(offset: dataStartOffset - freeAtBegin, data);
296
297 Q_ASSERT((pos == QArrayData::GrowsAtEnd && this->freeSpaceAtEnd() >= n)
298 || (pos == QArrayData::GrowsAtBeginning && this->freeSpaceAtBegin() >= n));
299 return true;
300 }
301
302 /*! \internal
303
304 Relocates [begin(), end()) by \a offset and updates \a data if it is not
305 \c nullptr and points into [begin(), end()).
306 */
307 void relocate(qsizetype offset, const T **data = nullptr)
308 {
309 T *res = this->ptr + offset;
310 QtPrivate::q_relocate_overlap_n(this->ptr, this->size, res);
311 // first update data pointer, then this->ptr
312 if (data && QtPrivate::q_points_into_range(*data, *this))
313 *data += offset;
314 this->ptr = res;
315 }
316
317 template <typename InputIterator, typename Projection = q20::identity>
318 void assign(InputIterator first, InputIterator last, Projection proj = {})
319 {
320 // This function only provides the basic exception guarantee.
321 constexpr bool IsFwdIt = std::is_convertible_v<
322 typename std::iterator_traits<InputIterator>::iterator_category,
323 std::forward_iterator_tag>;
324 constexpr bool IsIdentity = std::is_same_v<Projection, q20::identity>;
325
326 if constexpr (IsFwdIt) {
327 const qsizetype n = std::distance(first, last);
328 if (needsDetach() || n > constAllocatedCapacity()) {
329 QArrayDataPointer allocated(Data::allocate(detachCapacity(newSize: n)));
330 swap(other&: allocated);
331 }
332 } else if (needsDetach()) {
333 QArrayDataPointer allocated(Data::allocate(allocatedCapacity()));
334 swap(other&: allocated);
335 // We don't want to copy data that we know we'll overwrite
336 }
337
338 auto offset = freeSpaceAtBegin();
339 const auto capacityBegin = begin() - offset;
340 const auto prependBufferEnd = begin();
341
342 if constexpr (!std::is_nothrow_constructible_v<T, decltype(std::invoke(proj, *first))>) {
343 // If construction can throw, and we have freeSpaceAtBegin(),
344 // it's easiest to just clear the container and start fresh.
345 // The alternative would be to keep track of two active, disjoint ranges.
346 if (offset) {
347 (*this)->truncate(0);
348 setBegin(capacityBegin);
349 offset = 0;
350 }
351 }
352
353 auto dst = capacityBegin;
354 const auto dend = end();
355 if (offset) { // avoids dead stores
356 setBegin(capacityBegin); // undo prepend optimization
357
358 // By construction, the following loop is nothrow!
359 // (otherwise, we can't reach here)
360 // Assumes InputIterator operations don't throw.
361 // (but we can't statically assert that, as these operations
362 // have preconditons, so typically aren't noexcept)
363 while (true) {
364 if (dst == prependBufferEnd) { // ran out of prepend buffer space
365 size += offset;
366 // we now have a contiguous buffer, continue with the main loop:
367 break;
368 }
369 if (first == last) { // ran out of elements to assign
370 std::destroy(prependBufferEnd, dend);
371 size = dst - begin();
372 return;
373 }
374 // construct element in prepend buffer
375 q20::construct_at(dst, std::invoke(proj, *first));
376 ++dst;
377 ++first;
378 }
379 }
380
381 while (true) {
382 if (first == last) { // ran out of elements to assign
383 std::destroy(dst, dend);
384 break;
385 }
386 if (dst == dend) { // ran out of existing elements to overwrite
387 if constexpr (IsFwdIt && IsIdentity) {
388 dst = std::uninitialized_copy(first, last, dst);
389 break;
390 } else if constexpr (IsFwdIt && !IsIdentity
391 && std::is_nothrow_constructible_v<T, decltype(std::invoke(proj, *first))>) {
392 for (; first != last; ++dst, ++first) // uninitialized_copy with projection
393 q20::construct_at(dst, std::invoke(proj, *first));
394 break;
395 } else {
396 do {
397 (*this)->emplace(size, std::invoke(proj, *first));
398 } while (++first != last);
399 return; // size() is already correct (and dst invalidated)!
400 }
401 }
402 *dst = std::invoke(proj, *first); // overwrite existing element
403 ++dst;
404 ++first;
405 }
406 size = dst - begin();
407 }
408
409 // forwards from QArrayData
410 qsizetype allocatedCapacity() noexcept { return d ? d->allocatedCapacity() : 0; }
411 qsizetype constAllocatedCapacity() const noexcept { return d ? d->constAllocatedCapacity() : 0; }
412 void ref() noexcept { if (d) d->ref(); }
413 bool deref() noexcept { return !d || d->deref(); }
414 bool isMutable() const noexcept { return d; }
415 bool isShared() const noexcept { return !d || d->isShared(); }
416 bool isSharedWith(const QArrayDataPointer &other) const noexcept { return d && d == other.d; }
417 bool needsDetach() const noexcept { return !d || d->needsDetach(); }
418 qsizetype detachCapacity(qsizetype newSize) const noexcept { return d ? d->detachCapacity(newSize) : newSize; }
419 const typename Data::ArrayOptions flags() const noexcept { return d ? d->flags : Data::ArrayOptionDefault; }
420 void setFlag(typename Data::ArrayOptions f) noexcept { Q_ASSERT(d); d->flags |= f; }
421 void clearFlag(typename Data::ArrayOptions f) noexcept { if (d) d->flags &= ~f; }
422
423 Data *d_ptr() noexcept { return d; }
424 void setBegin(T *begin) noexcept { ptr = begin; }
425
426 qsizetype freeSpaceAtBegin() const noexcept
427 {
428 if (d == nullptr)
429 return 0;
430 return this->ptr - Data::dataStart(d, alignof(typename Data::AlignmentDummy));
431 }
432
433 qsizetype freeSpaceAtEnd() const noexcept
434 {
435 if (d == nullptr)
436 return 0;
437 return d->constAllocatedCapacity() - freeSpaceAtBegin() - this->size;
438 }
439
440 // allocate and grow. Ensure that at the minimum requiredSpace is available at the requested end
441 static QArrayDataPointer allocateGrow(const QArrayDataPointer &from, qsizetype n, QArrayData::GrowthPosition position)
442 {
443 // calculate new capacity. We keep the free capacity at the side that does not have to grow
444 // to avoid quadratic behavior with mixed append/prepend cases
445
446 // use qMax below, because constAllocatedCapacity() can be 0 when using fromRawData()
447 qsizetype minimalCapacity = qMax(from.size, from.constAllocatedCapacity()) + n;
448 // subtract the free space at the side we want to allocate. This ensures that the total size requested is
449 // the existing allocation at the other side + size + n.
450 minimalCapacity -= (position == QArrayData::GrowsAtEnd) ? from.freeSpaceAtEnd() : from.freeSpaceAtBegin();
451 qsizetype capacity = from.detachCapacity(minimalCapacity);
452 const bool grows = capacity > from.constAllocatedCapacity();
453 auto [header, dataPtr] = Data::allocate(capacity, grows ? QArrayData::Grow : QArrayData::KeepSize);
454 const bool valid = header != nullptr && dataPtr != nullptr;
455 if (!valid)
456 return QArrayDataPointer(header, dataPtr);
457
458 // Idea: * when growing backwards, adjust pointer to prepare free space at the beginning
459 // * when growing forward, adjust by the previous data pointer offset
460 dataPtr += (position == QArrayData::GrowsAtBeginning)
461 ? n + qMax(0, (header->alloc - from.size - n) / 2)
462 : from.freeSpaceAtBegin();
463 header->flags = from.flags();
464 return QArrayDataPointer(header, dataPtr);
465 }
466
467 friend bool operator==(const QArrayDataPointer &lhs, const QArrayDataPointer &rhs) noexcept
468 {
469 return lhs.data() == rhs.data() && lhs.size == rhs.size;
470 }
471
472 friend bool operator!=(const QArrayDataPointer &lhs, const QArrayDataPointer &rhs) noexcept
473 {
474 return lhs.data() != rhs.data() || lhs.size != rhs.size;
475 }
476
477 Data *d;
478 T *ptr;
479 qsizetype size;
480};
481
482template <class T>
483inline void swap(QArrayDataPointer<T> &p1, QArrayDataPointer<T> &p2) noexcept
484{
485 p1.swap(p2);
486}
487
488////////////////////////////////////////////////////////////////////////////////
489// Q_ARRAY_LITERAL
490
491// The idea here is to place a (read-only) copy of header and array data in an
492// mmappable portion of the executable (typically, .rodata section).
493
494// Hide array inside a lambda
495#define Q_ARRAY_LITERAL(Type, ...) \
496 ([]() -> QArrayDataPointer<Type> { \
497 static Type const data[] = { __VA_ARGS__ }; \
498 return QArrayDataPointer<Type>::fromRawData(const_cast<Type *>(data), std::size(data)); \
499 }())
500/**/
501
502QT_END_NAMESPACE
503
504#endif // include guard
505

source code of qtbase/src/corelib/tools/qarraydatapointer.h