1 /****************************************************************************

     2 **

     3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

     4 ** All rights reserved.

     5 ** Contact: Nokia Corporation (qt-info@nokia.com)

     6 **

     7 ** This file is part of the QtCore module of the Qt Toolkit.

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

    11 ** This file contains pre-release code and may not be distributed.

    12 ** You may use this file in accordance with the terms and conditions

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    15 **

    16 ** GNU Lesser General Public License Usage

    17 ** Alternatively, this file may be used under the terms of the GNU Lesser

    18 ** General Public License version 2.1 as published by the Free Software

    19 ** Foundation and appearing in the file LICENSE.LGPL included in the

    20 ** packaging of this file.  Please review the following information to

    21 ** ensure the GNU Lesser General Public License version 2.1 requirements

    22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

    23 **

    24 ** In addition, as a special exception, Nokia gives you certain additional

    25 ** rights.  These rights are described in the Nokia Qt LGPL Exception

    26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

    27 **

    28 ** If you have questions regarding the use of this file, please contact

    29 ** Nokia at qt-info@nokia.com.

    30 **

    31 **

    32 **

    33 **

    34 **

    35 **

    36 **

    37 **

    38 ** $QT_END_LICENSE$

    39 **

    40 ****************************************************************************/

    41 

    42 #include "qcontiguouscache.h"

    43 #ifdef QT_QCONTIGUOUSCACHE_DEBUG

    44 #include <QDebug>

    45 #endif

    46 

    47 QT_BEGIN_NAMESPACE

    48 

    49 #ifdef QT_QCONTIGUOUSCACHE_DEBUG

    50 void QContiguousCacheData::dump() const

    51 {

    52     qDebug() << "capacity:" << alloc;

    53     qDebug() << "count:" << count;

    54     qDebug() << "start:" << start;

    55     qDebug() << "offset:" << offset;

    56 }

    57 #endif

    58 

    59 /*! \class QContiguousCache

    60     \brief The QContiguousCache class is a template class that provides a contiguous cache.

    61     \ingroup tools

    62     \ingroup shared

    63     \reentrant

    64     \since 4.6

    65 

    66     The QContiguousCache class provides an efficient way of caching items for

    67     display in a user interface view.  Unlike QCache, it adds a restriction

    68     that elements within the cache are contiguous.  This has the advantage

    69     of matching how user interface views most commonly request data, as

    70     a set of rows localized around the current scrolled position.  This

    71     restriction allows the cache to consume less memory and processor

    72     cycles than QCache.  The QContiguousCache class also can provide

    73     an upper bound on memory usage via setCapacity().

    74 

    75     The simplest way of using a contiguous cache is to use the append()

    76     and prepend().

    77 

    78 \code

    79 MyRecord record(int row) const

    80 {

    81     Q_ASSERT(row >= 0 && row < count());

    82 

    83     while(row > cache.lastIndex())

    84         cache.append(slowFetchRecord(cache.lastIndex()+1));

    85     while(row < cache.firstIndex())

    86         cache.prepend(slowFetchRecord(cache.firstIndex()-1));

    87 

    88     return cache.at(row);

    89 }

    90 \endcode

    91 

    92     If the cache is full then the item at the opposite end of the cache from

    93     where the new item is appended or prepended will be removed.

    94 

    95     This usage can be further optimized by using the insert() function

    96     in the case where the requested row is a long way from the currently cached

    97     items. If there is a gap between where the new item is inserted and the currently

    98     cached items then the existing cached items are first removed to retain

    99     the contiguous nature of the cache. Hence it is important to take some care then

   100     when using insert() in order to avoid unwanted clearing of the cache.

   101 

   102     The range of valid indexes for the QContiguousCache class are from

   103     0 to INT_MAX.  Calling prepend() such that the first index would become less

   104     than 0 or append() such that the last index would become greater

   105     than INT_MAX can result in the indexes of the cache being invalid.

   106     When the cache indexes are invalid it is important to call

   107     normalizeIndexes() before calling any of containsIndex(), firstIndex(),

   108     lastIndex(), at() or \l{QContiguousCache::operator[]()}{operator[]()}.

   109     Calling these functions when the cache has invalid indexes will result in

   110     undefined behavior. The indexes can be checked by using areIndexesValid()

   111 

   112     In most cases the indexes will not exceed 0 to INT_MAX, and

   113     normalizeIndexes() will not need to be used.

   114 

   115     See the \l{Contiguous Cache Example}{Contiguous Cache} example.

   116 */

   117 

   118 /*! \fn QContiguousCache::QContiguousCache(int capacity)

   119 

   120     Constructs a cache with the given \a capacity.

   121 

   122     \sa setCapacity()

   123 */

   124 

   125 /*! \fn QContiguousCache::QContiguousCache(const QContiguousCache<T> &other)

   126 

   127     Constructs a copy of \a other.

   128 

   129     This operation takes \l{constant time}, because QContiguousCache is

   130     \l{implicitly shared}.  This makes returning a QContiguousCache from a

   131     function very fast.  If a shared instance is modified, it will be

   132     copied (copy-on-write), and that takes \l{linear time}.

   133 

   134     \sa operator=()

   135 */

   136 

   137 /*! \fn QContiguousCache::~QContiguousCache()

   138 

   139     Destroys the cache.

   140 */

   141 

   142 /*! \fn void QContiguousCache::detach()

   143 

   144     \internal

   145 */

   146 

   147 /*! \fn bool QContiguousCache::isDetached() const

   148 

   149     \internal

   150 */

   151 

   152 /*! \fn void QContiguousCache::setSharable(bool sharable)

   153 

   154     \internal

   155 */

   156 

   157 /*! \fn QContiguousCache<T> &QContiguousCache::operator=(const QContiguousCache<T> &other)

   158 

   159     Assigns \a other to this cache and returns a reference to this cache.

   160 */

   161 

   162 /*! \fn bool QContiguousCache::operator==(const QContiguousCache<T> &other) const

   163 

   164     Returns true if \a other is equal to this cache; otherwise returns false.

   165 

   166     Two caches are considered equal if they contain the same values at the same

   167     indexes.  This function requires the value type to implement the \c operator==().

   168 

   169     \sa operator!=()

   170 */

   171 

   172 /*! \fn bool QContiguousCache::operator!=(const QContiguousCache<T> &other) const

   173 

   174     Returns true if \a other is not equal to this cache; otherwise

   175     returns false.

   176 

   177     Two caches are considered equal if they contain the same values at the same

   178     indexes.  This function requires the value type to implement the \c operator==().

   179 

   180     \sa operator==()

   181 */

   182 

   183 /*! \fn int QContiguousCache::capacity() const

   184 

   185     Returns the number of items the cache can store before it is full.

   186     When a cache contains a number of items equal to its capacity, adding new

   187     items will cause items farthest from the added item to be removed.

   188 

   189     \sa setCapacity(), size()

   190 */

   191 

   192 /*! \fn int QContiguousCache::count() const

   193 

   194     Same as size().

   195 */

   196 

   197 /*! \fn int QContiguousCache::size() const

   198 

   199     Returns the number of items contained within the cache.

   200 

   201     \sa capacity()

   202 */

   203 

   204 /*! \fn bool QContiguousCache::isEmpty() const

   205 

   206     Returns true if no items are stored within the cache.

   207 

   208     \sa size(), capacity()

   209 */

   210 

   211 /*! \fn bool QContiguousCache::isFull() const

   212 

   213     Returns true if the number of items stored within the cache is equal

   214     to the capacity of the cache.

   215 

   216     \sa size(), capacity()

   217 */

   218 

   219 /*! \fn int QContiguousCache::available() const

   220 

   221     Returns the number of items that can be added to the cache before it becomes full.

   222 

   223     \sa size(), capacity(), isFull()

   224 */

   225 

   226 /*! \fn void QContiguousCache::clear()

   227 

   228     Removes all items from the cache.  The capacity is unchanged.

   229 */

   230 

   231 /*! \fn void QContiguousCache::setCapacity(int size)

   232 

   233     Sets the capacity of the cache to the given \a size.  A cache can hold a

   234     number of items equal to its capacity.  When inserting, appending or prepending

   235     items to the cache, if the cache is already full then the item farthest from

   236     the added item will be removed.

   237 

   238     If the given \a size is smaller than the current count of items in the cache

   239     then only the last \a size items from the cache will remain.

   240 

   241     \sa capacity(), isFull()

   242 */

   243 

   244 /*! \fn const T &QContiguousCache::at(int i) const

   245 

   246     Returns the item at index position \a i in the cache.  \a i must

   247     be a valid index position in the cache (i.e, firstIndex() <= \a i <= lastIndex()).

   248 

   249     The indexes in the cache refer to the number of positions the item is from the

   250     first item appended into the cache.  That is to say a cache with a capacity of

   251     100, that has had 150 items appended will have a valid index range of

   252     50 to 149.  This allows inserting and retrieving items into the cache based

   253     on a theoretical infinite list

   254 

   255     \sa firstIndex(), lastIndex(), insert(), operator[]()

   256 */

   257 

   258 /*! \fn T &QContiguousCache::operator[](int i)

   259 

   260     Returns the item at index position \a i as a modifiable reference. If

   261     the cache does not contain an item at the given index position \a i

   262     then it will first insert an empty item at that position.

   263 

   264     In most cases it is better to use either at() or insert().

   265 

   266     \note This non-const overload of operator[] requires QContiguousCache 

   267     to make a deep copy. Use at() for read-only access to a non-const 

   268     QContiguousCache.

   269 

   270     \sa insert(), at()

   271 */

   272 

   273 /*! \fn const T &QContiguousCache::operator[](int i) const

   274 

   275     \overload

   276 

   277     Same as at(\a i).

   278 */

   279 

   280 /*! \fn void QContiguousCache::append(const T &value)

   281 

   282     Inserts \a value at the end of the cache.  If the cache is already full

   283     the item at the start of the cache will be removed.

   284 

   285     \sa prepend(), insert(), isFull()

   286 */

   287 

   288 /*! \fn void QContiguousCache::prepend(const T &value)

   289 

   290     Inserts \a value at the start of the cache.  If the cache is already full

   291     the item at the end of the cache will be removed.

   292 

   293     \sa append(), insert(), isFull()

   294 */

   295 

   296 /*! \fn void QContiguousCache::insert(int i, const T &value)

   297 

   298     Inserts the \a value at the index position \a i.  If the cache already contains

   299     an item at \a i then that value is replaced.  If \a i is either one more than

   300     lastIndex() or one less than firstIndex() it is the equivalent to an append()

   301     or a prepend().

   302 

   303     If the given index \a i is not within the current range of the cache nor adjacent

   304     to the bounds of the cache's index range, the cache is first cleared before

   305     inserting the item.  At this point the cache will have a size of 1.  It is

   306     worthwhile taking effort to insert items in an order that starts adjacent

   307     to the current index range for the cache.

   308 

   309     The range of valid indexes for the QContiguousCache class are from

   310     0 to INT_MAX. Inserting outside of this range has undefined behavior.

   311 

   312 

   313     \sa prepend(), append(), isFull(), firstIndex(), lastIndex()

   314 */

   315 

   316 /*! \fn bool QContiguousCache::containsIndex(int i) const

   317 

   318     Returns true if the cache's index range includes the given index \a i.

   319 

   320     \sa firstIndex(), lastIndex()

   321 */

   322 

   323 /*! \fn int QContiguousCache::firstIndex() const

   324 

   325     Returns the first valid index in the cache.  The index will be invalid if the

   326     cache is empty.

   327 

   328     \sa capacity(), size(), lastIndex()

   329 */

   330 

   331 /*! \fn int QContiguousCache::lastIndex() const

   332 

   333     Returns the last valid index in the cache.  The index will be invalid if the cache is empty.

   334 

   335     \sa capacity(), size(), firstIndex()

   336 */

   337 

   338 

   339 /*! \fn T &QContiguousCache::first()

   340 

   341     Returns a reference to the first item in the cache.  This function

   342     assumes that the cache isn't empty.

   343 

   344     \sa last(), isEmpty()

   345 */

   346 

   347 /*! \fn T &QContiguousCache::last()

   348 

   349     Returns a reference to the last item in the cache.  This function

   350     assumes that the cache isn't empty.

   351 

   352     \sa first(), isEmpty()

   353 */

   354 

   355 /*! \fn const T& QContiguousCache::first() const

   356 

   357     \overload

   358 */

   359 

   360 /*! \fn const T& QContiguousCache::last() const

   361 

   362     \overload

   363 */

   364 

   365 /*! \fn void QContiguousCache::removeFirst()

   366 

   367     Removes the first item from the cache.  This function assumes that

   368     the cache isn't empty.

   369 

   370     \sa removeLast()

   371 */

   372 

   373 /*! \fn void QContiguousCache::removeLast()

   374 

   375     Removes the last item from the cache.  This function assumes that

   376     the cache isn't empty.

   377 

   378     \sa removeFirst()

   379 */

   380 

   381 /*! \fn T QContiguousCache::takeFirst()

   382 

   383     Removes the first item in the cache and returns it.  This function

   384     assumes that the cache isn't empty.

   385 

   386     If you don't use the return value, removeFirst() is more efficient.

   387 

   388     \sa takeLast(), removeFirst()

   389 */

   390 

   391 /*! \fn T QContiguousCache::takeLast()

   392 

   393     Removes the last 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, removeLast() is more efficient.

   397 

   398     \sa takeFirst(), removeLast()

   399 */

   400 

   401 /*! \fn void QContiguousCache::normalizeIndexes()

   402 

   403     Moves the first index and last index of the cache

   404     such that they point to valid indexes.  The function does not modify

   405     the contents of the cache or the ordering of elements within the cache.

   406 

   407     It is provided so that index overflows can be corrected when using the

   408     cache as a circular buffer.

   409 

   410     \code

   411     QContiguousCache<int> cache(10);

   412     cache.insert(INT_MAX, 1); // cache contains one value and has valid indexes, INT_MAX to INT_MAX

   413     cache.append(2); // cache contains two values but does not have valid indexes.

   414     cache.normalizeIndexes(); // cache has two values, 1 and 2.  New first index will be in the range of 0 to capacity().

   415     \endcode

   416 

   417     \sa areIndexesValid(), append(), prepend()

   418 */

   419 

   420 /*! \fn bool QContiguousCache::areIndexesValid() const

   421 

   422     Returns whether the indexes for items stored in the cache are valid.

   423     Indexes can become invalid if items are appended after the index position

   424     INT_MAX or prepended before the index position 0.  This is only expected

   425     to occur in very long lived circular buffer style usage of the

   426     contiguous cache.  Indexes can be made valid again by calling

   427     normalizeIndexs().

   428 

   429     \sa normalizeIndexes(), append(), prepend()

   430 */

   431 

   432 QT_END_NAMESPACE