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

source code of qtbase/src/corelib/tools/qcontiguouscache.h