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

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