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 */