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