util/kdevvarlengtharray.h

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 1992-2008 Trolltech ASA. All rights reserved.
   4 **
   5 ** This file is part of the QtCore module of the Qt Toolkit.
   6 **
   7 ** This file may be used under the terms of the GNU General Public
   8 ** License versions 2.0 or 3.0 as published by the Free Software
   9 ** Foundation and appearing in the files LICENSE.GPL2 and LICENSE.GPL3
  10 ** included in the packaging of this file.  Alternatively you may (at
  11 ** your option) use any later version of the GNU General Public
  12 ** License if such license has been publicly approved by Trolltech ASA
  13 ** (or its successors, if any) and the KDE Free Qt Foundation. In
  14 ** addition, as a special exception, Trolltech gives you certain
  15 ** additional rights. These rights are described in the Trolltech GPL
  16 ** Exception version 1.2, which can be found at
  17 ** http://www.trolltech.com/products/qt/gplexception/ and in the file
  18 ** GPL_EXCEPTION.txt in this package.
  19 **
  20 ** Please review the following information to ensure GNU General
  21 ** Public Licensing requirements will be met:
  22 ** http://trolltech.com/products/qt/licenses/licensing/opensource/. If
  23 ** you are unsure which license is appropriate for your use, please
  24 ** review the following information:
  25 ** http://trolltech.com/products/qt/licenses/licensing/licensingoverview
  26 ** or contact the sales department at sales@trolltech.com.
  27 **
  28 ** In addition, as a special exception, Trolltech, as the sole
  29 ** copyright holder for Qt Designer, grants users of the Qt/Eclipse
  30 ** Integration plug-in the right for the Qt/Eclipse Integration to
  31 ** link to functionality provided by Qt Designer and its related
  32 ** libraries.
  33 **
  34 ** This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
  35 ** INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
  36 ** A PARTICULAR PURPOSE. Trolltech reserves all rights not expressly
  37 ** granted herein.
  38 **
  39 ** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  40 ** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  41 **
  42 ****************************************************************************/
  43
  44 #ifndef KDEVVARLENGTHARRAY_H
  45 #define KDEVVARLENGTHARRAY_H
  46
  47 #include <QtCore/qcontainerfwd.h>
  48 #include <QtCore/qglobal.h>
  49 #include <new>
  50
  51 ///Foreach macro that also works with QVarLengthArray or KDevVarLengthArray
  52 ///@warning Unlike the Qt foreach macro, this does not temporarily copy the array, which its size must not be changed while the iteration.
  53 #define FOREACH_ARRAY(item, container) for(int a = 0, mustDo = 1; a < container.size(); ++a) if((mustDo == 0 || mustDo == 1) && (mustDo = 2)) for(item(container[a]); mustDo; mustDo = 0)
  54
  55 QT_BEGIN_HEADER
  56
  57 QT_BEGIN_NAMESPACE
  58
  59 QT_MODULE(Core)
  60
  61 template<class T, int Prealloc = 256>
  62 class KDevVarLengthArray
  63 {
  64 public:
  65     inline explicit KDevVarLengthArray(int size = 0);
  66
  67     inline KDevVarLengthArray(const KDevVarLengthArray<T, Prealloc> &other)
  68         : a(Prealloc), s(0), ptr(reinterpret_cast<T *>(array))
  69     {
  70         append(other.constData(), other.size());
  71     }
  72
  73     inline ~KDevVarLengthArray() {
  74         if (QTypeInfo<T>::isComplex) {
  75             T *i = ptr + s;
  76             while (i-- != ptr)
  77                 i->~T();
  78         }
  79         if (ptr != reinterpret_cast<T *>(array))
  80             qFree(ptr);
  81     }
  82     inline KDevVarLengthArray<T, Prealloc> &operator=(const KDevVarLengthArray<T, Prealloc> &other)
  83     {
  84         if (this != &other) {
  85             clear();
  86             append(other.constData(), other.size());
  87         }
  88         return *this;
  89     }
  90
  91     inline int size() const { return s; }
  92     inline int count() const { return s; }
  93     inline bool isEmpty() const { return (s == 0); }
  94     inline void resize(int size);
  95     inline void clear() { resize(0); }
  96
  97     inline int capacity() const { return a; }
  98     inline void reserve(int size);
  99
 100     inline T &operator[](int idx) {
 101         Q_ASSERT(idx >= 0 && idx < s);
 102         return ptr[idx];
 103     }
 104     inline const T &operator[](int idx) const {
 105         Q_ASSERT(idx >= 0 && idx < s);
 106         return ptr[idx];
 107     }
 108
 109     ///Returns the index of the given item in this array, or -1
 110     int indexOf(const T& t) const {
 111         for(int a = 0; a < s; ++a)
 112             if(t == ptr[a])
 113                 return a;
 114         return -1;
 115     }
 116
 117     inline KDevVarLengthArray& operator<<(const T &t) {
 118         append(t);
 119         return *this;
 120     }
 121
 122     inline void append(const T &t) {
 123         const int idx = s++;
 124         ///This is currently the difference to KDevVarLengthArray(which uses s == a), and it prevents a crash.
 125         if (s >= a)
 126             realloc(s, s<<1);
 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
 135     inline T *data() { return ptr; }
 136     inline const T *data() const { return ptr; }
 137     inline const T * constData() const { return ptr; }
 138
 139     ///Returns whether the given item is contained in this array
 140     bool contains(const T& value) const {
 141       for(int a = 0; a < s; ++a)
 142           if(ptr[a] == value)
 143           return true;
 144
 145       return false;
 146     }
 147
 148     ///Inserts the given item at the given position, moving all items behind the position back
 149     void insert(const T& item, int position) {
 150         Q_ASSERT(position >= 0 && position <= size());
 151         resize(s+1);
 152         for(int a = s-1; a > position; --a) {
 153             ptr[a] = ptr[a-1];
 154         }
 155         ptr[position] = item;
 156     }
 157
 158     ///Removes the given position from the array, moving all items behind it one back.
 159     void erase(int position) {
 160         Q_ASSERT(position >= 0 && position < s);
 161         for(int a = position; a < s-1; ++a) {
 162             ptr[a] = ptr[a+1];
 163         }
 164         resize(s-1);
 165     }
 166
 167     ///Removes exactly one occurence of the given value from the array. Returns false if none was found.
 168     bool removeOne(const T& value) {
 169     for(int a = 0; a < s; ++a) {
 170         if(ptr[a] == value) {
 171         erase(a);
 172         return true;
 173         }
 174     }
 175     return false;
 176     }
 177
 178     T& back() {
 179         return ptr[s-1];
 180     }
 181
 182     const T& back() const {
 183         return ptr[s-1];
 184     }
 185
 186     void pop_back() {
 187         resize(s-1);
 188     }
 189
 190 private:
 191     void realloc(int size, int alloc);
 192
 193     int a;
 194     int s;
 195     T *ptr;
 196     union {
 197         // ### Qt 5: Use 'Prealloc * sizeof(T)' as array size
 198         char array[sizeof(qint64) * (((Prealloc * sizeof(T)) / sizeof(qint64)) + 1)];
 199         qint64 q_for_alignment_1;
 200         double q_for_alignment_2;
 201     };
 202 };
 203
 204 template <class T, int Prealloc>
 205 Q_INLINE_TEMPLATE KDevVarLengthArray<T, Prealloc>::KDevVarLengthArray(int asize)
 206     : s(asize) {
 207     if (s > Prealloc) {
 208         ptr = reinterpret_cast<T *>(qMalloc(s * sizeof(T)));
 209         a = s;
 210     } else {
 211         ptr = reinterpret_cast<T *>(array);
 212         a = Prealloc;
 213     }
 214     if (QTypeInfo<T>::isComplex) {
 215         T *i = ptr + s;
 216         while (i != ptr)
 217             new (--i) T;
 218     }
 219 }
 220
 221 template <class T, int Prealloc>
 222 Q_INLINE_TEMPLATE void KDevVarLengthArray<T, Prealloc>::resize(int asize)
 223 { realloc(asize, qMax(asize, a)); }
 224
 225 template <class T, int Prealloc>
 226 Q_INLINE_TEMPLATE void KDevVarLengthArray<T, Prealloc>::reserve(int asize)
 227 { if (asize > a) realloc(s, asize); }
 228
 229 template <class T, int Prealloc>
 230 Q_OUTOFLINE_TEMPLATE void KDevVarLengthArray<T, Prealloc>::append(const T *abuf, int asize)
 231 {
 232     Q_ASSERT(abuf);
 233     if (asize <= 0)
 234         return;
 235
 236     const int idx = s;
 237     const int news = s + asize;
 238     if (news >= a)
 239         realloc(news, news<<1);
 240     else
 241         s = news;
 242
 243     if (QTypeInfo<T>::isComplex) {
 244         T *i = ptr + idx;
 245         T *j = i + asize;
 246         while (i < j)
 247             new (i++) T(*abuf++);
 248     } else {
 249         qMemCopy(&ptr[idx], abuf, asize * sizeof(T));
 250     }
 251 }
 252
 253 template <class T, int Prealloc>
 254 Q_OUTOFLINE_TEMPLATE void KDevVarLengthArray<T, Prealloc>::realloc(int asize, int aalloc)
 255 {
 256     Q_ASSERT(aalloc >= asize);
 257     T *oldPtr = ptr;
 258     int osize = s;
 259     s = asize;
 260
 261     if (aalloc != a) {
 262         ptr = reinterpret_cast<T *>(qMalloc(aalloc * sizeof(T)));
 263         if (ptr) {
 264             a = aalloc;
 265
 266             if (QTypeInfo<T>::isStatic) {
 267                 T *i = ptr + osize;
 268                 T *j = oldPtr + osize;
 269                 while (i != ptr) {
 270                     new (--i) T(*--j);
 271                     j->~T();
 272                 }
 273             } else {
 274                 qMemCopy(ptr, oldPtr, osize * sizeof(T));
 275             }
 276         } else {
 277             ptr = oldPtr;
 278             s = 0;
 279             asize = 0;
 280         }
 281     }
 282
 283     if (QTypeInfo<T>::isComplex) {
 284         if (asize < osize) {
 285             T *i = oldPtr + osize;
 286             T *j = oldPtr + asize;
 287             while (i-- != j)
 288                 i->~T();
 289         } else {
 290             T *i = ptr + asize;
 291             T *j = ptr + osize;
 292             while (i != j)
 293                 new (--i) T;
 294         }
 295     }
 296
 297     if (oldPtr != reinterpret_cast<T *>(array) && oldPtr != ptr)
 298         qFree(oldPtr);
 299 }
 300
 301 QT_END_NAMESPACE
 302
 303 QT_END_HEADER
 304
 305 #endif // QVARLENGTHARRAY_H