qcontiguouscache.cpp

Absolute File Name:/home/qt/qt5_coco/qt5/qtbase/src/corelib/tools/qcontiguouscache.cpp
Source codeSwitch to Preprocessed file
LineSourceCount
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(int size, int alignment)-
58{-
59 return static_cast<QContiguousCacheData *>(qMallocAligned(size, alignment));
executed 28 times by 2 tests: return static_cast<QContiguousCacheData *>(qMallocAligned(size, alignment));
Executed by:
  • tst_Collections
  • tst_QContiguousCache
28
60}-
61-
62void QContiguousCacheData::freeData(QContiguousCacheData *data)-
63{-
64 qFreeAligned(data);-
65}
executed 25 times by 2 tests: end of block
Executed by:
  • tst_Collections
  • tst_QContiguousCache
25
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\code-
95MyRecord record(int row) const-
96{-
97 Q_ASSERT(row >= 0 && row < count());-
98-
99 while(row > cache.lastIndex())-
100 cache.append(slowFetchRecord(cache.lastIndex()+1));-
101 while(row < cache.firstIndex())-
102 cache.prepend(slowFetchRecord(cache.firstIndex()-1));-
103-
104 return cache.at(row);-
105}-
106\endcode-
107-
108 If the cache is full then the item at the opposite end of the cache from-
109 where the new item is appended or prepended will be removed.-
110-
111 This usage can be further optimized by using the insert() function-
112 in the case where the requested row is a long way from the currently cached-
113 items. If there is a gap between where the new item is inserted and the currently-
114 cached items then the existing cached items are first removed to retain-
115 the contiguous nature of the cache. Hence it is important to take some care then-
116 when using insert() in order to avoid unwanted clearing of the cache.-
117-
118 The range of valid indexes for the QContiguousCache class are from-
119 0 to INT_MAX. Calling prepend() such that the first index would become less-
120 than 0 or append() such that the last index would become greater-
121 than INT_MAX can result in the indexes of the cache being invalid.-
122 When the cache indexes are invalid it is important to call-
123 normalizeIndexes() before calling any of containsIndex(), firstIndex(),-
124 lastIndex(), at() or \l{QContiguousCache::operator[]()}{operator[]()}.-
125 Calling these functions when the cache has invalid indexes will result in-
126 undefined behavior. The indexes can be checked by using areIndexesValid()-
127-
128 In most cases the indexes will not exceed 0 to INT_MAX, and-
129 normalizeIndexes() will not need to be used.-
130-
131 See the \l{Contiguous Cache Example}{Contiguous Cache} example.-
132*/-
133-
134/*! \fn QContiguousCache::QContiguousCache(int capacity)-
135-
136 Constructs a cache with the given \a capacity.-
137-
138 \sa setCapacity()-
139*/-
140-
141/*! \fn QContiguousCache::QContiguousCache(const QContiguousCache<T> &other)-
142-
143 Constructs a copy of \a other.-
144-
145 This operation takes \l{constant time}, because QContiguousCache is-
146 \l{implicitly shared}. This makes returning a QContiguousCache from a-
147 function very fast. If a shared instance is modified, it will be-
148 copied (copy-on-write), and that takes \l{linear time}.-
149-
150 \sa operator=()-
151*/-
152-
153/*! \fn QContiguousCache::~QContiguousCache()-
154-
155 Destroys the cache.-
156*/-
157-
158/*! \fn void QContiguousCache::detach()-
159 \internal-
160*/-
161-
162/*! \fn bool QContiguousCache::isDetached() const-
163 \internal-
164*/-
165-
166/*! \fn void QContiguousCache::setSharable(bool sharable)-
167 \internal-
168*/-
169-
170/*! \typedef QContiguousCache::value_type-
171 \internal-
172 */-
173-
174/*! \typedef QContiguousCache::pointer-
175 \internal-
176 */-
177-
178/*! \typedef QContiguousCache::const_pointer-
179 \internal-
180 */-
181-
182/*! \typedef QContiguousCache::reference-
183 \internal-
184 */-
185-
186/*! \typedef QContiguousCache::const_reference-
187 \internal-
188 */-
189-
190/*! \typedef QContiguousCache::difference_type-
191 \internal-
192 */-
193-
194/*! \typedef QContiguousCache::size_type-
195 \internal-
196 */-
197-
198/*! \fn QContiguousCache<T> &QContiguousCache::operator=(const QContiguousCache<T> &other)-
199-
200 Assigns \a other to this cache and returns a reference to this cache.-
201*/-
202-
203/*!-
204 \fn QContiguousCache<T> &QContiguousCache::operator=(QContiguousCache<T> &&other)-
205-
206 Move-assigns \a other to this QContiguousCache instance.-
207-
208 \since 5.2-
209*/-
210-
211/*! \fn void QContiguousCache::swap(QContiguousCache<T> &other)-
212 \since 4.8-
213-
214 Swaps cache \a other with this cache. This operation is very-
215 fast and never fails.-
216*/-
217-
218/*! \fn bool QContiguousCache::operator==(const QContiguousCache<T> &other) const-
219-
220 Returns \c true if \a other is equal to this cache; otherwise returns \c false.-
221-
222 Two caches are considered equal if they contain the same values at the same-
223 indexes. This function requires the value type to implement the \c operator==().-
224-
225 \sa operator!=()-
226*/-
227-
228/*! \fn bool QContiguousCache::operator!=(const QContiguousCache<T> &other) const-
229-
230 Returns \c true if \a other is not equal to this cache; otherwise-
231 returns \c false.-
232-
233 Two caches are considered equal if they contain the same values at the same-
234 indexes. This function requires the value type to implement the \c operator==().-
235-
236 \sa operator==()-
237*/-
238-
239/*! \fn int QContiguousCache::capacity() const-
240-
241 Returns the number of items the cache can store before it is full.-
242 When a cache contains a number of items equal to its capacity, adding new-
243 items will cause items farthest from the added item to be removed.-
244-
245 \sa setCapacity(), size()-
246*/-
247-
248/*! \fn int QContiguousCache::count() const-
249-
250 Same as size().-
251*/-
252-
253/*! \fn int QContiguousCache::size() const-
254-
255 Returns the number of items contained within the cache.-
256-
257 \sa capacity()-
258*/-
259-
260/*! \fn bool QContiguousCache::isEmpty() const-
261-
262 Returns \c true if no items are stored within the cache.-
263-
264 \sa size(), capacity()-
265*/-
266-
267/*! \fn bool QContiguousCache::isFull() const-
268-
269 Returns \c true if the number of items stored within the cache is equal-
270 to the capacity of the cache.-
271-
272 \sa size(), capacity()-
273*/-
274-
275/*! \fn int QContiguousCache::available() const-
276-
277 Returns the number of items that can be added to the cache before it becomes full.-
278-
279 \sa size(), capacity(), isFull()-
280*/-
281-
282/*! \fn void QContiguousCache::clear()-
283-
284 Removes all items from the cache. The capacity is unchanged.-
285*/-
286-
287/*! \fn void QContiguousCache::setCapacity(int size)-
288-
289 Sets the capacity of the cache to the given \a size. A cache can hold a-
290 number of items equal to its capacity. When inserting, appending or prepending-
291 items to the cache, if the cache is already full then the item farthest from-
292 the added item will be removed.-
293-
294 If the given \a size is smaller than the current count of items in the cache-
295 then only the last \a size items from the cache will remain.-
296-
297 \sa capacity(), isFull()-
298*/-
299-
300/*! \fn const T &QContiguousCache::at(int i) const-
301-
302 Returns the item at index position \a i in the cache. \a i must-
303 be a valid index position in the cache (i.e, firstIndex() <= \a i <= lastIndex()).-
304-
305 The indexes in the cache refer to the number of positions the item is from the-
306 first item appended into the cache. That is to say a cache with a capacity of-
307 100, that has had 150 items appended will have a valid index range of-
308 50 to 149. This allows inserting and retrieving items into the cache based-
309 on a theoretical infinite list-
310-
311 \sa firstIndex(), lastIndex(), insert(), operator[]()-
312*/-
313-
314/*! \fn T &QContiguousCache::operator[](int i)-
315-
316 Returns the item at index position \a i as a modifiable reference. If-
317 the cache does not contain an item at the given index position \a i-
318 then it will first insert an empty item at that position.-
319-
320 In most cases it is better to use either at() or insert().-
321-
322 \note This non-const overload of operator[] requires QContiguousCache-
323 to make a deep copy. Use at() for read-only access to a non-const-
324 QContiguousCache.-
325-
326 \sa insert(), at()-
327*/-
328-
329/*! \fn const T &QContiguousCache::operator[](int i) const-
330-
331 \overload-
332-
333 Same as at(\a i).-
334*/-
335-
336/*! \fn void QContiguousCache::append(const T &value)-
337-
338 Inserts \a value at the end of the cache. If the cache is already full-
339 the item at the start of the cache will be removed.-
340-
341 \sa prepend(), insert(), isFull()-
342*/-
343-
344/*! \fn void QContiguousCache::prepend(const T &value)-
345-
346 Inserts \a value at the start of the cache. If the cache is already full-
347 the item at the end of the cache will be removed.-
348-
349 \sa append(), insert(), isFull()-
350*/-
351-
352/*! \fn void QContiguousCache::insert(int i, const T &value)-
353-
354 Inserts the \a value at the index position \a i. If the cache already contains-
355 an item at \a i then that value is replaced. If \a i is either one more than-
356 lastIndex() or one less than firstIndex() it is the equivalent to an append()-
357 or a prepend().-
358-
359 If the given index \a i is not within the current range of the cache nor adjacent-
360 to the bounds of the cache's index range, the cache is first cleared before-
361 inserting the item. At this point the cache will have a size of 1. It is-
362 worthwhile taking effort to insert items in an order that starts adjacent-
363 to the current index range for the cache.-
364-
365 The range of valid indexes for the QContiguousCache class are from-
366 0 to INT_MAX. Inserting outside of this range has undefined behavior.-
367-
368-
369 \sa prepend(), append(), isFull(), firstIndex(), lastIndex()-
370*/-
371-
372/*! \fn bool QContiguousCache::containsIndex(int i) const-
373-
374 Returns \c true if the cache's index range includes the given index \a i.-
375-
376 \sa firstIndex(), lastIndex()-
377*/-
378-
379/*! \fn int QContiguousCache::firstIndex() const-
380-
381 Returns the first valid index in the cache. The index will be invalid if the-
382 cache is empty.-
383-
384 \sa capacity(), size(), lastIndex()-
385*/-
386-
387/*! \fn int QContiguousCache::lastIndex() const-
388-
389 Returns the last valid index in the cache. The index will be invalid if the cache is empty.-
390-
391 \sa capacity(), size(), firstIndex()-
392*/-
393-
394-
395/*! \fn T &QContiguousCache::first()-
396-
397 Returns a reference to the first item in the cache. This function-
398 assumes that the cache isn't empty.-
399-
400 \sa last(), isEmpty()-
401*/-
402-
403/*! \fn T &QContiguousCache::last()-
404-
405 Returns a reference to the last item in the cache. This function-
406 assumes that the cache isn't empty.-
407-
408 \sa first(), isEmpty()-
409*/-
410-
411/*! \fn const T& QContiguousCache::first() const-
412-
413 \overload-
414*/-
415-
416/*! \fn const T& QContiguousCache::last() const-
417-
418 \overload-
419*/-
420-
421/*! \fn void QContiguousCache::removeFirst()-
422-
423 Removes the first item from the cache. This function assumes that-
424 the cache isn't empty.-
425-
426 \sa removeLast()-
427*/-
428-
429/*! \fn void QContiguousCache::removeLast()-
430-
431 Removes the last item from the cache. This function assumes that-
432 the cache isn't empty.-
433-
434 \sa removeFirst()-
435*/-
436-
437/*! \fn T QContiguousCache::takeFirst()-
438-
439 Removes the first item in the cache and returns it. This function-
440 assumes that the cache isn't empty.-
441-
442 If you don't use the return value, removeFirst() is more efficient.-
443-
444 \sa takeLast(), removeFirst()-
445*/-
446-
447/*! \fn T QContiguousCache::takeLast()-
448-
449 Removes the last item in the cache and returns it. This function-
450 assumes that the cache isn't empty.-
451-
452 If you don't use the return value, removeLast() is more efficient.-
453-
454 \sa takeFirst(), removeLast()-
455*/-
456-
457/*! \fn void QContiguousCache::normalizeIndexes()-
458-
459 Moves the first index and last index of the cache-
460 such that they point to valid indexes. The function does not modify-
461 the contents of the cache or the ordering of elements within the cache.-
462-
463 It is provided so that index overflows can be corrected when using the-
464 cache as a circular buffer.-
465-
466 \code-
467 QContiguousCache<int> cache(10);-
468 cache.insert(INT_MAX, 1); // cache contains one value and has valid indexes, INT_MAX to INT_MAX-
469 cache.append(2); // cache contains two values but does not have valid indexes.-
470 cache.normalizeIndexes(); // cache has two values, 1 and 2. New first index will be in the range of 0 to capacity().-
471 \endcode-
472-
473 \sa areIndexesValid(), append(), prepend()-
474*/-
475-
476/*! \fn bool QContiguousCache::areIndexesValid() const-
477-
478 Returns whether the indexes for items stored in the cache are valid.-
479 Indexes can become invalid if items are appended after the index position-
480 INT_MAX or prepended before the index position 0. This is only expected-
481 to occur in very long lived circular buffer style usage of the-
482 contiguous cache. Indexes can be made valid again by calling-
483 normalizeIndexes().-
484-
485 \sa normalizeIndexes(), append(), prepend()-
486*/-
487-
488QT_END_NAMESPACE-
Source codeSwitch to Preprocessed file
Generated by Squish Coco Non-Commercial 4.3.0-BETA-master-30-08-2018-4cb69e9