Chameleon

Chameleon Svn Source Tree

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

Source at commit 1322 created 9 years 5 months ago.
By meklort, Add doxygen to utils folder
1/****************************************************************************
2**
3**
4** Implementation of QGDict and QGDictIterator classes
5**
6** Created : 920529
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 "qgdict.h"
39#include "qlist.h"
40#include "qstring.h"
41#include "qdatastream.h"
42#include <ctype.h>
43
44// NOT REVISED
45/*!
46 \class QGDict qgdict.h
47 \brief The QGDict class is an internal class for implementing QDict template classes.
48
49 QGDict is a strictly internal class that acts as a base class for the
50 \link collection.html collection classes\endlink QDict and QIntDict.
51
52 QGDict has some virtual functions that can be reimplemented to customize
53 the subclasses.
54 <ul>
55 <li> read() reads a collection/dictionary item from a QDataStream.
56 <li> write() writes a collection/dictionary item to a QDataStream.
57 </ul>
58 Normally, you do not have to reimplement any of these functions.
59*/
60
61static const int op_find = 0;
62static const int op_insert = 1;
63static const int op_replace = 2;
64
65
66class QGDItList : public QList<QGDictIterator>
67{
68public:
69 QGDItList() : QList<QGDictIterator>() {}
70 QGDItList( const QGDItList &list ) : QList<QGDictIterator>(list) {}
71 ~QGDItList() { clear(); }
72 QGDItList &operator=(const QGDItList &list)
73{ return (QGDItList&)QList<QGDictIterator>::operator=(list); }
74};
75
76
77/*****************************************************************************
78 Default implementation of special and virtual functions
79 *****************************************************************************/
80
81/*!
82 \internal
83 Returns the hash key for \e key, when key is a string.
84*/
85
86int QGDict::hashKeyString( const QString &key )
87{
88#if defined(CHECK_NULL)
89 if ( key.isNull() )
90qWarning( "QGDict::hashStringKey: Invalid null key" );
91#endif
92 int i;
93 register uint h=0;
94 uint g;
95 int len = key.length();
96 const QChar *p = key.unicode();
97 if ( cases ) {// case sensitive
98for ( i=0; i<len; i++ ) {
99 h = (h<<4) + p[i].cell();
100 if ( (g = h & 0xf0000000) )
101h ^= g >> 24;
102 h &= ~g;
103}
104 } else {// case insensitive
105for ( i=0; i<len; i++ ) {
106 h = (h<<4) + p[i].lower().cell();
107 if ( (g = h & 0xf0000000) )
108h ^= g >> 24;
109 h &= ~g;
110}
111 }
112 int index = h;
113 if ( index < 0 )// adjust index to table size
114index = -index;
115 return index;
116}
117
118/*!
119 \internal
120 Returns the hash key for \a key, which is a C string.
121*/
122
123int QGDict::hashKeyAscii( const char *key )
124{
125#if defined(CHECK_NULL)
126 if ( key == 0 )
127 {
128qWarning( "QGDict::hashAsciiKey: Invalid null key" );
129 return 0;
130 }
131#endif
132 register const char *k = key;
133 register uint h=0;
134 uint g;
135 if ( cases ) {// case sensitive
136while ( *k ) {
137 h = (h<<4) + *k++;
138 if ( (g = h & 0xf0000000) )
139h ^= g >> 24;
140 h &= ~g;
141}
142 } else {// case insensitive
143while ( *k ) {
144 h = (h<<4) + tolower(*k);
145 if ( (g = h & 0xf0000000) )
146h ^= g >> 24;
147 h &= ~g;
148 k++;
149}
150 }
151 int index = h;
152 if ( index < 0 )// adjust index to table size
153index = -index;
154 return index;
155}
156
157#ifndef QT_NO_DATASTREAM
158
159/*!
160 Reads a collection/dictionary item from the stream \e s and returns a
161 reference to the stream.
162
163 The default implementation sets \e item to 0.
164
165 \sa write()
166*/
167
168QDataStream& QGDict::read( QDataStream &s, QCollection::Item &item )
169{
170 item = 0;
171 return s;
172}
173
174/*!
175 Writes a collection/dictionary item to the stream \e s and returns a
176 reference to the stream.
177
178 \sa read()
179*/
180
181QDataStream& QGDict::write( QDataStream &s, QCollection::Item ) const
182{
183 return s;
184}
185#endif //QT_NO_DATASTREAM
186
187/*****************************************************************************
188 QGDict member functions
189 *****************************************************************************/
190
191/*!
192 \internal
193 Constructs a dictionary.
194*/
195
196QGDict::QGDict( uint len, KeyType kt, bool caseSensitive, bool copyKeys )
197{
198 init( len, kt, caseSensitive, copyKeys );
199}
200
201
202void QGDict::init( uint len, KeyType kt, bool caseSensitive, bool copyKeys )
203{
204 vec = new QBaseBucket *[vlen = len];// allocate hash table
205 CHECK_PTR( vec );
206 memset( (char*)vec, 0, vlen*sizeof(QBaseBucket*) );
207 numItems = 0;
208 iterators = 0;
209 // The caseSensitive and copyKey options don't make sense for
210 // all dict types.
211 switch ( (keytype = (uint)kt) ) {
212case StringKey:
213 cases = caseSensitive;
214 copyk = FALSE;
215 break;
216case AsciiKey:
217 cases = caseSensitive;
218 copyk = copyKeys;
219 break;
220default:
221 cases = FALSE;
222 copyk = FALSE;
223 break;
224 }
225}
226
227
228/*!
229 \internal
230 Constructs a copy of \e dict.
231*/
232
233QGDict::QGDict( const QGDict & dict )
234 : QCollection( dict )
235{
236 init( dict.vlen, (KeyType)dict.keytype, dict.cases, dict.copyk );
237 QGDictIterator it( dict );
238 while ( it.get() ) {// copy from other dict
239switch ( keytype ) {
240 case StringKey:
241look_string( it.getKeyString(), it.get(), op_insert );
242break;
243 case AsciiKey:
244look_ascii( it.getKeyAscii(), it.get(), op_insert );
245break;
246 case IntKey:
247look_int( it.getKeyInt(), it.get(), op_insert );
248break;
249 case PtrKey:
250look_ptr( it.getKeyPtr(), it.get(), op_insert );
251break;
252}
253++it;
254 }
255}
256
257
258/*!
259 \internal
260 Removes all items from the dictionary and destroys it.
261*/
262
263QGDict::~QGDict()
264{
265 clear();// delete everything
266 delete [] vec;
267 if ( !iterators )// no iterators for this dict
268return;
269 QGDictIterator *i = iterators->first();
270 while ( i ) {// notify all iterators that
271i->dict = 0;// this dict is deleted
272i = iterators->next();
273 }
274 delete iterators;
275}
276
277
278/*!
279 \internal
280 Assigns \e dict to this dictionary.
281*/
282
283QGDict &QGDict::operator=( const QGDict &dict )
284{
285 clear();
286 QGDictIterator it( dict );
287 while ( it.get() ) {// copy from other dict
288switch ( keytype ) {
289 case StringKey:
290look_string( it.getKeyString(), it.get(), op_insert );
291break;
292 case AsciiKey:
293look_ascii( it.getKeyAscii(), it.get(), op_insert );
294break;
295 case IntKey:
296look_int( it.getKeyInt(), it.get(), op_insert );
297break;
298 case PtrKey:
299look_ptr( it.getKeyPtr(), it.get(), op_insert );
300break;
301}
302++it;
303 }
304 return *this;
305}
306
307
308/*! \fn QCollection::Item QGDictIterator::get() const
309
310 \internal
311*/
312
313
314/*! \fn QString QGDictIterator::getKeyString() const
315
316 \internal
317*/
318
319
320/*! \fn const char * QGDictIterator::getKeyAscii() const
321
322 \internal
323*/
324
325
326/*! \fn void * QGDictIterator::getKeyPtr() const
327
328 \internal
329*/
330
331
332/*! \fn long QGDictIterator::getKeyInt() const
333
334 \internal
335*/
336
337
338/*!
339 \fn uint QGDict::count() const
340 \internal
341 Returns the number of items in the dictionary.
342*/
343
344/*!
345 \fn uint QGDict::size() const
346 \internal
347 Returns the size of the hash array.
348*/
349
350
351/*!
352 \internal
353 The do-it-all function; op is one of op_find, op_insert, op_replace
354*/
355
356QCollection::Item QGDict::look_string( const QString &key, QCollection::Item d, int op )
357{
358 QStringBucket *n;
359 intindex = hashKeyString(key) % vlen;
360 if ( op == op_find ) {// find
361if ( cases ) {
362 for ( n=(QStringBucket*)vec[index]; n;
363 n=(QStringBucket*)n->getNext() ) {
364if ( key == n->getKey() )
365 return n->getData();// item found
366 }
367} else {
368 QString k = key.lower();
369 for ( n=(QStringBucket*)vec[index]; n;
370 n=(QStringBucket*)n->getNext() ) {
371if ( k == n->getKey().lower() )
372 return n->getData();// item found
373 }
374}
375return 0;// not found
376 }
377 if ( op == op_replace ) {// replace
378if ( vec[index] != 0 )// maybe something there
379 remove_string( key );
380 }
381 // op_insert or op_replace
382 n = new QStringBucket(key,newItem(d),vec[index]);
383 CHECK_PTR( n );
384#if defined(CHECK_NULL)
385 if ( n->getData() == 0 )
386qWarning( "QDict: Cannot insert null item" );
387#endif
388 vec[index] = n;
389 numItems++;
390 return n->getData();
391}
392
393
394/*! \internal */
395
396QCollection::Item QGDict::look_ascii( const char *key, QCollection::Item d, int op )
397{
398 QAsciiBucket *n;
399 intindex = hashKeyAscii(key) % vlen;
400 if ( op == op_find ) {// find
401if ( cases ) {
402 for ( n=(QAsciiBucket*)vec[index]; n;
403 n=(QAsciiBucket*)n->getNext() ) {
404if ( qstrcmp(n->getKey(),key) == 0 )
405 return n->getData();// item found
406 }
407} else {
408 for ( n=(QAsciiBucket*)vec[index]; n;
409 n=(QAsciiBucket*)n->getNext() ) {
410if ( qstricmp(n->getKey(),key) == 0 )
411 return n->getData();// item found
412 }
413}
414return 0;// not found
415 }
416 if ( op == op_replace ) {// replace
417if ( vec[index] != 0 )// maybe something there
418 remove_ascii( key );
419 }
420 // op_insert or op_replace
421 n = new QAsciiBucket(copyk ? qstrdup(key) : key,newItem(d),vec[index]);
422 CHECK_PTR( n );
423#if defined(CHECK_NULL)
424 if ( n->getData() == 0 )
425qWarning( "QAsciiDict: Cannot insert null item" );
426#endif
427 vec[index] = n;
428 numItems++;
429 return n->getData();
430}
431
432
433/*! \internal */
434
435QCollection::Item QGDict::look_int( long key, QCollection::Item d, int op )
436{
437 QIntBucket *n;
438 int index = (int)((ulong)key % vlen);// simple hash
439 if ( op == op_find ) {// find
440for ( n=(QIntBucket*)vec[index]; n;
441 n=(QIntBucket*)n->getNext() ) {
442 if ( n->getKey() == key )
443return n->getData();// item found
444}
445return 0;// not found
446 }
447 if ( op == op_replace ) {// replace
448if ( vec[index] != 0 )// maybe something there
449 remove_int( key );
450 }
451 // op_insert or op_replace
452 n = new QIntBucket(key,newItem(d),vec[index]);
453 CHECK_PTR( n );
454#if defined(CHECK_NULL)
455 if ( n->getData() == 0 )
456qWarning( "QIntDict: Cannot insert null item" );
457#endif
458 vec[index] = n;
459 numItems++;
460 return n->getData();
461}
462
463
464/*! \internal */
465
466QCollection::Item QGDict::look_ptr( void *key, QCollection::Item d, int op )
467{
468 QPtrBucket *n;
469 int index = (int)((ulong)key % vlen);// simple hash
470 if ( op == op_find ) {// find
471for ( n=(QPtrBucket*)vec[index]; n;
472 n=(QPtrBucket*)n->getNext() ) {
473 if ( n->getKey() == key )
474return n->getData();// item found
475}
476return 0;// not found
477 }
478 if ( op == op_replace ) {// replace
479if ( vec[index] != 0 )// maybe something there
480 remove_ptr( key );
481 }
482 // op_insert or op_replace
483 n = new QPtrBucket(key,newItem(d),vec[index]);
484 CHECK_PTR( n );
485#if defined(CHECK_NULL)
486 if ( n->getData() == 0 )
487qWarning( "QPtrDict: Cannot insert null item" );
488#endif
489 vec[index] = n;
490 numItems++;
491 return n->getData();
492}
493
494
495/*!
496 \internal
497 Changes the size of the hashtable.
498 The contents of the dictionary are preserved,
499 but all iterators on the dictionary become invalid.
500*/
501void QGDict::resize( uint newsize )
502{
503 // Save old information
504 QBaseBucket **old_vec = vec;
505 uint old_vlen = vlen;
506 bool old_copyk = copyk;
507
508 vec = new QBaseBucket *[vlen = newsize];
509 CHECK_PTR( vec );
510 memset( (char*)vec, 0, vlen*sizeof(QBaseBucket*) );
511 numItems = 0;
512 copyk = FALSE;
513
514 // Reinsert every item from vec, deleting vec as we go
515 for ( uint index = 0; index < old_vlen; index++ ) {
516switch ( keytype ) {
517 case StringKey:
518{
519 QStringBucket *n=(QStringBucket *)old_vec[index];
520 while ( n ) {
521look_string( n->getKey(), n->getData(), op_insert );
522QStringBucket *t=(QStringBucket *)n->getNext();
523delete n;
524n = t;
525 }
526}
527break;
528 case AsciiKey:
529{
530 QAsciiBucket *n=(QAsciiBucket *)old_vec[index];
531 while ( n ) {
532look_ascii( n->getKey(), n->getData(), op_insert );
533QAsciiBucket *t=(QAsciiBucket *)n->getNext();
534delete n;
535n = t;
536 }
537}
538break;
539 case IntKey:
540{
541 QIntBucket *n=(QIntBucket *)old_vec[index];
542 while ( n ) {
543look_int( n->getKey(), n->getData(), op_insert );
544QIntBucket *t=(QIntBucket *)n->getNext();
545delete n;
546n = t;
547 }
548}
549break;
550 case PtrKey:
551{
552 QPtrBucket *n=(QPtrBucket *)old_vec[index];
553 while ( n ) {
554look_ptr( n->getKey(), n->getData(), op_insert );
555QPtrBucket *t=(QPtrBucket *)n->getNext();
556delete n;
557n = t;
558 }
559}
560break;
561}
562 }
563 delete [] old_vec;
564
565 // Restore state
566 copyk = old_copyk;
567
568 // Invalidate all iterators, since order is lost
569 if ( iterators && iterators->count() ) {
570QGDictIterator *i = iterators->first();
571while ( i ) {
572 i->toFirst();
573 i = iterators->next();
574}
575 }
576}
577
578/*!
579 \internal
580 Unlinks the bucket with the specified key (and specified data pointer,
581 if it is set).
582*/
583
584void QGDict::unlink_common( int index, QBaseBucket *node, QBaseBucket *prev )
585{
586 if ( iterators && iterators->count() ) {// update iterators
587QGDictIterator *i = iterators->first();
588while ( i ) {// invalidate all iterators
589 if ( i->curNode == node )// referring to pending node
590i->operator++();
591 i = iterators->next();
592}
593 }
594 if ( prev )// unlink node
595prev->setNext( node->getNext() );
596 else
597vec[index] = node->getNext();
598 numItems--;
599}
600
601QStringBucket *QGDict::unlink_string( const QString &key, QCollection::Item d )
602{
603 if ( numItems == 0 )// nothing in dictionary
604return 0;
605 QStringBucket *n;
606 QStringBucket *prev = 0;
607 int index = hashKeyString(key) % vlen;
608 if ( cases ) {
609for ( n=(QStringBucket*)vec[index]; n;
610 n=(QStringBucket*)n->getNext() ) {
611 bool found = (key == n->getKey());
612 if ( found && d )
613found = (n->getData() == d);
614 if ( found ) {
615unlink_common(index,n,prev);
616return n;
617 }
618 prev = n;
619}
620 } else {
621QString k = key.lower();
622for ( n=(QStringBucket*)vec[index]; n;
623 n=(QStringBucket*)n->getNext() ) {
624 bool found = (k == n->getKey().lower());
625 if ( found && d )
626found = (n->getData() == d);
627 if ( found ) {
628unlink_common(index,n,prev);
629return n;
630 }
631 prev = n;
632}
633 }
634 return 0;
635}
636
637QAsciiBucket *QGDict::unlink_ascii( const char *key, QCollection::Item d )
638{
639 if ( numItems == 0 )// nothing in dictionary
640return 0;
641 QAsciiBucket *n;
642 QAsciiBucket *prev = 0;
643 int index = hashKeyAscii(key) % vlen;
644 for ( n=(QAsciiBucket *)vec[index]; n; n=(QAsciiBucket *)n->getNext() ) {
645bool found = (cases ? qstrcmp(n->getKey(),key)
646 : qstricmp(n->getKey(),key)) == 0;
647if ( found && d )
648 found = (n->getData() == d);
649if ( found ) {
650 unlink_common(index,n,prev);
651 return n;
652}
653prev = n;
654 }
655 return 0;
656}
657
658QIntBucket *QGDict::unlink_int( long key, QCollection::Item d )
659{
660 if ( numItems == 0 )// nothing in dictionary
661return 0;
662 QIntBucket *n;
663 QIntBucket *prev = 0;
664 int index = (int)((ulong)key % vlen);
665 for ( n=(QIntBucket *)vec[index]; n; n=(QIntBucket *)n->getNext() ) {
666bool found = (n->getKey() == key);
667if ( found && d )
668 found = (n->getData() == d);
669if ( found ) {
670 unlink_common(index,n,prev);
671 return n;
672}
673prev = n;
674 }
675 return 0;
676}
677
678QPtrBucket *QGDict::unlink_ptr( void *key, QCollection::Item d )
679{
680 if ( numItems == 0 )// nothing in dictionary
681return 0;
682 QPtrBucket *n;
683 QPtrBucket *prev = 0;
684 int index = (int)((ulong)key % vlen);
685 for ( n=(QPtrBucket *)vec[index]; n; n=(QPtrBucket *)n->getNext() ) {
686bool found = (n->getKey() == key);
687if ( found && d )
688 found = (n->getData() == d);
689if ( found ) {
690 unlink_common(index,n,prev);
691 return n;
692}
693prev = n;
694 }
695 return 0;
696}
697
698
699/*!
700 \internal
701 Removes the item with the specified key. If item is non-null,
702 the remove will match the \a item as well (used to remove an
703 item when several items have the same key).
704*/
705
706bool QGDict::remove_string( const QString &key, QCollection::Item item )
707{
708 QStringBucket *n = unlink_string( key, item );
709 if ( n ) {
710deleteItem( n->getData() );
711delete n;
712return TRUE;
713 } else {
714return FALSE;
715 }
716}
717
718
719/*! \internal */
720
721bool QGDict::remove_ascii( const char *key, QCollection::Item item )
722{
723 QAsciiBucket *n = unlink_ascii( key, item );
724 if ( n ) {
725if ( copyk )
726 delete [] (char *)n->getKey();
727deleteItem( n->getData() );
728delete n;
729 }
730 return n != 0;
731}
732
733
734/*! \internal */
735
736bool QGDict::remove_int( long key, QCollection::Item item )
737{
738 QIntBucket *n = unlink_int( key, item );
739 if ( n ) {
740deleteItem( n->getData() );
741delete n;
742 }
743 return n != 0;
744}
745
746
747/*! \internal */
748
749bool QGDict::remove_ptr( void *key, QCollection::Item item )
750{
751 QPtrBucket *n = unlink_ptr( key, item );
752 if ( n ) {
753deleteItem( n->getData() );
754delete n;
755 }
756 return n != 0;
757}
758
759
760/*! \internal */
761
762QCollection::Item QGDict::take_string( const QString &key )
763{
764 QStringBucket *n = unlink_string( key );
765 Item d;
766 if ( n ) {
767d = n->getData();
768delete n;
769 } else {
770d = 0;
771 }
772 return d;
773}
774
775
776/*! \internal */
777
778QCollection::Item QGDict::take_ascii( const char *key )
779{
780 QAsciiBucket *n = unlink_ascii( key );
781 Item d;
782 if ( n ) {
783if ( copyk )
784 delete [] (char *)n->getKey();
785d = n->getData();
786delete n;
787 } else {
788d = 0;
789 }
790 return d;
791}
792
793
794/*! \internal */
795
796QCollection::Item QGDict::take_int( long key )
797{
798 QIntBucket *n = unlink_int( key );
799 Item d;
800 if ( n ) {
801d = n->getData();
802delete n;
803 } else {
804d = 0;
805 }
806 return d;
807}
808
809
810/*! \internal */
811
812QCollection::Item QGDict::take_ptr( void *key )
813{
814 QPtrBucket *n = unlink_ptr( key );
815 Item d;
816 if ( n ) {
817d = n->getData();
818delete n;
819 } else {
820d = 0;
821 }
822 return d;
823}
824
825
826/*!
827 \internal
828 Removes all items from the dictionary.
829*/
830
831void QGDict::clear()
832{
833 if ( !numItems )
834return;
835 numItems = 0;// disable remove() function
836 for ( uint j=0; j<vlen; j++ ) {// destroy hash table
837if ( vec[j] ) {
838 switch ( keytype ) {
839case StringKey:
840 {
841QStringBucket *n=(QStringBucket *)vec[j];
842while ( n ) {
843 QStringBucket *next = (QStringBucket*)n->getNext();
844 deleteItem( n->getData() );
845 delete n;
846 n = next;
847}
848 }
849 break;
850case AsciiKey:
851 {
852QAsciiBucket *n=(QAsciiBucket *)vec[j];
853while ( n ) {
854 QAsciiBucket *next = (QAsciiBucket*)n->getNext();
855 if ( copyk )
856delete [] (char *)n->getKey();
857 deleteItem( n->getData() );
858 delete n;
859 n = next;
860}
861 }
862 break;
863case IntKey:
864 {
865QIntBucket *n=(QIntBucket *)vec[j];
866while ( n ) {
867 QIntBucket *next = (QIntBucket*)n->getNext();
868 deleteItem( n->getData() );
869 delete n;
870 n = next;
871}
872 }
873 break;
874case PtrKey:
875 {
876QPtrBucket *n=(QPtrBucket *)vec[j];
877while ( n ) {
878 QPtrBucket *next = (QPtrBucket*)n->getNext();
879 deleteItem( n->getData() );
880 delete n;
881 n = next;
882}
883 }
884 break;
885 }
886 vec[j] = 0;// detach list of buckets
887}
888 }
889 if ( iterators && iterators->count() ) {// invalidate all iterators
890QGDictIterator *i = iterators->first();
891while ( i ) {
892 i->curNode = 0;
893 i = iterators->next();
894}
895 }
896}
897
898
899/*!
900 \internal
901 Outputs debug statistics.
902*/
903
904void QGDict::statistics() const
905{
906#if defined(DEBUG)
907 QString line;
908 line.fill( '-', 60 );
909 double real, ideal;
910 qDebug( "%s",line.ascii() );
911 qDebug( "DICTIONARY STATISTICS:" );
912 if ( count() == 0 ) {
913qDebug( "Empty!" );
914qDebug( "%s", line.ascii() );
915return;
916 }
917 real = 0.0;
918 ideal = (float)count()/(2.0*size())*(count()+2.0*size()-1);
919 uint i = 0;
920 while ( i<size() ) {
921QBaseBucket *n = vec[i];
922int b = 0;
923while ( n ) {// count number of buckets
924 b++;
925 n = n->getNext();
926}
927real = real + (double)b * ((double)b+1.0)/2.0;
928char buf[80], *pbuf;
929if ( b > 78 )
930 b = 78;
931pbuf = buf;
932while ( b-- )
933 *pbuf++ = '*';
934*pbuf = '\0';
935qDebug( "%s", buf );
936i++;
937 }
938 qDebug( "Array size = %d", size() );
939 qDebug( "# items = %d", count() );
940 qDebug( "Real dist = %g", real );
941 qDebug( "Rand dist = %g", ideal );
942 qDebug( "Real/Rand = %g", real/ideal );
943 qDebug( "%s",line.ascii() );
944#endif // DEBUG
945}
946
947
948/*****************************************************************************
949 QGDict stream functions
950 *****************************************************************************/
951#ifndef QT_NO_DATASTREAM
952QDataStream &operator>>( QDataStream &s, QGDict &dict )
953{
954 return dict.read( s );
955}
956
957QDataStream &operator<<( QDataStream &s, const QGDict &dict )
958{
959 return dict.write( s );
960}
961
962#if defined(_CC_DEC_) && defined(__alpha) && (__DECCXX_VER >= 50190001)
963#pragma message disable narrowptr
964#endif
965
966/*!
967 \internal
968 Reads a dictionary from the stream \e s.
969*/
970
971QDataStream &QGDict::read( QDataStream &s )
972{
973 uint num;
974 s >> num;// read number of items
975 clear();// clear dict
976 while ( num-- ) {// read all items
977Item d;
978switch ( keytype ) {
979 case StringKey:
980{
981 QString k;
982 s >> k;
983 read( s, d );
984 look_string( k, d, op_insert );
985}
986break;
987 case AsciiKey:
988{
989 char *k;
990 s >> k;
991 read( s, d );
992 look_ascii( k, d, op_insert );
993 if ( copyk )
994delete [] k;
995}
996break;
997 case IntKey:
998{
999 Q_UINT32 k;
1000 s >> k;
1001 read( s, d );
1002 look_int( k, d, op_insert );
1003}
1004break;
1005 case PtrKey:
1006{
1007 Q_UINT32 k;
1008 s >> k;
1009 read( s, d );
1010 // ### cannot insert 0 - this renders the thing
1011 // useless since all pointers are written as 0,
1012 // but hey, serializing pointers? can it be done
1013 // at all, ever?
1014 if ( k )
1015look_ptr( (void *)k, d, op_insert );
1016}
1017break;
1018}
1019 }
1020 return s;
1021}
1022
1023/*!
1024 \internal
1025 Writes the dictionary to the stream \e s.
1026*/
1027
1028QDataStream& QGDict::write( QDataStream &s ) const
1029{
1030 s << count();// write number of items
1031 uint i = 0;
1032 while ( i<size() ) {
1033QBaseBucket *n = vec[i];
1034while ( n ) {// write all buckets
1035 switch ( keytype ) {
1036case StringKey:
1037 s << ((QStringBucket*)n)->getKey();
1038 break;
1039case AsciiKey:
1040 s << ((QAsciiBucket*)n)->getKey();
1041 break;
1042case IntKey:
1043 s << (Q_UINT32)((QIntBucket*)n)->getKey();
1044 break;
1045case PtrKey:
1046 s << (Q_UINT32)0; // ### cannot serialize a pointer
1047 break;
1048 }
1049 write( s, n->getData() );// write data
1050 n = n->getNext();
1051}
1052i++;
1053 }
1054 return s;
1055}
1056#endif //QT_NO_DATASTREAM
1057
1058/*****************************************************************************
1059 QGDictIterator member functions
1060 *****************************************************************************/
1061
1062/*!
1063 \class QGDictIterator qgdict.h
1064 \brief An internal class for implementing QDictIterator and QIntDictIterator.
1065
1066 QGDictIterator is a strictly internal class that does the heavy work for
1067 QDictIterator and QIntDictIterator.
1068*/
1069
1070/*!
1071 \internal
1072 Constructs an iterator that operates on the dictionary \e d.
1073*/
1074
1075QGDictIterator::QGDictIterator( const QGDict &d )
1076{
1077 dict = (QGDict *)&d;// get reference to dict
1078 toFirst();// set to first noe
1079 if ( !dict->iterators ) {
1080dict->iterators = new QGDItList;// create iterator list
1081CHECK_PTR( dict->iterators );
1082 }
1083 dict->iterators->append( this );// attach iterator to dict
1084}
1085
1086/*!
1087 \internal
1088 Constructs a copy of the iterator \e it.
1089*/
1090
1091QGDictIterator::QGDictIterator( const QGDictIterator &it )
1092{
1093 dict = it.dict;
1094 curNode = it.curNode;
1095 curIndex = it.curIndex;
1096 if ( dict )
1097dict->iterators->append( this );// attach iterator to dict
1098}
1099
1100/*!
1101 \internal
1102 Assigns a copy of the iterator \e it and returns a reference to this
1103 iterator.
1104*/
1105
1106QGDictIterator &QGDictIterator::operator=( const QGDictIterator &it )
1107{
1108 if ( dict )// detach from old dict
1109dict->iterators->removeRef( this );
1110 dict = it.dict;
1111 curNode = it.curNode;
1112 curIndex = it.curIndex;
1113 if ( dict )
1114dict->iterators->append( this );// attach to new list
1115 return *this;
1116}
1117
1118/*!
1119 \internal
1120 Destroys the iterator.
1121*/
1122
1123QGDictIterator::~QGDictIterator()
1124{
1125 if ( dict )// detach iterator from dict
1126dict->iterators->removeRef( this );
1127}
1128
1129
1130/*!
1131 \internal
1132 Sets the iterator to point to the first item in the dictionary.
1133*/
1134
1135QCollection::Item QGDictIterator::toFirst()
1136{
1137 if ( !dict ) {
1138#if defined(CHECK_NULL)
1139qWarning( "QGDictIterator::toFirst: Dictionary has been deleted" );
1140#endif
1141return 0;
1142 }
1143 if ( dict->count() == 0 ) {// empty dictionary
1144curNode = 0;
1145return 0;
1146 }
1147 register uint i = 0;
1148 register QBaseBucket **v = dict->vec;
1149 while ( !(*v++) )
1150i++;
1151 curNode = dict->vec[i];
1152 curIndex = i;
1153 return curNode->getData();
1154}
1155
1156
1157/*!
1158 \internal
1159 Moves to the next item (postfix).
1160*/
1161
1162QCollection::Item QGDictIterator::operator()()
1163{
1164 if ( !dict ) {
1165#if defined(CHECK_NULL)
1166qWarning( "QGDictIterator::operator(): Dictionary has been deleted" );
1167#endif
1168return 0;
1169 }
1170 if ( !curNode )
1171return 0;
1172 QCollection::Item d = curNode->getData();
1173 this->operator++();
1174 return d;
1175}
1176
1177/*!
1178 \internal
1179 Moves to the next item (prefix).
1180*/
1181
1182QCollection::Item QGDictIterator::operator++()
1183{
1184 if ( !dict ) {
1185#if defined(CHECK_NULL)
1186qWarning( "QGDictIterator::operator++: Dictionary has been deleted" );
1187#endif
1188return 0;
1189 }
1190 if ( !curNode )
1191return 0;
1192 curNode = curNode->getNext();
1193 if ( !curNode ) {// no next bucket
1194register uint i = curIndex + 1;// look from next vec element
1195register QBaseBucket **v = &dict->vec[i];
1196while ( i < dict->size() && !(*v++) )
1197 i++;
1198if ( i == dict->size() ) {// nothing found
1199 curNode = 0;
1200 return 0;
1201}
1202curNode = dict->vec[i];
1203curIndex = i;
1204 }
1205 return curNode->getData();
1206}
1207
1208/*!
1209 \internal
1210 Moves \e jumps positions forward.
1211*/
1212
1213QCollection::Item QGDictIterator::operator+=( uint jumps )
1214{
1215 while ( curNode && jumps-- )
1216operator++();
1217 return curNode ? curNode->getData() : 0;
1218}
1219

Archive Download this file

Revision: 1322