Release-1.3.5-20031215

4 files changed, 1103 insertions, 0 deletions

diff --git a/qtools/qcache.h b/qtools/qcache.h
new file mode 100644
index 0000000..39b9139
--- /dev/null
+++ b/qtools/qcache.h
@@ -0,0 +1,104 @@
+/****************************************************************************
+** 
+**
+** Definition of QCache template class
+**
+** Created : 950209
+**
+** 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.
+**
+**********************************************************************/
+
+#ifndef QCACHE_H
+#define QCACHE_H
+
+#ifndef QT_H
+#include "qgcache.h"
+#endif // QT_H
+
+
+template<class type> class Q_EXPORT QCache : public QGCache
+{
+public:
+    QCache( const QCache<type> &c ) : QGCache(c) {}
+    QCache( int maxCost=100, int size=17, bool caseSensitive=TRUE )
+	: QGCache( maxCost, size, StringKey, caseSensitive, FALSE ) {}
+   ~QCache()				{ clear(); }
+    QCache<type> &operator=( const QCache<type> &c )
+			{ return (QCache<type>&)QGCache::operator=(c); }
+    int	  maxCost()   const		{ return QGCache::maxCost(); }
+    int	  totalCost() const		{ return QGCache::totalCost(); }
+    void  setMaxCost( int m )		{ QGCache::setMaxCost(m); }
+    uint  count()     const		{ return QGCache::count(); }
+    uint  size()      const		{ return QGCache::size(); }
+    bool  isEmpty()   const		{ return QGCache::count() == 0; }
+    void  clear()			{ QGCache::clear(); }
+    bool  insert( const QString &k, const type *d, int c=1, int p=0 )
+			{ return QGCache::insert_string(k,(Item)d,c,p);}
+    bool  remove( const QString &k )
+			{ return QGCache::remove_string(k); }
+    type *take( const QString &k )
+			{ return (type *)QGCache::take_string(k); }
+    type *find( const QString &k, bool ref=TRUE ) const
+			{ return (type *)QGCache::find_string(k,ref);}
+    type *operator[]( const QString &k ) const
+			{ return (type *)QGCache::find_string(k);}
+    void  statistics() const	      { QGCache::statistics(); }
+private:
+    void  deleteItem( Item d )	      { if ( del_item ) delete (type *)d; }
+};
+
+
+
+template<class type> class Q_EXPORT QCacheIterator : public QGCacheIterator
+{
+public:
+    QCacheIterator( const QCache<type> &c ):QGCacheIterator((QGCache &)c) {}
+    QCacheIterator( const QCacheIterator<type> &ci)
+				: QGCacheIterator( (QGCacheIterator &)ci ) {}
+    QCacheIterator<type> &operator=(const QCacheIterator<type>&ci)
+	{ return ( QCacheIterator<type>&)QGCacheIterator::operator=( ci ); }
+    uint  count()   const     { return QGCacheIterator::count(); }
+    bool  isEmpty() const     { return QGCacheIterator::count() == 0; }
+    bool  atFirst() const     { return QGCacheIterator::atFirst(); }
+    bool  atLast()  const     { return QGCacheIterator::atLast(); }
+    type *toFirst()	      { return (type *)QGCacheIterator::toFirst(); }
+    type *toLast()	      { return (type *)QGCacheIterator::toLast(); }
+    operator type *() const   { return (type *)QGCacheIterator::get(); }
+    type *current()   const   { return (type *)QGCacheIterator::get(); }
+    QString currentKey() const{ return QGCacheIterator::getKeyString(); }
+    type *operator()()	      { return (type *)QGCacheIterator::operator()();}
+    type *operator++()	      { return (type *)QGCacheIterator::operator++(); }
+    type *operator+=(uint j)  { return (type *)QGCacheIterator::operator+=(j);}
+    type *operator--()	      { return (type *)QGCacheIterator::operator--(); }
+    type *operator-=(uint j)  { return (type *)QGCacheIterator::operator-=(j);}
+};
+
+
+#endif // QCACHE_H
diff --git a/qtools/qgcache.cpp b/qtools/qgcache.cpp
new file mode 100644
index 0000000..1fd876d
--- /dev/null
+++ b/qtools/qgcache.cpp
@@ -0,0 +1,868 @@
+/****************************************************************************
+** 
+**
+** 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 "qlist.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 QList<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 QList<QCacheItem>::removeFirst(); }
+    bool	removeLast()	{ return QList<QCacheItem>::removeLast(); }
+
+    QCacheItem *first()		{ return QList<QCacheItem>::first(); }
+    QCacheItem *last()		{ return QList<QCacheItem>::last(); }
+    QCacheItem *prev()		{ return QList<QCacheItem>::prev(); }
+    QCacheItem *next()		{ return QList<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 )
+	QList<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 )
+{
+    QList<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 QListIterator<QCacheItem>
+{
+public:
+    QCListIt( const QCList *p ): QListIterator<QCacheItem>( *p ) {}
+    QCListIt( const QCListIt *p ): QListIterator<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 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(); }
+};
+
+
+/*****************************************************************************
+  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 QString &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 QString(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( (long)key, ci );
+    tCost += cost;
+    return TRUE;
+}
+
+
+/*!
+  \internal
+  Removes an item from the cache.
+*/
+
+bool QGCache::remove_string( const QString &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 QString &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 (QString*)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( (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;
+}
+
+
+/*!
+  \internal
+  Clears the cache.
+*/
+
+void QGCache::clear()
+{
+    QCacheItem *ci;
+    while ( (ci = lruList->first()) ) {
+	switch ( keytype ) {
+	    case StringKey:
+		dict->remove_string( ci );
+		delete (QString*)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 QString &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((long)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;
+    register 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 (QString*)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)
+    QString 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
+}
+
+
+/*****************************************************************************
+  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.
+*/
+
+QString QGCacheIterator::getKeyString() const
+{
+    QCacheItem *item = it->current();
+    return item ? *((QString*)item->key) : QString::null;
+}
+
+/*!
+  \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.
+*/
+
+long QGCacheIterator::getKeyInt() const
+{
+    QCacheItem *item = it->current();
+    return item ? (long)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;
+}
diff --git a/qtools/qgcache.h b/qtools/qgcache.h
new file mode 100644
index 0000000..5c3e126
--- /dev/null
+++ b/qtools/qgcache.h
@@ -0,0 +1,128 @@
+/****************************************************************************
+** 
+**
+** Definition 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.
+**
+**********************************************************************/
+
+#ifndef QGCACHE_H
+#define QGCACHE_H
+
+#ifndef QT_H
+#include "qcollection.h"
+#include "qglist.h"
+#include "qgdict.h"
+#endif // QT_H
+
+
+class QCList;					// internal classes
+class QCListIt;
+class QCDict;
+
+
+class Q_EXPORT QGCache : public QCollection	// generic LRU cache
+{
+friend class QGCacheIterator;
+protected:
+    enum KeyType { StringKey, AsciiKey, IntKey, PtrKey };
+      // identical to QGDict's, but PtrKey is not used at the moment
+
+    QGCache( int maxCost, uint size, KeyType kt, bool caseSensitive,
+	     bool copyKeys );
+    QGCache( const QGCache & );			// not allowed, calls fatal()
+   ~QGCache();
+    QGCache &operator=( const QGCache & );	// not allowed, calls fatal()
+
+    uint    count()	const	{ return ((QGDict*)dict)->count(); }
+    uint    size()	const	{ return ((QGDict*)dict)->size(); }
+    int	    maxCost()	const	{ return mCost; }
+    int	    totalCost() const	{ return tCost; }
+    void    setMaxCost( int maxCost );
+    void    clear();
+
+    bool    insert_string( const QString &key, QCollection::Item,
+			   int cost, int priority );
+    bool    insert_other( const char *key, QCollection::Item,
+			  int cost, int priority );
+    bool    remove_string( const QString &key );
+    bool    remove_other( const char *key );
+    QCollection::Item take_string( const QString &key );
+    QCollection::Item take_other( const char *key );
+
+    QCollection::Item find_string( const QString &key, bool ref=TRUE ) const;
+    QCollection::Item find_other( const char *key, bool ref=TRUE ) const;
+
+    void    statistics() const;
+
+private:
+    bool    makeRoomFor( int cost, int priority = -1 );
+    KeyType keytype;
+    QCList *lruList;
+    QCDict *dict;
+    int	    mCost;
+    int	    tCost;
+    bool    copyk;
+};
+
+
+class Q_EXPORT QGCacheIterator			// generic cache iterator
+{
+protected:
+    QGCacheIterator( const QGCache & );
+    QGCacheIterator( const QGCacheIterator & );
+   ~QGCacheIterator();
+    QGCacheIterator &operator=( const QGCacheIterator & );
+
+    uint	      count()   const;
+    bool	      atFirst() const;
+    bool	      atLast()  const;
+    QCollection::Item toFirst();
+    QCollection::Item toLast();
+
+    QCollection::Item get() const;
+    QString	      getKeyString() const;
+    const char       *getKeyAscii()  const;
+    long	      getKeyInt()    const;
+
+    QCollection::Item operator()();
+    QCollection::Item operator++();
+    QCollection::Item operator+=( uint );
+    QCollection::Item operator--();
+    QCollection::Item operator-=( uint );
+
+protected:
+    QCListIt *it;				// iterator on cache list
+};
+
+
+#endif // QGCACHE_H
diff --git a/qtools/qtools.pro.in b/qtools/qtools.pro.in
index 1a02797..37fc143 100644
--- a/qtools/qtools.pro.in
+++ b/qtools/qtools.pro.in
@@ -2,6 +2,8 @@ TEMPLATE	= lib
 CONFIG		= warn_on staticlib $extraopts
 HEADERS		= qarray.h \
 		  qbuffer.h \
+                  qcache.h \
+                  qgcache.h \
 		  qcollection.h \
 		  qconfig.h \
 		  qcstring.h \
@@ -50,6 +52,7 @@ SOURCES		= qbuffer.cpp \
 		  qfile.cpp \
 		  qfileinfo.cpp \
 		  qgarray.cpp \
+		  qgcache.cpp \
 		  qgdict.cpp \
 		  qglist.cpp \
 		  qglobal.cpp \