src/corelib/tools/qcontiguouscache.cpp

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
   4 ** Contact: http://www.qt-project.org/
   5 **
   6 ** This file is part of the QtCore module of the Qt Toolkit.
   7 **
   8 ** $QT_BEGIN_LICENSE:LGPL$
   9 ** GNU Lesser General Public License Usage
  10 ** This file may be used under the terms of the GNU Lesser General Public
  11 ** License version 2.1 as published by the Free Software Foundation and
  12 ** appearing in the file LICENSE.LGPL included in the packaging of this
  13 ** file. Please review the following information to ensure the GNU Lesser
  14 ** General Public License version 2.1 requirements will be met:
  15 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  16 **
  17 ** In addition, as a special exception, Nokia gives you certain additional
  18 ** rights. These rights are described in the Nokia Qt LGPL Exception
  19 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  20 **
  21 ** GNU General Public License Usage
  22 ** Alternatively, this file may be used under the terms of the GNU General
  23 ** Public License version 3.0 as published by the Free Software Foundation
  24 ** and appearing in the file LICENSE.GPL included in the packaging of this
  25 ** file. Please review the following information to ensure the GNU General
  26 ** Public License version 3.0 requirements will be met:
  27 ** http://www.gnu.org/copyleft/gpl.html.
  28 **
  29 ** Other Usage
  30 ** Alternatively, this file may be used in accordance with the terms and
  31 ** conditions contained in a signed written agreement between you and Nokia.
  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 QContiguousCacheData *QContiguousCacheData::allocate(int size, int alignment)
  60 {
  61     return static_cast<QContiguousCacheData *>(qMallocAligned(size, alignment));
  62 }
  63
  64 void QContiguousCacheData::free(QContiguousCacheData *data)
  65 {
  66     qFreeAligned(data);
  67 }
  68
  69 /*! \class QContiguousCache
  70     \brief The QContiguousCache class is a template class that provides a contiguous cache.
  71     \ingroup tools
  72     \ingroup shared
  73     \reentrant
  74     \since 4.6
  75
  76     The QContiguousCache class provides an efficient way of caching items for
  77     display in a user interface view.  Unlike QCache, it adds a restriction
  78     that elements within the cache are contiguous.  This has the advantage
  79     of matching how user interface views most commonly request data, as
  80     a set of rows localized around the current scrolled position.  This
  81     restriction allows the cache to consume less memory and processor
  82     cycles than QCache.  The QContiguousCache class also can provide
  83     an upper bound on memory usage via setCapacity().
  84
  85     The simplest way of using a contiguous cache is to use the append()
  86     and prepend().
  87
  88 \code
  89 MyRecord 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 /*! \fn void QContiguousCache::swap(QContiguousCache<T> &other)
 198     \since 4.8
 199
 200     Swaps cache \a other with this cache. This operation is very
 201     fast and never fails.
 202 */
 203
 204 /*! \fn bool QContiguousCache::operator==(const QContiguousCache<T> &other) const
 205
 206     Returns true if \a other is equal to this cache; otherwise returns false.
 207
 208     Two caches are considered equal if they contain the same values at the same
 209     indexes.  This function requires the value type to implement the \c operator==().
 210
 211     \sa operator!=()
 212 */
 213
 214 /*! \fn bool QContiguousCache::operator!=(const QContiguousCache<T> &other) const
 215
 216     Returns true if \a other is not equal to this cache; otherwise
 217     returns false.
 218
 219     Two caches are considered equal if they contain the same values at the same
 220     indexes.  This function requires the value type to implement the \c operator==().
 221
 222     \sa operator==()
 223 */
 224
 225 /*! \fn int QContiguousCache::capacity() const
 226
 227     Returns the number of items the cache can store before it is full.
 228     When a cache contains a number of items equal to its capacity, adding new
 229     items will cause items farthest from the added item to be removed.
 230
 231     \sa setCapacity(), size()
 232 */
 233
 234 /*! \fn int QContiguousCache::count() const
 235
 236     Same as size().
 237 */
 238
 239 /*! \fn int QContiguousCache::size() const
 240
 241     Returns the number of items contained within the cache.
 242
 243     \sa capacity()
 244 */
 245
 246 /*! \fn bool QContiguousCache::isEmpty() const
 247
 248     Returns true if no items are stored within the cache.
 249
 250     \sa size(), capacity()
 251 */
 252
 253 /*! \fn bool QContiguousCache::isFull() const
 254
 255     Returns true if the number of items stored within the cache is equal
 256     to the capacity of the cache.
 257
 258     \sa size(), capacity()
 259 */
 260
 261 /*! \fn int QContiguousCache::available() const
 262
 263     Returns the number of items that can be added to the cache before it becomes full.
 264
 265     \sa size(), capacity(), isFull()
 266 */
 267
 268 /*! \fn void QContiguousCache::clear()
 269
 270     Removes all items from the cache.  The capacity is unchanged.
 271 */
 272
 273 /*! \fn void QContiguousCache::setCapacity(int size)
 274
 275     Sets the capacity of the cache to the given \a size.  A cache can hold a
 276     number of items equal to its capacity.  When inserting, appending or prepending
 277     items to the cache, if the cache is already full then the item farthest from
 278     the added item will be removed.
 279
 280     If the given \a size is smaller than the current count of items in the cache
 281     then only the last \a size items from the cache will remain.
 282
 283     \sa capacity(), isFull()
 284 */
 285
 286 /*! \fn const T &QContiguousCache::at(int i) const
 287
 288     Returns the item at index position \a i in the cache.  \a i must
 289     be a valid index position in the cache (i.e, firstIndex() <= \a i <= lastIndex()).
 290
 291     The indexes in the cache refer to the number of positions the item is from the
 292     first item appended into the cache.  That is to say a cache with a capacity of
 293     100, that has had 150 items appended will have a valid index range of
 294     50 to 149.  This allows inserting and retrieving items into the cache based
 295     on a theoretical infinite list
 296
 297     \sa firstIndex(), lastIndex(), insert(), operator[]()
 298 */
 299
 300 /*! \fn T &QContiguousCache::operator[](int i)
 301
 302     Returns the item at index position \a i as a modifiable reference. If
 303     the cache does not contain an item at the given index position \a i
 304     then it will first insert an empty item at that position.
 305
 306     In most cases it is better to use either at() or insert().
 307
 308     \note This non-const overload of operator[] requires QContiguousCache
 309     to make a deep copy. Use at() for read-only access to a non-const
 310     QContiguousCache.
 311
 312     \sa insert(), at()
 313 */
 314
 315 /*! \fn const T &QContiguousCache::operator[](int i) const
 316
 317     \overload
 318
 319     Same as at(\a i).
 320 */
 321
 322 /*! \fn void QContiguousCache::append(const T &value)
 323
 324     Inserts \a value at the end of the cache.  If the cache is already full
 325     the item at the start of the cache will be removed.
 326
 327     \sa prepend(), insert(), isFull()
 328 */
 329
 330 /*! \fn void QContiguousCache::prepend(const T &value)
 331
 332     Inserts \a value at the start of the cache.  If the cache is already full
 333     the item at the end of the cache will be removed.
 334
 335     \sa append(), insert(), isFull()
 336 */
 337
 338 /*! \fn void QContiguousCache::insert(int i, const T &value)
 339
 340     Inserts the \a value at the index position \a i.  If the cache already contains
 341     an item at \a i then that value is replaced.  If \a i is either one more than
 342     lastIndex() or one less than firstIndex() it is the equivalent to an append()
 343     or a prepend().
 344
 345     If the given index \a i is not within the current range of the cache nor adjacent
 346     to the bounds of the cache's index range, the cache is first cleared before
 347     inserting the item.  At this point the cache will have a size of 1.  It is
 348     worthwhile taking effort to insert items in an order that starts adjacent
 349     to the current index range for the cache.
 350
 351     The range of valid indexes for the QContiguousCache class are from
 352     0 to INT_MAX. Inserting outside of this range has undefined behavior.
 353
 354
 355     \sa prepend(), append(), isFull(), firstIndex(), lastIndex()
 356 */
 357
 358 /*! \fn bool QContiguousCache::containsIndex(int i) const
 359
 360     Returns true if the cache's index range includes the given index \a i.
 361
 362     \sa firstIndex(), lastIndex()
 363 */
 364
 365 /*! \fn int QContiguousCache::firstIndex() const
 366
 367     Returns the first valid index in the cache.  The index will be invalid if the
 368     cache is empty.
 369
 370     \sa capacity(), size(), lastIndex()
 371 */
 372
 373 /*! \fn int QContiguousCache::lastIndex() const
 374
 375     Returns the last valid index in the cache.  The index will be invalid if the cache is empty.
 376
 377     \sa capacity(), size(), firstIndex()
 378 */
 379
 380
 381 /*! \fn T &QContiguousCache::first()
 382
 383     Returns a reference to the first item in the cache.  This function
 384     assumes that the cache isn't empty.
 385
 386     \sa last(), isEmpty()
 387 */
 388
 389 /*! \fn T &QContiguousCache::last()
 390
 391     Returns a reference to the last item in the cache.  This function
 392     assumes that the cache isn't empty.
 393
 394     \sa first(), isEmpty()
 395 */
 396
 397 /*! \fn const T& QContiguousCache::first() const
 398
 399     \overload
 400 */
 401
 402 /*! \fn const T& QContiguousCache::last() const
 403
 404     \overload
 405 */
 406
 407 /*! \fn void QContiguousCache::removeFirst()
 408
 409     Removes the first item from the cache.  This function assumes that
 410     the cache isn't empty.
 411
 412     \sa removeLast()
 413 */
 414
 415 /*! \fn void QContiguousCache::removeLast()
 416
 417     Removes the last item from the cache.  This function assumes that
 418     the cache isn't empty.
 419
 420     \sa removeFirst()
 421 */
 422
 423 /*! \fn T QContiguousCache::takeFirst()
 424
 425     Removes the first item in the cache and returns it.  This function
 426     assumes that the cache isn't empty.
 427
 428     If you don't use the return value, removeFirst() is more efficient.
 429
 430     \sa takeLast(), removeFirst()
 431 */
 432
 433 /*! \fn T QContiguousCache::takeLast()
 434
 435     Removes the last item in the cache and returns it. This function
 436     assumes that the cache isn't empty.
 437
 438     If you don't use the return value, removeLast() is more efficient.
 439
 440     \sa takeFirst(), removeLast()
 441 */
 442
 443 /*! \fn void QContiguousCache::normalizeIndexes()
 444
 445     Moves the first index and last index of the cache
 446     such that they point to valid indexes.  The function does not modify
 447     the contents of the cache or the ordering of elements within the cache.
 448
 449     It is provided so that index overflows can be corrected when using the
 450     cache as a circular buffer.
 451
 452     \code
 453     QContiguousCache<int> cache(10);
 454     cache.insert(INT_MAX, 1); // cache contains one value and has valid indexes, INT_MAX to INT_MAX
 455     cache.append(2); // cache contains two values but does not have valid indexes.
 456     cache.normalizeIndexes(); // cache has two values, 1 and 2.  New first index will be in the range of 0 to capacity().
 457     \endcode
 458
 459     \sa areIndexesValid(), append(), prepend()
 460 */
 461
 462 /*! \fn bool QContiguousCache::areIndexesValid() const
 463
 464     Returns whether the indexes for items stored in the cache are valid.
 465     Indexes can become invalid if items are appended after the index position
 466     INT_MAX or prepended before the index position 0.  This is only expected
 467     to occur in very long lived circular buffer style usage of the
 468     contiguous cache.  Indexes can be made valid again by calling
 469     normalizeIndexs().
 470
 471     \sa normalizeIndexes(), append(), prepend()
 472 */
 473
 474 QT_END_NAMESPACE