doc/src/q3intcache.qdoc

   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 documentation 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 /*!
  43     \class Q3IntCache
  44     \brief The Q3IntCache class is a template class that provides a cache based on long keys.
  45     \compat
  46
  47     Q3IntCache is implemented as a template class. Define a template
  48     instance Q3IntCache\<X\> to create a cache that operates on
  49     pointers to X, or X*.
  50
  51     A cache is a least recently used (LRU) list of cache items,
  52     accessed via \c long keys. Each cache item has a cost. The sum
  53     of item costs, totalCost(), will not exceed the maximum cache
  54     cost, maxCost(). If inserting a new item would cause the total
  55     cost to exceed the maximum cost, the least recently used items in
  56     the cache are removed.
  57
  58     Apart from insert(), by far the most important function is find()
  59     (which also exists as operator[]). This function looks up an
  60     item, returns it, and by default marks it as being the most
  61     recently used item.
  62
  63     There are also methods to remove() or take() an object from the
  64     cache. Calling setAutoDelete(TRUE) for a cache tells it to delete
  65     items that are removed. The default is to not delete items when
  66     they are removed (i.e. remove() and take() are equivalent).
  67
  68     When inserting an item into the cache, only the pointer is copied,
  69     not the item itself. This is called a shallow copy. It is possible
  70     to make the cache copy all of the item's data (known as a deep
  71     copy) when an item is inserted. insert() calls the virtual
  72     function Q3PtrCollection::newItem() for the item to be inserted.
  73     Inherit a dictionary and reimplement newItem() if you want deep
  74     copies.
  75
  76     When removing a cache item, the item will be automatically
  77     deleted if auto-deletion is enabled.
  78
  79     There is a Q3IntCacheIterator which may be used to traverse the
  80     items in the cache in arbitrary order.
  81
  82     \sa Q3IntCacheIterator, Q3Cache, Q3AsciiCache
  83 */
  84
  85 /*!
  86   \fn Q3IntCache::Q3IntCache( const Q3IntCache<type> &c )
  87
  88   \internal
  89
  90   Do not use. A Q3IntCache cannot be copied. Calls qFatal() in debug version.
  91 */
  92
  93 /*!
  94     \fn Q3IntCache::Q3IntCache( int maxCost, int size  )
  95
  96     Constructs a cache whose contents will never have a total cost
  97     greater than \a maxCost and which is expected to contain less than
  98     \a size items.
  99
 100     \a size is actually the size of an internal hash array; it's
 101     usually best to make it prime and at least 50% bigger than the
 102     largest expected number of items in the cache.
 103
 104     Each inserted item is associated with a cost. When inserting a new
 105     item, if the total cost of all items in the cache will exceed \a
 106     maxCost, the cache will start throwing out the older (least
 107     recently used) items until there is enough room for the new item
 108     to be inserted.
 109 */
 110
 111 /*!
 112     \fn Q3IntCache::~Q3IntCache()
 113
 114     Removes all items from the cache and then destroys the int cache.
 115     If auto-deletion is enabled the cache's items are deleted. All
 116     iterators that access this cache will be reset.
 117 */
 118
 119 /*!
 120   \fn Q3IntCache<type>& Q3IntCache::operator=( const Q3IntCache<type> &c )
 121
 122   \internal
 123
 124   Do not use. A Q3IntCache cannot be copied. Calls qFatal() in debug version.
 125 */
 126
 127 /*!
 128     \fn int Q3IntCache::maxCost() const
 129
 130     Returns the maximum allowed total cost of the cache.
 131
 132     \sa setMaxCost() totalCost()
 133 */
 134
 135 /*!
 136     \fn int Q3IntCache::totalCost() const
 137
 138     Returns the total cost of the items in the cache. This is an
 139     integer in the range 0 to maxCost().
 140
 141     \sa setMaxCost()
 142 */
 143
 144 /*!
 145     \fn void Q3IntCache::setMaxCost( int m )
 146
 147     Sets the maximum allowed total cost of the cache to \a m. If the
 148     current total cost is greater than \a m, some items are removed
 149     immediately.
 150
 151     \sa maxCost() totalCost()
 152 */
 153
 154 /*!
 155     \fn uint Q3IntCache::count() const
 156
 157     Returns the number of items in the cache.
 158
 159     \sa totalCost()
 160 */
 161
 162 /*!
 163     \fn uint Q3IntCache::size() const
 164
 165     Returns the size of the hash array used to implement the cache.
 166     This should be a bit larger than count() is likely to be.
 167 */
 168
 169 /*!
 170     \fn bool Q3IntCache::isEmpty() const
 171
 172     Returns TRUE if the cache is empty; otherwise returns FALSE.
 173 */
 174
 175 /*!
 176     \fn bool Q3IntCache::insert( long k, const type *d, int c, int p )
 177
 178     Inserts the item \a d into the cache with key \a k and assigns it
 179     a cost of \a c (default 1). Returns TRUE if it succeeds; otherwise
 180     returns FALSE.
 181
 182     The cache's size is limited, and if the total cost is too high,
 183     Q3IntCache will remove old, least-used items until there is room
 184     for this new item.
 185
 186     The parameter \a p is internal and should be left at the default
 187     value (0).
 188
 189     \warning If this function returns FALSE (for example, the cost \c,
 190     exceeds maxCost()), you must delete \a d yourself. Additionally,
 191     be very careful about using \a d after calling this function. Any
 192     other insertions into the cache, from anywhere in the application
 193     or within Qt itself, could cause the object to be discarded from
 194     the cache and the pointer to become invalid.
 195 */
 196
 197 /*!
 198     \fn bool Q3IntCache::remove( long k )
 199
 200     Removes the item associated with \a k, and returns TRUE if the
 201     item was present in the cache; otherwise returns FALSE.
 202
 203     The item is deleted if auto-deletion has been enabled, i.e. if you
 204     have called setAutoDelete(TRUE).
 205
 206     If there are two or more items with equal keys, the one that was
 207     inserted most recently is removed.
 208
 209     All iterators that refer to the removed item are set to point to
 210     the next item in the cache's traversal order.
 211
 212     \sa take(), clear()
 213 */
 214
 215 /*!
 216     \fn type * Q3IntCache::take( long k )
 217
 218     Takes the item associated with \a k out of the cache without
 219     deleting it, and returns a pointer to the item taken out or 0 if
 220     the key does not exist in the cache.
 221
 222     If there are two or more items with equal keys, the one that was
 223     inserted most recently is taken.
 224
 225     All iterators that refer to the taken item are set to point to the
 226     next item in the cache's traversal order.
 227
 228     \sa remove(), clear()
 229 */
 230
 231 /*!
 232     \fn void Q3IntCache::clear()
 233
 234     Removes all items from the cache, and deletes them if
 235     auto-deletion has been enabled.
 236
 237     All cache iterators that operate this on cache are reset.
 238
 239     \sa remove() take()
 240 */
 241
 242 /*!
 243     \fn type * Q3IntCache::find( long k, bool ref ) const
 244
 245     Returns the item associated with \a k, or 0 if the key does not
 246     exist in the cache. If \a ref is TRUE (the default), the item is
 247     moved to the front of the least recently used list.
 248
 249     If there are two or more items with equal keys, the one that was
 250     inserted most recently is returned.
 251 */
 252
 253 /*!
 254     \fn type * Q3IntCache::operator[]( long k ) const
 255
 256     Returns the item associated with \a k, or 0 if \a k does not exist
 257     in the cache, and moves the item to the front of the least
 258     recently used list.
 259
 260     If there are two or more items with equal keys, the one that was
 261     inserted most recently is returned.
 262
 263     This is the same as find( k, TRUE ).
 264
 265     \sa find()
 266 */
 267
 268 /*!
 269     \fn void Q3IntCache::statistics() const
 270
 271     A debug-only utility function. Prints out cache usage, hit/miss,
 272     and distribution information using qDebug(). This function does
 273     nothing in the release library.
 274 */
 275
 276 /*!
 277     \class Q3IntCacheIterator
 278     \brief The Q3IntCacheIterator class provides an iterator for Q3IntCache collections.
 279     \compat
 280
 281     Note that the traversal order is arbitrary; you are not guaranteed
 282     any particular order. If new objects are inserted into the cache
 283     while the iterator is active, the iterator may or may not see
 284     them.
 285
 286     Multiple iterators are completely independent, even when they
 287     operate on the same Q3IntCache. Q3IntCache updates all iterators
 288     that refer an item when that item is removed.
 289
 290     Q3IntCacheIterator provides an operator++(), and an operator+=() to
 291     traverse the cache; current() and currentKey() to access the
 292     current cache item and its key; atFirst() atLast(), which return
 293     TRUE if the iterator points to the first/last item in the cache;
 294     isEmpty(), which returns TRUE if the cache is empty; and count(),
 295     which returns the number of items in the cache.
 296
 297     Note that atFirst() and atLast() refer to the iterator's arbitrary
 298     ordering, not to the cache's internal least recently used list.
 299
 300     \sa Q3IntCache
 301 */
 302
 303 /*!
 304     \fn Q3IntCacheIterator::Q3IntCacheIterator( const Q3IntCache<type> &cache )
 305
 306     Constructs an iterator for \a cache. The current iterator item is
 307     set to point to the first item in the \a cache (or rather, the
 308     first item is defined to be the item at which this constructor
 309     sets the iterator to point).
 310 */
 311
 312 /*!
 313     \fn Q3IntCacheIterator::Q3IntCacheIterator (const Q3IntCacheIterator<type> & ci)
 314
 315     Constructs an iterator for the same cache as \a ci. The new
 316     iterator starts at the same item as ci.current(), but moves
 317     independently from there on.
 318 */
 319
 320 /*!
 321     \fn Q3IntCacheIterator<type>& Q3IntCacheIterator::operator=( const Q3IntCacheIterator<type> &ci )
 322
 323     Makes this an iterator for the same cache as \a ci. The new
 324     iterator starts at the same item as ci.current(), but moves
 325     independently thereafter.
 326 */
 327
 328 /*!
 329     \fn uint Q3IntCacheIterator::count() const
 330
 331     Returns the number of items in the cache on which this iterator
 332     operates.
 333
 334     \sa isEmpty()
 335 */
 336
 337 /*!
 338     \fn bool Q3IntCacheIterator::isEmpty() const
 339
 340     Returns TRUE if the cache is empty; otherwise returns FALSE.
 341
 342     \sa count()
 343 */
 344
 345 /*!
 346     \fn bool Q3IntCacheIterator::atFirst() const
 347
 348     Returns TRUE if the iterator points to the first item in the
 349     cache; otherwise returns FALSE. Note that this refers to the
 350     iterator's arbitrary ordering, not to the cache's internal least
 351     recently used list.
 352
 353     \sa toFirst(), atLast()
 354 */
 355
 356 /*!
 357     \fn bool Q3IntCacheIterator::atLast() const
 358
 359     Returns TRUE if the iterator points to the last item in the cache;
 360     otherwise returns FALSE. Note that this refers to the iterator's
 361     arbitrary ordering, not to the cache's internal least recently
 362     used list.
 363
 364     \sa toLast(), atFirst()
 365 */
 366
 367 /*!
 368     \fn type *Q3IntCacheIterator::toFirst()
 369
 370     Sets the iterator to point to the first item in the cache and
 371     returns a pointer to the item.
 372
 373     Sets the iterator to 0, and returns 0, if the cache is empty.
 374
 375     \sa toLast() isEmpty()
 376 */
 377
 378 /*!
 379     \fn type *Q3IntCacheIterator::toLast()
 380
 381     Sets the iterator to point to the last item in the cache and
 382     returns a pointer to the item.
 383
 384     Sets the iterator to 0, and returns 0, if the cache is empty.
 385
 386     \sa toFirst() isEmpty()
 387 */
 388
 389 /*!
 390     \fn Q3IntCacheIterator::operator type *() const
 391
 392     Cast operator. Returns a pointer to the current iterator item.
 393     Same as current().
 394 */
 395
 396 /*!
 397     \fn type *Q3IntCacheIterator::current() const
 398
 399     Returns a pointer to the current iterator item.
 400 */
 401
 402 /*!
 403     \fn long Q3IntCacheIterator::currentKey() const
 404
 405     Returns the key for the current iterator item.
 406 */
 407
 408 /*!
 409     \fn type *Q3IntCacheIterator::operator()()
 410
 411     Makes the succeeding item current and returns the original current
 412     item.
 413
 414     If the current iterator item was the last item in the cache or if
 415     it was 0, 0 is returned.
 416 */
 417
 418 /*!
 419     \fn type *Q3IntCacheIterator::operator+=( uint jump )
 420
 421     Returns the item \a jump positions after the current item, or 0 if
 422     it is beyond the last item. Makes this the current item.
 423 */
 424
 425 /*!
 426     \fn type *Q3IntCacheIterator::operator-=( uint jump )
 427
 428     Returns the item \a jump positions before the current item, or 0
 429     if it is beyond the first item. Makes this the current item.
 430 */
 431
 432 /*!
 433     \fn type *Q3IntCacheIterator::operator++()
 434
 435     Prefix ++ makes the iterator point to the item just after
 436     current(), and makes it the new current item for the iterator. If
 437     current() was the last item, operator--() returns 0.
 438 */
 439
 440 /*!
 441     \fn type *Q3IntCacheIterator::operator--()
 442
 443     Prefix -- makes the iterator point to the item just before
 444     current(), and makes it the new current item for the iterator. If
 445     current() was the first item, operator--() returns 0.
 446 */