src/corelib/tools/qvarlengtharray.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 QVARLENGTHARRAY_H
  43 #define QVARLENGTHARRAY_H
  44
  45 #include <QtCore/qcontainerfwd.h>
  46 #include <QtCore/qglobal.h>
  47 #include <QtCore/qalgorithms.h>
  48
  49 #include <new>
  50 #include <string.h>
  51 #include <stdlib.h>
  52
  53 QT_BEGIN_HEADER
  54
  55 QT_BEGIN_NAMESPACE
  56
  57
  58 template<class T, int Prealloc>
  59 class QPodList;
  60
  61 // Prealloc = 256 by default, specified in qcontainerfwd.h
  62 template<class T, int Prealloc>
  63 class QVarLengthArray
  64 {
  65 public:
  66     inline explicit QVarLengthArray(int size = 0);
  67
  68     inline QVarLengthArray(const QVarLengthArray<T, Prealloc> &other)
  69         : a(Prealloc), s(0), ptr(reinterpret_cast<T *>(array))
  70     {
  71         append(other.constData(), other.size());
  72     }
  73
  74     inline ~QVarLengthArray() {
  75         if (QTypeInfo<T>::isComplex) {
  76             T *i = ptr + s;
  77             while (i-- != ptr)
  78                 i->~T();
  79         }
  80         if (ptr != reinterpret_cast<T *>(array))
  81             free(ptr);
  82     }
  83     inline QVarLengthArray<T, Prealloc> &operator=(const QVarLengthArray<T, Prealloc> &other)
  84     {
  85         if (this != &other) {
  86             clear();
  87             append(other.constData(), other.size());
  88         }
  89         return *this;
  90     }
  91
  92     inline void removeLast() {
  93         Q_ASSERT(s > 0);
  94         realloc(s - 1, a);
  95     }
  96     inline int size() const { return s; }
  97     inline int count() const { return s; }
  98     inline int length() const { return s; }
  99     inline T& first() { Q_ASSERT(!isEmpty()); return *begin(); }
 100     inline const T& first() const { Q_ASSERT(!isEmpty()); return *begin(); }
 101     T& last() { Q_ASSERT(!isEmpty()); return *(end() - 1); }
 102     const T& last() const { Q_ASSERT(!isEmpty()); return *(end() - 1); }
 103     inline bool isEmpty() const { return (s == 0); }
 104     inline void resize(int size);
 105     inline void clear() { resize(0); }
 106
 107     inline int capacity() const { return a; }
 108     inline void reserve(int size);
 109
 110     inline T &operator[](int idx) {
 111         Q_ASSERT(idx >= 0 && idx < s);
 112         return ptr[idx];
 113     }
 114     inline const T &operator[](int idx) const {
 115         Q_ASSERT(idx >= 0 && idx < s);
 116         return ptr[idx];
 117     }
 118     inline const T &at(int idx) const { return operator[](idx); }
 119
 120     T value(int i) const;
 121     T value(int i, const T &defaultValue) const;
 122
 123     inline void append(const T &t) {
 124         if (s == a)   // i.e. s != 0
 125             realloc(s, s<<1);
 126         const int idx = s++;
 127         if (QTypeInfo<T>::isComplex) {
 128             new (ptr + idx) T(t);
 129         } else {
 130             ptr[idx] = t;
 131         }
 132     }
 133     void append(const T *buf, int size);
 134     inline QVarLengthArray<T, Prealloc> &operator<<(const T &t)
 135     { append(t); return *this; }
 136     inline QVarLengthArray<T, Prealloc> &operator+=(const T &t)
 137     { append(t); return *this; }
 138
 139     void prepend(const T &t);
 140     void insert(int i, const T &t);
 141     void insert(int i, int n, const T &t);
 142     void replace(int i, const T &t);
 143     void remove(int i);
 144     void remove(int i, int n);
 145
 146
 147     inline T *data() { return ptr; }
 148     inline const T *data() const { return ptr; }
 149     inline const T * constData() const { return ptr; }
 150     typedef int size_type;
 151     typedef T value_type;
 152     typedef value_type *pointer;
 153     typedef const value_type *const_pointer;
 154     typedef value_type &reference;
 155     typedef const value_type &const_reference;
 156     typedef qptrdiff difference_type;
 157
 158
 159     typedef T* iterator;
 160     typedef const T* const_iterator;
 161
 162     inline iterator begin() { return ptr; }
 163     inline const_iterator begin() const { return ptr; }
 164     inline const_iterator cbegin() const { return ptr; }
 165     inline const_iterator constBegin() const { return ptr; }
 166     inline iterator end() { return ptr + s; }
 167     inline const_iterator end() const { return ptr + s; }
 168     inline const_iterator cend() const { return ptr + s; }
 169     inline const_iterator constEnd() const { return ptr + s; }
 170     iterator insert(iterator before, int n, const T &x);
 171     inline iterator insert(iterator before, const T &x) { return insert(before, 1, x); }
 172     iterator erase(iterator begin, iterator end);
 173     inline iterator erase(iterator pos) { return erase(pos, pos+1); }
 174
 175 private:
 176     friend class QPodList<T, Prealloc>;
 177     void realloc(int size, int alloc);
 178
 179     int a;      // capacity
 180     int s;      // size
 181     T *ptr;     // data
 182     union {
 183         // ### Qt 5: Use 'Prealloc * sizeof(T)' as array size
 184         char array[sizeof(qint64) * (((Prealloc * sizeof(T)) / sizeof(qint64)) + 1)];
 185         qint64 q_for_alignment_1;
 186         double q_for_alignment_2;
 187     };
 188 };
 189
 190 template <class T, int Prealloc>
 191 Q_INLINE_TEMPLATE QVarLengthArray<T, Prealloc>::QVarLengthArray(int asize)
 192     : s(asize) {
 193     if (s > Prealloc) {
 194         ptr = reinterpret_cast<T *>(malloc(s * sizeof(T)));
 195         Q_CHECK_PTR(ptr);
 196         a = s;
 197     } else {
 198         ptr = reinterpret_cast<T *>(array);
 199         a = Prealloc;
 200     }
 201     if (QTypeInfo<T>::isComplex) {
 202         T *i = ptr + s;
 203         while (i != ptr)
 204             new (--i) T;
 205     }
 206 }
 207
 208 template <class T, int Prealloc>
 209 Q_INLINE_TEMPLATE void QVarLengthArray<T, Prealloc>::resize(int asize)
 210 { realloc(asize, qMax(asize, a)); }
 211
 212 template <class T, int Prealloc>
 213 Q_INLINE_TEMPLATE void QVarLengthArray<T, Prealloc>::reserve(int asize)
 214 { if (asize > a) realloc(s, asize); }
 215
 216 template <class T, int Prealloc>
 217 Q_OUTOFLINE_TEMPLATE void QVarLengthArray<T, Prealloc>::append(const T *abuf, int increment)
 218 {
 219     Q_ASSERT(abuf);
 220     if (increment <= 0)
 221         return;
 222
 223     const int asize = s + increment;
 224
 225     if (asize >= a)
 226         realloc(s, qMax(s*2, asize));
 227
 228     if (QTypeInfo<T>::isComplex) {
 229         // call constructor for new objects (which can throw)
 230         while (s < asize)
 231             new (ptr+(s++)) T(*abuf++);
 232     } else {
 233         qMemCopy(&ptr[s], abuf, increment * sizeof(T));
 234         s = asize;
 235     }
 236 }
 237
 238 template <class T, int Prealloc>
 239 Q_OUTOFLINE_TEMPLATE void QVarLengthArray<T, Prealloc>::realloc(int asize, int aalloc)
 240 {
 241     Q_ASSERT(aalloc >= asize);
 242     T *oldPtr = ptr;
 243     int osize = s;
 244
 245     const int copySize = qMin(asize, osize);
 246     if (aalloc != a) {
 247         ptr = reinterpret_cast<T *>(malloc(aalloc * sizeof(T)));
 248         Q_CHECK_PTR(ptr);
 249         if (ptr) {
 250             s = 0;
 251             a = aalloc;
 252
 253             if (QTypeInfo<T>::isStatic) {
 254                 QT_TRY {
 255                     // copy all the old elements
 256                     while (s < copySize) {
 257                         new (ptr+s) T(*(oldPtr+s));
 258                         (oldPtr+s)->~T();
 259                         s++;
 260                     }
 261                 } QT_CATCH(...) {
 262                     // clean up all the old objects and then free the old ptr
 263                     int sClean = s;
 264                     while (sClean < osize)
 265                         (oldPtr+(sClean++))->~T();
 266                     if (oldPtr != reinterpret_cast<T *>(array) && oldPtr != ptr)
 267                         free(oldPtr);
 268                     QT_RETHROW;
 269                 }
 270             } else {
 271                 qMemCopy(ptr, oldPtr, copySize * sizeof(T));
 272             }
 273         } else {
 274             ptr = oldPtr;
 275             return;
 276         }
 277     }
 278     s = copySize;
 279
 280     if (QTypeInfo<T>::isComplex) {
 281         // destroy remaining old objects
 282         while (osize > asize)
 283             (oldPtr+(--osize))->~T();
 284     }
 285
 286     if (oldPtr != reinterpret_cast<T *>(array) && oldPtr != ptr)
 287         free(oldPtr);
 288
 289     if (QTypeInfo<T>::isComplex) {
 290         // call default constructor for new objects (which can throw)
 291         while (s < asize)
 292             new (ptr+(s++)) T;
 293     } else {
 294         s = asize;
 295     }
 296 }
 297
 298 template <class T, int Prealloc>
 299 Q_OUTOFLINE_TEMPLATE T QVarLengthArray<T, Prealloc>::value(int i) const
 300 {
 301     if (i < 0 || i >= size()) {
 302         return T();
 303     }
 304     return at(i);
 305 }
 306 template <class T, int Prealloc>
 307 Q_OUTOFLINE_TEMPLATE T QVarLengthArray<T, Prealloc>::value(int i, const T &defaultValue) const
 308 {
 309     return (i < 0 || i >= size()) ? defaultValue : at(i);
 310 }
 311
 312 template <class T, int Prealloc>
 313 inline void QVarLengthArray<T, Prealloc>::insert(int i, const T &t)
 314 { Q_ASSERT_X(i >= 0 && i <= s, "QVarLengthArray::insert", "index out of range");
 315   insert(begin() + i, 1, t); }
 316 template <class T, int Prealloc>
 317 inline void QVarLengthArray<T, Prealloc>::insert(int i, int n, const T &t)
 318 { Q_ASSERT_X(i >= 0 && i <= s, "QVarLengthArray::insert", "index out of range");
 319   insert(begin() + i, n, t); }
 320 template <class T, int Prealloc>
 321 inline void QVarLengthArray<T, Prealloc>::remove(int i, int n)
 322 { Q_ASSERT_X(i >= 0 && n >= 0 && i + n <= s, "QVarLengthArray::remove", "index out of range");
 323   erase(begin() + i, begin() + i + n); }
 324 template <class T, int Prealloc>
 325 inline void QVarLengthArray<T, Prealloc>::remove(int i)
 326 { Q_ASSERT_X(i >= 0 && i < s, "QVarLengthArray::remove", "index out of range");
 327   erase(begin() + i, begin() + i + 1); }
 328 template <class T, int Prealloc>
 329 inline void QVarLengthArray<T, Prealloc>::prepend(const T &t)
 330 { insert(begin(), 1, t); }
 331
 332 template <class T, int Prealloc>
 333 inline void QVarLengthArray<T, Prealloc>::replace(int i, const T &t)
 334 {
 335     Q_ASSERT_X(i >= 0 && i < s, "QVarLengthArray::replace", "index out of range");
 336     const T copy(t);
 337     data()[i] = copy;
 338 }
 339
 340
 341 template <class T, int Prealloc>
 342 Q_OUTOFLINE_TEMPLATE typename QVarLengthArray<T, Prealloc>::iterator QVarLengthArray<T, Prealloc>::insert(iterator before, size_type n, const T &t)
 343 {
 344     int offset = int(before - ptr);
 345     if (n != 0) {
 346         resize(s + n);
 347         const T copy(t);
 348         if (QTypeInfo<T>::isStatic) {
 349             T *b = ptr + offset;
 350             T *j = ptr + s;
 351             T *i = j - n;
 352             while (i != b)
 353                 *--j = *--i;
 354             i = b + n;
 355             while (i != b)
 356                 *--i = copy;
 357         } else {
 358             T *b = ptr + offset;
 359             T *i = b + n;
 360             memmove(i, b, (s - offset - n) * sizeof(T));
 361             while (i != b)
 362                 new (--i) T(copy);
 363         }
 364     }
 365     return ptr + offset;
 366 }
 367
 368 template <class T, int Prealloc>
 369 Q_OUTOFLINE_TEMPLATE typename QVarLengthArray<T, Prealloc>::iterator QVarLengthArray<T, Prealloc>::erase(iterator abegin, iterator aend)
 370 {
 371     int f = int(abegin - ptr);
 372     int l = int(aend - ptr);
 373     int n = l - f;
 374     if (QTypeInfo<T>::isComplex) {
 375         qCopy(ptr + l, ptr + s, ptr + f);
 376         T *i = ptr + s;
 377         T *b = ptr + s - n;
 378         while (i != b) {
 379             --i;
 380             i->~T();
 381         }
 382     } else {
 383         memmove(ptr + f, ptr + l, (s - l) * sizeof(T));
 384     }
 385     s -= n;
 386     return ptr + f;
 387 }
 388
 389 template <typename T, int Prealloc1, int Prealloc2>
 390 bool operator==(const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r)
 391 {
 392     if (l.size() != r.size())
 393         return false;
 394     for (int i = 0; i < l.size(); i++) {
 395         if (l.at(i) != r.at(i))
 396             return false;
 397     }
 398     return true;
 399 }
 400
 401 template <typename T, int Prealloc1, int Prealloc2>
 402 bool operator!=(const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r)
 403 {
 404     return !(l == r);
 405 }
 406
 407 QT_END_NAMESPACE
 408
 409 QT_END_HEADER
 410
 411 #endif // QVARLENGTHARRAY_H