Line data Source code
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 :
46 : QT_BEGIN_NAMESPACE
47 :
48 : struct 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 664 : void *data()
58 : {
59 664 : Q_ASSERT(size == 0
60 : || offset < 0 || size_t(offset) >= sizeof(QArrayData));
61 664 : return reinterpret_cast<char *>(this) + offset;
62 : }
63 :
64 42 : const void *data() const
65 : {
66 42 : Q_ASSERT(size == 0
67 : || offset < 0 || size_t(offset) >= sizeof(QArrayData));
68 42 : 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 2 : AllocationOptions detachFlags() const
100 : {
101 2 : AllocationOptions result;
102 2 : if (capacityReserved)
103 0 : result |= CapacityReserved;
104 2 : 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 459 : static QArrayData *sharedNull() Q_DECL_NOTHROW { return const_cast<QArrayData*>(shared_null); }
124 : };
125 :
126 : Q_DECLARE_OPERATORS_FOR_FLAGS(QArrayData::AllocationOptions)
127 :
128 : template <class T>
129 : struct 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(Q_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 : inline int operator-(iterator j) const { return i - j.i; }
163 : inline operator T*() const { return i; }
164 : };
165 : friend class iterator;
166 :
167 : class const_iterator {
168 : public:
169 : const T *i;
170 : typedef std::random_access_iterator_tag iterator_category;
171 : typedef int difference_type;
172 : typedef T value_type;
173 : typedef const T *pointer;
174 : typedef const T &reference;
175 :
176 : inline const_iterator() : i(Q_NULLPTR) {}
177 : inline const_iterator(const T *n) : i(n) {}
178 : inline const_iterator(const const_iterator &o): i(o.i) {} // #### Qt 6: remove, the default version is fine
179 : inline explicit const_iterator(const iterator &o): i(o.i) {}
180 : inline const T &operator*() const { return *i; }
181 : inline const T *operator->() const { return i; }
182 : inline const T &operator[](int j) const { return *(i + j); }
183 : inline bool operator==(const const_iterator &o) const { return i == o.i; }
184 : inline bool operator!=(const const_iterator &o) const { return i != o.i; }
185 : inline bool operator<(const const_iterator& other) const { return i < other.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 const_iterator &operator++() { ++i; return *this; }
190 : inline const_iterator operator++(int) { const T *n = i; ++i; return n; }
191 : inline const_iterator &operator--() { i--; return *this; }
192 : inline const_iterator operator--(int) { const T *n = i; i--; return n; }
193 : inline const_iterator &operator+=(int j) { i+=j; return *this; }
194 : inline const_iterator &operator-=(int j) { i-=j; return *this; }
195 : inline const_iterator operator+(int j) const { return const_iterator(i+j); }
196 : inline const_iterator operator-(int j) const { return const_iterator(i-j); }
197 : inline int operator-(const_iterator j) const { return i - j.i; }
198 : inline operator const T*() const { return i; }
199 : };
200 : friend class const_iterator;
201 : #else
202 : typedef T* iterator;
203 : typedef const T* const_iterator;
204 : #endif
205 :
206 664 : T *data() { return static_cast<T *>(QArrayData::data()); }
207 42 : const T *data() const { return static_cast<const T *>(QArrayData::data()); }
208 :
209 16 : iterator begin(iterator = iterator()) { return data(); }
210 14 : iterator end(iterator = iterator()) { return data() + size; }
211 : const_iterator begin(const_iterator = const_iterator()) const { return data(); }
212 : const_iterator end(const_iterator = const_iterator()) const { return data() + size; }
213 6 : const_iterator constBegin(const_iterator = const_iterator()) const { return data(); }
214 36 : const_iterator constEnd(const_iterator = const_iterator()) const { return data() + size; }
215 :
216 : class AlignmentDummy { QArrayData header; T data; };
217 :
218 10 : Q_REQUIRED_RESULT static QTypedArrayData *allocate(size_t capacity,
219 : AllocationOptions options = Default)
220 : {
221 : Q_STATIC_ASSERT(sizeof(QTypedArrayData) == sizeof(QArrayData));
222 : return static_cast<QTypedArrayData *>(QArrayData::allocate(sizeof(T),
223 10 : Q_ALIGNOF(AlignmentDummy), capacity, options));
224 : }
225 :
226 : static QTypedArrayData *reallocateUnaligned(QTypedArrayData *data, size_t capacity,
227 : AllocationOptions options = Default)
228 : {
229 : Q_STATIC_ASSERT(sizeof(QTypedArrayData) == sizeof(QArrayData));
230 : return static_cast<QTypedArrayData *>(QArrayData::reallocateUnaligned(data, sizeof(T),
231 : capacity, options));
232 : }
233 :
234 3371 : static void deallocate(QArrayData *data)
235 : {
236 : Q_STATIC_ASSERT(sizeof(QTypedArrayData) == sizeof(QArrayData));
237 3371 : QArrayData::deallocate(data, sizeof(T), Q_ALIGNOF(AlignmentDummy));
238 3371 : }
239 :
240 : static QTypedArrayData *fromRawData(const T *data, size_t n,
241 : AllocationOptions options = Default)
242 : {
243 : Q_STATIC_ASSERT(sizeof(QTypedArrayData) == sizeof(QArrayData));
244 : QTypedArrayData *result = allocate(0, options | RawData);
245 : if (result) {
246 : Q_ASSERT(!result->ref.isShared()); // No shared empty, please!
247 :
248 : result->offset = reinterpret_cast<const char *>(data)
249 : - reinterpret_cast<const char *>(result);
250 : result->size = int(n);
251 : }
252 : return result;
253 : }
254 :
255 459 : static QTypedArrayData *sharedNull() Q_DECL_NOTHROW
256 : {
257 : Q_STATIC_ASSERT(sizeof(QTypedArrayData) == sizeof(QArrayData));
258 459 : return static_cast<QTypedArrayData *>(QArrayData::sharedNull());
259 : }
260 :
261 : static QTypedArrayData *sharedEmpty()
262 : {
263 : Q_STATIC_ASSERT(sizeof(QTypedArrayData) == sizeof(QArrayData));
264 : return allocate(/* capacity */ 0);
265 : }
266 :
267 : #if !defined(QT_NO_UNSHARABLE_CONTAINERS)
268 6 : static QTypedArrayData *unsharableEmpty()
269 : {
270 : Q_STATIC_ASSERT(sizeof(QTypedArrayData) == sizeof(QArrayData));
271 6 : return allocate(/* capacity */ 0, Unsharable);
272 : }
273 : #endif
274 : };
275 :
276 : template <class T, size_t N>
277 : struct QStaticArrayData
278 : {
279 : QArrayData header;
280 : T data[N];
281 : };
282 :
283 : // Support for returning QArrayDataPointer<T> from functions
284 : template <class T>
285 : struct QArrayDataPointerRef
286 : {
287 : QTypedArrayData<T> *ptr;
288 : };
289 :
290 : #define Q_STATIC_ARRAY_DATA_HEADER_INITIALIZER_WITH_OFFSET(size, offset) \
291 : { Q_REFCOUNT_INITIALIZE_STATIC, size, 0, 0, offset } \
292 : /**/
293 :
294 : #define Q_STATIC_ARRAY_DATA_HEADER_INITIALIZER(type, size) \
295 : Q_STATIC_ARRAY_DATA_HEADER_INITIALIZER_WITH_OFFSET(size,\
296 : ((sizeof(QArrayData) + (Q_ALIGNOF(type) - 1)) & ~(Q_ALIGNOF(type) - 1) )) \
297 : /**/
298 :
299 : ////////////////////////////////////////////////////////////////////////////////
300 : // Q_ARRAY_LITERAL
301 :
302 : // The idea here is to place a (read-only) copy of header and array data in an
303 : // mmappable portion of the executable (typically, .rodata section). This is
304 : // accomplished by hiding a static const instance of QStaticArrayData, which is
305 : // POD.
306 :
307 : #if defined(Q_COMPILER_VARIADIC_MACROS)
308 : #if defined(Q_COMPILER_LAMBDA)
309 : // Hide array inside a lambda
310 : #define Q_ARRAY_LITERAL(Type, ...) \
311 : ([]() -> QArrayDataPointerRef<Type> { \
312 : /* MSVC 2010 Doesn't support static variables in a lambda, but */ \
313 : /* happily accepts them in a static function of a lambda-local */ \
314 : /* struct :-) */ \
315 : struct StaticWrapper { \
316 : static QArrayDataPointerRef<Type> get() \
317 : { \
318 : Q_ARRAY_LITERAL_IMPL(Type, __VA_ARGS__) \
319 : return ref; \
320 : } \
321 : }; \
322 : return StaticWrapper::get(); \
323 : }()) \
324 : /**/
325 : #endif
326 : #endif // defined(Q_COMPILER_VARIADIC_MACROS)
327 :
328 : #if defined(Q_ARRAY_LITERAL)
329 : #define Q_ARRAY_LITERAL_IMPL(Type, ...) \
330 : union { Type type_must_be_POD; } dummy; Q_UNUSED(dummy) \
331 : \
332 : /* Portable compile-time array size computation */ \
333 : Type data[] = { __VA_ARGS__ }; Q_UNUSED(data) \
334 : enum { Size = sizeof(data) / sizeof(data[0]) }; \
335 : \
336 : static const QStaticArrayData<Type, Size> literal = { \
337 : Q_STATIC_ARRAY_DATA_HEADER_INITIALIZER(Type, Size), { __VA_ARGS__ } }; \
338 : \
339 : QArrayDataPointerRef<Type> ref = \
340 : { static_cast<QTypedArrayData<Type> *>( \
341 : const_cast<QArrayData *>(&literal.header)) }; \
342 : /**/
343 : #else
344 : // As a fallback, memory is allocated and data copied to the heap.
345 :
346 : // The fallback macro does NOT use variadic macros and does NOT support
347 : // variable number of arguments. It is suitable for char arrays.
348 :
349 : namespace QtPrivate {
350 : template <class T, size_t N>
351 : inline QArrayDataPointerRef<T> qMakeArrayLiteral(const T (&array)[N])
352 : {
353 : union { T type_must_be_POD; } dummy; Q_UNUSED(dummy)
354 :
355 : QArrayDataPointerRef<T> result = { QTypedArrayData<T>::allocate(N) };
356 : Q_CHECK_PTR(result.ptr);
357 :
358 : ::memcpy(result.ptr->data(), array, N * sizeof(T));
359 : result.ptr->size = N;
360 :
361 : return result;
362 : }
363 : }
364 :
365 : #define Q_ARRAY_LITERAL(Type, Array) \
366 : QT_PREPEND_NAMESPACE(QtPrivate::qMakeArrayLiteral)<Type>( Array )
367 : #endif // !defined(Q_ARRAY_LITERAL)
368 :
369 : namespace QtPrivate {
370 : struct Q_CORE_EXPORT QContainerImplHelper
371 : {
372 : enum CutResult { Null, Empty, Full, Subset };
373 : static CutResult mid(int originalLength, int *position, int *length);
374 : };
375 : }
376 :
377 : QT_END_NAMESPACE
378 :
379 : #endif // include guard
|