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

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