tools/qcontiguouscache.cpp

Source codeSwitch to Preprocessed file
LineSource CodeCoverage
1/**************************************************************************** -
2** -
3** Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies). -
4** Contact: http://www.qt-project.org/legal -
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 Digia. For licensing terms and -
14** conditions see http://qt.digia.com/licensing. For further information -
15** use the contact form at http://qt.digia.com/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 as published by the Free Software -
20** Foundation and appearing in the file LICENSE.LGPL included in the -
21** packaging of this file. Please review the following information to -
22** ensure the GNU Lesser General Public License version 2.1 requirements -
23** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. -
24** -
25** In addition, as a special exception, Digia gives you certain additional -
26** rights. These rights are described in the Digia Qt LGPL Exception -
27** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. -
28** -
29** GNU General Public License Usage -
30** Alternatively, this file may be used under the terms of the GNU -
31** General Public License version 3.0 as published by the Free Software -
32** Foundation and appearing in the file LICENSE.GPL included in the -
33** packaging of this file. Please review the following information to -
34** ensure the GNU General Public License version 3.0 requirements will be -
35** met: http://www.gnu.org/copyleft/gpl.html. -
36** -
37** -
38** $QT_END_LICENSE$ -
39** -
40****************************************************************************/ -
41 -
42#include "qcontiguouscache.h" -
43#ifdef QT_QCONTIGUOUSCACHE_DEBUG -
44#include <QDebug> -
45#endif -
46 -
47QT_BEGIN_NAMESPACE -
48 -
49#ifdef QT_QCONTIGUOUSCACHE_DEBUG -
50void QContiguousCacheData::dump() const -
51{ -
52 qDebug() << "capacity:" << alloc; -
53 qDebug() << "count:" << count; -
54 qDebug() << "start:" << start; -
55 qDebug() << "offset:" << offset; -
56} -
57#endif -
58 -
59QContiguousCacheData *QContiguousCacheData::allocateData(int size, int alignment) -
60{ -
61 return static_cast<QContiguousCacheData *>(qMallocAligned(size, alignment));
executed: return static_cast<QContiguousCacheData *>(qMallocAligned(size, alignment));
Execution Count:26
26
62} -
63 -
64void QContiguousCacheData::freeData(QContiguousCacheData *data) -
65{ -
66 qFreeAligned(data);
executed (the execution status of this line is deduced): qFreeAligned(data);
-
67}
executed: }
Execution Count:23
23
68 -
69/*! \class QContiguousCache -
70 \inmodule QtCore -
71 \brief The QContiguousCache class is a template class that provides a contiguous cache. -
72 \ingroup tools -
73 \ingroup shared -
74 \reentrant -
75 \since 4.6 -
76 -
77 The QContiguousCache class provides an efficient way of caching items for -
78 display in a user interface view. Unlike QCache, it adds a restriction -
79 that elements within the cache are contiguous. This has the advantage -
80 of matching how user interface views most commonly request data, as -
81 a set of rows localized around the current scrolled position. This -
82 restriction allows the cache to consume less memory and processor -
83 cycles than QCache. -
84 -
85 QContiguousCache operates on a fixed capacity, set with setCapacity() or -
86 passed as a parameter to the constructor. This capacity is the upper bound -
87 on memory usage by the cache itself, not including the memory allocated by -
88 the elements themselves. Note that a cache with a capacity of zero (the -
89 default) means no items will be stored: the insert(), append() and -
90 prepend() operations will effectively be no-ops. Therefore, it's important -
91 to set the capacity to a reasonable value before adding items to the cache. -
92 -
93 The simplest way of using a contiguous cache is to use the append() -
94 and prepend(). -
95 -
96\code -
97MyRecord record(int row) const -
98{ -
99 Q_ASSERT(row >= 0 && row < count()); -
100 -
101 while(row > cache.lastIndex()) -
102 cache.append(slowFetchRecord(cache.lastIndex()+1)); -
103 while(row < cache.firstIndex()) -
104 cache.prepend(slowFetchRecord(cache.firstIndex()-1)); -
105 -
106 return cache.at(row); -
107} -
108\endcode -
109 -
110 If the cache is full then the item at the opposite end of the cache from -
111 where the new item is appended or prepended will be removed. -
112 -
113 This usage can be further optimized by using the insert() function -
114 in the case where the requested row is a long way from the currently cached -
115 items. If there is a gap between where the new item is inserted and the currently -
116 cached items then the existing cached items are first removed to retain -
117 the contiguous nature of the cache. Hence it is important to take some care then -
118 when using insert() in order to avoid unwanted clearing of the cache. -
119 -
120 The range of valid indexes for the QContiguousCache class are from -
121 0 to INT_MAX. Calling prepend() such that the first index would become less -
122 than 0 or append() such that the last index would become greater -
123 than INT_MAX can result in the indexes of the cache being invalid. -
124 When the cache indexes are invalid it is important to call -
125 normalizeIndexes() before calling any of containsIndex(), firstIndex(), -
126 lastIndex(), at() or \l{QContiguousCache::operator[]()}{operator[]()}. -
127 Calling these functions when the cache has invalid indexes will result in -
128 undefined behavior. The indexes can be checked by using areIndexesValid() -
129 -
130 In most cases the indexes will not exceed 0 to INT_MAX, and -
131 normalizeIndexes() will not need to be used. -
132 -
133 See the \l{Contiguous Cache Example}{Contiguous Cache} example. -
134*/ -
135 -
136/*! \fn QContiguousCache::QContiguousCache(int capacity) -
137 -
138 Constructs a cache with the given \a capacity. -
139 -
140 \sa setCapacity() -
141*/ -
142 -
143/*! \fn QContiguousCache::QContiguousCache(const QContiguousCache<T> &other) -
144 -
145 Constructs a copy of \a other. -
146 -
147 This operation takes \l{constant time}, because QContiguousCache is -
148 \l{implicitly shared}. This makes returning a QContiguousCache from a -
149 function very fast. If a shared instance is modified, it will be -
150 copied (copy-on-write), and that takes \l{linear time}. -
151 -
152 \sa operator=() -
153*/ -
154 -
155/*! \fn QContiguousCache::~QContiguousCache() -
156 -
157 Destroys the cache. -
158*/ -
159 -
160/*! \fn void QContiguousCache::detach() -
161 \internal -
162*/ -
163 -
164/*! \fn bool QContiguousCache::isDetached() const -
165 \internal -
166*/ -
167 -
168/*! \fn void QContiguousCache::setSharable(bool sharable) -
169 \internal -
170*/ -
171 -
172/*! \typedef QContiguousCache::value_type -
173 \internal -
174 */ -
175 -
176/*! \typedef QContiguousCache::pointer -
177 \internal -
178 */ -
179 -
180/*! \typedef QContiguousCache::const_pointer -
181 \internal -
182 */ -
183 -
184/*! \typedef QContiguousCache::reference -
185 \internal -
186 */ -
187 -
188/*! \typedef QContiguousCache::const_reference -
189 \internal -
190 */ -
191 -
192/*! \typedef QContiguousCache::difference_type -
193 \internal -
194 */ -
195 -
196/*! \typedef QContiguousCache::size_type -
197 \internal -
198 */ -
199 -
200/*! \fn QContiguousCache<T> &QContiguousCache::operator=(const QContiguousCache<T> &other) -
201 -
202 Assigns \a other to this cache and returns a reference to this cache. -
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 true if \a other is equal to this cache; otherwise returns 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 true if \a other is not equal to this cache; otherwise -
225 returns 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 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 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 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 normalizeIndexs(). -
478 -
479 \sa normalizeIndexes(), append(), prepend() -
480*/ -
481 -
482QT_END_NAMESPACE -
483 -
Source codeSwitch to Preprocessed file
Generated by Squish Coco Non-Commercial