Qt 4.8
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 
58 {
60  int alloc;
61  int count;
62  int start;
63  int offset;
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;
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 
112  QContiguousCache<T> &operator=(const QContiguousCache<T> &other);
113 #ifdef Q_COMPILER_RVALUE_REFS
114  inline QContiguousCache<T> &operator=(QContiguousCache<T> &&other)
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);
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--) {
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--) {
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) {
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>
332 {
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>
347 void QContiguousCache<T>::append(const T &value)
348 {
349  if (!d->alloc)
350  return; // zero capacity
351  detach();
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>
370 void QContiguousCache<T>::prepend(const T &value)
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 
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)) {
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;
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--;
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--;
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
double d
Definition: qnumeric_p.h:62
bool operator!=(const QContiguousCache< T > &other) const
Returns true if other is not equal to this cache; otherwise returns false.
void prepend(const T &value)
Inserts value at the start of the cache.
The QContiguousCache class is a template class that provides a contiguous cache.
int alignOfTypedData() const
void removeLast()
Removes the last item from the cache.
QContiguousCacheData * d
Q_DECL_CONSTEXPR const T & qMin(const T &a, const T &b)
Definition: qglobal.h:1215
#define QT_END_NAMESPACE
This macro expands to.
Definition: qglobal.h:90
#define QT_MODULE(x)
Definition: qglobal.h:2783
int capacity() const
Returns the number of items the cache can store before it is full.
#define QT_BEGIN_HEADER
Definition: qglobal.h:136
#define at(className, varName)
~QContiguousCache()
Destroys the cache.
const T & last() const
This is an overloaded member function, provided for convenience. It differs from the above function o...
static void clear(QVariant::Private *d)
Definition: qvariant.cpp:197
static void free(QContiguousCacheData *data)
bool isFull() const
Returns true if the number of items stored within the cache is equal to the capacity of the cache...
T takeLast()
Removes the last item in the cache and returns it.
T & last()
Returns a reference to the last item in the cache.
#define Q_ASSERT(cond)
Definition: qglobal.h:1823
bool isEmpty() const
Returns true if no items are stored within the cache.
value_type * pointer
void free(Data *d)
Definition: qvector.h:458
const value_type & const_reference
int available() const
Returns the number of items that can be added to the cache before it becomes full.
QBasicAtomicInt ref
void setCapacity(int size)
Sets the capacity of the cache to the given size.
#define QT_BEGIN_NAMESPACE
This macro expands to.
Definition: qglobal.h:89
QContiguousCache< T > & operator=(const QContiguousCache< T > &other)
Assigns other to this cache and returns a reference to this cache.
static bool isEmpty(const char *str)
const T & at(int pos) const
Returns the item at index position i in the cache.
void normalizeIndexes()
Moves the first index and last index of the cache such that they point to valid indexes.
QIntegerForSizeof< void * >::Signed qptrdiff
Definition: qglobal.h:987
QContiguousCacheTypedData< T > * p
void insert(int pos, const T &value)
Inserts the value at the index position i.
QContiguousCacheData * malloc(int aalloc)
static const char * data(const QByteArray &arr)
unsigned int uint
Definition: qglobal.h:996
QContiguousCache(int capacity=0)
Constructs a cache with the given capacity.
int firstIndex() const
Returns the first valid index in the cache.
void swap(QContiguousCache< T > &other)
Swaps cache other with this cache.
void qSwap(T &value1, T &value2)
Definition: qglobal.h:2181
static QContiguousCacheData * allocate(int size, int alignment)
bool operator==(const QContiguousCache< T > &other) const
Returns true if other is equal to this cache; otherwise returns false.
static void free(QContiguousCacheTypedData *data)
int size() const
Returns the number of items contained within the cache.
#define Q_ASSERT_X(cond, where, what)
Definition: qglobal.h:1837
#define Q_CORE_EXPORT
Definition: qglobal.h:1449
bool isDetached() const
bool areIndexesValid() const
Returns whether the indexes for items stored in the cache are valid.
void removeFirst()
Removes the first item from the cache.
void free(Data *x)
bool containsIndex(int pos) const
Returns true if the cache&#39;s index range includes the given index i.
int count() const
Same as size().
T & first()
Returns a reference to the first item in the cache.
static QString dump(const QByteArray &)
void setSharable(bool sharable)
const T & first() const
This is an overloaded member function, provided for convenience. It differs from the above function o...
T & operator[](int i)
Returns the item at index position i as a modifiable reference.
T takeFirst()
Removes the first item in the cache and returns it.
void clear()
Removes all items from the cache.
const value_type * const_pointer
value_type & reference
#define QT_END_HEADER
Definition: qglobal.h:137
bool operator==(QBool b1, bool b2)
Definition: qglobal.h:2023
int size() const
Returns the number of items in the vector.
Definition: qvector.h:137
#define INT_MAX
void append(const T &value)
Inserts value at the end of the cache.
QContiguousCacheTypedData< T > Data
int lastIndex() const
Returns the last valid index in the cache.
QContiguousCache(const QContiguousCache< T > &v)
Constructs a copy of other.