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 Q3Cache

    44     \brief The Q3Cache class is a template class that provides a cache based on QString keys.

    45     \compat

    46 

    47     A cache is a least recently used (LRU) list of cache items. Each

    48     cache item has a key and a certain cost. The sum of item costs,

    49     totalCost(), never exceeds the maximum cache cost, maxCost(). If

    50     inserting a new item would cause the total cost to exceed the

    51     maximum cost, the least recently used items in the cache are

    52     removed.

    53 

    54     Q3Cache is a template class. Q3Cache\<X\> defines a cache that

    55     operates on pointers to X, or X*.

    56 

    57     Apart from insert(), by far the most important function is find()

    58     (which also exists as operator[]()). This function looks up an

    59     item, returns it, and by default marks it as being the most

    60     recently used item.

    61 

    62     There are also methods to remove() or take() an object from the

    63     cache. Calling setAutoDelete(TRUE) for a cache tells it to delete

    64     items that are removed. The default is to not delete items when

    65     they are removed (i.e., remove() and take() are equivalent).

    66 

    67     When inserting an item into the cache, only the pointer is copied,

    68     not the item itself. This is called a shallow copy. It is possible

    69     to make the cache copy all of the item's data (known as a deep

    70     copy) when an item is inserted. insert() calls the virtual

    71     function Q3PtrCollection::newItem() for the item to be inserted.

    72     Inherit a cache and reimplement newItem() if you want deep copies.

    73 

    74     When removing a cache item, the virtual function

    75     Q3PtrCollection::deleteItem() is called. The default

    76     implementation deletes the item if auto-deletion is enabled, and

    77     does nothing otherwise.

    78 

    79     There is a Q3CacheIterator that can be used to traverse the items

    80     in the cache in arbitrary order.

    81 

    82     In Q3Cache, the cache items are accessed via QString keys, which

    83     are Unicode strings. If you want to use non-Unicode, plain 8-bit

    84     \c char* keys, use the Q3AsciiCache template. A Q3Cache has the

    85     same performance as a Q3AsciiCache.

    86 

    87     \sa Q3CacheIterator, Q3AsciiCache, Q3IntCache

    88 */

    89 

    90 /*!

    91   \fn Q3Cache::Q3Cache( const Q3Cache<type> &c )

    92 

    93   \internal

    94 

    95   Do not use. A Q3Cache cannot be copied. Calls qFatal() in debug version.

    96 */

    97 

    98 

    99 /*!

   100     \fn Q3Cache::Q3Cache( int maxCost, int size, bool caseSensitive )

   101 

   102     Constructs a cache whose contents will never have a total cost

   103     greater than \a maxCost and which is expected to contain less than

   104     \a size items.

   105 

   106     \a size is actually the size of an internal hash array; it's

   107     usually best to make it a prime number and at least 50% bigger

   108     than the largest expected number of items in the cache.

   109 

   110     Each inserted item has an associated cost. When inserting a new

   111     item, if the total cost of all items in the cache will exceed \a

   112     maxCost, the cache will start throwing out the older (least

   113     recently used) items until there is enough room for the new item

   114     to be inserted.

   115 

   116     If \a caseSensitive is TRUE (the default), the cache keys are case

   117     sensitive; if it is FALSE, they are case-insensitive.

   118     Case-insensitive comparison considers all Unicode letters.

   119 */

   120 

   121 /*!

   122     \fn Q3Cache::~Q3Cache()

   123 

   124     Removes all items from the cache and destroys it. All iterators

   125     that access this cache will be reset.

   126 */

   127 

   128 /*!

   129   \fn Q3Cache<type>& Q3Cache::operator=( const Q3Cache<type> &c )

   130 

   131   \internal

   132 

   133   Do not use. A Q3Cache cannot be copied. Calls qFatal() in debug version.

   134 */

   135 

   136 /*!

   137     \fn int Q3Cache::maxCost() const

   138 

   139     Returns the maximum allowed total cost of the cache.

   140 

   141     \sa setMaxCost() totalCost()

   142 */

   143 

   144 /*!

   145     \fn int Q3Cache::totalCost() const

   146 

   147     Returns the total cost of the items in the cache. This is an

   148     integer in the range 0 to maxCost().

   149 

   150     \sa setMaxCost()

   151 */

   152 

   153 /*!

   154     \fn void Q3Cache::setMaxCost( int m )

   155 

   156     Sets the maximum allowed total cost of the cache to \a m. If the

   157     current total cost is greater than \a m, some items are deleted

   158     immediately.

   159 

   160     \sa maxCost() totalCost()

   161 */

   162 

   163 /*!

   164     \fn uint Q3Cache::count() const

   165 

   166     Returns the number of items in the cache.

   167 

   168     \sa totalCost()

   169 */

   170 

   171 /*!

   172     \fn uint Q3Cache::size() const

   173 

   174     Returns the size of the hash array used to implement the cache.

   175     This should be a bit bigger than count() is likely to be.

   176 */

   177 

   178 /*!

   179     \fn bool Q3Cache::isEmpty() const

   180 

   181     Returns TRUE if the cache is empty; otherwise returns FALSE.

   182 */

   183 

   184 /*!

   185     \fn bool Q3Cache::insert( const QString &k, const type *d, int c, int p )

   186 

   187     Inserts the item \a d into the cache with key \a k and associated

   188     cost, \a c. Returns TRUE if it is successfully inserted; otherwise

   189     returns FALSE.

   190 

   191     The cache's size is limited, and if the total cost is too high,

   192     Q3Cache will remove old, least recently used items until there is

   193     room for this new item.

   194 

   195     The parameter \a p is internal and should be left at the default

   196     value (0).

   197 

   198     \warning If this function returns FALSE (which could happen, e.g.

   199     if the cost of this item alone exceeds maxCost()) you must delete

   200     \a d yourself. Additionally, be very careful about using \a d

   201     after calling this function because any other insertions into the

   202     cache, from anywhere in the application or within Qt itself, could

   203     cause the object to be discarded from the cache and the pointer to

   204     become invalid.

   205 */

   206 

   207 /*!

   208     \fn bool Q3Cache::remove( const QString &k )

   209 

   210     Removes the item associated with \a k, and returns TRUE if the

   211     item was present in the cache; otherwise returns FALSE.

   212 

   213     The item is deleted if auto-deletion has been enabled, i.e., if

   214     you have called setAutoDelete(TRUE).

   215 

   216     If there are two or more items with equal keys, the one that was

   217     inserted last is removed.

   218 

   219     All iterators that refer to the removed item are set to point to

   220     the next item in the cache's traversal order.

   221 

   222     \sa take(), clear()

   223 */

   224 

   225 /*!

   226     \fn type *Q3Cache::take( const QString &k )

   227 

   228     Takes the item associated with \a k out of the cache without

   229     deleting it, and returns a pointer to the item taken out, or 0

   230     if the key does not exist in the cache.

   231 

   232     If there are two or more items with equal keys, the one that was

   233     inserted last is taken.

   234 

   235     All iterators that refer to the taken item are set to point to the

   236     next item in the cache's traversal order.

   237 

   238     \sa remove(), clear()

   239 */

   240 

   241 /*!

   242     \fn void Q3Cache::clear()

   243 

   244     Removes all items from the cache and deletes them if auto-deletion

   245     has been enabled.

   246 

   247     All cache iterators that operate this on cache are reset.

   248 

   249     \sa remove() take()

   250 */

   251 

   252 /*!

   253     \fn type *Q3Cache::find( const QString &k, bool ref ) const

   254 

   255     Returns the item associated with key \a k, or 0 if the key does

   256     not exist in the cache. If \a ref is TRUE (the default), the item

   257     is moved to the front of the least recently used list.

   258 

   259     If there are two or more items with equal keys, the one that was

   260     inserted last is returned.

   261 */

   262 

   263 /*!

   264     \fn type *Q3Cache::operator[]( const QString &k ) const

   265 

   266     Returns the item associated with key \a k, or 0 if \a k does not

   267     exist in the cache, and moves the item to the front of the least

   268     recently used list.

   269 

   270     If there are two or more items with equal keys, the one that was

   271     inserted last is returned.

   272 

   273     This is the same as find( k, TRUE ).

   274 

   275     \sa find()

   276 */

   277 

   278 /*!

   279     \fn void Q3Cache::statistics() const

   280 

   281     A debug-only utility function. Prints out cache usage, hit/miss,

   282     and distribution information using qDebug(). This function does

   283     nothing in the release library.

   284 */

   285 

   286 /*****************************************************************************

   287   Q3CacheIterator documentation

   288  *****************************************************************************/

   289 

   290 /*!

   291     \class Q3CacheIterator qcache.h

   292     \brief The Q3CacheIterator class provides an iterator for Q3Cache collections.

   293     \compat

   294 

   295     Note that the traversal order is arbitrary; you are not guaranteed

   296     any particular order. If new objects are inserted into the cache

   297     while the iterator is active, the iterator may or may not see

   298     them.

   299 

   300     Multiple iterators are completely independent, even when they

   301     operate on the same Q3Cache. Q3Cache updates all iterators that

   302     refer an item when that item is removed.

   303 

   304     Q3CacheIterator provides an operator++(), and an operator+=() to

   305     traverse the cache. The current() and currentKey() functions are

   306     used to access the current cache item and its key. The atFirst()

   307     and atLast() return TRUE if the iterator points to the first or

   308     last item in the cache respectively. The isEmpty() function

   309     returns TRUE if the cache is empty, and count() returns the number

   310     of items in the cache.

   311 

   312     Note that atFirst() and atLast() refer to the iterator's arbitrary

   313     ordering, not to the cache's internal least recently used list.

   314 

   315     \sa Q3Cache

   316 */

   317 

   318 /*!

   319     \fn Q3CacheIterator::Q3CacheIterator( const Q3Cache<type> &cache )

   320 

   321     Constructs an iterator for \a cache. The current iterator item is

   322     set to point to the first item in the \a cache.

   323 */

   324 

   325 /*!

   326     \fn Q3CacheIterator::Q3CacheIterator (const Q3CacheIterator<type> & ci)

   327 

   328     Constructs an iterator for the same cache as \a ci. The new

   329     iterator starts at the same item as ci.current(), but moves

   330     independently from there on.

   331 */

   332 

   333 /*!

   334     \fn Q3CacheIterator<type>& Q3CacheIterator::operator=( const Q3CacheIterator<type> &ci )

   335 

   336     Makes this an iterator for the same cache as \a ci. The new

   337     iterator starts at the same item as ci.current(), but moves

   338     independently thereafter.

   339 */

   340 

   341 /*!

   342     \fn uint Q3CacheIterator::count() const

   343 

   344     Returns the number of items in the cache on which this iterator

   345     operates.

   346 

   347     \sa isEmpty()

   348 */

   349 

   350 /*!

   351     \fn bool Q3CacheIterator::isEmpty() const

   352 

   353     Returns TRUE if the cache is empty, i.e. count() == 0; otherwise

   354     it returns FALSE.

   355     

   356     \sa count()

   357 */

   358 

   359 /*!

   360     \fn bool Q3CacheIterator::atFirst() const

   361 

   362     Returns TRUE if the iterator points to the first item in the

   363     cache; otherwise returns FALSE. Note that this refers to the

   364     iterator's arbitrary ordering, not to the cache's internal least

   365     recently used list.

   366 

   367     \sa toFirst(), atLast()

   368 */

   369 

   370 /*!

   371     \fn bool Q3CacheIterator::atLast() const

   372 

   373     Returns TRUE if the iterator points to the last item in the cache;

   374     otherwise returns FALSE. Note that this refers to the iterator's

   375     arbitrary ordering, not to the cache's internal least recently

   376     used list.

   377 

   378     \sa toLast(), atFirst()

   379 */

   380 

   381 /*!

   382     \fn type *Q3CacheIterator::toFirst()

   383 

   384     Sets the iterator to point to the first item in the cache and

   385     returns a pointer to the item.

   386 

   387     Sets the iterator to 0 and returns 0 if the cache is empty.

   388 

   389     \sa toLast() isEmpty()

   390 */

   391 

   392 /*!

   393     \fn type *Q3CacheIterator::toLast()

   394 

   395     Sets the iterator to point to the last item in the cache and

   396     returns a pointer to the item.

   397 

   398     Sets the iterator to 0 and returns 0 if the cache is empty.

   399 

   400     \sa toFirst() isEmpty()

   401 */

   402 

   403 /*!

   404     \fn Q3CacheIterator::operator type *() const

   405 

   406     Cast operator. Returns a pointer to the current iterator item.

   407     Same as current().

   408 */

   409 

   410 /*!

   411     \fn type *Q3CacheIterator::current() const

   412 

   413     Returns a pointer to the current iterator item.

   414 */

   415 

   416 /*!

   417     \fn QString Q3CacheIterator::currentKey() const

   418 

   419     Returns the key for the current iterator item.

   420 */

   421 

   422 /*!

   423     \fn type *Q3CacheIterator::operator()()

   424 

   425     Makes the succeeding item current and returns the original current

   426     item.

   427 

   428     If the current iterator item was the last item in the cache or if

   429     it was 0, 0 is returned.

   430 */

   431 

   432 /*!

   433     \fn type *Q3CacheIterator::operator+=( uint jump )

   434 

   435     Returns the item \a jump positions after the current item, or 0 if

   436     it is beyond the last item. Makes this the current item.

   437 */

   438 

   439 /*!

   440     \fn type *Q3CacheIterator::operator-=( uint jump )

   441 

   442     Returns the item \a jump positions before the current item, or 0

   443     if it is before the first item. Makes this the current item.

   444 */

   445 

   446 /*!

   447     \fn type *Q3CacheIterator::operator++()

   448 

   449     Prefix++ makes the iterator point to the item just after current()

   450     and makes that the new current item for the iterator. If current()

   451     was the last item, operator++() returns 0.

   452 */

   453 

   454 /*!

   455     \fn type *Q3CacheIterator::operator--()

   456 

   457     Prefix-- makes the iterator point to the item just before

   458     current() and makes that the new current item for the iterator. If

   459     current() was the first item, operator--() returns 0.

   460 */

   461