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