QtCore/qcontiguouscache.h Source File

qcontiguouscache.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 QCONTIGUOUSCACHE_H
43 #define QCONTIGUOUSCACHE_H
44 
45 #include <QtCore/qatomic.h>
46 #include <limits.h>
47 #include <new>
48 
50 
52 
53 #undef QT_QCONTIGUOUSCACHE_DEBUG
54 QT_MODULE(Core)
55 
56 
57 struct Q_CORE_EXPORT QContiguousCacheData
58 {
60  int alloc;
61  int count;
62  int start;
63  int offset;
64  uint sharable : 1;
65  uint reserved : 31;
66 
67  // total is 24 bytes (HP-UX aCC: 40 bytes)
68  // the next entry is already aligned to 8 bytes
69  // there will be an 8 byte gap here if T requires 16-byte alignment
70  // (such as long double on 64-bit platforms, __int128, __float128)
71 
72  static QContiguousCacheData *allocate(int size, int alignment);
73  static void free(QContiguousCacheData *data);
74 
75 #ifdef QT_QCONTIGUOUSCACHE_DEBUG
76  void dump() const;
77 #endif
78 };
79 
80 template <typename T>
82 {
83  // private inheritance to avoid aliasing warningss
84  T array[1];
85 
87 };
88 
89 template<typename T>
93 public:
94  // STL compatibility
95  typedef T value_type;
96  typedef value_type* pointer;
97  typedef const value_type* const_pointer;
98  typedef value_type& reference;
99  typedef const value_type& const_reference;
100  typedef qptrdiff difference_type;
101  typedef int size_type;
102 
103  explicit QContiguousCache(int capacity = 0);
104  QContiguousCache(const QContiguousCache<T> &v) : d(v.d) { d->ref.ref(); if (!d->sharable) detach_helper(); }
105 
106  inline ~QContiguousCache() { if (!d) return; if (!d->ref.deref()) free(p); }
107 
108  inline void detach() { if (d->ref != 1) detach_helper(); }
109  inline bool isDetached() const { return d->ref == 1; }
110  inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }
111 
113 #ifdef Q_COMPILER_RVALUE_REFS
115  { qSwap(d, other.d); return *this; }
116 #endif
117  inline void swap(QContiguousCache<T> &other) { qSwap(d, other.d); }
118  bool operator==(const QContiguousCache<T> &other) const;
119  inline bool operator!=(const QContiguousCache<T> &other) const { return !(*this == other); }
120 
121  inline int capacity() const {return d->alloc; }
122  inline int count() const { return d->count; }
123  inline int size() const { return d->count; }
124 
125  inline bool isEmpty() const { return d->count == 0; }
126  inline bool isFull() const { return d->count == d->alloc; }
127  inline int available() const { return d->alloc - d->count; }
128 
129  void clear();
130  void setCapacity(int size);
131 
132  const T &at(int pos) const;
133  T &operator[](int i);
134  const T &operator[](int i) const;
135 
136  void append(const T &value);
137  void prepend(const T &value);
138  void insert(int pos, const T &value);
139 
140  inline bool containsIndex(int pos) const { return pos >= d->offset && pos - d->offset < d->count; }
141  inline int firstIndex() const { return d->offset; }
142  inline int lastIndex() const { return d->offset + d->count - 1; }
143 
144  inline const T &first() const { Q_ASSERT(!isEmpty()); return p->array[d->start]; }
145  inline const T &last() const { Q_ASSERT(!isEmpty()); return p->array[(d->start + d->count -1) % d->alloc]; }
146  inline T &first() { Q_ASSERT(!isEmpty()); detach(); return p->array[d->start]; }
147  inline T &last() { Q_ASSERT(!isEmpty()); detach(); return p->array[(d->start + d->count -1) % d->alloc]; }
148 
149  void removeFirst();
150  T takeFirst();
151  void removeLast();
152  T takeLast();
153 
154  inline bool areIndexesValid() const
155  { return d->offset >= 0 && d->offset < INT_MAX - d->count && (d->offset % d->alloc) == d->start; }
156 
157  inline void normalizeIndexes() { d->offset = d->start; }
158 
159 #ifdef QT_QCONTIGUOUSCACHE_DEBUG
160  void dump() const { p->dump(); }
161 #endif
162 private:
163  void detach_helper();
164 
165  QContiguousCacheData *malloc(int aalloc);
166  void free(Data *x);
167  int sizeOfTypedData() {
168  // this is more or less the same as sizeof(Data), except that it doesn't
169  // count the padding at the end
170  return reinterpret_cast<const char *>(&(reinterpret_cast<const Data *>(this))->array[1]) - reinterpret_cast<const char *>(this);
171  }
172  int alignOfTypedData() const
173  {
174 #ifdef Q_ALIGNOF
175  return qMax<int>(sizeof(void*), Q_ALIGNOF(Data));
176 #else
177  return 0;
178 #endif
179  }
180 };
181 
182 template <typename T>
184 {
186 
187  x.d = malloc(d->alloc);
188  x.d->ref = 1;
189  x.d->count = d->count;
190  x.d->start = d->start;
191  x.d->offset = d->offset;
192  x.d->alloc = d->alloc;
193  x.d->sharable = true;
194  x.d->reserved = 0;
195 
196  T *dest = x.p->array + x.d->start;
197  T *src = p->array + d->start;
198  int oldcount = x.d->count;
199  while (oldcount--) {
200  if (QTypeInfo<T>::isComplex) {
201  new (dest) T(*src);
202  } else {
203  *dest = *src;
204  }
205  dest++;
206  if (dest == x.p->array + x.d->alloc)
207  dest = x.p->array;
208  src++;
209  if (src == p->array + d->alloc)
210  src = p->array;
211  }
212 
213  if (!d->ref.deref())
214  free(p);
215  d = x.d;
216 }
217 
218 template <typename T>
220 {
221  if (asize == d->alloc)
222  return;
223  detach();
225  x.d = malloc(asize);
226  x.d->alloc = asize;
227  x.d->count = qMin(d->count, asize);
228  x.d->offset = d->offset + d->count - x.d->count;
229  if(asize)
230  x.d->start = x.d->offset % x.d->alloc;
231  else
232  x.d->start = 0;
233 
234  int oldcount = x.d->count;
235  if(oldcount)
236  {
237  T *dest = x.p->array + (x.d->start + x.d->count-1) % x.d->alloc;
238  T *src = p->array + (d->start + d->count-1) % d->alloc;
239  while (oldcount--) {
240  if (QTypeInfo<T>::isComplex) {
241  new (dest) T(*src);
242  } else {
243  *dest = *src;
244  }
245  if (dest == x.p->array)
246  dest = x.p->array + x.d->alloc;
247  dest--;
248  if (src == p->array)
249  src = p->array + d->alloc;
250  src--;
251  }
252  }
253  /* free old */
254  free(p);
255  d = x.d;
256 }
257 
258 template <typename T>
260 {
261  if (d->ref == 1) {
262  if (QTypeInfo<T>::isComplex) {
263  int oldcount = d->count;
264  T * i = p->array + d->start;
265  T * e = p->array + d->alloc;
266  while (oldcount--) {
267  i->~T();
268  i++;
269  if (i == e)
270  i = p->array;
271  }
272  }
273  d->count = d->start = d->offset = 0;
274  } else {
276  x.d = malloc(d->alloc);
277  x.d->ref = 1;
278  x.d->alloc = d->alloc;
279  x.d->count = x.d->start = x.d->offset = 0;
280  x.d->sharable = true;
281  if (!d->ref.deref()) free(p);
282  d = x.d;
283  }
284 }
285 
286 template <typename T>
288 {
289  return QContiguousCacheData::allocate(sizeOfTypedData() + (aalloc - 1) * sizeof(T), alignOfTypedData());
290 }
291 
292 template <typename T>
294 {
295  d = malloc(cap);
296  d->ref = 1;
297  d->alloc = cap;
298  d->count = d->start = d->offset = 0;
299  d->sharable = true;
300 }
301 
302 template <typename T>
304 {
305  other.d->ref.ref();
306  if (!d->ref.deref())
307  free(d);
308  d = other.d;
309  if (!d->sharable)
310  detach_helper();
311  return *this;
312 }
313 
314 template <typename T>
316 {
317  if (other.d == d)
318  return true;
319  if (other.d->start != d->start
320  || other.d->count != d->count
321  || other.d->offset != d->offset
322  || other.d->alloc != d->alloc)
323  return false;
324  for (int i = firstIndex(); i <= lastIndex(); ++i)
325  if (!(at(i) == other.at(i)))
326  return false;
327  return true;
328 }
329 
330 template <typename T>
331 void QContiguousCache<T>::free(Data *x)
332 {
333  if (QTypeInfo<T>::isComplex) {
334  int oldcount = d->count;
335  T * i = p->array + d->start;
336  T * e = p->array + d->alloc;
337  while (oldcount--) {
338  i->~T();
339  i++;
340  if (i == e)
341  i = p->array;
342  }
343  }
344  x->free(x);
345 }
346 template <typename T>
348 {
349  if (!d->alloc)
350  return; // zero capacity
351  detach();
352  if (QTypeInfo<T>::isComplex) {
353  if (d->count == d->alloc)
354  (p->array + (d->start+d->count) % d->alloc)->~T();
355  new (p->array + (d->start+d->count) % d->alloc) T(value);
356  } else {
357  p->array[(d->start+d->count) % d->alloc] = value;
358  }
359 
360  if (d->count == d->alloc) {
361  d->start++;
362  d->start %= d->alloc;
363  d->offset++;
364  } else {
365  d->count++;
366  }
367 }
368 
369 template<typename T>
371 {
372  if (!d->alloc)
373  return; // zero capacity
374  detach();
375  if (d->start)
376  d->start--;
377  else
378  d->start = d->alloc-1;
379  d->offset--;
380 
381  if (d->count != d->alloc)
382  d->count++;
383  else
384  if (d->count == d->alloc)
385  (p->array + d->start)->~T();
386 
387  if (QTypeInfo<T>::isComplex)
388  new (p->array + d->start) T(value);
389  else
390  p->array[d->start] = value;
391 }
392 
393 template<typename T>
394 void QContiguousCache<T>::insert(int pos, const T &value)
395 {
396  Q_ASSERT_X(pos >= 0 && pos < INT_MAX, "QContiguousCache<T>::insert", "index out of range");
397  if (!d->alloc)
398  return; // zero capacity
399  detach();
400  if (containsIndex(pos)) {
401  if (QTypeInfo<T>::isComplex) {
402  (p->array + pos % d->alloc)->~T();
403  new (p->array + pos % d->alloc) T(value);
404  } else {
405  p->array[pos % d->alloc] = value;
406  }
407  } else if (pos == d->offset-1)
408  prepend(value);
409  else if (pos == d->offset+d->count)
410  append(value);
411  else {
412  // we don't leave gaps.
413  clear();
414  d->offset = pos;
415  d->start = pos % d->alloc;
416  d->count = 1;
417  if (QTypeInfo<T>::isComplex)
418  new (p->array + d->start) T(value);
419  else
420  p->array[d->start] = value;
421  }
422 }
423 
424 template <typename T>
425 inline const T &QContiguousCache<T>::at(int pos) const
426 { Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache<T>::at", "index out of range"); return p->array[pos % d->alloc]; }
427 template <typename T>
428 inline const T &QContiguousCache<T>::operator[](int pos) const
429 { Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache<T>::at", "index out of range"); return p->array[pos % d->alloc]; }
430 
431 template <typename T>
433 {
434  detach();
435  if (!containsIndex(pos))
436  insert(pos, T());
437  return p->array[pos % d->alloc];
438 }
439 
440 template <typename T>
442 {
443  Q_ASSERT(d->count > 0);
444  detach();
445  d->count--;
446  if (QTypeInfo<T>::isComplex)
447  (p->array + d->start)->~T();
448  d->start = (d->start + 1) % d->alloc;
449  d->offset++;
450 }
451 
452 template <typename T>
454 {
455  Q_ASSERT(d->count > 0);
456  detach();
457  d->count--;
458  if (QTypeInfo<T>::isComplex)
459  (p->array + (d->start + d->count) % d->alloc)->~T();
460 }
461 
462 template <typename T>
464 { T t = first(); removeFirst(); return t; }
465 
466 template <typename T>
468 { T t = last(); removeLast(); return t; }
469 
471 
473 
474 #endif
void setSharable(bool sharable)
bool isFull() const
static void free(QContiguousCacheTypedData *data)
#define QT_END_NAMESPACE
Definition: qglobal.h:128
int available() const
#define QT_BEGIN_HEADER
Definition: qglobal.h:141
void insert(int pos, const T &value)
value_type & reference
void append(const T &value)
GLuint src
Definition: GLee.h:7190
QContiguousCache(int capacity=0)
QContiguousCacheData * d
int lastIndex() const
#define QT_BEGIN_NAMESPACE
Definition: qglobal.h:127
GLsizei GLsizei GLenum GLenum const GLvoid * data
Definition: GLee.h:880
GLint * first
Definition: GLee.h:1362
QContiguousCache< T > & operator=(const QContiguousCache< T > &other)
Q_INLINE_TEMPLATE void qSwap(QScopedPointer< T, Cleanup > &p1, QScopedPointer< T, Cleanup > &p2)
int firstIndex() const
const T & last() const
bool isEmpty() const
bool isDetached() const
GLenum GLint x
Definition: GLee.h:876
GLenum cap
Definition: GLee.h:7211
const GLdouble * v
Definition: GLee.h:1174
QContiguousCacheTypedData< T > * p
bool areIndexesValid() const
QContiguousCache(const QContiguousCache< T > &v)
void setCapacity(int size)
GLsizei const GLfloat * value
Definition: GLee.h:1742
int count() const
GLfloat GLfloat p
Definition: GLee.h:5416
const T & first() const
static QContiguousCacheData * allocate(int size, int alignment)
static void free(QContiguousCacheData *data)
value_type * pointer
bool operator==(const QContiguousCache< T > &other) const
const T & at(int pos) const
QBasicAtomicInt ref
void prepend(const T &value)
const value_type & const_reference
GLdouble GLdouble t
Definition: GLee.h:1181
#define QT_END_HEADER
Definition: qglobal.h:142
bool operator!=(const QContiguousCache< T > &other) const
GLsizeiptr size
Definition: GLee.h:1561
bool containsIndex(int pos) const
const value_type * const_pointer
void swap(QContiguousCache< T > &other)
int capacity() const