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 48 QT_BEGIN_NAMESPACE 49 50 namespace QtPrivate { 51 52 QT_WARNING_PUSH 53 #if defined(Q_CC_GNU) && Q_CC_GNU >= 700 54 QT_WARNING_DISABLE_GCC("-Wstringop-overflow") 55 #endif 56 57 template <class T> 58 struct QPodArrayOps 59 : QTypedArrayData<T> 60 { appendInitializeQPodArrayOps61 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 copyAppendQPodArrayOps74 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 copyAppendQPodArrayOps86 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 truncateQPodArrayOps99 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 destroyAllQPodArrayOps108 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 insertQPodArrayOps117 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 eraseQPodArrayOps132 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 }; 144 QT_WARNING_POP 145 146 template <class T> 147 struct QGenericArrayOps 148 : QTypedArrayData<T> 149 { appendInitializeQGenericArrayOps150 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 copyAppendQGenericArrayOps163 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 copyAppendQGenericArrayOps177 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 truncateQGenericArrayOps191 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 destroyAllQGenericArrayOps203 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 insertQGenericArrayOps218 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 eraseQGenericArrayOps284 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 305 template <class T> 306 struct 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 insertQMovableArrayOps314 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 eraseQMovableArrayOps381 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 417 template <class T, class = void> 418 struct QArrayOpsSelector 419 { 420 typedef QGenericArrayOps<T> Type; 421 }; 422 423 template <class T> 424 struct QArrayOpsSelector<T, 425 typename std::enable_if< 426 !QTypeInfoQuery<T>::isComplex && QTypeInfoQuery<T>::isRelocatable 427 >::type> 428 { 429 typedef QPodArrayOps<T> Type; 430 }; 431 432 template <class T> 433 struct 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 443 template <class T> 444 struct QArrayDataOps 445 : QtPrivate::QArrayOpsSelector<T>::Type 446 { 447 }; 448 449 QT_END_NAMESPACE 450 451 #endif // include guard 452