src/corelib/tools/qvarlengtharray.h

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2012 Digia Plc and/or its subsidiary(-ies).
   4 ** Contact: http://www.qt-project.org/legal
   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 Digia.  For licensing terms and
  14 ** conditions see http://qt.digia.com/licensing.  For further information
  15 ** use the contact form at http://qt.digia.com/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 2.1 as published by the Free Software
  20 ** Foundation and appearing in the file LICENSE.LGPL included in the
  21 ** packaging of this file.  Please review the following information to
  22 ** ensure the GNU Lesser General Public License version 2.1 requirements
  23 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  24 **
  25 ** In addition, as a special exception, Digia gives you certain additional
  26 ** rights.  These rights are described in the Digia Qt LGPL Exception
  27 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  28 **
  29 ** GNU General Public License Usage
  30 ** Alternatively, this file may be used under the terms of the GNU
  31 ** General Public License version 3.0 as published by the Free Software
  32 ** Foundation and appearing in the file LICENSE.GPL included in the
  33 ** packaging of this file.  Please review the following information to
  34 ** ensure the GNU General Public License version 3.0 requirements will be
  35 ** met: http://www.gnu.org/copyleft/gpl.html.
  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(const_iterator before, int n, const T &x);
 171     inline iterator insert(const_iterator before, const T &x) { return insert(before, 1, x); }
 172     iterator erase(const_iterator begin, const_iterator end);
 173     inline iterator erase(const_iterator pos) { return erase(pos, pos+1); }
 174
 175     // STL compatibility:
 176     inline bool empty() const { return isEmpty(); }
 177     inline void push_back(const T &t) { append(t); }
 178     inline void pop_back() { removeLast(); }
 179     inline T &front() { return first(); }
 180     inline const T &front() const { return first(); }
 181     inline T &back() { return last(); }
 182     inline const T &back() const { return last(); }
 183
 184 private:
 185     friend class QPodList<T, Prealloc>;
 186     void realloc(int size, int alloc);
 187
 188     int a;      // capacity
 189     int s;      // size
 190     T *ptr;     // data
 191     union {
 192         char array[Prealloc * sizeof(T)];
 193         qint64 q_for_alignment_1;
 194         double q_for_alignment_2;
 195     };
 196 };
 197
 198 template <class T, int Prealloc>
 199 Q_INLINE_TEMPLATE QVarLengthArray<T, Prealloc>::QVarLengthArray(int asize)
 200     : s(asize) {
 201     if (s > Prealloc) {
 202         ptr = reinterpret_cast<T *>(malloc(s * sizeof(T)));
 203         Q_CHECK_PTR(ptr);
 204         a = s;
 205     } else {
 206         ptr = reinterpret_cast<T *>(array);
 207         a = Prealloc;
 208     }
 209     if (QTypeInfo<T>::isComplex) {
 210         T *i = ptr + s;
 211         while (i != ptr)
 212             new (--i) T;
 213     }
 214 }
 215
 216 template <class T, int Prealloc>
 217 Q_INLINE_TEMPLATE void QVarLengthArray<T, Prealloc>::resize(int asize)
 218 { realloc(asize, qMax(asize, a)); }
 219
 220 template <class T, int Prealloc>
 221 Q_INLINE_TEMPLATE void QVarLengthArray<T, Prealloc>::reserve(int asize)
 222 { if (asize > a) realloc(s, asize); }
 223
 224 template <class T, int Prealloc>
 225 Q_OUTOFLINE_TEMPLATE void QVarLengthArray<T, Prealloc>::append(const T *abuf, int increment)
 226 {
 227     Q_ASSERT(abuf);
 228     if (increment <= 0)
 229         return;
 230
 231     const int asize = s + increment;
 232
 233     if (asize >= a)
 234         realloc(s, qMax(s*2, asize));
 235
 236     if (QTypeInfo<T>::isComplex) {
 237         // call constructor for new objects (which can throw)
 238         while (s < asize)
 239             new (ptr+(s++)) T(*abuf++);
 240     } else {
 241         memcpy(&ptr[s], abuf, increment * sizeof(T));
 242         s = asize;
 243     }
 244 }
 245
 246 template <class T, int Prealloc>
 247 Q_OUTOFLINE_TEMPLATE void QVarLengthArray<T, Prealloc>::realloc(int asize, int aalloc)
 248 {
 249     Q_ASSERT(aalloc >= asize);
 250     T *oldPtr = ptr;
 251     int osize = s;
 252
 253     const int copySize = qMin(asize, osize);
 254     if (aalloc != a) {
 255         T* newPtr = reinterpret_cast<T *>(malloc(aalloc * sizeof(T)));
 256         Q_CHECK_PTR(newPtr); // could throw
 257         // by design: in case of QT_NO_EXCEPTIONS malloc must not fail or it crashes here
 258         ptr = newPtr;
 259         s = 0;
 260         a = aalloc;
 261         if (QTypeInfo<T>::isStatic) {
 262             QT_TRY {
 263                 // copy all the old elements
 264                 while (s < copySize) {
 265                     new (ptr+s) T(*(oldPtr+s));
 266                     (oldPtr+s)->~T();
 267                     s++;
 268                 }
 269             } QT_CATCH(...) {
 270                 // clean up all the old objects and then free the old ptr
 271                 int sClean = s;
 272                 while (sClean < osize)
 273                     (oldPtr+(sClean++))->~T();
 274                 if (oldPtr != reinterpret_cast<T *>(array) && oldPtr != ptr)
 275                     free(oldPtr);
 276                 QT_RETHROW;
 277             }
 278         } else {
 279             memcpy(ptr, oldPtr, copySize * sizeof(T));
 280         }
 281     }
 282     s = copySize;
 283
 284     if (QTypeInfo<T>::isComplex) {
 285         // destroy remaining old objects
 286         while (osize > asize)
 287             (oldPtr+(--osize))->~T();
 288     }
 289
 290     if (oldPtr != reinterpret_cast<T *>(array) && oldPtr != ptr)
 291         free(oldPtr);
 292
 293     if (QTypeInfo<T>::isComplex) {
 294         // call default constructor for new objects (which can throw)
 295         while (s < asize)
 296             new (ptr+(s++)) T;
 297     } else {
 298         s = asize;
 299     }
 300 }
 301
 302 template <class T, int Prealloc>
 303 Q_OUTOFLINE_TEMPLATE T QVarLengthArray<T, Prealloc>::value(int i) const
 304 {
 305     if (i < 0 || i >= size()) {
 306         return T();
 307     }
 308     return at(i);
 309 }
 310 template <class T, int Prealloc>
 311 Q_OUTOFLINE_TEMPLATE T QVarLengthArray<T, Prealloc>::value(int i, const T &defaultValue) const
 312 {
 313     return (i < 0 || i >= size()) ? defaultValue : at(i);
 314 }
 315
 316 template <class T, int Prealloc>
 317 inline void QVarLengthArray<T, Prealloc>::insert(int i, const T &t)
 318 { Q_ASSERT_X(i >= 0 && i <= s, "QVarLengthArray::insert", "index out of range");
 319   insert(begin() + i, 1, t); }
 320 template <class T, int Prealloc>
 321 inline void QVarLengthArray<T, Prealloc>::insert(int i, int n, const T &t)
 322 { Q_ASSERT_X(i >= 0 && i <= s, "QVarLengthArray::insert", "index out of range");
 323   insert(begin() + i, n, t); }
 324 template <class T, int Prealloc>
 325 inline void QVarLengthArray<T, Prealloc>::remove(int i, int n)
 326 { Q_ASSERT_X(i >= 0 && n >= 0 && i + n <= s, "QVarLengthArray::remove", "index out of range");
 327   erase(begin() + i, begin() + i + n); }
 328 template <class T, int Prealloc>
 329 inline void QVarLengthArray<T, Prealloc>::remove(int i)
 330 { Q_ASSERT_X(i >= 0 && i < s, "QVarLengthArray::remove", "index out of range");
 331   erase(begin() + i, begin() + i + 1); }
 332 template <class T, int Prealloc>
 333 inline void QVarLengthArray<T, Prealloc>::prepend(const T &t)
 334 { insert(begin(), 1, t); }
 335
 336 template <class T, int Prealloc>
 337 inline void QVarLengthArray<T, Prealloc>::replace(int i, const T &t)
 338 {
 339     Q_ASSERT_X(i >= 0 && i < s, "QVarLengthArray::replace", "index out of range");
 340     const T copy(t);
 341     data()[i] = copy;
 342 }
 343
 344
 345 template <class T, int Prealloc>
 346 Q_OUTOFLINE_TEMPLATE typename QVarLengthArray<T, Prealloc>::iterator QVarLengthArray<T, Prealloc>::insert(const_iterator before, size_type n, const T &t)
 347 {
 348     int offset = int(before - ptr);
 349     if (n != 0) {
 350         resize(s + n);
 351         const T copy(t);
 352         if (QTypeInfo<T>::isStatic) {
 353             T *b = ptr + offset;
 354             T *j = ptr + s;
 355             T *i = j - n;
 356             while (i != b)
 357                 *--j = *--i;
 358             i = b + n;
 359             while (i != b)
 360                 *--i = copy;
 361         } else {
 362             T *b = ptr + offset;
 363             T *i = b + n;
 364             memmove(i, b, (s - offset - n) * sizeof(T));
 365             while (i != b)
 366                 new (--i) T(copy);
 367         }
 368     }
 369     return ptr + offset;
 370 }
 371
 372 template <class T, int Prealloc>
 373 Q_OUTOFLINE_TEMPLATE typename QVarLengthArray<T, Prealloc>::iterator QVarLengthArray<T, Prealloc>::erase(const_iterator abegin, const_iterator aend)
 374 {
 375     int f = int(abegin - ptr);
 376     int l = int(aend - ptr);
 377     int n = l - f;
 378     if (QTypeInfo<T>::isComplex) {
 379         qCopy(ptr + l, ptr + s, ptr + f);
 380         T *i = ptr + s;
 381         T *b = ptr + s - n;
 382         while (i != b) {
 383             --i;
 384             i->~T();
 385         }
 386     } else {
 387         memmove(ptr + f, ptr + l, (s - l) * sizeof(T));
 388     }
 389     s -= n;
 390     return ptr + f;
 391 }
 392
 393 template <typename T, int Prealloc1, int Prealloc2>
 394 bool operator==(const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r)
 395 {
 396     if (l.size() != r.size())
 397         return false;
 398     for (int i = 0; i < l.size(); i++) {
 399         if (l.at(i) != r.at(i))
 400             return false;
 401     }
 402     return true;
 403 }
 404
 405 template <typename T, int Prealloc1, int Prealloc2>
 406 bool operator!=(const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r)
 407 {
 408     return !(l == r);
 409 }
 410
 411 QT_END_NAMESPACE
 412
 413 QT_END_HEADER
 414
 415 #endif // QVARLENGTHARRAY_H