diff options
Diffstat (limited to 'qtools/qgcache.cpp')
| -rw-r--r-- | qtools/qgcache.cpp | 878 |
1 files changed, 0 insertions, 878 deletions
diff --git a/qtools/qgcache.cpp b/qtools/qgcache.cpp deleted file mode 100644 index 230823c..0000000 --- a/qtools/qgcache.cpp +++ /dev/null @@ -1,878 +0,0 @@ -/**************************************************************************** -** -** -** Implementation of QGCache and QGCacheIterator classes -** -** Created : 950208 -** -** Copyright (C) 1992-2000 Trolltech AS. All rights reserved. -** -** This file is part of the tools module of the Qt GUI Toolkit. -** -** This file may be distributed under the terms of the Q Public License -** as defined by Trolltech AS of Norway and appearing in the file -** LICENSE.QPL included in the packaging of this file. -** -** This file may be distributed and/or modified under the terms of the -** GNU General Public License version 2 as published by the Free Software -** Foundation and appearing in the file LICENSE.GPL included in the -** packaging of this file. -** -** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition -** licenses may use this file in accordance with the Qt Commercial License -** Agreement provided with the Software. -** -** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE -** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. -** -** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for -** information about Qt Commercial License Agreements. -** See http://www.trolltech.com/qpl/ for QPL licensing information. -** See http://www.trolltech.com/gpl/ for GPL licensing information. -** -** Contact info@trolltech.com if any conditions of this licensing are -** not clear to you. -** -**********************************************************************/ - -#include "qgcache.h" -#include "qinternallist.h" -#include "qdict.h" -#include "qstring.h" - - -// NOT REVISED -/*! - \class QGCache qgcache.h - - \brief The QGCache class is an internal class for implementing QCache template classes. - - QGCache is a strictly internal class that acts as a base class for the - \link collection.html collection classes\endlink QCache and QIntCache. -*/ - - -/***************************************************************************** - QGCacheItem class (internal cache item) - *****************************************************************************/ - -struct QCacheItem -{ - QCacheItem( void *k, QCollection::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; - QCollection::Item data; - QLNode *node; -}; - - -/***************************************************************************** - QCList class (internal list of cache items) - *****************************************************************************/ - -class QCList : private QInternalList<QCacheItem> -{ -friend class QGCacheIterator; -friend class QCListIt; -public: - QCList() {} - ~QCList(); - - void insert( QCacheItem * ); // insert according to priority - void insert( int, QCacheItem * ); - void take( QCacheItem * ); - void reference( QCacheItem * ); - - void setAutoDelete( bool del ) { QCollection::setAutoDelete(del); } - - bool removeFirst() { return QInternalList<QCacheItem>::removeFirst(); } - bool removeLast() { return QInternalList<QCacheItem>::removeLast(); } - - QCacheItem *first() { return QInternalList<QCacheItem>::first(); } - QCacheItem *last() { return QInternalList<QCacheItem>::last(); } - QCacheItem *prev() { return QInternalList<QCacheItem>::prev(); } - QCacheItem *next() { return QInternalList<QCacheItem>::next(); } - -#if defined(DEBUG) - int inserts; // variables for statistics - int insertCosts; - int insertMisses; - int finds; - int hits; - int hitCosts; - int dumps; - int dumpCosts; -#endif -}; - - -QCList::~QCList() -{ -#if defined(DEBUG) - ASSERT( count() == 0 ); -#endif -} - - -void QCList::insert( QCacheItem *ci ) -{ - QCacheItem *item = first(); - while( item && item->skipPriority > ci->priority ) { - item->skipPriority--; - item = next(); - } - if ( item ) - QInternalList<QCacheItem>::insert( at(), ci ); - else - append( ci ); -#if defined(DEBUG) - ASSERT( ci->node == 0 ); -#endif - ci->node = currentNode(); -} - -inline void QCList::insert( int i, QCacheItem *ci ) -{ - QInternalList<QCacheItem>::insert( i, ci ); -#if defined(DEBUG) - ASSERT( ci->node == 0 ); -#endif - ci->node = currentNode(); -} - - -void QCList::take( QCacheItem *ci ) -{ - if ( ci ) { -#if defined(DEBUG) - ASSERT( ci->node != 0 ); -#endif - takeNode( ci->node ); - ci->node = 0; - } -} - - -inline void QCList::reference( QCacheItem *ci ) -{ -#if defined(DEBUG) - ASSERT( ci != 0 && ci->node != 0 ); -#endif - ci->skipPriority = ci->priority; - relinkNode( ci->node ); // relink as first item -} - - -class QCListIt: public QInternalListIterator<QCacheItem> -{ -public: - QCListIt( const QCList *p ): QInternalListIterator<QCacheItem>( *p ) {} - QCListIt( const QCListIt *p ): QInternalListIterator<QCacheItem>( *p ) {} -}; - - -/***************************************************************************** - QCDict 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 QGDict. -// - -class QCDict : public QGDict -{ -public: - QCDict( uint size, uint kt, bool caseSensitive, bool copyKeys ) - : QGDict( size, (KeyType)kt, caseSensitive, copyKeys ) {} - - QCacheItem *find_string(const QCString &key) const - { return (QCacheItem*)((QCDict*)this)->look_string(key, 0, 0); } - QCacheItem *find_ascii(const char *key) const - { return (QCacheItem*)((QCDict*)this)->look_ascii(key, 0, 0); } - QCacheItem *find_int(long key) const - { return (QCacheItem*)((QCDict*)this)->look_int(key, 0, 0); } - - QCacheItem *take_string(const QCString &key) - { return (QCacheItem*)QGDict::take_string(key); } - QCacheItem *take_ascii(const char *key) - { return (QCacheItem*)QGDict::take_ascii(key); } - QCacheItem *take_int(long key) - { return (QCacheItem*)QGDict::take_int(key); } - - bool insert_string( const QCString &key, const QCacheItem *ci ) - { return QGDict::look_string(key,(Item)ci,1)!=0;} - bool insert_ascii( const char *key, const QCacheItem *ci ) - { return QGDict::look_ascii(key,(Item)ci,1)!=0;} - bool insert_int( long key, const QCacheItem *ci ) - { return QGDict::look_int(key,(Item)ci,1)!=0;} - - bool remove_string( QCacheItem *item ) - { return QGDict::remove_string(*((QCString*)(item->key)),item); } - bool remove_ascii( QCacheItem *item ) - { return QGDict::remove_ascii((const char *)item->key,item); } - bool remove_int( QCacheItem *item ) - { return QGDict::remove_int((intptr_t)item->key,item);} - - void statistics() { QGDict::statistics(); } -}; - - -/***************************************************************************** - QGDict member functions - *****************************************************************************/ - -/*! - \internal - Constructs a cache. -*/ - -QGCache::QGCache( int maxCost, uint size, KeyType kt, bool caseSensitive, - bool copyKeys ) -{ - keytype = kt; - lruList = new QCList; - CHECK_PTR( lruList ); - lruList->setAutoDelete( TRUE ); - copyk = ((keytype == AsciiKey) && copyKeys); - dict = new QCDict( size, kt, caseSensitive, FALSE ); - CHECK_PTR( dict ); - mCost = maxCost; - tCost = 0; -#if defined(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 -} - -/*! - \internal - Cannot copy a cache. -*/ - -QGCache::QGCache( const QGCache & ) - : QCollection() -{ -#if defined(CHECK_NULL) - qFatal( "QGCache::QGCache(QGCache &): Cannot copy a cache" ); -#endif -} - -/*! - \internal - Removes all items from the cache and destroys it. -*/ - -QGCache::~QGCache() -{ - clear(); // delete everything first - delete dict; - delete lruList; -} - -/*! - \internal - Cannot assign a cache. -*/ - -QGCache &QGCache::operator=( const QGCache & ) -{ -#if defined(CHECK_NULL) - qFatal( "QGCache::operator=: Cannot copy a cache" ); -#endif - return *this; // satisfy the compiler -} - - -/*! - \fn uint QGCache::count() const - \internal - Returns the number of items in the cache. -*/ - -/*! - \fn uint QGCache::size() const - \internal - Returns the size of the hash array. -*/ - -/*! - \fn int QGCache::maxCost() const - \internal - Returns the maximum cache cost. -*/ - -/*! - \fn int QGCache::totalCost() const - \internal - Returns the total cache cost. -*/ - -/*! - \internal - Sets the maximum cache cost. -*/ - -void QGCache::setMaxCost( int maxCost ) -{ - if ( maxCost < tCost ) { - if ( !makeRoomFor(tCost - maxCost) ) // remove excess cost - return; - } - mCost = maxCost; -} - - -/*! - \internal - Inserts an item into the cache. - - \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 Qt itself, could cause the - data to be discarded from the cache, and the pointer to become - invalid. -*/ - -bool QGCache::insert_string( const QCString &key, QCollection::Item data, - int cost, int priority) -{ - if ( tCost + cost > mCost ) { - if ( !makeRoomFor(tCost + cost - mCost, priority) ) { -#if defined(DEBUG) - lruList->insertMisses++; -#endif - return FALSE; - } - } -#if defined(DEBUG) - ASSERT( keytype == StringKey ); - lruList->inserts++; - lruList->insertCosts += cost; -#endif - if ( priority < -32768 ) - priority = -32768; - else if ( priority > 32767 ) - priority = 32677; - QCacheItem *ci = new QCacheItem( new QCString(key), newItem(data), - cost, (short)priority ); - CHECK_PTR( ci ); - lruList->insert( 0, ci ); - dict->insert_string( key, ci ); - tCost += cost; - return TRUE; -} - - -/*! \internal */ - -bool QGCache::insert_other( const char *key, QCollection::Item data, - int cost, int priority) -{ - if ( tCost + cost > mCost ) { - if ( !makeRoomFor(tCost + cost - mCost, priority) ) { -#if defined(DEBUG) - lruList->insertMisses++; -#endif - return FALSE; - } - } -#if defined(DEBUG) - 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; - QCacheItem *ci = new QCacheItem( (void*)key, newItem(data), cost, - (short)priority ); - CHECK_PTR( ci ); - lruList->insert( 0, ci ); - if ( keytype == AsciiKey ) - dict->insert_ascii( key, ci ); - else - dict->insert_int( (intptr_t)key, ci ); - tCost += cost; - return TRUE; -} - - -/*! - \internal - Removes an item from the cache. -*/ - -bool QGCache::remove_string( const QCString &key ) -{ - Item d = take_string( key ); - if ( d ) - deleteItem( d ); - return d != 0; -} - - -/*! \internal */ - -bool QGCache::remove_other( const char *key ) -{ - Item d = take_other( key ); - if ( d ) - deleteItem( d ); - return d != 0; -} - - -/*! - \internal - Takes an item out of the cache (no delete). -*/ - -QCollection::Item QGCache::take_string( const QCString &key ) -{ - QCacheItem *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 (QCString*)ci->key; - delete ci; - } else { - d = 0; - } - return d; -} - -/*! - \internal - Takes an item out of the cache (no delete). -*/ - -QCollection::Item QGCache::take_other( const char *key ) -{ - QCacheItem *ci; - if ( keytype == AsciiKey ) - ci = dict->take_ascii( key ); - else - ci = dict->take_int( (intptr_t)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; -} - - -/*! - \internal - Clears the cache. -*/ - -void QGCache::clear() -{ - QCacheItem *ci; - while ( (ci = lruList->first()) ) { - switch ( keytype ) { - case StringKey: - dict->remove_string( ci ); - delete (QCString*)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; -} - - -/*! - \internal - Finds an item in the cache. -*/ - -QCollection::Item QGCache::find_string( const QCString &key, bool ref ) const -{ - QCacheItem *ci = dict->find_string( key ); -#if defined(DEBUG) - lruList->finds++; -#endif - if ( ci ) { -#if defined(DEBUG) - lruList->hits++; - lruList->hitCosts += ci->cost; -#endif - if ( ref ) - lruList->reference( ci ); - return ci->data; - } - return 0; -} - - -/*! - \internal - Finds an item in the cache. -*/ - -QCollection::Item QGCache::find_other( const char *key, bool ref ) const -{ - QCacheItem *ci = keytype == AsciiKey ? dict->find_ascii(key) - : dict->find_int((intptr_t)key); -#if defined(DEBUG) - lruList->finds++; -#endif - if ( ci ) { -#if defined(DEBUG) - lruList->hits++; - lruList->hitCosts += ci->cost; -#endif - if ( ref ) - lruList->reference( ci ); - return ci->data; - } - return 0; -} - - -/*! - \internal - Allocates cache space for one or more items. -*/ - -bool QGCache::makeRoomFor( int cost, int priority ) -{ - if ( cost > mCost ) // cannot make room for more - return FALSE; // than maximum cost - if ( priority == -1 ) - priority = 32767; - QCacheItem *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(DEBUG) - ASSERT( dumps > 0 ); -#endif - while ( dumps-- ) { - ci = lruList->last(); -#if defined(DEBUG) - lruList->dumps++; - lruList->dumpCosts += ci->cost; -#endif - switch ( keytype ) { - case StringKey: - dict->remove_string( ci ); - delete (QCString*)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; -} - - -/*! - \internal - Outputs debug statistics. -*/ - -void QGCache::statistics() const -{ -#if defined(DEBUG) - QCString line; - line.fill( '*', 80 ); - qDebug( "%s",line.data() ); - 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( "%s",line.data() ); -#endif -} - -int QGCache::hits() const -{ - return lruList->hits; -} - -int QGCache::misses() const -{ - return lruList->finds - lruList->hits; -} - - -/***************************************************************************** - QGCacheIterator member functions - *****************************************************************************/ - -/*! - \class QGCacheIterator qgcache.h - - \brief An internal class for implementing QCacheIterator and QIntCacheIterator. - - QGCacheIterator is a strictly internal class that does the heavy work for - QCacheIterator and QIntCacheIterator. -*/ - -/*! - \internal - Constructs an iterator that operates on the cache \e c. -*/ - -QGCacheIterator::QGCacheIterator( const QGCache &c ) -{ - it = new QCListIt( c.lruList ); -#if defined(DEBUG) - ASSERT( it != 0 ); -#endif -} - -/*! - \internal - Constructs an iterator that operates on the same cache as \e ci. -*/ - -QGCacheIterator::QGCacheIterator( const QGCacheIterator &ci ) -{ - it = new QCListIt( ci.it ); -#if defined(DEBUG) - ASSERT( it != 0 ); -#endif -} - -/*! - \internal - Destroys the iterator. -*/ - -QGCacheIterator::~QGCacheIterator() -{ - delete it; -} - -/*! - \internal - Assigns the iterator \e ci to this cache iterator. -*/ - -QGCacheIterator &QGCacheIterator::operator=( const QGCacheIterator &ci ) -{ - *it = *ci.it; - return *this; -} - -/*! - \internal - Returns the number of items in the cache. -*/ - -uint QGCacheIterator::count() const -{ - return it->count(); -} - -/*! - \internal - Returns TRUE if the iterator points to the first item. -*/ - -bool QGCacheIterator::atFirst() const -{ - return it->atFirst(); -} - -/*! - \internal - Returns TRUE if the iterator points to the last item. -*/ - -bool QGCacheIterator::atLast() const -{ - return it->atLast(); -} - -/*! - \internal - Sets the list iterator to point to the first item in the cache. -*/ - -QCollection::Item QGCacheIterator::toFirst() -{ - QCacheItem *item = it->toFirst(); - return item ? item->data : 0; -} - -/*! - \internal - Sets the list iterator to point to the last item in the cache. -*/ - -QCollection::Item QGCacheIterator::toLast() -{ - QCacheItem *item = it->toLast(); - return item ? item->data : 0; -} - -/*! - \internal - Returns the current item. -*/ - -QCollection::Item QGCacheIterator::get() const -{ - QCacheItem *item = it->current(); - return item ? item->data : 0; -} - -/*! - \internal - Returns the key of the current item. -*/ - -QCString QGCacheIterator::getKeyString() const -{ - QCacheItem *item = it->current(); - return item ? *((QCString*)item->key) : QCString(); -} - -/*! - \internal - Returns the key of the current item, as a \0-terminated C string. -*/ - -const char *QGCacheIterator::getKeyAscii() const -{ - QCacheItem *item = it->current(); - return item ? (const char *)item->key : 0; -} - -/*! - \internal - Returns the key of the current item, as a long. -*/ - -intptr_t QGCacheIterator::getKeyInt() const -{ - QCacheItem *item = it->current(); - return item ? (intptr_t)item->key : 0; -} - -/*! - \internal - Moves to the next item (postfix). -*/ - -QCollection::Item QGCacheIterator::operator()() -{ - QCacheItem *item = it->operator()(); - return item ? item->data : 0; -} - -/*! - \internal - Moves to the next item (prefix). -*/ - -QCollection::Item QGCacheIterator::operator++() -{ - QCacheItem *item = it->operator++(); - return item ? item->data : 0; -} - -/*! - \internal - Moves \e jumps positions forward. -*/ - -QCollection::Item QGCacheIterator::operator+=( uint jump ) -{ - QCacheItem *item = it->operator+=(jump); - return item ? item->data : 0; -} - -/*! - \internal - Moves to the previous item (prefix). -*/ - -QCollection::Item QGCacheIterator::operator--() -{ - QCacheItem *item = it->operator--(); - return item ? item->data : 0; -} - -/*! - \internal - Moves \e jumps positions backward. -*/ - -QCollection::Item QGCacheIterator::operator-=( uint jump ) -{ - QCacheItem *item = it->operator-=(jump); - return item ? item->data : 0; -} |