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 QARRAYDATAOPS_H
41#define QARRAYDATAOPS_H
42
43#include <QtCore/qarraydata.h>
44
45#include <new>
46#include <string.h>
47
48QT_BEGIN_NAMESPACE
49
50namespace QtPrivate {
51
52QT_WARNING_PUSH
53#if defined(Q_CC_GNU) && Q_CC_GNU >= 700
54QT_WARNING_DISABLE_GCC("-Wstringop-overflow")
55#endif
56
57template <class T>
58struct QPodArrayOps
59 : QTypedArrayData<T>
60{
61 void appendInitialize(size_t newSize)
62 {
63 Q_ASSERT(this->isMutable());
64 Q_ASSERT(!this->ref.isShared());
65 Q_ASSERT(newSize > uint(this->size));
66 Q_ASSERT(newSize <= this->alloc);
67
68 T *const begin = this->begin();
69 do {
70 new (begin + this->size) T();
71 } while (uint(++this->size) != newSize);
72 }
73
74 void copyAppend(const T *b, const T *e)
75 {
76 Q_ASSERT(this->isMutable());
77 Q_ASSERT(!this->ref.isShared());
78 Q_ASSERT(b < e);
79 Q_ASSERT(size_t(e - b) <= this->alloc - uint(this->size));
80
81 ::memcpy(static_cast<void *>(this->end()), static_cast<const void *>(b),
82 (e - b) * sizeof(T));
83 this->size += e - b;
84 }
85
86 void copyAppend(size_t n, const T &t)
87 {
88 Q_ASSERT(this->isMutable());
89 Q_ASSERT(!this->ref.isShared());
90 Q_ASSERT(n <= this->alloc - uint(this->size));
91
92 T *iter = this->end();
93 const T *const end = iter + n;
94 for (; iter != end; ++iter)
95 ::memcpy(iter, &t, sizeof(T));
96 this->size += int(n);
97 }
98
99 void truncate(size_t newSize)
100 {
101 Q_ASSERT(this->isMutable());
102 Q_ASSERT(!this->ref.isShared());
103 Q_ASSERT(newSize < size_t(this->size));
104
105 this->size = int(newSize);
106 }
107
108 void destroyAll() // Call from destructors, ONLY!
109 {
110 Q_ASSERT(this->isMutable());
111 Q_ASSERT(this->ref.atomic.loadRelaxed() == 0);
112
113 // As this is to be called only from destructor, it doesn't need to be
114 // exception safe; size not updated.
115 }
116
117 void insert(T *where, const T *b, const T *e)
118 {
119 Q_ASSERT(this->isMutable());
120 Q_ASSERT(!this->ref.isShared());
121 Q_ASSERT(where >= this->begin() && where < this->end()); // Use copyAppend at end
122 Q_ASSERT(b < e);
123 Q_ASSERT(e <= where || b > this->end()); // No overlap
124 Q_ASSERT(size_t(e - b) <= this->alloc - uint(this->size));
125
126 ::memmove(static_cast<void *>(where + (e - b)), static_cast<void *>(where),
127 (static_cast<const T*>(this->end()) - where) * sizeof(T));
128 ::memcpy(static_cast<void *>(where), static_cast<const void *>(b), (e - b) * sizeof(T));
129 this->size += (e - b);
130 }
131
132 void erase(T *b, T *e)
133 {
134 Q_ASSERT(this->isMutable());
135 Q_ASSERT(b < e);
136 Q_ASSERT(b >= this->begin() && b < this->end());
137 Q_ASSERT(e > this->begin() && e < this->end());
138
139 ::memmove(static_cast<void *>(b), static_cast<void *>(e),
140 (static_cast<T *>(this->end()) - e) * sizeof(T));
141 this->size -= (e - b);
142 }
143};
144QT_WARNING_POP
145
146template <class T>
147struct QGenericArrayOps
148 : QTypedArrayData<T>
149{
150 void appendInitialize(size_t newSize)
151 {
152 Q_ASSERT(this->isMutable());
153 Q_ASSERT(!this->ref.isShared());
154 Q_ASSERT(newSize > uint(this->size));
155 Q_ASSERT(newSize <= this->alloc);
156
157 T *const begin = this->begin();
158 do {
159 new (begin + this->size) T();
160 } while (uint(++this->size) != newSize);
161 }
162
163 void copyAppend(const T *b, const T *e)
164 {
165 Q_ASSERT(this->isMutable());
166 Q_ASSERT(!this->ref.isShared());
167 Q_ASSERT(b < e);
168 Q_ASSERT(size_t(e - b) <= this->alloc - uint(this->size));
169
170 T *iter = this->end();
171 for (; b != e; ++iter, ++b) {
172 new (iter) T(*b);
173 ++this->size;
174 }
175 }
176
177 void copyAppend(size_t n, const T &t)
178 {
179 Q_ASSERT(this->isMutable());
180 Q_ASSERT(!this->ref.isShared());
181 Q_ASSERT(n <= this->alloc - uint(this->size));
182
183 T *iter = this->end();
184 const T *const end = iter + n;
185 for (; iter != end; ++iter) {
186 new (iter) T(t);
187 ++this->size;
188 }
189 }
190
191 void truncate(size_t newSize)
192 {
193 Q_ASSERT(this->isMutable());
194 Q_ASSERT(!this->ref.isShared());
195 Q_ASSERT(newSize < size_t(this->size));
196
197 const T *const b = this->begin();
198 do {
199 (b + --this->size)->~T();
200 } while (uint(this->size) != newSize);
201 }
202
203 void destroyAll() // Call from destructors, ONLY
204 {
205 Q_ASSERT(this->isMutable());
206 // As this is to be called only from destructor, it doesn't need to be
207 // exception safe; size not updated.
208
209 Q_ASSERT(this->ref.atomic.loadRelaxed() == 0);
210
211 const T *const b = this->begin();
212 const T *i = this->end();
213
214 while (i != b)
215 (--i)->~T();
216 }
217
218 void insert(T *where, const T *b, const T *e)
219 {
220 Q_ASSERT(this->isMutable());
221 Q_ASSERT(!this->ref.isShared());
222 Q_ASSERT(where >= this->begin() && where < this->end()); // Use copyAppend at end
223 Q_ASSERT(b < e);
224 Q_ASSERT(e <= where || b > this->end()); // No overlap
225 Q_ASSERT(size_t(e - b) <= this->alloc - uint(this->size));
226
227 // Array may be truncated at where in case of exceptions
228
229 T *const end = this->end();
230 const T *readIter = end;
231 T *writeIter = end + (e - b);
232
233 const T *const step1End = where + qMax(e - b, end - where);
234
235 struct Destructor
236 {
237 Destructor(T *&it)
238 : iter(&it)
239 , end(it)
240 {
241 }
242
243 void commit()
244 {
245 iter = &end;
246 }
247
248 ~Destructor()
249 {
250 for (; *iter != end; --*iter)
251 (*iter)->~T();
252 }
253
254 T **iter;
255 T *end;
256 } destroyer(writeIter);
257
258 // Construct new elements in array
259 do {
260 --readIter, --writeIter;
261 new (writeIter) T(*readIter);
262 } while (writeIter != step1End);
263
264 while (writeIter != end) {
265 --e, --writeIter;
266 new (writeIter) T(*e);
267 }
268
269 destroyer.commit();
270 this->size += destroyer.end - end;
271
272 // Copy assign over existing elements
273 while (readIter != where) {
274 --readIter, --writeIter;
275 *writeIter = *readIter;
276 }
277
278 while (writeIter != where) {
279 --e, --writeIter;
280 *writeIter = *e;
281 }
282 }
283
284 void erase(T *b, T *e)
285 {
286 Q_ASSERT(this->isMutable());
287 Q_ASSERT(b < e);
288 Q_ASSERT(b >= this->begin() && b < this->end());
289 Q_ASSERT(e > this->begin() && e < this->end());
290
291 const T *const end = this->end();
292
293 do {
294 *b = *e;
295 ++b, ++e;
296 } while (e != end);
297
298 do {
299 (--e)->~T();
300 --this->size;
301 } while (e != b);
302 }
303};
304
305template <class T>
306struct QMovableArrayOps
307 : QGenericArrayOps<T>
308{
309 // using QGenericArrayOps<T>::appendInitialize;
310 // using QGenericArrayOps<T>::copyAppend;
311 // using QGenericArrayOps<T>::truncate;
312 // using QGenericArrayOps<T>::destroyAll;
313
314 void insert(T *where, const T *b, const T *e)
315 {
316 Q_ASSERT(this->isMutable());
317 Q_ASSERT(!this->ref.isShared());
318 Q_ASSERT(where >= this->begin() && where < this->end()); // Use copyAppend at end
319 Q_ASSERT(b < e);
320 Q_ASSERT(e <= where || b > this->end()); // No overlap
321 Q_ASSERT(size_t(e - b) <= this->alloc - uint(this->size));
322
323 // Provides strong exception safety guarantee,
324 // provided T::~T() nothrow
325
326 struct ReversibleDisplace
327 {
328 ReversibleDisplace(T *start, T *finish, size_t diff)
329 : begin(start)
330 , end(finish)
331 , displace(diff)
332 {
333 ::memmove(static_cast<void *>(begin + displace), static_cast<void *>(begin),
334 (end - begin) * sizeof(T));
335 }
336
337 void commit() { displace = 0; }
338
339 ~ReversibleDisplace()
340 {
341 if (displace)
342 ::memmove(static_cast<void *>(begin), static_cast<void *>(begin + displace),
343 (end - begin) * sizeof(T));
344 }
345
346 T *const begin;
347 T *const end;
348 size_t displace;
349
350 } displace(where, this->end(), size_t(e - b));
351
352 struct CopyConstructor
353 {
354 CopyConstructor(T *w) : where(w) {}
355
356 void copy(const T *src, const T *const srcEnd)
357 {
358 n = 0;
359 for (; src != srcEnd; ++src) {
360 new (where + n) T(*src);
361 ++n;
362 }
363 n = 0;
364 }
365
366 ~CopyConstructor()
367 {
368 while (n)
369 where[--n].~T();
370 }
371
372 T *const where;
373 size_t n;
374 } copier(where);
375
376 copier.copy(b, e);
377 displace.commit();
378 this->size += (e - b);
379 }
380
381 void erase(T *b, T *e)
382 {
383 Q_ASSERT(this->isMutable());
384 Q_ASSERT(b < e);
385 Q_ASSERT(b >= this->begin() && b < this->end());
386 Q_ASSERT(e > this->begin() && e < this->end());
387
388 struct Mover
389 {
390 Mover(T *&start, const T *finish, int &sz)
391 : destination(start)
392 , source(start)
393 , n(finish - start)
394 , size(sz)
395 {
396 }
397
398 ~Mover()
399 {
400 ::memmove(static_cast<void *>(destination), static_cast<const void *>(source), n * sizeof(T));
401 size -= (source - destination);
402 }
403
404 T *&destination;
405 const T *const source;
406 size_t n;
407 int &size;
408 } mover(e, this->end(), this->size);
409
410 do {
411 // Exceptions or not, dtor called once per instance
412 (--e)->~T();
413 } while (e != b);
414 }
415};
416
417template <class T, class = void>
418struct QArrayOpsSelector
419{
420 typedef QGenericArrayOps<T> Type;
421};
422
423template <class T>
424struct QArrayOpsSelector<T,
425 typename std::enable_if<
426 !QTypeInfoQuery<T>::isComplex && QTypeInfoQuery<T>::isRelocatable
427 >::type>
428{
429 typedef QPodArrayOps<T> Type;
430};
431
432template <class T>
433struct QArrayOpsSelector<T,
434 typename std::enable_if<
435 QTypeInfoQuery<T>::isComplex && QTypeInfoQuery<T>::isRelocatable
436 >::type>
437{
438 typedef QMovableArrayOps<T> Type;
439};
440
441} // namespace QtPrivate
442
443template <class T>
444struct QArrayDataOps
445 : QtPrivate::QArrayOpsSelector<T>::Type
446{
447};
448
449QT_END_NAMESPACE
450
451#endif // include guard
452