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#include "qcontiguouscache.h"
5#ifdef QT_QCONTIGUOUSCACHE_DEBUG
6#include <QDebug>
7#endif
8
9#include <QtCore/qmalloc.h>
10
11QT_BEGIN_NAMESPACE
12
13#ifdef QT_QCONTIGUOUSCACHE_DEBUG
14void QContiguousCacheData::dump() const
15{
16 qDebug() << "capacity:" << alloc;
17 qDebug() << "count:" << count;
18 qDebug() << "start:" << start;
19 qDebug() << "offset:" << offset;
20}
21#endif
22
23QContiguousCacheData *QContiguousCacheData::allocateData(qsizetype size, qsizetype alignment)
24{
25 return static_cast<QContiguousCacheData *>(qMallocAligned(size: size_t(size), alignment: size_t(alignment)));
26}
27
28void QContiguousCacheData::freeData(QContiguousCacheData *data)
29{
30 qFreeAligned(ptr: data);
31}
32
33/*! \class QContiguousCache
34 \inmodule QtCore
35 \brief The QContiguousCache class is a template class that provides a contiguous cache.
36 \ingroup tools
37 \ingroup shared
38 \reentrant
39 \since 4.6
40
41 The QContiguousCache class provides an efficient way of caching items for
42 display in a user interface view. Unlike QCache, it adds a restriction
43 that elements within the cache are contiguous. This has the advantage
44 of matching how user interface views most commonly request data, as
45 a set of rows localized around the current scrolled position. This
46 restriction allows the cache to consume less memory and processor
47 cycles than QCache.
48
49 QContiguousCache operates on a fixed capacity, set with setCapacity() or
50 passed as a parameter to the constructor. This capacity is the upper bound
51 on memory usage by the cache itself, not including the memory allocated by
52 the elements themselves. Note that a cache with a capacity of zero (the
53 default) means no items will be stored: the insert(), append() and
54 prepend() operations will effectively be no-ops. Therefore, it's important
55 to set the capacity to a reasonable value before adding items to the cache.
56
57 The simplest way of using a contiguous cache is to use the append()
58 and prepend().
59
60 \snippet code/src_corelib_tools_qcontiguouscache.cpp 0
61
62 If the cache is full then the item at the opposite end of the cache from
63 where the new item is appended or prepended will be removed.
64
65 This usage can be further optimized by using the insert() function
66 in the case where the requested row is a long way from the currently cached
67 items. If there is a gap between where the new item is inserted and the currently
68 cached items then the existing cached items are first removed to retain
69 the contiguous nature of the cache. Hence it is important to take some care then
70 when using insert() in order to avoid unwanted clearing of the cache.
71
72 The range of valid indexes for the QContiguousCache class are from
73 0 to INT_MAX. Calling prepend() such that the first index would become less
74 than 0 or append() such that the last index would become greater
75 than INT_MAX can result in the indexes of the cache being invalid.
76 When the cache indexes are invalid it is important to call
77 normalizeIndexes() before calling any of containsIndex(), firstIndex(),
78 lastIndex(), at() or \l{QContiguousCache::operator[]()}{operator[]()}.
79 Calling these functions when the cache has invalid indexes will result in
80 undefined behavior. The indexes can be checked by using areIndexesValid()
81
82 In most cases the indexes will not exceed 0 to INT_MAX, and
83 normalizeIndexes() will not need to be used.
84
85 See the \l{Contiguous Cache Example}{Contiguous Cache} example.
86*/
87
88/*! \fn template<typename T> QContiguousCache<T>::QContiguousCache(qsizetype capacity)
89
90 Constructs a cache with the given \a capacity.
91
92 \sa setCapacity()
93*/
94
95/*! \fn template<typename T> QContiguousCache<T>::QContiguousCache(const QContiguousCache<T> &other)
96
97 Constructs a copy of \a other.
98
99 This operation takes \l{constant time}, because QContiguousCache is
100 \l{implicitly shared}. This makes returning a QContiguousCache from a
101 function very fast. If a shared instance is modified, it will be
102 copied (copy-on-write), and that takes \l{linear time}.
103
104 \sa operator=()
105*/
106
107/*! \fn template<typename T> QContiguousCache<T>::~QContiguousCache()
108
109 Destroys the cache.
110*/
111
112/*! \fn template<typename T> void QContiguousCache<T>::detach()
113 \internal
114*/
115
116/*! \fn template<typename T> bool QContiguousCache<T>::isDetached() const
117 \internal
118*/
119
120/*! \fn template<typename T> void QContiguousCache<T>::setSharable(bool sharable)
121 \internal
122*/
123
124/*! \typedef QContiguousCache::value_type
125 \internal
126 */
127
128/*! \typedef QContiguousCache::pointer
129 \internal
130 */
131
132/*! \typedef QContiguousCache::const_pointer
133 \internal
134 */
135
136/*! \typedef QContiguousCache::reference
137 \internal
138 */
139
140/*! \typedef QContiguousCache::const_reference
141 \internal
142 */
143
144/*! \typedef QContiguousCache::difference_type
145 \internal
146 */
147
148/*! \typedef QContiguousCache::size_type
149 \internal
150 */
151
152/*! \fn template<typename T> QContiguousCache<T> &QContiguousCache<T>::operator=(const QContiguousCache<T> &other)
153
154 Assigns \a other to this cache and returns a reference to this cache.
155*/
156
157/*!
158 \fn template<typename T> QContiguousCache<T> &QContiguousCache<T>::operator=(QContiguousCache<T> &&other)
159
160 Move-assigns \a other to this QContiguousCache instance.
161
162 \since 5.2
163*/
164
165/*! \fn template<typename T> void QContiguousCache<T>::swap(QContiguousCache<T> &other)
166 \since 4.8
167
168 Swaps cache \a other with this cache. This operation is very
169 fast and never fails.
170*/
171
172/*! \fn template<typename T> bool QContiguousCache<T>::operator==(const QContiguousCache<T> &other) const
173
174 Returns \c true if \a other is equal to this cache; otherwise returns \c false.
175
176 Two caches are considered equal if they contain the same values at the same
177 indexes. This function requires the value type to implement the \c operator==().
178
179 \sa operator!=()
180*/
181
182/*! \fn template<typename T> bool QContiguousCache<T>::operator!=(const QContiguousCache<T> &other) const
183
184 Returns \c true if \a other is not equal to this cache; otherwise
185 returns \c false.
186
187 Two caches are considered equal if they contain the same values at the same
188 indexes. This function requires the value type to implement the \c operator==().
189
190 \sa operator==()
191*/
192
193/*! \fn template<typename T> qsizetype QContiguousCache<T>::capacity() const
194
195 Returns the number of items the cache can store before it is full.
196 When a cache contains a number of items equal to its capacity, adding new
197 items will cause items farthest from the added item to be removed.
198
199 \sa setCapacity(), size()
200*/
201
202/*! \fn template<typename T> qsizetype QContiguousCache<T>::count() const
203
204 Same as size().
205*/
206
207/*! \fn template<typename T> qsizetype QContiguousCache<T>::size() const
208
209 Returns the number of items contained within the cache.
210
211 \sa capacity()
212*/
213
214/*! \fn template<typename T> bool QContiguousCache<T>::isEmpty() const
215
216 Returns \c true if no items are stored within the cache.
217
218 \sa size(), capacity()
219*/
220
221/*! \fn template<typename T> bool QContiguousCache<T>::isFull() const
222
223 Returns \c true if the number of items stored within the cache is equal
224 to the capacity of the cache.
225
226 \sa size(), capacity()
227*/
228
229/*! \fn template<typename T> qsizetype QContiguousCache<T>::available() const
230
231 Returns the number of items that can be added to the cache before it becomes full.
232
233 \sa size(), capacity(), isFull()
234*/
235
236/*! \fn template<typename T> void QContiguousCache<T>::clear()
237
238 Removes all items from the cache. The capacity is unchanged.
239*/
240
241/*! \fn template<typename T> void QContiguousCache<T>::setCapacity(qsizetype size)
242
243 Sets the capacity of the cache to the given \a size. A cache can hold a
244 number of items equal to its capacity. When inserting, appending or prepending
245 items to the cache, if the cache is already full then the item farthest from
246 the added item will be removed.
247
248 If the given \a size is smaller than the current count of items in the cache
249 then only the last \a size items from the cache will remain.
250
251 \sa capacity(), isFull()
252*/
253
254/*! \fn template<typename T> const T &QContiguousCache<T>::at(qsizetype i) const
255
256 Returns the item at index position \a i in the cache. \a i must
257 be a valid index position in the cache (i.e, firstIndex() <= \a i <= lastIndex()).
258
259 The indexes in the cache refer to the number of positions the item is from the
260 first item appended into the cache. That is to say a cache with a capacity of
261 100, that has had 150 items appended will have a valid index range of
262 50 to 149. This allows inserting and retrieving items into the cache based
263 on a theoretical infinite list
264
265 \sa firstIndex(), lastIndex(), insert(), operator[]()
266*/
267
268/*! \fn template<typename T> T &QContiguousCache<T>::operator[](qsizetype i)
269
270 Returns the item at index position \a i as a modifiable reference. If
271 the cache does not contain an item at the given index position \a i
272 then it will first insert an empty item at that position.
273
274 In most cases it is better to use either at() or insert().
275
276 \note This non-const overload of operator[] requires QContiguousCache
277 to make a deep copy. Use at() for read-only access to a non-const
278 QContiguousCache.
279
280 \sa insert(), at()
281*/
282
283/*! \fn template<typename T> const T &QContiguousCache<T>::operator[](qsizetype i) const
284
285 \overload
286
287 Same as at(\a i).
288*/
289
290/*! \fn template<typename T> void QContiguousCache<T>::append(const T &value)
291
292 Inserts \a value at the end of the cache. If the cache is already full
293 the item at the start of the cache will be removed.
294
295 \sa prepend(), insert(), isFull()
296*/
297
298/*! \fn template<typename T> void QContiguousCache<T>::prepend(const T &value)
299
300 Inserts \a value at the start of the cache. If the cache is already full
301 the item at the end of the cache will be removed.
302
303 \sa append(), insert(), isFull()
304*/
305
306/*! \fn template<typename T> void QContiguousCache<T>::insert(qsizetype i, const T &value)
307
308 Inserts the \a value at the index position \a i. If the cache already contains
309 an item at \a i then that value is replaced. If \a i is either one more than
310 lastIndex() or one less than firstIndex() it is the equivalent to an append()
311 or a prepend().
312
313 If the given index \a i is not within the current range of the cache nor adjacent
314 to the bounds of the cache's index range, the cache is first cleared before
315 inserting the item. At this point the cache will have a size of 1. It is
316 worthwhile taking effort to insert items in an order that starts adjacent
317 to the current index range for the cache.
318
319 The range of valid indexes for the QContiguousCache class are from
320 0 to INT_MAX. Inserting outside of this range has undefined behavior.
321
322
323 \sa prepend(), append(), isFull(), firstIndex(), lastIndex()
324*/
325
326/*! \fn template<typename T> bool QContiguousCache<T>::containsIndex(qsizetype i) const
327
328 Returns \c true if the cache's index range includes the given index \a i.
329
330 \sa firstIndex(), lastIndex()
331*/
332
333/*! \fn template<typename T> qsizetype QContiguousCache<T>::firstIndex() const
334
335 Returns the first valid index in the cache. The index will be invalid if the
336 cache is empty.
337
338 \sa capacity(), size(), lastIndex()
339*/
340
341/*! \fn template<typename T> qsizetype QContiguousCache<T>::lastIndex() const
342
343 Returns the last valid index in the cache. The index will be invalid if the cache is empty.
344
345 \sa capacity(), size(), firstIndex()
346*/
347
348
349/*! \fn template<typename T> T &QContiguousCache<T>::first()
350
351 Returns a reference to the first item in the cache. This function
352 assumes that the cache isn't empty.
353
354 \sa last(), isEmpty()
355*/
356
357/*! \fn template<typename T> T &QContiguousCache<T>::last()
358
359 Returns a reference to the last item in the cache. This function
360 assumes that the cache isn't empty.
361
362 \sa first(), isEmpty()
363*/
364
365/*! \fn template<typename T> const T& QContiguousCache<T>::first() const
366
367 \overload
368*/
369
370/*! \fn template<typename T> const T& QContiguousCache<T>::last() const
371
372 \overload
373*/
374
375/*! \fn template<typename T> void QContiguousCache<T>::removeFirst()
376
377 Removes the first item from the cache. This function assumes that
378 the cache isn't empty.
379
380 \sa removeLast()
381*/
382
383/*! \fn template<typename T> void QContiguousCache<T>::removeLast()
384
385 Removes the last item from the cache. This function assumes that
386 the cache isn't empty.
387
388 \sa removeFirst()
389*/
390
391/*! \fn template<typename T> T QContiguousCache<T>::takeFirst()
392
393 Removes the first item in the cache and returns it. This function
394 assumes that the cache isn't empty.
395
396 If you don't use the return value, removeFirst() is more efficient.
397
398 \sa takeLast(), removeFirst()
399*/
400
401/*! \fn template<typename T> T QContiguousCache<T>::takeLast()
402
403 Removes the last item in the cache and returns it. This function
404 assumes that the cache isn't empty.
405
406 If you don't use the return value, removeLast() is more efficient.
407
408 \sa takeFirst(), removeLast()
409*/
410
411/*! \fn template<typename T> void QContiguousCache<T>::normalizeIndexes()
412
413 Moves the first index and last index of the cache
414 such that they point to valid indexes. The function does not modify
415 the contents of the cache or the ordering of elements within the cache.
416
417 It is provided so that index overflows can be corrected when using the
418 cache as a circular buffer.
419
420 \snippet code/src_corelib_tools_qcontiguouscache.cpp 1
421
422 \sa areIndexesValid(), append(), prepend()
423*/
424
425/*! \fn template<typename T> bool QContiguousCache<T>::areIndexesValid() const
426
427 Returns whether the indexes for items stored in the cache are valid.
428 Indexes can become invalid if items are appended after the index position
429 INT_MAX or prepended before the index position 0. This is only expected
430 to occur in very long lived circular buffer style usage of the
431 contiguous cache. Indexes can be made valid again by calling
432 normalizeIndexes().
433
434 \sa normalizeIndexes(), append(), prepend()
435*/
436
437QT_END_NAMESPACE
438

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