Chameleon

Chameleon Svn Source Tree

Root/branches/xZenu/src/util/doxygen/qtools/qgcache.cpp

Source at commit 1322 created 9 years 5 months ago.
By meklort, Add doxygen to utils folder
1/****************************************************************************
2**
3**
4** Implementation of QGCache and QGCacheIterator classes
5**
6** Created : 950208
7**
8** Copyright (C) 1992-2000 Trolltech AS. All rights reserved.
9**
10** This file is part of the tools module of the Qt GUI Toolkit.
11**
12** This file may be distributed under the terms of the Q Public License
13** as defined by Trolltech AS of Norway and appearing in the file
14** LICENSE.QPL included in the packaging of this file.
15**
16** This file may be distributed and/or modified under the terms of the
17** GNU General Public License version 2 as published by the Free Software
18** Foundation and appearing in the file LICENSE.GPL included in the
19** packaging of this file.
20**
21** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition
22** licenses may use this file in accordance with the Qt Commercial License
23** Agreement provided with the Software.
24**
25** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
26** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
27**
28** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for
29** information about Qt Commercial License Agreements.
30** See http://www.trolltech.com/qpl/ for QPL licensing information.
31** See http://www.trolltech.com/gpl/ for GPL licensing information.
32**
33** Contact info@trolltech.com if any conditions of this licensing are
34** not clear to you.
35**
36**********************************************************************/
37
38#include "qgcache.h"
39#include "qlist.h"
40#include "qdict.h"
41#include "qstring.h"
42
43
44// NOT REVISED
45/*!
46 \class QGCache qgcache.h
47
48 \brief The QGCache class is an internal class for implementing QCache template classes.
49
50 QGCache is a strictly internal class that acts as a base class for the
51 \link collection.html collection classes\endlink QCache and QIntCache.
52*/
53
54
55/*****************************************************************************
56 QGCacheItem class (internal cache item)
57 *****************************************************************************/
58
59struct QCacheItem
60{
61 QCacheItem( void *k, QCollection::Item d, int c, short p )
62: priority(p), skipPriority(p), cost(c), key(k), data(d), node(0) {}
63 shortpriority;
64 shortskipPriority;
65 intcost;
66 void *key;
67 QCollection::Item data;
68 QLNode *node;
69};
70
71
72/*****************************************************************************
73 QCList class (internal list of cache items)
74 *****************************************************************************/
75
76class QCList : private QList<QCacheItem>
77{
78friend class QGCacheIterator;
79friend class QCListIt;
80public:
81 QCList(){}
82 ~QCList();
83
84 voidinsert( QCacheItem * );// insert according to priority
85 voidinsert( int, QCacheItem * );
86 voidtake( QCacheItem * );
87 voidreference( QCacheItem * );
88
89 voidsetAutoDelete( bool del ) { QCollection::setAutoDelete(del); }
90
91 boolremoveFirst(){ return QList<QCacheItem>::removeFirst(); }
92 boolremoveLast(){ return QList<QCacheItem>::removeLast(); }
93
94 QCacheItem *first(){ return QList<QCacheItem>::first(); }
95 QCacheItem *last(){ return QList<QCacheItem>::last(); }
96 QCacheItem *prev(){ return QList<QCacheItem>::prev(); }
97 QCacheItem *next(){ return QList<QCacheItem>::next(); }
98
99#if defined(DEBUG)
100 intinserts;// variables for statistics
101 intinsertCosts;
102 intinsertMisses;
103 intfinds;
104 inthits;
105 inthitCosts;
106 intdumps;
107 intdumpCosts;
108#endif
109};
110
111
112QCList::~QCList()
113{
114#if defined(DEBUG)
115 ASSERT( count() == 0 );
116#endif
117}
118
119
120void QCList::insert( QCacheItem *ci )
121{
122 QCacheItem *item = first();
123 while( item && item->skipPriority > ci->priority ) {
124item->skipPriority--;
125item = next();
126 }
127 if ( item )
128QList<QCacheItem>::insert( at(), ci );
129 else
130append( ci );
131#if defined(DEBUG)
132 ASSERT( ci->node == 0 );
133#endif
134 ci->node = currentNode();
135}
136
137inline void QCList::insert( int i, QCacheItem *ci )
138{
139 QList<QCacheItem>::insert( i, ci );
140#if defined(DEBUG)
141 ASSERT( ci->node == 0 );
142#endif
143 ci->node = currentNode();
144}
145
146
147void QCList::take( QCacheItem *ci )
148{
149 if ( ci ) {
150#if defined(DEBUG)
151ASSERT( ci->node != 0 );
152#endif
153takeNode( ci->node );
154ci->node = 0;
155 }
156}
157
158
159inline void QCList::reference( QCacheItem *ci )
160{
161#if defined(DEBUG)
162 ASSERT( ci != 0 && ci->node != 0 );
163#endif
164 ci->skipPriority = ci->priority;
165 relinkNode( ci->node );// relink as first item
166}
167
168
169class QCListIt: public QListIterator<QCacheItem>
170{
171public:
172 QCListIt( const QCList *p ): QListIterator<QCacheItem>( *p ) {}
173 QCListIt( const QCListIt *p ): QListIterator<QCacheItem>( *p ) {}
174};
175
176
177/*****************************************************************************
178 QCDict class (internal dictionary of cache items)
179 *****************************************************************************/
180
181//
182// Since we need to decide if the dictionary should use an int or const
183// char * key (the "bool trivial" argument in the constructor below)
184// we cannot use the macro/template dict, but inherit directly from QGDict.
185//
186
187class QCDict : public QGDict
188{
189public:
190 QCDict( uint size, uint kt, bool caseSensitive, bool copyKeys )
191: QGDict( size, (KeyType)kt, caseSensitive, copyKeys ) {}
192
193 QCacheItem *find_string(const QString &key) const
194{ return (QCacheItem*)((QCDict*)this)->look_string(key, 0, 0); }
195 QCacheItem *find_ascii(const char *key) const
196{ return (QCacheItem*)((QCDict*)this)->look_ascii(key, 0, 0); }
197 QCacheItem *find_int(long key) const
198{ return (QCacheItem*)((QCDict*)this)->look_int(key, 0, 0); }
199
200 QCacheItem *take_string(const QString &key)
201{ return (QCacheItem*)QGDict::take_string(key); }
202 QCacheItem *take_ascii(const char *key)
203{ return (QCacheItem*)QGDict::take_ascii(key); }
204 QCacheItem *take_int(long key)
205{ return (QCacheItem*)QGDict::take_int(key); }
206
207 bool insert_string( const QString &key, const QCacheItem *ci )
208{ return QGDict::look_string(key,(Item)ci,1)!=0;}
209 bool insert_ascii( const char *key, const QCacheItem *ci )
210{ return QGDict::look_ascii(key,(Item)ci,1)!=0;}
211 bool insert_int( long key, const QCacheItem *ci )
212{ return QGDict::look_int(key,(Item)ci,1)!=0;}
213
214 bool remove_string( QCacheItem *item )
215{ return QGDict::remove_string(*((QString*)(item->key)),item); }
216 bool remove_ascii( QCacheItem *item )
217{ return QGDict::remove_ascii((const char *)item->key,item); }
218 bool remove_int( QCacheItem *item )
219{ return QGDict::remove_int((long)item->key,item);}
220
221 void statistics(){ QGDict::statistics(); }
222};
223
224
225/*****************************************************************************
226 QGDict member functions
227 *****************************************************************************/
228
229/*!
230 \internal
231 Constructs a cache.
232*/
233
234QGCache::QGCache( int maxCost, uint size, KeyType kt, bool caseSensitive,
235 bool copyKeys )
236{
237 keytype = kt;
238 lruList = new QCList;
239 CHECK_PTR( lruList );
240 lruList->setAutoDelete( TRUE );
241 copyk = ((keytype == AsciiKey) && copyKeys);
242 dict = new QCDict( size, kt, caseSensitive, FALSE );
243 CHECK_PTR( dict );
244 mCost = maxCost;
245 tCost = 0;
246#if defined(DEBUG)
247 lruList->inserts = 0;
248 lruList->insertCosts = 0;
249 lruList->insertMisses = 0;
250 lruList->finds = 0;
251 lruList->hits = 0;
252 lruList->hitCosts = 0;
253 lruList->dumps = 0;
254 lruList->dumpCosts = 0;
255#endif
256}
257
258/*!
259 \internal
260 Cannot copy a cache.
261*/
262
263QGCache::QGCache( const QGCache & )
264 : QCollection()
265{
266#if defined(CHECK_NULL)
267 qFatal( "QGCache::QGCache(QGCache &): Cannot copy a cache" );
268#endif
269}
270
271/*!
272 \internal
273 Removes all items from the cache and destroys it.
274*/
275
276QGCache::~QGCache()
277{
278 clear();// delete everything first
279 delete dict;
280 delete lruList;
281}
282
283/*!
284 \internal
285 Cannot assign a cache.
286*/
287
288QGCache &QGCache::operator=( const QGCache & )
289{
290#if defined(CHECK_NULL)
291 qFatal( "QGCache::operator=: Cannot copy a cache" );
292#endif
293 return *this;// satisfy the compiler
294}
295
296
297/*!
298 \fn uint QGCache::count() const
299 \internal
300 Returns the number of items in the cache.
301*/
302
303/*!
304 \fn uint QGCache::size() const
305 \internal
306 Returns the size of the hash array.
307*/
308
309/*!
310 \fn int QGCache::maxCost() const
311 \internal
312 Returns the maximum cache cost.
313*/
314
315/*!
316 \fn int QGCache::totalCost() const
317 \internal
318 Returns the total cache cost.
319*/
320
321/*!
322 \internal
323 Sets the maximum cache cost.
324*/
325
326void QGCache::setMaxCost( int maxCost )
327{
328 if ( maxCost < tCost ) {
329if ( !makeRoomFor(tCost - maxCost) )// remove excess cost
330 return;
331 }
332 mCost = maxCost;
333}
334
335
336/*!
337 \internal
338 Inserts an item into the cache.
339
340 \warning If this function returns FALSE, you must delete \a data
341 yourself. Additionally, be very careful about using \a data after
342 calling this function, as any other insertions into the cache, from
343 anywhere in the application, or within Qt itself, could cause the
344 data to be discarded from the cache, and the pointer to become
345 invalid.
346*/
347
348bool QGCache::insert_string( const QString &key, QCollection::Item data,
349 int cost, int priority)
350{
351 if ( tCost + cost > mCost ) {
352if ( !makeRoomFor(tCost + cost - mCost, priority) ) {
353#if defined(DEBUG)
354 lruList->insertMisses++;
355#endif
356 return FALSE;
357}
358 }
359#if defined(DEBUG)
360 ASSERT( keytype == StringKey );
361 lruList->inserts++;
362 lruList->insertCosts += cost;
363#endif
364 if ( priority < -32768 )
365priority = -32768;
366 else if ( priority > 32767 )
367priority = 32677;
368 QCacheItem *ci = new QCacheItem( new QString(key), newItem(data),
369 cost, (short)priority );
370 CHECK_PTR( ci );
371 lruList->insert( 0, ci );
372 dict->insert_string( key, ci );
373 tCost += cost;
374 return TRUE;
375}
376
377
378/*! \internal */
379
380bool QGCache::insert_other( const char *key, QCollection::Item data,
381 int cost, int priority)
382{
383 if ( tCost + cost > mCost ) {
384if ( !makeRoomFor(tCost + cost - mCost, priority) ) {
385#if defined(DEBUG)
386 lruList->insertMisses++;
387#endif
388 return FALSE;
389}
390 }
391#if defined(DEBUG)
392 ASSERT( keytype != StringKey );
393 lruList->inserts++;
394 lruList->insertCosts += cost;
395#endif
396 if ( keytype == AsciiKey && copyk )
397key = qstrdup( key );
398 if ( priority < -32768 )
399priority = -32768;
400 else if ( priority > 32767 )
401priority = 32677;
402 QCacheItem *ci = new QCacheItem( (void*)key, newItem(data), cost,
403 (short)priority );
404 CHECK_PTR( ci );
405 lruList->insert( 0, ci );
406 if ( keytype == AsciiKey )
407dict->insert_ascii( key, ci );
408 else
409dict->insert_int( (long)key, ci );
410 tCost += cost;
411 return TRUE;
412}
413
414
415/*!
416 \internal
417 Removes an item from the cache.
418*/
419
420bool QGCache::remove_string( const QString &key )
421{
422 Item d = take_string( key );
423 if ( d )
424deleteItem( d );
425 return d != 0;
426}
427
428
429/*! \internal */
430
431bool QGCache::remove_other( const char *key )
432{
433 Item d = take_other( key );
434 if ( d )
435deleteItem( d );
436 return d != 0;
437}
438
439
440/*!
441 \internal
442 Takes an item out of the cache (no delete).
443*/
444
445QCollection::Item QGCache::take_string( const QString &key )
446{
447 QCacheItem *ci = dict->take_string( key );// take from dict
448 Item d;
449 if ( ci ) {
450d = ci->data;
451tCost -= ci->cost;
452lruList->take( ci );// take from list
453delete (QString*)ci->key;
454delete ci;
455 } else {
456d = 0;
457 }
458 return d;
459}
460
461/*!
462 \internal
463 Takes an item out of the cache (no delete).
464*/
465
466QCollection::Item QGCache::take_other( const char *key )
467{
468 QCacheItem *ci;
469 if ( keytype == AsciiKey )
470ci = dict->take_ascii( key );
471 else
472ci = dict->take_int( (long)key );
473 Item d;
474 if ( ci ) {
475d = ci->data;
476tCost -= ci->cost;
477lruList->take( ci );// take from list
478if ( copyk )
479 delete [] (char *)ci->key;
480delete ci;
481 } else {
482d = 0;
483 }
484 return d;
485}
486
487
488/*!
489 \internal
490 Clears the cache.
491*/
492
493void QGCache::clear()
494{
495 QCacheItem *ci;
496 while ( (ci = lruList->first()) ) {
497switch ( keytype ) {
498 case StringKey:
499dict->remove_string( ci );
500delete (QString*)ci->key;
501break;
502 case AsciiKey:
503dict->remove_ascii( ci );
504if ( copyk )
505 delete [] (char*)ci->key;
506break;
507 case IntKey:
508dict->remove_int( ci );
509break;
510 case PtrKey:// unused
511break;
512}
513deleteItem( ci->data );// delete data
514lruList->removeFirst();// remove from list
515 }
516 tCost = 0;
517}
518
519
520/*!
521 \internal
522 Finds an item in the cache.
523*/
524
525QCollection::Item QGCache::find_string( const QString &key, bool ref ) const
526{
527 QCacheItem *ci = dict->find_string( key );
528#if defined(DEBUG)
529 lruList->finds++;
530#endif
531 if ( ci ) {
532#if defined(DEBUG)
533lruList->hits++;
534lruList->hitCosts += ci->cost;
535#endif
536if ( ref )
537 lruList->reference( ci );
538return ci->data;
539 }
540 return 0;
541}
542
543
544/*!
545 \internal
546 Finds an item in the cache.
547*/
548
549QCollection::Item QGCache::find_other( const char *key, bool ref ) const
550{
551 QCacheItem *ci = keytype == AsciiKey ? dict->find_ascii(key)
552 : dict->find_int((long)key);
553#if defined(DEBUG)
554 lruList->finds++;
555#endif
556 if ( ci ) {
557#if defined(DEBUG)
558lruList->hits++;
559lruList->hitCosts += ci->cost;
560#endif
561if ( ref )
562 lruList->reference( ci );
563return ci->data;
564 }
565 return 0;
566}
567
568
569/*!
570 \internal
571 Allocates cache space for one or more items.
572*/
573
574bool QGCache::makeRoomFor( int cost, int priority )
575{
576 if ( cost > mCost )// cannot make room for more
577return FALSE;// than maximum cost
578 if ( priority == -1 )
579priority = 32767;
580 register QCacheItem *ci = lruList->last();
581 int cntCost = 0;
582 int dumps= 0;// number of items to dump
583 while ( cntCost < cost && ci && ci->skipPriority <= priority ) {
584cntCost += ci->cost;
585ci = lruList->prev();
586dumps++;
587 }
588 if ( cntCost < cost )// can enough cost be dumped?
589return FALSE;// no
590#if defined(DEBUG)
591 ASSERT( dumps > 0 );
592#endif
593 while ( dumps-- ) {
594ci = lruList->last();
595#if defined(DEBUG)
596lruList->dumps++;
597lruList->dumpCosts += ci->cost;
598#endif
599switch ( keytype ) {
600 case StringKey:
601dict->remove_string( ci );
602delete (QString*)ci->key;
603break;
604 case AsciiKey:
605dict->remove_ascii( ci );
606if ( copyk )
607 delete [] (char *)ci->key;
608break;
609 case IntKey:
610dict->remove_int( ci );
611break;
612 case PtrKey:// unused
613break;
614}
615deleteItem( ci->data );// delete data
616lruList->removeLast();// remove from list
617 }
618 tCost -= cntCost;
619 return TRUE;
620}
621
622
623/*!
624 \internal
625 Outputs debug statistics.
626*/
627
628void QGCache::statistics() const
629{
630#if defined(DEBUG)
631 QString line;
632 line.fill( '*', 80 );
633 qDebug( "%s",line.ascii() );
634 qDebug( "CACHE STATISTICS:" );
635 qDebug( "cache contains %d item%s, with a total cost of %d",
636 count(), count() != 1 ? "s" : "", tCost );
637 qDebug( "maximum cost is %d, cache is %d%% full.",
638 mCost, (200*tCost + mCost) / (mCost*2) );
639 qDebug( "find() has been called %d time%s",
640 lruList->finds, lruList->finds != 1 ? "s" : "" );
641 qDebug( "%d of these were hits, items found had a total cost of %d.",
642 lruList->hits,lruList->hitCosts );
643 qDebug( "%d item%s %s been inserted with a total cost of %d.",
644 lruList->inserts,lruList->inserts != 1 ? "s" : "",
645 lruList->inserts != 1 ? "have" : "has", lruList->insertCosts );
646 qDebug( "%d item%s %s too large or had too low priority to be inserted.",
647 lruList->insertMisses, lruList->insertMisses != 1 ? "s" : "",
648 lruList->insertMisses != 1 ? "were" : "was" );
649 qDebug( "%d item%s %s been thrown away with a total cost of %d.",
650 lruList->dumps, lruList->dumps != 1 ? "s" : "",
651 lruList->dumps != 1 ? "have" : "has", lruList->dumpCosts );
652 qDebug( "Statistics from internal dictionary class:" );
653 dict->statistics();
654 qDebug( "%s",line.ascii() );
655#endif
656}
657
658
659/*****************************************************************************
660 QGCacheIterator member functions
661 *****************************************************************************/
662
663/*!
664 \class QGCacheIterator qgcache.h
665
666 \brief An internal class for implementing QCacheIterator and QIntCacheIterator.
667
668 QGCacheIterator is a strictly internal class that does the heavy work for
669 QCacheIterator and QIntCacheIterator.
670*/
671
672/*!
673 \internal
674 Constructs an iterator that operates on the cache \e c.
675*/
676
677QGCacheIterator::QGCacheIterator( const QGCache &c )
678{
679 it = new QCListIt( c.lruList );
680#if defined(DEBUG)
681 ASSERT( it != 0 );
682#endif
683}
684
685/*!
686 \internal
687 Constructs an iterator that operates on the same cache as \e ci.
688*/
689
690QGCacheIterator::QGCacheIterator( const QGCacheIterator &ci )
691{
692 it = new QCListIt( ci.it );
693#if defined(DEBUG)
694 ASSERT( it != 0 );
695#endif
696}
697
698/*!
699 \internal
700 Destroys the iterator.
701*/
702
703QGCacheIterator::~QGCacheIterator()
704{
705 delete it;
706}
707
708/*!
709 \internal
710 Assigns the iterator \e ci to this cache iterator.
711*/
712
713QGCacheIterator &QGCacheIterator::operator=( const QGCacheIterator &ci )
714{
715 *it = *ci.it;
716 return *this;
717}
718
719/*!
720 \internal
721 Returns the number of items in the cache.
722*/
723
724uint QGCacheIterator::count() const
725{
726 return it->count();
727}
728
729/*!
730 \internal
731 Returns TRUE if the iterator points to the first item.
732*/
733
734bool QGCacheIterator::atFirst() const
735{
736 return it->atFirst();
737}
738
739/*!
740 \internal
741 Returns TRUE if the iterator points to the last item.
742*/
743
744bool QGCacheIterator::atLast() const
745{
746 return it->atLast();
747}
748
749/*!
750 \internal
751 Sets the list iterator to point to the first item in the cache.
752*/
753
754QCollection::Item QGCacheIterator::toFirst()
755{
756 QCacheItem *item = it->toFirst();
757 return item ? item->data : 0;
758}
759
760/*!
761 \internal
762 Sets the list iterator to point to the last item in the cache.
763*/
764
765QCollection::Item QGCacheIterator::toLast()
766{
767 QCacheItem *item = it->toLast();
768 return item ? item->data : 0;
769}
770
771/*!
772 \internal
773 Returns the current item.
774*/
775
776QCollection::Item QGCacheIterator::get() const
777{
778 QCacheItem *item = it->current();
779 return item ? item->data : 0;
780}
781
782/*!
783 \internal
784 Returns the key of the current item.
785*/
786
787QString QGCacheIterator::getKeyString() const
788{
789 QCacheItem *item = it->current();
790 return item ? *((QString*)item->key) : QString::null;
791}
792
793/*!
794 \internal
795 Returns the key of the current item, as a \0-terminated C string.
796*/
797
798const char *QGCacheIterator::getKeyAscii() const
799{
800 QCacheItem *item = it->current();
801 return item ? (const char *)item->key : 0;
802}
803
804/*!
805 \internal
806 Returns the key of the current item, as a long.
807*/
808
809long QGCacheIterator::getKeyInt() const
810{
811 QCacheItem *item = it->current();
812 return item ? (long)item->key : 0;
813}
814
815/*!
816 \internal
817 Moves to the next item (postfix).
818*/
819
820QCollection::Item QGCacheIterator::operator()()
821{
822 QCacheItem *item = it->operator()();
823 return item ? item->data : 0;
824}
825
826/*!
827 \internal
828 Moves to the next item (prefix).
829*/
830
831QCollection::Item QGCacheIterator::operator++()
832{
833 QCacheItem *item = it->operator++();
834 return item ? item->data : 0;
835}
836
837/*!
838 \internal
839 Moves \e jumps positions forward.
840*/
841
842QCollection::Item QGCacheIterator::operator+=( uint jump )
843{
844 QCacheItem *item = it->operator+=(jump);
845 return item ? item->data : 0;
846}
847
848/*!
849 \internal
850 Moves to the previous item (prefix).
851*/
852
853QCollection::Item QGCacheIterator::operator--()
854{
855 QCacheItem *item = it->operator--();
856 return item ? item->data : 0;
857}
858
859/*!
860 \internal
861 Moves \e jumps positions backward.
862*/
863
864QCollection::Item QGCacheIterator::operator-=( uint jump )
865{
866 QCacheItem *item = it->operator-=(jump);
867 return item ? item->data : 0;
868}
869

Archive Download this file

Revision: 1322