1 /****************************************************************************
2 **
3 ** Copyright (C) 2016 The Qt Company Ltd.
4 ** Contact: https://www.qt.io/licensing/
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 The Qt Company. For licensing terms
14 ** and conditions see https://www.qt.io/terms-conditions. For further
15 ** information use the contact form at https://www.qt.io/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 3 as published by the Free Software
20 ** Foundation and appearing in the file LICENSE.LGPL3 included in the
21 ** packaging of this file. Please review the following information to
22 ** ensure the GNU Lesser General Public License version 3 requirements
23 ** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24 **
25 ** GNU General Public License Usage
26 ** Alternatively, this file may be used under the terms of the GNU
27 ** General Public License version 2.0 or (at your option) the GNU General
28 ** Public license version 3 or any later version approved by the KDE Free
29 ** Qt Foundation. The licenses are as published by the Free Software
30 ** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31 ** included in the packaging of this file. Please review the following
32 ** information to ensure the GNU General Public License requirements will
33 ** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34 ** https://www.gnu.org/licenses/gpl-3.0.html.
35 **
36 ** $QT_END_LICENSE$
37 **
38 ****************************************************************************/
39
40 #ifndef QCONTIGUOUSCACHE_H
41 #define QCONTIGUOUSCACHE_H
42
43 #include <QtCore/qatomic.h>
44 #include <limits.h>
45 #include <new>
46
47 QT_BEGIN_NAMESPACE
48
49 #undef QT_QCONTIGUOUSCACHE_DEBUG
50
51
52 struct Q_CORE_EXPORT QContiguousCacheData
53 {
54 QBasicAtomicInt ref;
55 int alloc;
56 int count;
57 int start;
58 int offset;
59 uint sharable : 1;
60 uint reserved : 31;
61
62 // total is 24 bytes (HP-UX aCC: 40 bytes)
63 // the next entry is already aligned to 8 bytes
64 // there will be an 8 byte gap here if T requires 16-byte alignment
65 // (such as long double on 64-bit platforms, __int128, __float128)
66
67 static QContiguousCacheData *allocateData(int size, int alignment);
68 static void freeData(QContiguousCacheData *data);
69
70 #ifdef QT_QCONTIGUOUSCACHE_DEBUG
71 void dump() const;
72 #endif
73 };
74
75 template <typename T>
76 struct QContiguousCacheTypedData: private QContiguousCacheData
77 {
78 // private inheritance to avoid aliasing warningss
79 T array[1];
80
freeDataQContiguousCacheTypedData81 static inline void freeData(QContiguousCacheTypedData *data) { QContiguousCacheData::freeData(data); }
82 };
83
84 template<typename T>
85 class QContiguousCache {
86 typedef QContiguousCacheTypedData<T> Data;
87 union { QContiguousCacheData *d; QContiguousCacheTypedData<T> *p; };
88 public:
89 // STL compatibility
90 typedef T value_type;
91 typedef value_type* pointer;
92 typedef const value_type* const_pointer;
93 typedef value_type& reference;
94 typedef const value_type& const_reference;
95 typedef qptrdiff difference_type;
96 typedef int size_type;
97
98 explicit QContiguousCache(int capacity = 0);
QContiguousCache(const QContiguousCache<T> & v)99 QContiguousCache(const QContiguousCache<T> &v) : d(v.d) { d->ref.ref(); if (!d->sharable) detach_helper(); }
100
~QContiguousCache()101 inline ~QContiguousCache() { if (!d) return; if (!d->ref.deref()) freeData(p); }
102
detach()103 inline void detach() { if (d->ref.loadRelaxed() != 1) detach_helper(); }
isDetached()104 inline bool isDetached() const { return d->ref.loadRelaxed() == 1; }
105 #if !defined(QT_NO_UNSHARABLE_CONTAINERS)
setSharable(bool sharable)106 inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }
107 #endif
108
109 QContiguousCache<T> &operator=(const QContiguousCache<T> &other);
110 inline QContiguousCache<T> &operator=(QContiguousCache<T> &&other) noexcept
111 { qSwap(d, other.d); return *this; }
swap(QContiguousCache<T> & other)112 inline void swap(QContiguousCache<T> &other) noexcept { qSwap(d, other.d); }
113 bool operator==(const QContiguousCache<T> &other) const;
114 inline bool operator!=(const QContiguousCache<T> &other) const { return !(*this == other); }
115
capacity()116 inline int capacity() const {return d->alloc; }
count()117 inline int count() const { return d->count; }
size()118 inline int size() const { return d->count; }
119
isEmpty()120 inline bool isEmpty() const { return d->count == 0; }
isFull()121 inline bool isFull() const { return d->count == d->alloc; }
available()122 inline int available() const { return d->alloc - d->count; }
123
124 void clear();
125 void setCapacity(int size);
126
127 const T &at(int pos) const;
128 T &operator[](int i);
129 const T &operator[](int i) const;
130
131 void append(const T &value);
132 void prepend(const T &value);
133 void insert(int pos, const T &value);
134
containsIndex(int pos)135 inline bool containsIndex(int pos) const { return pos >= d->offset && pos - d->offset < d->count; }
firstIndex()136 inline int firstIndex() const { return d->offset; }
lastIndex()137 inline int lastIndex() const { return d->offset + d->count - 1; }
138
first()139 inline const T &first() const { Q_ASSERT(!isEmpty()); return p->array[d->start]; }
last()140 inline const T &last() const { Q_ASSERT(!isEmpty()); return p->array[(d->start + d->count -1) % d->alloc]; }
first()141 inline T &first() { Q_ASSERT(!isEmpty()); detach(); return p->array[d->start]; }
last()142 inline T &last() { Q_ASSERT(!isEmpty()); detach(); return p->array[(d->start + d->count -1) % d->alloc]; }
143
144 void removeFirst();
145 T takeFirst();
146 void removeLast();
147 T takeLast();
148
areIndexesValid()149 inline bool areIndexesValid() const
150 { return d->offset >= 0 && d->offset < INT_MAX - d->count && (d->offset % d->alloc) == d->start; }
151
normalizeIndexes()152 inline void normalizeIndexes() { d->offset = d->start; }
153
154 #ifdef QT_QCONTIGUOUSCACHE_DEBUG
dump()155 void dump() const { p->dump(); }
156 #endif
157 private:
158 void detach_helper();
159
160 QContiguousCacheData *allocateData(int aalloc);
161 void freeData(Data *x);
sizeOfTypedData()162 int sizeOfTypedData() {
163 // this is more or less the same as sizeof(Data), except that it doesn't
164 // count the padding at the end
165 return reinterpret_cast<const char *>(&(reinterpret_cast<const Data *>(this))->array[1]) - reinterpret_cast<const char *>(this);
166 }
alignOfTypedData()167 int alignOfTypedData() const
168 {
169 return qMax<int>(sizeof(void*), Q_ALIGNOF(Data));
170 }
171 };
172
173 template <typename T>
detach_helper()174 void QContiguousCache<T>::detach_helper()
175 {
176 union { QContiguousCacheData *d; QContiguousCacheTypedData<T> *p; } x;
177
178 x.d = allocateData(d->alloc);
179 x.d->ref.storeRelaxed(1);
180 x.d->count = d->count;
181 x.d->start = d->start;
182 x.d->offset = d->offset;
183 x.d->alloc = d->alloc;
184 x.d->sharable = true;
185 x.d->reserved = 0;
186
187 T *dest = x.p->array + x.d->start;
188 T *src = p->array + d->start;
189 int oldcount = x.d->count;
190 while (oldcount--) {
191 if (QTypeInfo<T>::isComplex) {
192 new (dest) T(*src);
193 } else {
194 *dest = *src;
195 }
196 dest++;
197 if (dest == x.p->array + x.d->alloc)
198 dest = x.p->array;
199 src++;
200 if (src == p->array + d->alloc)
201 src = p->array;
202 }
203
204 if (!d->ref.deref())
205 freeData(p);
206 d = x.d;
207 }
208
209 template <typename T>
setCapacity(int asize)210 void QContiguousCache<T>::setCapacity(int asize)
211 {
212 Q_ASSERT(asize >= 0);
213 if (asize == d->alloc)
214 return;
215 detach();
216 union { QContiguousCacheData *d; QContiguousCacheTypedData<T> *p; } x;
217 x.d = allocateData(asize);
218 x.d->ref.storeRelaxed(1);
219 x.d->alloc = asize;
220 x.d->count = qMin(d->count, asize);
221 x.d->offset = d->offset + d->count - x.d->count;
222 if(asize)
223 x.d->start = x.d->offset % x.d->alloc;
224 else
225 x.d->start = 0;
226
227 int oldcount = x.d->count;
228 if(oldcount)
229 {
230 T *dest = x.p->array + (x.d->start + x.d->count-1) % x.d->alloc;
231 T *src = p->array + (d->start + d->count-1) % d->alloc;
232 while (oldcount--) {
233 if (QTypeInfo<T>::isComplex) {
234 new (dest) T(*src);
235 } else {
236 *dest = *src;
237 }
238 if (dest == x.p->array)
239 dest = x.p->array + x.d->alloc;
240 dest--;
241 if (src == p->array)
242 src = p->array + d->alloc;
243 src--;
244 }
245 }
246 /* free old */
247 freeData(p);
248 d = x.d;
249 }
250
251 template <typename T>
clear()252 void QContiguousCache<T>::clear()
253 {
254 if (d->ref.loadRelaxed() == 1) {
255 if (QTypeInfo<T>::isComplex) {
256 int oldcount = d->count;
257 T * i = p->array + d->start;
258 T * e = p->array + d->alloc;
259 while (oldcount--) {
260 i->~T();
261 i++;
262 if (i == e)
263 i = p->array;
264 }
265 }
266 d->count = d->start = d->offset = 0;
267 } else {
268 union { QContiguousCacheData *d; QContiguousCacheTypedData<T> *p; } x;
269 x.d = allocateData(d->alloc);
270 x.d->ref.storeRelaxed(1);
271 x.d->alloc = d->alloc;
272 x.d->count = x.d->start = x.d->offset = 0;
273 x.d->sharable = true;
274 if (!d->ref.deref()) freeData(p);
275 d = x.d;
276 }
277 }
278
279 template <typename T>
allocateData(int aalloc)280 inline QContiguousCacheData *QContiguousCache<T>::allocateData(int aalloc)
281 {
282 return QContiguousCacheData::allocateData(sizeOfTypedData() + (aalloc - 1) * sizeof(T), alignOfTypedData());
283 }
284
285 template <typename T>
QContiguousCache(int cap)286 QContiguousCache<T>::QContiguousCache(int cap)
287 {
288 Q_ASSERT(cap >= 0);
289 d = allocateData(cap);
290 d->ref.storeRelaxed(1);
291 d->alloc = cap;
292 d->count = d->start = d->offset = 0;
293 d->sharable = true;
294 }
295
296 template <typename T>
297 QContiguousCache<T> &QContiguousCache<T>::operator=(const QContiguousCache<T> &other)
298 {
299 other.d->ref.ref();
300 if (!d->ref.deref())
301 freeData(p);
302 d = other.d;
303 if (!d->sharable)
304 detach_helper();
305 return *this;
306 }
307
308 template <typename T>
309 bool QContiguousCache<T>::operator==(const QContiguousCache<T> &other) const
310 {
311 if (other.d == d)
312 return true;
313 if (other.d->start != d->start
314 || other.d->count != d->count
315 || other.d->offset != d->offset
316 || other.d->alloc != d->alloc)
317 return false;
318 for (int i = firstIndex(); i <= lastIndex(); ++i)
319 if (!(at(i) == other.at(i)))
320 return false;
321 return true;
322 }
323
324 template <typename T>
freeData(Data * x)325 void QContiguousCache<T>::freeData(Data *x)
326 {
327 if (QTypeInfo<T>::isComplex) {
328 int oldcount = d->count;
329 T * i = p->array + d->start;
330 T * e = p->array + d->alloc;
331 while (oldcount--) {
332 i->~T();
333 i++;
334 if (i == e)
335 i = p->array;
336 }
337 }
338 x->freeData(x);
339 }
340 template <typename T>
append(const T & value)341 void QContiguousCache<T>::append(const T &value)
342 {
343 if (!d->alloc)
344 return; // zero capacity
345 detach();
346 if (QTypeInfo<T>::isComplex) {
347 if (d->count == d->alloc)
348 (p->array + (d->start+d->count) % d->alloc)->~T();
349 new (p->array + (d->start+d->count) % d->alloc) T(value);
350 } else {
351 p->array[(d->start+d->count) % d->alloc] = value;
352 }
353
354 if (d->count == d->alloc) {
355 d->start++;
356 d->start %= d->alloc;
357 d->offset++;
358 } else {
359 d->count++;
360 }
361 }
362
363 template<typename T>
prepend(const T & value)364 void QContiguousCache<T>::prepend(const T &value)
365 {
366 if (!d->alloc)
367 return; // zero capacity
368 detach();
369 if (d->start)
370 d->start--;
371 else
372 d->start = d->alloc-1;
373 d->offset--;
374
375 if (d->count != d->alloc)
376 d->count++;
377 else
378 if (d->count == d->alloc)
379 (p->array + d->start)->~T();
380
381 if (QTypeInfo<T>::isComplex)
382 new (p->array + d->start) T(value);
383 else
384 p->array[d->start] = value;
385 }
386
387 template<typename T>
insert(int pos,const T & value)388 void QContiguousCache<T>::insert(int pos, const T &value)
389 {
390 Q_ASSERT_X(pos >= 0 && pos < INT_MAX, "QContiguousCache<T>::insert", "index out of range");
391 if (!d->alloc)
392 return; // zero capacity
393 detach();
394 if (containsIndex(pos)) {
395 if (QTypeInfo<T>::isComplex) {
396 (p->array + pos % d->alloc)->~T();
397 new (p->array + pos % d->alloc) T(value);
398 } else {
399 p->array[pos % d->alloc] = value;
400 }
401 } else if (pos == d->offset-1)
402 prepend(value);
403 else if (pos == d->offset+d->count)
404 append(value);
405 else {
406 // we don't leave gaps.
407 clear();
408 d->offset = pos;
409 d->start = pos % d->alloc;
410 d->count = 1;
411 if (QTypeInfo<T>::isComplex)
412 new (p->array + d->start) T(value);
413 else
414 p->array[d->start] = value;
415 }
416 }
417
418 template <typename T>
at(int pos)419 inline const T &QContiguousCache<T>::at(int pos) const
420 { Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache<T>::at", "index out of range"); return p->array[pos % d->alloc]; }
421 template <typename T>
422 inline const T &QContiguousCache<T>::operator[](int pos) const
423 { Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache<T>::at", "index out of range"); return p->array[pos % d->alloc]; }
424
425 template <typename T>
426 inline T &QContiguousCache<T>::operator[](int pos)
427 {
428 detach();
429 if (!containsIndex(pos))
430 insert(pos, T());
431 return p->array[pos % d->alloc];
432 }
433
434 template <typename T>
removeFirst()435 inline void QContiguousCache<T>::removeFirst()
436 {
437 Q_ASSERT(d->count > 0);
438 detach();
439 d->count--;
440 if (QTypeInfo<T>::isComplex)
441 (p->array + d->start)->~T();
442 d->start = (d->start + 1) % d->alloc;
443 d->offset++;
444 }
445
446 template <typename T>
removeLast()447 inline void QContiguousCache<T>::removeLast()
448 {
449 Q_ASSERT(d->count > 0);
450 detach();
451 d->count--;
452 if (QTypeInfo<T>::isComplex)
453 (p->array + (d->start + d->count) % d->alloc)->~T();
454 }
455
456 template <typename T>
takeFirst()457 inline T QContiguousCache<T>::takeFirst()
458 { T t = first(); removeFirst(); return t; }
459
460 template <typename T>
takeLast()461 inline T QContiguousCache<T>::takeLast()
462 { T t = last(); removeLast(); return t; }
463
464 QT_END_NAMESPACE
465
466 #endif
467