diff options
Diffstat (limited to 'tqtinterface/qt4/src/tools/tqgcache.cpp')
| -rw-r--r-- | tqtinterface/qt4/src/tools/tqgcache.cpp | 866 |
1 files changed, 0 insertions, 866 deletions
diff --git a/tqtinterface/qt4/src/tools/tqgcache.cpp b/tqtinterface/qt4/src/tools/tqgcache.cpp deleted file mode 100644 index 4e16ad7..0000000 --- a/tqtinterface/qt4/src/tools/tqgcache.cpp +++ /dev/null @@ -1,866 +0,0 @@ -/**************************************************************************** -** -** Implementation of TQGCache and TQGCacheIterator classes -** -** Created : 950208 -** -** Copyright (C) 2010 Timothy Pearson and (C) 1992-2008 Trolltech ASA. -** -** This file is part of the tools module of the TQt GUI Toolkit. -** -** This file may be used under the terms of the GNU General -** Public License versions 2.0 or 3.0 as published by the Free -** Software Foundation and appearing in the files LICENSE.GPL2 -** and LICENSE.GPL3 included in the packaging of this file. -** Alternatively you may (at your option) use any later version -** of the GNU General Public License if such license has been -** publicly approved by Trolltech ASA (or its successors, if any) -** and the KDE Free TQt Foundation. -** -** Please review the following information to ensure GNU General -** Public Licensing requirements will be met: -** http://trolltech.com/products/qt/licenses/licensing/opensource/. -** If you are unsure which license is appropriate for your use, please -** review the following information: -** http://trolltech.com/products/qt/licenses/licensing/licensingoverview -** or contact the sales department at sales@trolltech.com. -** -** This file may be used under the terms of the Q Public License as -** defined by Trolltech ASA and appearing in the file LICENSE.TQPL -** included in the packaging of this file. Licensees holding valid TQt -** Commercial licenses may use this file in accordance with the TQt -** Commercial License Agreement provided with the Software. -** -** This file is provided "AS IS" with NO WARRANTY OF ANY KIND, -** INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR -** A PARTICULAR PURPOSE. Trolltech reserves all rights not granted -** herein. -** -**********************************************************************/ - -#include "tqgcache.h" -#include "tqptrlist.h" -#include "tqdict.h" -#include "tqstring.h" - -/*! - \class TQGCache tqgcache.h - \reentrant - \ingroup shared - \ingroup collection - \brief The TQGCache class is an internal class for implementing TQCache - template classes. - - \internal - - TQGCache is a strictly internal class that acts as a base class for the - \link collection.html collection classes\endlink TQCache and TQIntCache. -*/ - - -/***************************************************************************** - TQGCacheItem class (internal cache item) - *****************************************************************************/ - -struct TQCacheItem -{ - TQCacheItem( void *k, TQPtrCollection::Item d, int c, short p ) - : priority(p), skipPriority(p), cost(c), key(k), data(d), node(0) {} - short priority; - short skipPriority; - int cost; - void *key; - TQPtrCollection::Item data; - TQLNode *node; -}; - - -/***************************************************************************** - TQCList class (internal list of cache items) - *****************************************************************************/ - -class TQCList : private TQPtrList<TQCacheItem> -{ -friend class TQGCacheIterator; -friend class TQCListIt; -public: - TQCList() {} - ~TQCList(); - - void insert( TQCacheItem * ); // insert according to priority - void insert( int, TQCacheItem * ); - void take( TQCacheItem * ); - void reference( TQCacheItem * ); - - void setAutoDelete( bool del ) { TQPtrCollection::setAutoDelete(del); } - - bool removeFirst() { return TQPtrList<TQCacheItem>::removeFirst(); } - bool removeLast() { return TQPtrList<TQCacheItem>::removeLast(); } - - TQCacheItem *first() { return TQPtrList<TQCacheItem>::first(); } - TQCacheItem *last() { return TQPtrList<TQCacheItem>::last(); } - TQCacheItem *prev() { return TQPtrList<TQCacheItem>::prev(); } - TQCacheItem *next() { return TQPtrList<TQCacheItem>::next(); } - -#if defined(TQT_DEBUG) - int inserts; // variables for statistics - int insertCosts; - int insertMisses; - int finds; - int hits; - int hitCosts; - int dumps; - int dumpCosts; -#endif -}; - - -TQCList::~TQCList() -{ -#if defined(TQT_DEBUG) - TQ_ASSERT( count() == 0 ); -#endif -} - - -void TQCList::insert( TQCacheItem *ci ) -{ - TQCacheItem *item = first(); - while( item && item->skipPriority > ci->priority ) { - item->skipPriority--; - item = next(); - } - if ( item ) - TQPtrList<TQCacheItem>::insert( at(), ci ); - else - append( ci ); -#if defined(TQT_DEBUG) - TQ_ASSERT( ci->node == 0 ); -#endif - ci->node = currentNode(); -} - -inline void TQCList::insert( int i, TQCacheItem *ci ) -{ - TQPtrList<TQCacheItem>::insert( i, ci ); -#if defined(TQT_DEBUG) - TQ_ASSERT( ci->node == 0 ); -#endif - ci->node = currentNode(); -} - - -void TQCList::take( TQCacheItem *ci ) -{ - if ( ci ) { -#if defined(TQT_DEBUG) - TQ_ASSERT( ci->node != 0 ); -#endif - takeNode( ci->node ); - ci->node = 0; - } -} - - -inline void TQCList::reference( TQCacheItem *ci ) -{ -#if defined(TQT_DEBUG) - TQ_ASSERT( ci != 0 && ci->node != 0 ); -#endif - ci->skipPriority = ci->priority; - relinkNode( ci->node ); // relink as first item -} - - -class TQCListIt: public TQPtrListIterator<TQCacheItem> -{ -public: - TQCListIt( const TQCList *p ): TQPtrListIterator<TQCacheItem>( *p ) {} - TQCListIt( const TQCListIt *p ): TQPtrListIterator<TQCacheItem>( *p ) {} -}; - - -/***************************************************************************** - TQCDict class (internal dictionary of cache items) - *****************************************************************************/ - -// -// Since we need to decide if the dictionary should use an int or const -// char * key (the "bool trivial" argument in the constructor below) -// we cannot use the macro/template dict, but inherit directly from TQGDict. -// - -class TQCDict : public TQGDict -{ -public: - TQCDict( uint size, uint kt, bool caseSensitive, bool copyKeys ) - : TQGDict( size, (KeyType)kt, caseSensitive, copyKeys ) {} - ~TQCDict(); - - void clear() { TQGDict::clear(); } - - TQCacheItem *find_string(const TQString &key) const - { return (TQCacheItem*)((TQCDict*)this)->look_string(key, 0, 0); } - TQCacheItem *find_ascii(const char *key) const - { return (TQCacheItem*)((TQCDict*)this)->look_ascii(key, 0, 0); } - TQCacheItem *find_int(long key) const - { return (TQCacheItem*)((TQCDict*)this)->look_int(key, 0, 0); } - - TQCacheItem *take_string(const TQString &key) - { return (TQCacheItem*)TQGDict::take_string(key); } - TQCacheItem *take_ascii(const char *key) - { return (TQCacheItem*)TQGDict::take_ascii(key); } - TQCacheItem *take_int(long key) - { return (TQCacheItem*)TQGDict::take_int(key); } - - bool insert_string( const TQString &key, const TQCacheItem *ci ) - { return TQGDict::look_string(key,(Item)ci,1)!=0;} - bool insert_ascii( const char *key, const TQCacheItem *ci ) - { return TQGDict::look_ascii(key,(Item)ci,1)!=0;} - bool insert_int( long key, const TQCacheItem *ci ) - { return TQGDict::look_int(key,(Item)ci,1)!=0;} - - bool remove_string( TQCacheItem *item ) - { return TQGDict::remove_string(*((TQString*)(item->key)),item); } - bool remove_ascii( TQCacheItem *item ) - { return TQGDict::remove_ascii((const char *)item->key,item); } - bool remove_int( TQCacheItem *item ) - { return TQGDict::remove_int((long)item->key,item);} - - void statistics() { TQGDict::statistics(); } - -private: - void deleteItem( void *item ) - { if ( del_item ) { TQCacheItem *d = (TQCacheItem*)item; delete d; } } -}; - -inline TQCDict::~TQCDict() -{ - clear(); -} - -/***************************************************************************** - TQGDict member functions - *****************************************************************************/ - -/*! - Constructs a cache. - The maximum cost of the cache is given by \a maxCost and the size by \a - size. The key type is \a kt which may be \c StringKey, \c AsciiKey, - \c IntKey or \c PtrKey. The case-sensitivity of lookups is set with - \a caseSensitive. Keys are copied if \a copyKeys is TRUE. -*/ - -TQGCache::TQGCache( int maxCost, uint size, KeyType kt, bool caseSensitive, - bool copyKeys ) -{ - keytype = kt; - lruList = new TQCList; - TQ_CHECK_PTR( lruList ); - lruList->setAutoDelete( TRUE ); - copyk = ((keytype == AsciiKey) && copyKeys); - dict = new TQCDict( size, kt, caseSensitive, FALSE ); - TQ_CHECK_PTR( dict ); - mCost = maxCost; - tCost = 0; -#if defined(TQT_DEBUG) - lruList->inserts = 0; - lruList->insertCosts = 0; - lruList->insertMisses = 0; - lruList->finds = 0; - lruList->hits = 0; - lruList->hitCosts = 0; - lruList->dumps = 0; - lruList->dumpCosts = 0; -#endif -} - -/*! - Cannot copy a cache. -*/ - -TQGCache::TQGCache( const TQGCache & ) - : TQPtrCollection() -{ -#if defined(TQT_CHECK_NULL) - qFatal( "TQGCache::TQGCache(TQGCache &): Cannot copy a cache" ); -#endif -} - -/*! - Removes all items from the cache and destroys it. -*/ - -TQGCache::~TQGCache() -{ - clear(); - delete dict; - delete lruList; -} - -/*! - Cannot assign a cache. -*/ - -TQGCache &TQGCache::operator=( const TQGCache & ) -{ -#if defined(TQT_CHECK_NULL) - qFatal( "TQGCache::operator=: Cannot copy a cache" ); -#endif - return *this; -} - - -/*! - Returns the number of items in the cache. -*/ - -uint TQGCache::count() const -{ - return dict->count(); -} - -/*! - Returns the size of the hash array. -*/ - -uint TQGCache::size() const -{ - return dict->size(); -} - -/*! - \fn int TQGCache::maxCost() const - - Returns the maximum cache cost. -*/ - -/*! - \fn int TQGCache::totalCost() const - - Returns the total cache cost. -*/ - -/*! - Sets the maximum cache cost to \a maxCost. -*/ - -void TQGCache::setMaxCost( int maxCost ) -{ - if ( maxCost < tCost ) { - if ( !makeRoomFor(tCost - maxCost) ) // remove excess cost - return; - } - mCost = maxCost; -} - - -/*! - Inserts an item with data \a data into the cache using key \a key. - The item has cost \a cost and priority \a priority. - - \warning If this function returns FALSE, you must delete \a data - yourself. Additionally, be very careful about using \a data after - calling this function, as any other insertions into the cache, from - anywhere in the application, or within TQt itself, could cause the - data to be discarded from the cache, and the pointer to become - invalid. -*/ - -bool TQGCache::insert_string( const TQString &key, TQPtrCollection::Item data, - int cost, int priority) -{ - if ( tCost + cost > mCost ) { - if ( !makeRoomFor(tCost + cost - mCost, priority) ) { -#if defined(TQT_DEBUG) - lruList->insertMisses++; -#endif - return FALSE; - } - } -#if defined(TQT_DEBUG) - TQ_ASSERT( keytype == StringKey ); - lruList->inserts++; - lruList->insertCosts += cost; -#endif - if ( priority < -32768 ) - priority = -32768; - else if ( priority > 32767 ) - priority = 32677; - TQCacheItem *ci = new TQCacheItem( new TQString(key), newItem(data), - cost, (short)priority ); - TQ_CHECK_PTR( ci ); - lruList->insert( 0, ci ); - dict->insert_string( key, ci ); - tCost += cost; - return TRUE; -} - -bool TQGCache::insert_other( const char *key, TQPtrCollection::Item data, - int cost, int priority) -{ - if ( tCost + cost > mCost ) { - if ( !makeRoomFor(tCost + cost - mCost, priority) ) { -#if defined(TQT_DEBUG) - lruList->insertMisses++; -#endif - return FALSE; - } - } -#if defined(TQT_DEBUG) - TQ_ASSERT( keytype != StringKey ); - lruList->inserts++; - lruList->insertCosts += cost; -#endif - if ( keytype == AsciiKey && copyk ) - key = qstrdup( key ); - if ( priority < -32768 ) - priority = -32768; - else if ( priority > 32767 ) - priority = 32677; - TQCacheItem *ci = new TQCacheItem( (void*)key, newItem(data), cost, - (short)priority ); - TQ_CHECK_PTR( ci ); - lruList->insert( 0, ci ); - if ( keytype == AsciiKey ) - dict->insert_ascii( key, ci ); - else - dict->insert_int( (long)key, ci ); - tCost += cost; - return TRUE; -} - - -/*! - Removes the item with key \a key from the cache. Returns TRUE if the - item was removed; otherwise returns FALSE. -*/ - -bool TQGCache::remove_string( const TQString &key ) -{ - Item d = take_string( key ); - if ( d ) - deleteItem( d ); - return d != 0; -} - -bool TQGCache::remove_other( const char *key ) -{ - Item d = take_other( key ); - if ( d ) - deleteItem( d ); - return d != 0; -} - - -/*! - Takes the item with key \a key out of the cache. The item is not - deleted. If no item has this \a key 0 is returned. -*/ - -TQPtrCollection::Item TQGCache::take_string( const TQString &key ) -{ - TQCacheItem *ci = dict->take_string( key ); // take from dict - Item d; - if ( ci ) { - d = ci->data; - tCost -= ci->cost; - lruList->take( ci ); // take from list - delete (TQString*)ci->key; - delete ci; - } else { - d = 0; - } - return d; -} - -/*! - Takes the item with key \a key out of the cache. The item is not - deleted. If no item has this \a key 0 is returned. -*/ - -TQPtrCollection::Item TQGCache::take_other( const char *key ) -{ - TQCacheItem *ci; - if ( keytype == AsciiKey ) - ci = dict->take_ascii( key ); - else - ci = dict->take_int( (long)key ); - Item d; - if ( ci ) { - d = ci->data; - tCost -= ci->cost; - lruList->take( ci ); // take from list - if ( copyk ) - delete [] (char *)ci->key; - delete ci; - } else { - d = 0; - } - return d; -} - - -/*! - Clears the cache. -*/ - -void TQGCache::clear() -{ - TQCacheItem *ci; - while ( (ci = lruList->first()) ) { - switch ( keytype ) { - case StringKey: - dict->remove_string( ci ); - delete (TQString*)ci->key; - break; - case AsciiKey: - dict->remove_ascii( ci ); - if ( copyk ) - delete [] (char*)ci->key; - break; - case IntKey: - dict->remove_int( ci ); - break; - case PtrKey: // unused - break; - } - deleteItem( ci->data ); // delete data - lruList->removeFirst(); // remove from list - } - tCost = 0; -} - - -/*! - Finds an item for \a key in the cache and adds a reference if \a ref is TRUE. -*/ - -TQPtrCollection::Item TQGCache::find_string( const TQString &key, bool ref ) const -{ - TQCacheItem *ci = dict->find_string( key ); -#if defined(TQT_DEBUG) - lruList->finds++; -#endif - if ( ci ) { -#if defined(TQT_DEBUG) - lruList->hits++; - lruList->hitCosts += ci->cost; -#endif - if ( ref ) - lruList->reference( ci ); - return ci->data; - } - return 0; -} - - -/*! - Finds an item for \a key in the cache and adds a reference if \a ref is TRUE. -*/ - -TQPtrCollection::Item TQGCache::find_other( const char *key, bool ref ) const -{ - TQCacheItem *ci = keytype == AsciiKey ? dict->find_ascii(key) - : dict->find_int((long)key); -#if defined(TQT_DEBUG) - lruList->finds++; -#endif - if ( ci ) { -#if defined(TQT_DEBUG) - lruList->hits++; - lruList->hitCosts += ci->cost; -#endif - if ( ref ) - lruList->reference( ci ); - return ci->data; - } - return 0; -} - - -/*! - Allocates cache space for one or more items. -*/ - -bool TQGCache::makeRoomFor( int cost, int priority ) -{ - if ( cost > mCost ) // cannot make room for more - return FALSE; // than maximum cost - if ( priority == -1 ) - priority = 32767; - register TQCacheItem *ci = lruList->last(); - int cntCost = 0; - int dumps = 0; // number of items to dump - while ( cntCost < cost && ci && ci->skipPriority <= priority ) { - cntCost += ci->cost; - ci = lruList->prev(); - dumps++; - } - if ( cntCost < cost ) // can enough cost be dumped? - return FALSE; // no -#if defined(TQT_DEBUG) - TQ_ASSERT( dumps > 0 ); -#endif - while ( dumps-- ) { - ci = lruList->last(); -#if defined(TQT_DEBUG) - lruList->dumps++; - lruList->dumpCosts += ci->cost; -#endif - switch ( keytype ) { - case StringKey: - dict->remove_string( ci ); - delete (TQString*)ci->key; - break; - case AsciiKey: - dict->remove_ascii( ci ); - if ( copyk ) - delete [] (char *)ci->key; - break; - case IntKey: - dict->remove_int( ci ); - break; - case PtrKey: // unused - break; - } - deleteItem( ci->data ); // delete data - lruList->removeLast(); // remove from list - } - tCost -= cntCost; - return TRUE; -} - - -/*! - Outputs debug statistics. -*/ - -void TQGCache::statistics() const -{ -#if defined(TQT_DEBUG) - TQString line; - line.fill( '*', 80 ); - qDebug( line.ascii() ); - qDebug( "CACHE STATISTICS:" ); - qDebug( "cache contains %d item%s, with a total cost of %d", - count(), count() != 1 ? "s" : "", tCost ); - qDebug( "maximum cost is %d, cache is %d%% full.", - mCost, (200*tCost + mCost) / (mCost*2) ); - qDebug( "find() has been called %d time%s", - lruList->finds, lruList->finds != 1 ? "s" : "" ); - qDebug( "%d of these were hits, items found had a total cost of %d.", - lruList->hits,lruList->hitCosts ); - qDebug( "%d item%s %s been inserted with a total cost of %d.", - lruList->inserts,lruList->inserts != 1 ? "s" : "", - lruList->inserts != 1 ? "have" : "has", lruList->insertCosts ); - qDebug( "%d item%s %s too large or had too low priority to be inserted.", - lruList->insertMisses, lruList->insertMisses != 1 ? "s" : "", - lruList->insertMisses != 1 ? "were" : "was" ); - qDebug( "%d item%s %s been thrown away with a total cost of %d.", - lruList->dumps, lruList->dumps != 1 ? "s" : "", - lruList->dumps != 1 ? "have" : "has", lruList->dumpCosts ); - qDebug( "Statistics from internal dictionary class:" ); - dict->statistics(); - qDebug( line.ascii() ); -#endif -} - - -/***************************************************************************** - TQGCacheIterator member functions - *****************************************************************************/ - -/*! - \class TQGCacheIterator tqgcache.h - \reentrant - \ingroup shared - \ingroup collection - \brief The TQGCacheIterator class is an internal class for implementing TQCacheIterator and - TQIntCacheIterator. - - \internal - - TQGCacheIterator is a strictly internal class that does the heavy work for - TQCacheIterator and TQIntCacheIterator. -*/ - -/*! - Constructs an iterator that operates on the cache \a c. -*/ - -TQGCacheIterator::TQGCacheIterator( const TQGCache &c ) -{ - it = new TQCListIt( c.lruList ); -#if defined(TQT_DEBUG) - TQ_ASSERT( it != 0 ); -#endif -} - -/*! - Constructs an iterator that operates on the same cache as \a ci. -*/ - -TQGCacheIterator::TQGCacheIterator( const TQGCacheIterator &ci ) -{ - it = new TQCListIt( ci.it ); -#if defined(TQT_DEBUG) - TQ_ASSERT( it != 0 ); -#endif -} - -/*! - Destroys the iterator. -*/ - -TQGCacheIterator::~TQGCacheIterator() -{ - delete it; -} - -/*! - Assigns the iterator \a ci to this cache iterator. -*/ - -TQGCacheIterator &TQGCacheIterator::operator=( const TQGCacheIterator &ci ) -{ - *it = *ci.it; - return *this; -} - -/*! - Returns the number of items in the cache. -*/ - -uint TQGCacheIterator::count() const -{ - return it->count(); -} - -/*! - Returns TRUE if the iterator points to the first item. -*/ - -bool TQGCacheIterator::atFirst() const -{ - return it->atFirst(); -} - -/*! - Returns TRUE if the iterator points to the last item. -*/ - -bool TQGCacheIterator::atLast() const -{ - return it->atLast(); -} - -/*! - Sets the list iterator to point to the first item in the cache. -*/ - -TQPtrCollection::Item TQGCacheIterator::toFirst() -{ - TQCacheItem *item = it->toFirst(); - return item ? item->data : 0; -} - -/*! - Sets the list iterator to point to the last item in the cache. -*/ - -TQPtrCollection::Item TQGCacheIterator::toLast() -{ - TQCacheItem *item = it->toLast(); - return item ? item->data : 0; -} - -/*! - Returns the current item. -*/ - -TQPtrCollection::Item TQGCacheIterator::get() const -{ - TQCacheItem *item = it->current(); - return item ? item->data : 0; -} - -/*! - Returns the key of the current item. -*/ - -TQString TQGCacheIterator::getKeyString() const -{ - TQCacheItem *item = it->current(); - return item ? *((TQString*)item->key) : TQString::null; -} - -/*! - Returns the key of the current item, as a \0-terminated C string. -*/ - -const char *TQGCacheIterator::getKeyAscii() const -{ - TQCacheItem *item = it->current(); - return item ? (const char *)item->key : 0; -} - -/*! - Returns the key of the current item, as a long. -*/ - -long TQGCacheIterator::getKeyInt() const -{ - TQCacheItem *item = it->current(); - return item ? (long)item->key : 0; -} - -/*! - Moves to the next item (postfix). -*/ - -TQPtrCollection::Item TQGCacheIterator::operator()() -{ - TQCacheItem *item = it->operator()(); - return item ? item->data : 0; -} - -/*! - Moves to the next item (prefix). -*/ - -TQPtrCollection::Item TQGCacheIterator::operator++() -{ - TQCacheItem *item = it->operator++(); - return item ? item->data : 0; -} - -/*! - Moves \a jump positions forward. -*/ - -TQPtrCollection::Item TQGCacheIterator::operator+=( uint jump ) -{ - TQCacheItem *item = it->operator+=(jump); - return item ? item->data : 0; -} - -/*! - Moves to the previous item (prefix). -*/ - -TQPtrCollection::Item TQGCacheIterator::operator--() -{ - TQCacheItem *item = it->operator--(); - return item ? item->data : 0; -} - -/*! - Moves \a jump positions backward. -*/ - -TQPtrCollection::Item TQGCacheIterator::operator-=( uint jump ) -{ - TQCacheItem *item = it->operator-=(jump); - return item ? item->data : 0; -} |