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

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