1/****************************************************************************
2**
3** Copyright (C) 2016 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 QARRAYDATA_H
41#define QARRAYDATA_H
42
43#include <QtCore/qrefcount.h>
44#include <string.h>
45
46QT_BEGIN_NAMESPACE
47
48struct Q_CORE_EXPORT QArrayData
49{
50 QtPrivate::RefCount ref;
51 int size;
52 uint alloc : 31;
53 uint capacityReserved : 1;
54
55 qptrdiff offset; // in bytes from beginning of header
56
57 void *data()
58 {
59 Q_ASSERT(size == 0
60 || offset < 0 || size_t(offset) >= sizeof(QArrayData));
61 return reinterpret_cast<char *>(this) + offset;
62 }
63
64 const void *data() const
65 {
66 Q_ASSERT(size == 0
67 || offset < 0 || size_t(offset) >= sizeof(QArrayData));
68 return reinterpret_cast<const char *>(this) + offset;
69 }
70
71 // This refers to array data mutability, not "header data" represented by
72 // data members in QArrayData. Shared data (array and header) must still
73 // follow COW principles.
74 bool isMutable() const
75 {
76 return alloc != 0;
77 }
78
79 enum AllocationOption {
80 CapacityReserved = 0x1,
81#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
82 Unsharable = 0x2,
83#endif
84 RawData = 0x4,
85 Grow = 0x8,
86
87 Default = 0
88 };
89
90 Q_DECLARE_FLAGS(AllocationOptions, AllocationOption)
91
92 size_t detachCapacity(size_t newSize) const
93 {
94 if (capacityReserved && newSize < alloc)
95 return alloc;
96 return newSize;
97 }
98
99 AllocationOptions detachFlags() const
100 {
101 AllocationOptions result;
102 if (capacityReserved)
103 result |= CapacityReserved;
104 return result;
105 }
106
107 AllocationOptions cloneFlags() const
108 {
109 AllocationOptions result;
110 if (capacityReserved)
111 result |= CapacityReserved;
112 return result;
113 }
114
115 Q_REQUIRED_RESULT static QArrayData *allocate(size_t objectSize, size_t alignment,
116 size_t capacity, AllocationOptions options = Default) Q_DECL_NOTHROW;
117 Q_REQUIRED_RESULT static QArrayData *reallocateUnaligned(QArrayData *data, size_t objectSize,
118 size_t newCapacity, AllocationOptions newOptions = Default) Q_DECL_NOTHROW;
119 static void deallocate(QArrayData *data, size_t objectSize,
120 size_t alignment) Q_DECL_NOTHROW;
121
122 static const QArrayData shared_null[2];
123 static QArrayData *sharedNull() Q_DECL_NOTHROW { return const_cast<QArrayData*>(shared_null); }
124};
125
126Q_DECLARE_OPERATORS_FOR_FLAGS(QArrayData::AllocationOptions)
127
128template <class T>
129struct QTypedArrayData
130 : QArrayData
131{
132#ifdef QT_STRICT_ITERATORS
133 class iterator {
134 public:
135 T *i;
136 typedef std::random_access_iterator_tag iterator_category;
137 typedef int difference_type;
138 typedef T value_type;
139 typedef T *pointer;
140 typedef T &reference;
141
142 inline iterator() : i(nullptr) {}
143 inline iterator(T *n) : i(n) {}
144 inline iterator(const iterator &o): i(o.i){} // #### Qt 6: remove, the implicit version is fine
145 inline T &operator*() const { return *i; }
146 inline T *operator->() const { return i; }
147 inline T &operator[](int j) const { return *(i + j); }
148 inline bool operator==(const iterator &o) const { return i == o.i; }
149 inline bool operator!=(const iterator &o) const { return i != o.i; }
150 inline bool operator<(const iterator& other) const { return i < other.i; }
151 inline bool operator<=(const iterator& other) const { return i <= other.i; }
152 inline bool operator>(const iterator& other) const { return i > other.i; }
153 inline bool operator>=(const iterator& other) const { return i >= other.i; }
154 inline iterator &operator++() { ++i; return *this; }
155 inline iterator operator++(int) { T *n = i; ++i; return n; }
156 inline iterator &operator--() { i--; return *this; }
157 inline iterator operator--(int) { T *n = i; i--; return n; }
158 inline iterator &operator+=(int j) { i+=j; return *this; }
159 inline iterator &operator-=(int j) { i-=j; return *this; }
160 inline iterator operator+(int j) const { return iterator(i+j); }
161 inline iterator operator-(int j) const { return iterator(i-j); }
162 friend inline iterator operator+(int j, iterator k) { return k + j; }
163 inline int operator-(iterator j) const { return i - j.i; }
164 inline operator T*() const { return i; }
165 };
166 friend class iterator;
167
168 class const_iterator {
169 public:
170 const T *i;
171 typedef std::random_access_iterator_tag iterator_category;
172 typedef int difference_type;
173 typedef T value_type;
174 typedef const T *pointer;
175 typedef const T &reference;
176
177 inline const_iterator() : i(nullptr) {}
178 inline const_iterator(const T *n) : i(n) {}
179 inline const_iterator(const const_iterator &o): i(o.i) {} // #### Qt 6: remove, the default version is fine
180 inline explicit const_iterator(const iterator &o): i(o.i) {}
181 inline const T &operator*() const { return *i; }
182 inline const T *operator->() const { return i; }
183 inline const T &operator[](int j) const { return *(i + j); }
184 inline bool operator==(const const_iterator &o) const { return i == o.i; }
185 inline bool operator!=(const const_iterator &o) const { return i != o.i; }
186 inline bool operator<(const const_iterator& other) const { return i < other.i; }
187 inline bool operator<=(const const_iterator& other) const { return i <= other.i; }
188 inline bool operator>(const const_iterator& other) const { return i > other.i; }
189 inline bool operator>=(const const_iterator& other) const { return i >= other.i; }
190 inline const_iterator &operator++() { ++i; return *this; }
191 inline const_iterator operator++(int) { const T *n = i; ++i; return n; }
192 inline const_iterator &operator--() { i--; return *this; }
193 inline const_iterator operator--(int) { const T *n = i; i--; return n; }
194 inline const_iterator &operator+=(int j) { i+=j; return *this; }
195 inline const_iterator &operator-=(int j) { i-=j; return *this; }
196 inline const_iterator operator+(int j) const { return const_iterator(i+j); }
197 inline const_iterator operator-(int j) const { return const_iterator(i-j); }
198 friend inline const_iterator operator+(int j, const_iterator k) { return k + j; }
199 inline int operator-(const_iterator j) const { return i - j.i; }
200 inline operator const T*() const { return i; }
201 };
202 friend class const_iterator;
203#else
204 typedef T* iterator;
205 typedef const T* const_iterator;
206#endif
207
208 T *data() { return static_cast<T *>(QArrayData::data()); }
209 const T *data() const { return static_cast<const T *>(QArrayData::data()); }
210
211 iterator begin(iterator = iterator()) { return data(); }
212 iterator end(iterator = iterator()) { return data() + size; }
213 const_iterator begin(const_iterator = const_iterator()) const { return data(); }
214 const_iterator end(const_iterator = const_iterator()) const { return data() + size; }
215 const_iterator constBegin(const_iterator = const_iterator()) const { return data(); }
216 const_iterator constEnd(const_iterator = const_iterator()) const { return data() + size; }
217
218 class AlignmentDummy { QArrayData header; T data; };
219
220 Q_REQUIRED_RESULT static QTypedArrayData *allocate(size_t capacity,
221 AllocationOptions options = Default)
222 {
223 Q_STATIC_ASSERT(sizeof(QTypedArrayData) == sizeof(QArrayData));
224 return static_cast<QTypedArrayData *>(QArrayData::allocate(sizeof(T),
225 Q_ALIGNOF(AlignmentDummy), capacity, options));
226 }
227
228 static QTypedArrayData *reallocateUnaligned(QTypedArrayData *data, size_t capacity,
229 AllocationOptions options = Default)
230 {
231 Q_STATIC_ASSERT(sizeof(QTypedArrayData) == sizeof(QArrayData));
232 return static_cast<QTypedArrayData *>(QArrayData::reallocateUnaligned(data, sizeof(T),
233 capacity, options));
234 }
235
236 static void deallocate(QArrayData *data)
237 {
238 Q_STATIC_ASSERT(sizeof(QTypedArrayData) == sizeof(QArrayData));
239 QArrayData::deallocate(data, sizeof(T), Q_ALIGNOF(AlignmentDummy));
240 }
241
242 static QTypedArrayData *fromRawData(const T *data, size_t n,
243 AllocationOptions options = Default)
244 {
245 Q_STATIC_ASSERT(sizeof(QTypedArrayData) == sizeof(QArrayData));
246 QTypedArrayData *result = allocate(0, options | RawData);
247 if (result) {
248 Q_ASSERT(!result->ref.isShared()); // No shared empty, please!
249
250 result->offset = reinterpret_cast<const char *>(data)
251 - reinterpret_cast<const char *>(result);
252 result->size = int(n);
253 }
254 return result;
255 }
256
257 static QTypedArrayData *sharedNull() Q_DECL_NOTHROW
258 {
259 Q_STATIC_ASSERT(sizeof(QTypedArrayData) == sizeof(QArrayData));
260 return static_cast<QTypedArrayData *>(QArrayData::sharedNull());
261 }
262
263 static QTypedArrayData *sharedEmpty()
264 {
265 Q_STATIC_ASSERT(sizeof(QTypedArrayData) == sizeof(QArrayData));
266 return allocate(/* capacity */ 0);
267 }
268
269#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
270 static QTypedArrayData *unsharableEmpty()
271 {
272 Q_STATIC_ASSERT(sizeof(QTypedArrayData) == sizeof(QArrayData));
273 return allocate(/* capacity */ 0, Unsharable);
274 }
275#endif
276};
277
278template <class T, size_t N>
279struct QStaticArrayData
280{
281 QArrayData header;
282 T data[N];
283};
284
285// Support for returning QArrayDataPointer<T> from functions
286template <class T>
287struct QArrayDataPointerRef
288{
289 QTypedArrayData<T> *ptr;
290};
291
292#define Q_STATIC_ARRAY_DATA_HEADER_INITIALIZER_WITH_OFFSET(size, offset) \
293 { Q_REFCOUNT_INITIALIZE_STATIC, size, 0, 0, offset } \
294 /**/
295
296#define Q_STATIC_ARRAY_DATA_HEADER_INITIALIZER(type, size) \
297 Q_STATIC_ARRAY_DATA_HEADER_INITIALIZER_WITH_OFFSET(size,\
298 ((sizeof(QArrayData) + (Q_ALIGNOF(type) - 1)) & ~(Q_ALIGNOF(type) - 1) )) \
299 /**/
300
301////////////////////////////////////////////////////////////////////////////////
302// Q_ARRAY_LITERAL
303
304// The idea here is to place a (read-only) copy of header and array data in an
305// mmappable portion of the executable (typically, .rodata section). This is
306// accomplished by hiding a static const instance of QStaticArrayData, which is
307// POD.
308
309#if defined(Q_COMPILER_VARIADIC_MACROS)
310#if defined(Q_COMPILER_LAMBDA)
311// Hide array inside a lambda
312#define Q_ARRAY_LITERAL(Type, ...) \
313 ([]() -> QArrayDataPointerRef<Type> { \
314 /* MSVC 2010 Doesn't support static variables in a lambda, but */ \
315 /* happily accepts them in a static function of a lambda-local */ \
316 /* struct :-) */ \
317 struct StaticWrapper { \
318 static QArrayDataPointerRef<Type> get() \
319 { \
320 Q_ARRAY_LITERAL_IMPL(Type, __VA_ARGS__) \
321 return ref; \
322 } \
323 }; \
324 return StaticWrapper::get(); \
325 }()) \
326 /**/
327#endif
328#endif // defined(Q_COMPILER_VARIADIC_MACROS)
329
330#if defined(Q_ARRAY_LITERAL)
331#define Q_ARRAY_LITERAL_IMPL(Type, ...) \
332 union { Type type_must_be_POD; } dummy; Q_UNUSED(dummy) \
333 \
334 /* Portable compile-time array size computation */ \
335 Type data[] = { __VA_ARGS__ }; Q_UNUSED(data) \
336 enum { Size = sizeof(data) / sizeof(data[0]) }; \
337 \
338 static const QStaticArrayData<Type, Size> literal = { \
339 Q_STATIC_ARRAY_DATA_HEADER_INITIALIZER(Type, Size), { __VA_ARGS__ } }; \
340 \
341 QArrayDataPointerRef<Type> ref = \
342 { static_cast<QTypedArrayData<Type> *>( \
343 const_cast<QArrayData *>(&literal.header)) }; \
344 /**/
345#else
346// As a fallback, memory is allocated and data copied to the heap.
347
348// The fallback macro does NOT use variadic macros and does NOT support
349// variable number of arguments. It is suitable for char arrays.
350
351namespace QtPrivate {
352 template <class T, size_t N>
353 inline QArrayDataPointerRef<T> qMakeArrayLiteral(const T (&array)[N])
354 {
355 union { T type_must_be_POD; } dummy; Q_UNUSED(dummy)
356
357 QArrayDataPointerRef<T> result = { QTypedArrayData<T>::allocate(N) };
358 Q_CHECK_PTR(result.ptr);
359
360 ::memcpy(result.ptr->data(), array, N * sizeof(T));
361 result.ptr->size = N;
362
363 return result;
364 }
365}
366
367#define Q_ARRAY_LITERAL(Type, Array) \
368 QT_PREPEND_NAMESPACE(QtPrivate::qMakeArrayLiteral)<Type>( Array )
369#endif // !defined(Q_ARRAY_LITERAL)
370
371namespace QtPrivate {
372struct Q_CORE_EXPORT QContainerImplHelper
373{
374 enum CutResult { Null, Empty, Full, Subset };
375 static CutResult mid(int originalLength, int *position, int *length);
376};
377}
378
379QT_END_NAMESPACE
380
381#endif // include guard
382