qgcache.cpp

Trolltech公司发布的图形界面操作系统。可在qt-embedded-2.3.10平台上编译为嵌入式图形界面操作系统。

/**********************************************************************
** Copyright (C) 2000-2005 Trolltech AS.  All rights reserved.
**
** This file is part of the Qtopia Environment.
** 
** This program is free software; you can redistribute it and/or modify it
** under the terms of the GNU General Public License as published by the
** Free Software Foundation; either version 2 of the License, or (at your
** option) any later version.
** 
** A copy of the GNU GPL license version 2 is included in this package as 
** LICENSE.GPL.
**
** This program is distributed in the hope that it will be useful, but
** WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 
** See the GNU General Public License for more details.
**
** In addition, as a special exception Trolltech gives permission to link
** the code of this program with Qtopia applications copyrighted, developed
** and distributed by Trolltech under the terms of the Qtopia Personal Use
** License Agreement. You must comply with the GNU General Public License
** in all respects for all of the code used other than the applications
** licensed under the Qtopia Personal Use License Agreement. If you modify
** this file, you may extend this exception to your version of the file,
** but you are not obligated to do so. If you do not wish to do so, delete
** this exception statement from your version.
** 
** See http://www.trolltech.com/gpl/ for GPL licensing information.
**
** Contact [e-mail] if any conditions of this licensing are
** not clear to you.
**
**********************************************************************/

#include "qgcache.h"
#include "qptrlist.h"
#include "qdict.h"
#include "qstring.h"

/*!
  \class QGCache qgcache.h
  \reentrant
  \ingroup shared
  \ingroup collection
  \brief The QGCache class is an internal class for implementing QCache
  template classes.

  \internal

  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, QPtrCollection::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;
    QPtrCollection::Item data;
    QLNode     *node;
};


/*****************************************************************************
  QCList class (internal list of cache items)
 *****************************************************************************/

class QCList : private QPtrList<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 ) { QPtrCollection::setAutoDelete(del); }

    bool	removeFirst()	{ return QPtrList<QCacheItem>::removeFirst(); }
    bool	removeLast()	{ return QPtrList<QCacheItem>::removeLast(); }

    QCacheItem *first()		{ return QPtrList<QCacheItem>::first(); }
    QCacheItem *last()		{ return QPtrList<QCacheItem>::last(); }
    QCacheItem *prev()		{ return QPtrList<QCacheItem>::prev(); }
    QCacheItem *next()		{ return QPtrList<QCacheItem>::next(); }

#if defined(QT_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(QT_DEBUG)
    Q_ASSERT( count() == 0 );
#endif
}


void QCList::insert( QCacheItem *ci )
{
    QCacheItem *item = first();
    while( item && item->skipPriority > ci->priority ) {
	item->skipPriority--;
	item = next();
    }
    if ( item )
	QPtrList<QCacheItem>::insert( at(), ci );
    else
	append( ci );
#if defined(QT_DEBUG)
    Q_ASSERT( ci->node == 0 );
#endif
    ci->node = currentNode();
}

inline void QCList::insert( int i, QCacheItem *ci )
{
    QPtrList<QCacheItem>::insert( i, ci );
#if defined(QT_DEBUG)
    Q_ASSERT( ci->node == 0 );
#endif
    ci->node = currentNode();
}


void QCList::take( QCacheItem *ci )
{
    if ( ci ) {
#if defined(QT_DEBUG)
	Q_ASSERT( ci->node != 0 );
#endif
	takeNode( ci->node );
	ci->node = 0;
    }
}


inline void QCList::reference( QCacheItem *ci )
{
#if defined(QT_DEBUG)
    Q_ASSERT( ci != 0 && ci->node != 0 );
#endif
    ci->skipPriority = ci->priority;
    relinkNode( ci->node );			// relink as first item
}


class QCListIt: public QPtrListIterator<QCacheItem>
{
public:
    QCListIt( const QCList *p ): QPtrListIterator<QCacheItem>( *p ) {}
    QCListIt( const QCListIt *p ): QPtrListIterator<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 ) {}
    ~QCDict();

    void clear() { QGDict::clear(); }

    QCacheItem *find_string(const QString &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 QString &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 QString &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(*((QString*)(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((long)item->key,item);}

    void  statistics()			{ QGDict::statistics(); }

private:
    void deleteItem( void *item )
	{ if ( del_item ) { QCacheItem *d = (QCacheItem*)item; delete d; } }
};

inline QCDict::~QCDict()
{
    clear();
}

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

QGCache::QGCache( int maxCost, uint size, KeyType kt, bool caseSensitive,
		  bool copyKeys )
{
    keytype = kt;
    lruList = new QCList;
    Q_CHECK_PTR( lruList );
    lruList->setAutoDelete( TRUE );
    copyk   = ((keytype == AsciiKey) && copyKeys);
    dict    = new QCDict( size, kt, caseSensitive, FALSE );
    Q_CHECK_PTR( dict );
    mCost   = maxCost;
    tCost   = 0;
#if defined(QT_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.
*/

QGCache::QGCache( const QGCache & )
    : QPtrCollection()
{
#if defined(QT_CHECK_NULL)
    qFatal( "QGCache::QGCache(QGCache &): Cannot copy a cache" );
#endif
}

/*!
  Removes all items from the cache and destroys it.
*/

QGCache::~QGCache()
{
    clear();
    delete dict;
    delete lruList;
}

/*!
  Cannot assign a cache.
*/

QGCache &QGCache::operator=( const QGCache & )
{
#if defined(QT_CHECK_NULL)
    qFatal( "QGCache::operator=: Cannot copy a cache" );
#endif
    return *this;
}


/*!
  Returns the number of items in the cache.
*/

uint QGCache::count() const
{
    return dict->count();
}

/*!
  Returns the size of the hash array.
*/

uint QGCache::size() const
{
    return dict->size();
}

/*!
  \fn int QGCache::maxCost() const

  Returns the maximum cache cost.
*/

/*!
  \fn int QGCache::totalCost() const

  Returns the total cache cost.
*/

/*!
  Sets the maximum cache cost to \a maxCost.
*/

void QGCache::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 Qt itself, could cause the
  data to be discarded from the cache, and the pointer to become
  invalid.
*/

bool QGCache::insert_string( const QString &key, QPtrCollection::Item data,
			     int cost, int priority)
{
    if ( tCost + cost > mCost ) {
	if ( !makeRoomFor(tCost + cost - mCost, priority) ) {
#if defined(QT_DEBUG)
	    lruList->insertMisses++;
#endif
	    return FALSE;
	}
    }
#if defined(QT_DEBUG)
    Q_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 QString(key), newItem(data),
				     cost, (short)priority );
    Q_CHECK_PTR( ci );
    lruList->insert( 0, ci );
    dict->insert_string( key, ci );
    tCost += cost;
    return TRUE;
}

bool QGCache::insert_other( const char *key, QPtrCollection::Item data,
			    int cost, int priority)
{
    if ( tCost + cost > mCost ) {
	if ( !makeRoomFor(tCost + cost - mCost, priority) ) {
#if defined(QT_DEBUG)
	    lruList->insertMisses++;
#endif
	    return FALSE;
	}
    }
#if defined(QT_DEBUG)
    Q_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 );
    Q_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.