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