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 | |
18 | QT_BEGIN_NAMESPACE |
19 | |
20 | #undef QT_QCONTIGUOUSCACHE_DEBUG |
21 | |
22 | |
23 | struct 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 | |
39 | template <typename T> |
40 | struct QContiguousCacheTypedData : public QContiguousCacheData |
41 | { |
42 | T array[1]; |
43 | }; |
44 | |
45 | template<typename T> |
46 | class 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; |
51 | public: |
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 |
143 | private: |
144 | void detach_helper(); |
145 | |
146 | Data *allocateData(qsizetype aalloc); |
147 | void freeData(Data *x); |
148 | }; |
149 | |
150 | template <typename T> |
151 | void 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 | |
178 | template <typename T> |
179 | void 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 | |
215 | template <typename T> |
216 | void 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 | |
242 | template <typename T> |
243 | inline 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 | |
248 | template <typename T> |
249 | QContiguousCache<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 | |
258 | template <typename T> |
259 | QContiguousCache<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 | |
268 | template <typename T> |
269 | void 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 | } |
284 | template <typename T> |
285 | void 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 | |
303 | template <typename T> |
304 | void 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 | |
322 | template<typename T> |
323 | void 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 | |
342 | template<typename T> |
343 | void 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 | |
362 | template<typename T> |
363 | void 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 | |
385 | template<typename T> |
386 | void QContiguousCache<T>::insert(qsizetype pos, const T &value) |
387 | { |
388 | return insert(pos, T(value)); |
389 | } |
390 | template <typename T> |
391 | inline 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]; } |
393 | template <typename T> |
394 | inline const T &QContiguousCache<T>::operator[](qsizetype pos) const |
395 | { return at(pos); } |
396 | |
397 | template <typename T> |
398 | inline 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 | |
406 | template <typename T> |
407 | inline 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 | |
418 | template <typename T> |
419 | inline 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 | |
428 | template <typename T> |
429 | inline T QContiguousCache<T>::takeFirst() |
430 | { T t = std::move(first()); removeFirst(); return t; } |
431 | |
432 | template <typename T> |
433 | inline T QContiguousCache<T>::takeLast() |
434 | { T t = std::move(last()); removeLast(); return t; } |
435 | |
436 | QT_END_NAMESPACE |
437 | |
438 | #endif |
439 |
Definitions
- QContiguousCacheData
- QContiguousCacheTypedData
- QContiguousCache
- QContiguousCache
- ~QContiguousCache
- detach
- isDetached
- swap
- operator==
- operator!=
- capacity
- count
- size
- isEmpty
- isFull
- available
- containsIndex
- firstIndex
- lastIndex
- first
- last
- first
- last
- areIndexesValid
- normalizeIndexes
- detach_helper
- setCapacity
- clear
- allocateData
- QContiguousCache
- operator=
- freeData
- append
- append
- prepend
- prepend
- insert
- insert
- at
- operator[]
- operator[]
- removeFirst
- removeLast
- takeFirst
Learn Advanced QML with KDAB
Find out more