src/corelib/tools/qarraydataops.h

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
   4 ** Contact: http://www.qt-project.org/
   5 **
   6 ** This file is part of the QtCore module of the Qt Toolkit.
   7 **
   8 ** $QT_BEGIN_LICENSE:LGPL$
   9 ** GNU Lesser General Public License Usage
  10 ** This file may be used under the terms of the GNU Lesser General Public
  11 ** License version 2.1 as published by the Free Software Foundation and
  12 ** appearing in the file LICENSE.LGPL included in the packaging of this
  13 ** file. Please review the following information to ensure the GNU Lesser
  14 ** General Public License version 2.1 requirements will be met:
  15 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  16 **
  17 ** In addition, as a special exception, Nokia gives you certain additional
  18 ** rights. These rights are described in the Nokia Qt LGPL Exception
  19 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  20 **
  21 ** GNU General Public License Usage
  22 ** Alternatively, this file may be used under the terms of the GNU General
  23 ** Public License version 3.0 as published by the Free Software Foundation
  24 ** and appearing in the file LICENSE.GPL included in the packaging of this
  25 ** file. Please review the following information to ensure the GNU General
  26 ** Public License version 3.0 requirements will be met:
  27 ** http://www.gnu.org/copyleft/gpl.html.
  28 **
  29 ** Other Usage
  30 ** Alternatively, this file may be used in accordance with the terms and
  31 ** conditions contained in a signed written agreement between you and Nokia.
  32 **
  33 **
  34 **
  35 **
  36 **
  37 **
  38 ** $QT_END_LICENSE$
  39 **
  40 ****************************************************************************/
  41
  42 #ifndef QARRAYDATAOPS_H
  43 #define QARRAYDATAOPS_H
  44
  45 #include <QtCore/qarraydata.h>
  46
  47 #include <new>
  48 #include <string.h>
  49
  50 QT_BEGIN_HEADER
  51
  52 QT_BEGIN_NAMESPACE
  53
  54 namespace QtPrivate {
  55
  56 template <class T>
  57 struct QPodArrayOps
  58     : QTypedArrayData<T>
  59 {
  60     void appendInitialize(size_t newSize)
  61     {
  62         Q_ASSERT(!this->ref.isShared());
  63         Q_ASSERT(newSize > uint(this->size));
  64         Q_ASSERT(newSize <= this->alloc);
  65
  66         ::memset(this->end(), 0, (newSize - this->size) * sizeof(T));
  67         this->size = newSize;
  68     }
  69
  70     void copyAppend(const T *b, const T *e)
  71     {
  72         Q_ASSERT(!this->ref.isShared());
  73         Q_ASSERT(b < e);
  74         Q_ASSERT(size_t(e - b) <= this->alloc - uint(this->size));
  75
  76         ::memcpy(this->end(), b, (e - b) * sizeof(T));
  77         this->size += e - b;
  78     }
  79
  80     void copyAppend(size_t n, const T &t)
  81     {
  82         Q_ASSERT(!this->ref.isShared());
  83         Q_ASSERT(n <= this->alloc - uint(this->size));
  84
  85         T *iter = this->end();
  86         const T *const end = iter + n;
  87         for (; iter != end; ++iter)
  88             ::memcpy(iter, &t, sizeof(T));
  89         this->size += n;
  90     }
  91
  92     void truncate(size_t newSize)
  93     {
  94         Q_ASSERT(!this->ref.isShared());
  95         Q_ASSERT(newSize < size_t(this->size));
  96
  97         this->size = newSize;
  98     }
  99
 100     void destroyAll() // Call from destructors, ONLY!
 101     {
 102         Q_ASSERT(this->ref.atomic.load() == 0);
 103
 104         // As this is to be called only from destructor, it doesn't need to be
 105         // exception safe; size not updated.
 106     }
 107
 108     void insert(T *where, const T *b, const T *e)
 109     {
 110         Q_ASSERT(!this->ref.isShared());
 111         Q_ASSERT(where >= this->begin() && where < this->end()); // Use copyAppend at end
 112         Q_ASSERT(b < e);
 113         Q_ASSERT(e <= where || b > this->end()); // No overlap
 114         Q_ASSERT(size_t(e - b) <= this->alloc - uint(this->size));
 115
 116         ::memmove(where + (e - b), where, (this->end() - where) * sizeof(T));
 117         ::memcpy(where, b, (e - b) * sizeof(T));
 118         this->size += (e - b);
 119     }
 120 };
 121
 122 template <class T>
 123 struct QGenericArrayOps
 124     : QTypedArrayData<T>
 125 {
 126     void appendInitialize(size_t newSize)
 127     {
 128         Q_ASSERT(!this->ref.isShared());
 129         Q_ASSERT(newSize > uint(this->size));
 130         Q_ASSERT(newSize <= this->alloc);
 131
 132         T *const begin = this->begin();
 133         do {
 134             new (begin + this->size) T();
 135         } while (uint(++this->size) != newSize);
 136     }
 137
 138     void copyAppend(const T *b, const T *e)
 139     {
 140         Q_ASSERT(!this->ref.isShared());
 141         Q_ASSERT(b < e);
 142         Q_ASSERT(size_t(e - b) <= this->alloc - uint(this->size));
 143
 144         T *iter = this->end();
 145         for (; b != e; ++iter, ++b) {
 146             new (iter) T(*b);
 147             ++this->size;
 148         }
 149     }
 150
 151     void copyAppend(size_t n, const T &t)
 152     {
 153         Q_ASSERT(!this->ref.isShared());
 154         Q_ASSERT(n <= this->alloc - uint(this->size));
 155
 156         T *iter = this->end();
 157         const T *const end = iter + n;
 158         for (; iter != end; ++iter) {
 159             new (iter) T(t);
 160             ++this->size;
 161         }
 162     }
 163
 164     void truncate(size_t newSize)
 165     {
 166         Q_ASSERT(!this->ref.isShared());
 167         Q_ASSERT(newSize < size_t(this->size));
 168
 169         const T *const b = this->begin();
 170         do {
 171             (b + --this->size)->~T();
 172         } while (uint(this->size) != newSize);
 173     }
 174
 175     void destroyAll() // Call from destructors, ONLY
 176     {
 177         // As this is to be called only from destructor, it doesn't need to be
 178         // exception safe; size not updated.
 179
 180         Q_ASSERT(this->ref.atomic.load() == 0);
 181
 182         const T *const b = this->begin();
 183         const T *i = this->end();
 184
 185         while (i != b)
 186             (--i)->~T();
 187     }
 188
 189     void insert(T *where, const T *b, const T *e)
 190     {
 191         Q_ASSERT(!this->ref.isShared());
 192         Q_ASSERT(where >= this->begin() && where < this->end()); // Use copyAppend at end
 193         Q_ASSERT(b < e);
 194         Q_ASSERT(e <= where || b > this->end()); // No overlap
 195         Q_ASSERT(size_t(e - b) <= this->alloc - uint(this->size));
 196
 197         // Array may be truncated at where in case of exceptions
 198
 199         T *const end = this->end();
 200         const T *readIter = end;
 201         T *writeIter = end + (e - b);
 202
 203         const T *const step1End = where + qMax(e - b, end - where);
 204
 205         struct Destructor
 206         {
 207             Destructor(T *&it)
 208                 : iter(&it)
 209                 , end(it)
 210             {
 211             }
 212
 213             void commit()
 214             {
 215                 iter = &end;
 216             }
 217
 218             ~Destructor()
 219             {
 220                 for (; *iter != end; --*iter)
 221                     (*iter)->~T();
 222             }
 223
 224             T **iter;
 225             T *end;
 226         } destroyer(writeIter);
 227
 228         // Construct new elements in array
 229         do {
 230             --readIter, --writeIter;
 231             new (writeIter) T(*readIter);
 232         } while (writeIter != step1End);
 233
 234         while (writeIter != end) {
 235             --e, --writeIter;
 236             new (writeIter) T(*e);
 237         }
 238
 239         destroyer.commit();
 240         this->size += destroyer.end - end;
 241
 242         // Copy assign over existing elements
 243         while (readIter != where) {
 244             --readIter, --writeIter;
 245             *writeIter = *readIter;
 246         }
 247
 248         while (writeIter != where) {
 249             --e, --writeIter;
 250             *writeIter = *e;
 251         }
 252     }
 253 };
 254
 255 template <class T>
 256 struct QMovableArrayOps
 257     : QGenericArrayOps<T>
 258 {
 259     // using QGenericArrayOps<T>::appendInitialize;
 260     // using QGenericArrayOps<T>::copyAppend;
 261     // using QGenericArrayOps<T>::truncate;
 262     // using QGenericArrayOps<T>::destroyAll;
 263
 264     void insert(T *where, const T *b, const T *e)
 265     {
 266         Q_ASSERT(!this->ref.isShared());
 267         Q_ASSERT(where >= this->begin() && where < this->end()); // Use copyAppend at end
 268         Q_ASSERT(b < e);
 269         Q_ASSERT(e <= where || b > this->end()); // No overlap
 270         Q_ASSERT(size_t(e - b) <= this->alloc - uint(this->size));
 271
 272         // Provides strong exception safety guarantee,
 273         // provided T::~T() nothrow
 274
 275         struct ReversibleDisplace
 276         {
 277             ReversibleDisplace(T *start, T *finish, size_t diff)
 278                 : begin(start)
 279                 , end(finish)
 280                 , displace(diff)
 281             {
 282                 ::memmove(begin + displace, begin, (end - begin) * sizeof(T));
 283             }
 284
 285             void commit() { displace = 0; }
 286
 287             ~ReversibleDisplace()
 288             {
 289                 if (displace)
 290                     ::memmove(begin, begin + displace, (end - begin) * sizeof(T));
 291             }
 292
 293             T *const begin;
 294             T *const end;
 295             size_t displace;
 296
 297         } displace(where, this->end(), size_t(e - b));
 298
 299         struct CopyConstructor
 300         {
 301             CopyConstructor(T *w) : where(w) {}
 302
 303             void copy(const T *src, const T *const srcEnd)
 304             {
 305                 n = 0;
 306                 for (; src != srcEnd; ++src) {
 307                     new (where + n) T(*src);
 308                     ++n;
 309                 }
 310                 n = 0;
 311             }
 312
 313             ~CopyConstructor()
 314             {
 315                 while (n)
 316                     where[--n].~T();
 317             }
 318
 319             T *const where;
 320             size_t n;
 321         } copier(where);
 322
 323         copier.copy(b, e);
 324         displace.commit();
 325         this->size += (e - b);
 326     }
 327 };
 328
 329 template <class T, class = void>
 330 struct QArrayOpsSelector
 331 {
 332     typedef QGenericArrayOps<T> Type;
 333 };
 334
 335 template <class T>
 336 struct QArrayOpsSelector<T,
 337     typename QEnableIf<
 338         !QTypeInfo<T>::isComplex && !QTypeInfo<T>::isStatic
 339     >::Type>
 340 {
 341     typedef QPodArrayOps<T> Type;
 342 };
 343
 344 template <class T>
 345 struct QArrayOpsSelector<T,
 346     typename QEnableIf<
 347         QTypeInfo<T>::isComplex && !QTypeInfo<T>::isStatic
 348     >::Type>
 349 {
 350     typedef QMovableArrayOps<T> Type;
 351 };
 352
 353 } // namespace QtPrivate
 354
 355 template <class T>
 356 struct QArrayDataOps
 357     : QtPrivate::QArrayOpsSelector<T>::Type
 358 {
 359 };
 360
 361 QT_END_NAMESPACE
 362
 363 QT_END_HEADER
 364
 365 #endif // include guard