Qt 4.8
qvarlengtharray.h
Go to the documentation of this file.
1 /****************************************************************************
2 **
3 ** Copyright (C) 2014 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 
53 
55 
56 QT_MODULE(Core)
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 
69  : a(Prealloc), s(0), ptr(reinterpret_cast<T *>(array))
70  {
71  append(other.constData(), other.size());
72  }
73 
74  inline ~QVarLengthArray() {
76  T *i = ptr + s;
77  while (i-- != ptr)
78  i->~T();
79  }
80  if (ptr != reinterpret_cast<T *>(array))
81  qFree(ptr);
82  }
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 bool isEmpty() const { return (s == 0); }
99  inline void resize(int size);
100  inline void clear() { resize(0); }
101 
102  inline int capacity() const { return a; }
103  inline void reserve(int size);
104 
105  inline T &operator[](int idx) {
106  Q_ASSERT(idx >= 0 && idx < s);
107  return ptr[idx];
108  }
109  inline const T &operator[](int idx) const {
110  Q_ASSERT(idx >= 0 && idx < s);
111  return ptr[idx];
112  }
113  inline const T &at(int idx) const { return operator[](idx); }
114 
115  T value(int i) const;
116  T value(int i, const T &defaultValue) const;
117 
118  inline void append(const T &t) {
119  if (s == a) // i.e. s != 0
120  realloc(s, s<<1);
121  const int idx = s++;
123  new (ptr + idx) T(t);
124  } else {
125  ptr[idx] = t;
126  }
127  }
128  void append(const T *buf, int size);
130  { append(t); return *this; }
132  { append(t); return *this; }
133 
134  void prepend(const T &t);
135  void insert(int i, const T &t);
136  void insert(int i, int n, const T &t);
137  void replace(int i, const T &t);
138  void remove(int i);
139  void remove(int i, int n);
140 
141 
142  inline T *data() { return ptr; }
143  inline const T *data() const { return ptr; }
144  inline const T * constData() const { return ptr; }
145  typedef int size_type;
146  typedef T value_type;
147  typedef value_type *pointer;
148  typedef const value_type *const_pointer;
149  typedef value_type &reference;
150  typedef const value_type &const_reference;
152 
153 
154  typedef T* iterator;
155  typedef const T* const_iterator;
156 
157  inline iterator begin() { return ptr; }
158  inline const_iterator begin() const { return ptr; }
159  inline const_iterator constBegin() const { return ptr; }
160  inline iterator end() { return ptr + s; }
161  inline const_iterator end() const { return ptr + s; }
162  inline const_iterator constEnd() const { return ptr + s; }
163  iterator insert(iterator before, int n, const T &x);
164  inline iterator insert(iterator before, const T &x) { return insert(before, 1, x); }
165  iterator erase(iterator begin, iterator end);
166  inline iterator erase(iterator pos) { return erase(pos, pos+1); }
167 
168 private:
169  friend class QPodList<T, Prealloc>;
170  void realloc(int size, int alloc);
171 
172  int a; // capacity
173  int s; // size
174  T *ptr; // data
175  union {
176  // ### Qt 5: Use 'Prealloc * sizeof(T)' as array size
177  char array[sizeof(qint64) * (((Prealloc * sizeof(T)) / sizeof(qint64)) + 1)];
180  };
181 };
182 
183 template <class T, int Prealloc>
185  : s(asize) {
186  if (s > Prealloc) {
187  ptr = reinterpret_cast<T *>(qMalloc(s * sizeof(T)));
188  Q_CHECK_PTR(ptr);
189  a = s;
190  } else {
191  ptr = reinterpret_cast<T *>(array);
192  a = Prealloc;
193  }
195  T *i = ptr + s;
196  while (i != ptr)
197  new (--i) T;
198  }
199 }
200 
201 template <class T, int Prealloc>
203 { realloc(asize, qMax(asize, a)); }
204 
205 template <class T, int Prealloc>
207 { if (asize > a) realloc(s, asize); }
208 
209 template <class T, int Prealloc>
211 {
212  Q_ASSERT(abuf);
213  if (increment <= 0)
214  return;
215 
216  const int asize = s + increment;
217 
218  if (asize >= a)
219  realloc(s, qMax(s*2, asize));
220 
222  // call constructor for new objects (which can throw)
223  while (s < asize)
224  new (ptr+(s++)) T(*abuf++);
225  } else {
226  qMemCopy(&ptr[s], abuf, increment * sizeof(T));
227  s = asize;
228  }
229 }
230 
231 template <class T, int Prealloc>
233 {
234  Q_ASSERT(aalloc >= asize);
235  T *oldPtr = ptr;
236  int osize = s;
237 
238  const int copySize = qMin(asize, osize);
239  if (aalloc != a) {
240  ptr = reinterpret_cast<T *>(qMalloc(aalloc * sizeof(T)));
241  Q_CHECK_PTR(ptr);
242  if (ptr) {
243  s = 0;
244  a = aalloc;
245 
247  QT_TRY {
248  // copy all the old elements
249  while (s < copySize) {
250  new (ptr+s) T(*(oldPtr+s));
251  (oldPtr+s)->~T();
252  s++;
253  }
254  } QT_CATCH(...) {
255  // clean up all the old objects and then free the old ptr
256  int sClean = s;
257  while (sClean < osize)
258  (oldPtr+(sClean++))->~T();
259  if (oldPtr != reinterpret_cast<T *>(array) && oldPtr != ptr)
260  qFree(oldPtr);
261  QT_RETHROW;
262  }
263  } else {
264  qMemCopy(ptr, oldPtr, copySize * sizeof(T));
265  }
266  } else {
267  ptr = oldPtr;
268  return;
269  }
270  }
271  s = copySize;
272 
274  // destroy remaining old objects
275  while (osize > asize)
276  (oldPtr+(--osize))->~T();
277  }
278 
279  if (oldPtr != reinterpret_cast<T *>(array) && oldPtr != ptr)
280  qFree(oldPtr);
281 
283  // call default constructor for new objects (which can throw)
284  while (s < asize)
285  new (ptr+(s++)) T;
286  } else {
287  s = asize;
288  }
289 }
290 
291 template <class T, int Prealloc>
293 {
294  if (i < 0 || i >= size()) {
295  return T();
296  }
297  return at(i);
298 }
299 template <class T, int Prealloc>
300 Q_OUTOFLINE_TEMPLATE T QVarLengthArray<T, Prealloc>::value(int i, const T &defaultValue) const
301 {
302  return (i < 0 || i >= size()) ? defaultValue : at(i);
303 }
304 
305 template <class T, int Prealloc>
306 inline void QVarLengthArray<T, Prealloc>::insert(int i, const T &t)
307 { Q_ASSERT_X(i >= 0 && i <= s, "QVarLengthArray::insert", "index out of range");
308  insert(begin() + i, 1, t); }
309 template <class T, int Prealloc>
310 inline void QVarLengthArray<T, Prealloc>::insert(int i, int n, const T &t)
311 { Q_ASSERT_X(i >= 0 && i <= s, "QVarLengthArray::insert", "index out of range");
312  insert(begin() + i, n, t); }
313 template <class T, int Prealloc>
314 inline void QVarLengthArray<T, Prealloc>::remove(int i, int n)
315 { Q_ASSERT_X(i >= 0 && n >= 0 && i + n <= s, "QVarLengthArray::remove", "index out of range");
316  erase(begin() + i, begin() + i + n); }
317 template <class T, int Prealloc>
319 { Q_ASSERT_X(i >= 0 && i < s, "QVarLengthArray::remove", "index out of range");
320  erase(begin() + i, begin() + i + 1); }
321 template <class T, int Prealloc>
323 { insert(begin(), 1, t); }
324 
325 template <class T, int Prealloc>
326 inline void QVarLengthArray<T, Prealloc>::replace(int i, const T &t)
327 {
328  Q_ASSERT_X(i >= 0 && i < s, "QVarLengthArray::replace", "index out of range");
329  const T copy(t);
330  data()[i] = copy;
331 }
332 
333 
334 template <class T, int Prealloc>
336 {
337  int offset = int(before - ptr);
338  if (n != 0) {
339  resize(s + n);
340  const T copy(t);
342  T *b = ptr + offset;
343  T *j = ptr + s;
344  T *i = j - n;
345  while (i != b)
346  *--j = *--i;
347  i = b + n;
348  while (i != b)
349  *--i = copy;
350  } else {
351  T *b = ptr + offset;
352  T *i = b + n;
353  memmove(i, b, (s - offset - n) * sizeof(T));
354  while (i != b)
355  new (--i) T(copy);
356  }
357  }
358  return ptr + offset;
359 }
360 
361 template <class T, int Prealloc>
363 {
364  int f = int(abegin - ptr);
365  int l = int(aend - ptr);
366  int n = l - f;
368  qCopy(ptr + l, ptr + s, ptr + f);
369  T *i = ptr + s;
370  T *b = ptr + s - n;
371  while (i != b) {
372  --i;
373  i->~T();
374  }
375  } else {
376  memmove(ptr + f, ptr + l, (s - l) * sizeof(T));
377  }
378  s -= n;
379  return ptr + f;
380 }
381 
382 template <typename T, int Prealloc1, int Prealloc2>
384 {
385  if (l.size() != r.size())
386  return false;
387  for (int i = 0; i < l.size(); i++) {
388  if (l.at(i) != r.at(i))
389  return false;
390  }
391  return true;
392 }
393 
394 template <typename T, int Prealloc1, int Prealloc2>
396 {
397  return !(l == r);
398 }
399 
401 
403 
404 #endif // QVARLENGTHARRAY_H
QVarLengthArray(int size=0)
void resize(int size)
iterator insert(iterator before, const T &x)
const T * constData() const
Q_DECL_CONSTEXPR const T & qMin(const T &a, const T &b)
Definition: qglobal.h:1215
iterator erase(iterator begin, iterator end)
#define QT_END_NAMESPACE
This macro expands to.
Definition: qglobal.h:90
#define QT_MODULE(x)
Definition: qglobal.h:2783
QVarLengthArray< T, Prealloc > & operator=(const QVarLengthArray< T, Prealloc > &other)
#define QT_BEGIN_HEADER
Definition: qglobal.h:136
Q_CORE_EXPORT void qFree(void *ptr)
Definition: qmalloc.cpp:58
const T * const_iterator
Q_CORE_EXPORT void * qMalloc(size_t size)
Definition: qmalloc.cpp:53
#define Q_ASSERT(cond)
Definition: qglobal.h:1823
void insert(int i, const T &t)
void append(const T &t)
Q_DECL_CONSTEXPR const T & qMax(const T &a, const T &b)
Definition: qglobal.h:1217
void prepend(const T &t)
const_iterator begin() const
#define QT_RETHROW
Definition: qglobal.h:1539
#define QT_BEGIN_NAMESPACE
This macro expands to.
Definition: qglobal.h:89
void remove(int i)
QIntegerForSizeof< void * >::Signed qptrdiff
Definition: qglobal.h:987
const_iterator end() const
QVarLengthArray(const QVarLengthArray< T, Prealloc > &other)
#define Q_INLINE_TEMPLATE
Definition: qglobal.h:1713
bool isEmpty() const
int capacity() const
__int64 qint64
Definition: qglobal.h:942
qptrdiff difference_type
const T & at(int idx) const
int count() const
#define QT_CATCH(A)
Definition: qglobal.h:1537
bool operator==(const QVarLengthArray< T, Prealloc1 > &l, const QVarLengthArray< T, Prealloc2 > &r)
T value(int i) const
T & operator[](int idx)
const_iterator constEnd() const
void * qMemCopy(void *dest, const void *src, size_t n)
Definition: qglobal.cpp:2508
#define Q_CHECK_PTR(p)
Definition: qglobal.h:1853
#define Q_ASSERT_X(cond, where, what)
Definition: qglobal.h:1837
QVarLengthArray< T, Prealloc > & operator<<(const T &t)
void replace(int i, const T &t)
QFactoryLoader * l
value_type * pointer
value_type & reference
void realloc(int size, int alloc)
QVarLengthArray< T, Prealloc > & operator+=(const T &t)
OutputIterator qCopy(InputIterator begin, InputIterator end, OutputIterator dest)
Definition: qalgorithms.h:79
char array[sizeof(qint64) *(((Prealloc *sizeof(T))/sizeof(qint64))+1)]
const_iterator constBegin() const
bool operator!=(const QVarLengthArray< T, Prealloc1 > &l, const QVarLengthArray< T, Prealloc2 > &r)
const T * data() const
#define Q_OUTOFLINE_TEMPLATE
Definition: qglobal.h:1710
#define QT_END_HEADER
Definition: qglobal.h:137
const value_type * const_pointer
#define QT_TRY
Definition: qglobal.h:1536
iterator erase(iterator pos)
const T & operator[](int idx) const
int size() const
const value_type & const_reference
void reserve(int size)