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
49QT_BEGIN_HEADER
50
51QT_BEGIN_NAMESPACE
52
53#undef QT_QCONTIGUOUSCACHE_DEBUG
54QT_MODULE(Core)
55
56
57struct Q_CORE_EXPORT QContiguousCacheData
58{
59 QBasicAtomicInt ref;
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
80template <typename T>
81struct QContiguousCacheTypedData: private QContiguousCacheData
82{
83 // private inheritance to avoid aliasing warningss
84 T array[1];
85
86 static inline void free(QContiguousCacheTypedData *data) { QContiguousCacheData::free(data); }
87};
88
89template<typename T>
90class QContiguousCache {
91 typedef QContiguousCacheTypedData<T> Data;
92 union { QContiguousCacheData *d; QContiguousCacheTypedData<T> *p; };
93public:
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
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
162private:
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
182template <typename T>
183void QContiguousCache<T>::detach_helper()
184{
185 union { QContiguousCacheData *d; QContiguousCacheTypedData<T> *p; } x;
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
218template <typename T>
219void QContiguousCache<T>::setCapacity(int asize)
220{
221 if (asize == d->alloc)
222 return;
223 detach();
224 union { QContiguousCacheData *d; QContiguousCacheTypedData<T> *p; } x;
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
258template <typename T>
259void QContiguousCache<T>::clear()
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 {
275 union { QContiguousCacheData *d; QContiguousCacheTypedData<T> *p; } x;
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
286template <typename T>
287inline QContiguousCacheData *QContiguousCache<T>::malloc(int aalloc)
288{
289 return QContiguousCacheData::allocate(sizeOfTypedData() + (aalloc - 1) * sizeof(T), alignOfTypedData());
290}
291
292template <typename T>
293QContiguousCache<T>::QContiguousCache(int cap)
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
302template <typename T>
303QContiguousCache<T> &QContiguousCache<T>::operator=(const QContiguousCache<T> &other)
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
314template <typename T>
315bool QContiguousCache<T>::operator==(const QContiguousCache<T> &other) const
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
330template <typename T>
331void 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}
346template <typename T>
347void QContiguousCache<T>::append(const T &value)
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
369template<typename T>
370void 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
387 if (QTypeInfo<T>::isComplex)
388 new (p->array + d->start) T(value);
389 else
390 p->array[d->start] = value;
391}
392
393template<typename T>
394void 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
424template <typename T>
425inline 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]; }
427template <typename T>
428inline 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
431template <typename T>
432inline T &QContiguousCache<T>::operator[](int pos)
433{
434 detach();
435 if (!containsIndex(pos))
436 insert(pos, T());
437 return p->array[pos % d->alloc];
438}
439
440template <typename T>
441inline void QContiguousCache<T>::removeFirst()
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
452template <typename T>
453inline void QContiguousCache<T>::removeLast()
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
462template <typename T>
463inline T QContiguousCache<T>::takeFirst()
464{ T t = first(); removeFirst(); return t; }
465
466template <typename T>
467inline T QContiguousCache<T>::takeLast()
468{ T t = last(); removeLast(); return t; }
469
470QT_END_NAMESPACE
471
472QT_END_HEADER
473
474#endif
475