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
47QT_BEGIN_NAMESPACE
48
49#undef QT_QCONTIGUOUSCACHE_DEBUG
50
51
52struct Q_CORE_EXPORT QContiguousCacheData
53{
54 QBasicAtomicInt ref;
55 qsizetype alloc;
56 qsizetype count;
57 qsizetype start;
58 qsizetype offset;
59
60 static QContiguousCacheData *allocateData(qsizetype size, qsizetype alignment);
61 static void freeData(QContiguousCacheData *data);
62
63#ifdef QT_QCONTIGUOUSCACHE_DEBUG
64 void dump() const;
65#endif
66};
67
68template <typename T>
69struct QContiguousCacheTypedData : public QContiguousCacheData
70{
71 T array[1];
72};
73
74template<typename T>
75class QContiguousCache {
76 typedef QContiguousCacheTypedData<T> Data;
77 Data *d;
78public:
79 // STL compatibility
80 typedef T value_type;
81 typedef value_type* pointer;
82 typedef const value_type* const_pointer;
83 typedef value_type& reference;
84 typedef const value_type& const_reference;
85 typedef qptrdiff difference_type;
86 typedef qsizetype size_type;
87
88 explicit QContiguousCache(qsizetype capacity = 0);
89 QContiguousCache(const QContiguousCache<T> &v) : d(v.d) { d->ref.ref(); }
90
91 inline ~QContiguousCache() { if (!d) return; if (!d->ref.deref()) freeData(d); }
92
93 inline void detach() { if (d->ref.loadRelaxed() != 1) detach_helper(); }
94 inline bool isDetached() const { return d->ref.loadRelaxed() == 1; }
95
96 QContiguousCache<T> &operator=(const QContiguousCache<T> &other);
97 QT_MOVE_ASSIGNMENT_OPERATOR_IMPL_VIA_PURE_SWAP(QContiguousCache)
98 inline void swap(QContiguousCache<T> &other) noexcept { qSwap(d, other.d); }
99
100 template <typename U = T>
101 QTypeTraits::compare_eq_result<U> operator==(const QContiguousCache<T> &other) const
102 {
103 if (other.d == d)
104 return true;
105 if (other.d->start != d->start
106 || other.d->count != d->count
107 || other.d->offset != d->offset
108 || other.d->alloc != d->alloc)
109 return false;
110 for (qsizetype i = firstIndex(); i <= lastIndex(); ++i)
111 if (!(at(i) == other.at(i)))
112 return false;
113 return true;
114 }
115 template <typename U = T>
116 QTypeTraits::compare_eq_result<U> operator!=(const QContiguousCache<T> &other) const
117 { return !(*this == other); }
118
119 inline qsizetype capacity() const {return d->alloc; }
120 inline qsizetype count() const { return d->count; }
121 inline qsizetype size() const { return d->count; }
122
123 inline bool isEmpty() const { return d->count == 0; }
124 inline bool isFull() const { return d->count == d->alloc; }
125 inline qsizetype available() const { return d->alloc - d->count; }
126
127 void clear();
128 void setCapacity(qsizetype size);
129
130 const T &at(qsizetype pos) const;
131 T &operator[](qsizetype i);
132 const T &operator[](qsizetype i) const;
133
134 void append(T &&value);
135 void append(const T &value);
136 void prepend(T &&value);
137 void prepend(const T &value);
138 void insert(qsizetype pos, T &&value);
139 void insert(qsizetype pos, const T &value);
140
141
142 inline bool containsIndex(qsizetype pos) const { return pos >= d->offset && pos - d->offset < d->count; }
143 inline qsizetype firstIndex() const { return d->offset; }
144 inline qsizetype lastIndex() const { return d->offset + d->count - 1; }
145
146 inline const T &first() const { Q_ASSERT(!isEmpty()); return d->array[d->start]; }
147 inline const T &last() const { Q_ASSERT(!isEmpty()); return d->array[(d->start + d->count -1) % d->alloc]; }
148 inline T &first() { Q_ASSERT(!isEmpty()); detach(); return d->array[d->start]; }
149 inline T &last() { Q_ASSERT(!isEmpty()); detach(); return d->array[(d->start + d->count -1) % d->alloc]; }
150
151 void removeFirst();
152 T takeFirst();
153 void removeLast();
154 T takeLast();
155
156 // Use extra parentheses around max to avoid expanding it if it is a macro.
157 inline bool areIndexesValid() const
158 { return d->offset >= 0 && d->offset < (std::numeric_limits<qsizetype>::max)() - d->count && (d->offset % d->alloc) == d->start; }
159
160 inline void normalizeIndexes() { d->offset = d->start; }
161
162#ifdef QT_QCONTIGUOUSCACHE_DEBUG
163 void dump() const { d->dump(); }
164#endif
165private:
166 void detach_helper();
167
168 Data *allocateData(qsizetype aalloc);
169 void freeData(Data *x);
170};
171
172template <typename T>
173void QContiguousCache<T>::detach_helper()
174{
175 Data *x = allocateData(d->alloc);
176 x->ref.storeRelaxed(1);
177 x->count = d->count;
178 x->start = d->start;
179 x->offset = d->offset;
180 x->alloc = d->alloc;
181
182 T *dest = x->array + x->start;
183 T *src = d->array + d->start;
184 qsizetype oldcount = x->count;
185 while (oldcount--) {
186 new (dest) T(*src);
187 dest++;
188 if (dest == x->array + x->alloc)
189 dest = x->array;
190 src++;
191 if (src == d->array + d->alloc)
192 src = d->array;
193 }
194
195 if (!d->ref.deref())
196 freeData(d);
197 d = x;
198}
199
200template <typename T>
201void QContiguousCache<T>::setCapacity(qsizetype asize)
202{
203 Q_ASSERT(asize >= 0);
204 if (asize == d->alloc)
205 return;
206 detach();
207 Data *x = allocateData(asize);
208 x->ref.storeRelaxed(1);
209 x->alloc = asize;
210 x->count = qMin(d->count, asize);
211 x->offset = d->offset + d->count - x->count;
212 if(asize)
213 x->start = x->offset % x->alloc;
214 else
215 x->start = 0;
216
217 qsizetype oldcount = x->count;
218 if(oldcount)
219 {
220 T *dest = x->array + (x->start + x->count-1) % x->alloc;
221 T *src = d->array + (d->start + d->count-1) % d->alloc;
222 while (oldcount--) {
223 new (dest) T(*src);
224 if (dest == x->array)
225 dest = x->array + x->alloc;
226 dest--;
227 if (src == d->array)
228 src = d->array + d->alloc;
229 src--;
230 }
231 }
232 /* free old */
233 freeData(d);
234 d = x;
235}
236
237template <typename T>
238void QContiguousCache<T>::clear()
239{
240 if (d->ref.loadRelaxed() == 1) {
241 if (QTypeInfo<T>::isComplex) {
242 qsizetype oldcount = d->count;
243 T * i = d->array + d->start;
244 T * e = d->array + d->alloc;
245 while (oldcount--) {
246 i->~T();
247 i++;
248 if (i == e)
249 i = d->array;
250 }
251 }
252 d->count = d->start = d->offset = 0;
253 } else {
254 Data *x = allocateData(d->alloc);
255 x->ref.storeRelaxed(1);
256 x->alloc = d->alloc;
257 x->count = x->start = x->offset = 0;
258 if (!d->ref.deref())
259 freeData(d);
260 d = x;
261 }
262}
263
264template <typename T>
265inline typename QContiguousCache<T>::Data *QContiguousCache<T>::allocateData(qsizetype aalloc)
266{
267 return static_cast<Data *>(QContiguousCacheData::allocateData(sizeof(Data) + (aalloc - 1) * sizeof(T), alignof(Data)));
268}
269
270template <typename T>
271QContiguousCache<T>::QContiguousCache(qsizetype cap)
272{
273 Q_ASSERT(cap >= 0);
274 d = allocateData(cap);
275 d->ref.storeRelaxed(1);
276 d->alloc = cap;
277 d->count = d->start = d->offset = 0;
278}
279
280template <typename T>
281QContiguousCache<T> &QContiguousCache<T>::operator=(const QContiguousCache<T> &other)
282{
283 other.d->ref.ref();
284 if (!d->ref.deref())
285 freeData(d);
286 d = other.d;
287 return *this;
288}
289
290template <typename T>
291void QContiguousCache<T>::freeData(Data *x)
292{
293 if (QTypeInfo<T>::isComplex) {
294 qsizetype oldcount = d->count;
295 T * i = d->array + d->start;
296 T * e = d->array + d->alloc;
297 while (oldcount--) {
298 i->~T();
299 i++;
300 if (i == e)
301 i = d->array;
302 }
303 }
304 Data::freeData(x);
305}
306template <typename T>
307void QContiguousCache<T>::append(T &&value)
308{
309 if (!d->alloc)
310 return; // zero capacity
311 detach();
312 if (d->count == d->alloc)
313 (d->array + (d->start+d->count) % d->alloc)->~T();
314 new (d->array + (d->start+d->count) % d->alloc) T(std::move(value));
315
316 if (d->count == d->alloc) {
317 d->start++;
318 d->start %= d->alloc;
319 d->offset++;
320 } else {
321 d->count++;
322 }
323}
324
325template <typename T>
326void QContiguousCache<T>::append(const T &value)
327{
328 if (!d->alloc)
329 return; // zero capacity
330 detach();
331 if (d->count == d->alloc)
332 (d->array + (d->start+d->count) % d->alloc)->~T();
333 new (d->array + (d->start+d->count) % d->alloc) T(value);
334
335 if (d->count == d->alloc) {
336 d->start++;
337 d->start %= d->alloc;
338 d->offset++;
339 } else {
340 d->count++;
341 }
342}
343
344template<typename T>
345void QContiguousCache<T>::prepend(T &&value)
346{
347 if (!d->alloc)
348 return; // zero capacity
349 detach();
350 if (d->start)
351 d->start--;
352 else
353 d->start = d->alloc-1;
354 d->offset--;
355
356 if (d->count != d->alloc)
357 d->count++;
358 else
359 if (d->count == d->alloc)
360 (d->array + d->start)->~T();
361
362 new (d->array + d->start) T(std::move(value));
363}
364
365template<typename T>
366void QContiguousCache<T>::prepend(const T &value)
367{
368 if (!d->alloc)
369 return; // zero capacity
370 detach();
371 if (d->start)
372 d->start--;
373 else
374 d->start = d->alloc-1;
375 d->offset--;
376
377 if (d->count != d->alloc)
378 d->count++;
379 else
380 if (d->count == d->alloc)
381 (d->array + d->start)->~T();
382
383 new (d->array + d->start) T(value);
384}
385
386template<typename T>
387void QContiguousCache<T>::insert(qsizetype pos, T &&value)
388{
389 Q_ASSERT_X(pos >= 0, "QContiguousCache<T>::insert", "index out of range");
390 if (!d->alloc)
391 return; // zero capacity
392 detach();
393 if (containsIndex(pos)) {
394 d->array[pos % d->alloc] = std::move(value);
395 } else if (pos == d->offset-1)
396 prepend(value);
397 else if (pos == d->offset+d->count)
398 append(value);
399 else {
400 // we don't leave gaps.
401 clear();
402 d->offset = pos;
403 d->start = pos % d->alloc;
404 d->count = 1;
405 new (d->array + d->start) T(std::move(value));
406 }
407}
408
409template<typename T>
410void QContiguousCache<T>::insert(qsizetype pos, const T &value)
411{
412 return insert(pos, T(value));
413}
414template <typename T>
415inline const T &QContiguousCache<T>::at(qsizetype pos) const
416{ Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache<T>::at", "index out of range"); return d->array[pos % d->alloc]; }
417template <typename T>
418inline const T &QContiguousCache<T>::operator[](qsizetype pos) const
419{ return at(pos); }
420
421template <typename T>
422inline T &QContiguousCache<T>::operator[](qsizetype pos)
423{
424 detach();
425 if (!containsIndex(pos))
426 insert(pos, T());
427 return d->array[pos % d->alloc];
428}
429
430template <typename T>
431inline void QContiguousCache<T>::removeFirst()
432{
433 Q_ASSERT(d->count > 0);
434 detach();
435 d->count--;
436 if (QTypeInfo<T>::isComplex)
437 (d->array + d->start)->~T();
438 d->start = (d->start + 1) % d->alloc;
439 d->offset++;
440}
441
442template <typename T>
443inline void QContiguousCache<T>::removeLast()
444{
445 Q_ASSERT(d->count > 0);
446 detach();
447 d->count--;
448 if (QTypeInfo<T>::isComplex)
449 (d->array + (d->start + d->count) % d->alloc)->~T();
450}
451
452template <typename T>
453inline T QContiguousCache<T>::takeFirst()
454{ T t = std::move(first()); removeFirst(); return t; }
455
456template <typename T>
457inline T QContiguousCache<T>::takeLast()
458{ T t = std::move(last()); removeLast(); return t; }
459
460QT_END_NAMESPACE
461
462#endif
463