Chameleon

Chameleon Svn Source Tree

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

Source at commit 1322 created 12 years 8 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() ) ␊
90␉qWarning( "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␊
98␉for ( i=0; i<len; i++ ) {␊
99␉ h = (h<<4) + p[i].cell();␊
100␉ if ( (g = h & 0xf0000000) )␊
101␉␉h ^= g >> 24;␊
102␉ h &= ~g;␊
103␉}␊
104 } else {␉␉␉␉␉// case insensitive␊
105␉for ( i=0; i<len; i++ ) {␊
106␉ h = (h<<4) + p[i].lower().cell();␊
107␉ if ( (g = h & 0xf0000000) )␊
108␉␉h ^= g >> 24;␊
109␉ h &= ~g;␊
110␉}␊
111 }␊
112 int index = h;␊
113 if ( index < 0 )␉␉␉␉// adjust index to table size␊
114␉index = -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 {␊
128␉qWarning( "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␊
136␉while ( *k ) {␊
137␉ h = (h<<4) + *k++;␊
138␉ if ( (g = h & 0xf0000000) )␊
139␉␉h ^= g >> 24;␊
140␉ h &= ~g;␊
141␉}␊
142 } else {␉␉␉␉␉// case insensitive␊
143␉while ( *k ) {␊
144␉ h = (h<<4) + tolower(*k);␊
145␉ if ( (g = h & 0xf0000000) )␊
146␉␉h ^= g >> 24;␊
147␉ h &= ~g;␊
148␉ k++;␊
149␉}␊
150 }␊
151 int index = h;␊
152 if ( index < 0 )␉␉␉␉// adjust index to table size␊
153␉index = -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) ) {␊
212␉case StringKey:␊
213␉ cases = caseSensitive;␊
214␉ copyk = FALSE;␊
215␉ break;␊
216␉case AsciiKey:␊
217␉ cases = caseSensitive;␊
218␉ copyk = copyKeys;␊
219␉ break;␊
220␉default:␊
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␊
239␉switch ( keytype ) {␊
240␉ case StringKey:␊
241␉␉look_string( it.getKeyString(), it.get(), op_insert );␊
242␉␉break;␊
243␉ case AsciiKey:␊
244␉␉look_ascii( it.getKeyAscii(), it.get(), op_insert );␊
245␉␉break;␊
246␉ case IntKey:␊
247␉␉look_int( it.getKeyInt(), it.get(), op_insert );␊
248␉␉break;␊
249␉ case PtrKey:␊
250␉␉look_ptr( it.getKeyPtr(), it.get(), op_insert );␊
251␉␉break;␊
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␊
268␉return;␊
269 QGDictIterator *i = iterators->first();␊
270 while ( i ) {␉␉␉␉// notify all iterators that␊
271␉i->dict = 0;␉␉␉␉// this dict is deleted␊
272␉i = 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␊
288␉switch ( keytype ) {␊
289␉ case StringKey:␊
290␉␉look_string( it.getKeyString(), it.get(), op_insert );␊
291␉␉break;␊
292␉ case AsciiKey:␊
293␉␉look_ascii( it.getKeyAscii(), it.get(), op_insert );␊
294␉␉break;␊
295␉ case IntKey:␊
296␉␉look_int( it.getKeyInt(), it.get(), op_insert );␊
297␉␉break;␊
298␉ case PtrKey:␊
299␉␉look_ptr( it.getKeyPtr(), it.get(), op_insert );␊
300␉␉break;␊
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 int␉index = hashKeyString(key) % vlen;␊
360 if ( op == op_find ) {␉␉␉// find␊
361␉if ( cases ) {␊
362␉ for ( n=(QStringBucket*)vec[index]; n;␊
363␉␉ n=(QStringBucket*)n->getNext() ) {␊
364␉␉if ( 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() ) {␊
371␉␉if ( k == n->getKey().lower() )␊
372␉␉ return n->getData();␉// item found␊
373␉ }␊
374␉}␊
375␉return 0;␉␉␉␉// not found␊
376 }␊
377 if ( op == op_replace ) {␉␉␉// replace␊
378␉if ( 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 )␊
386␉qWarning( "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 int␉index = hashKeyAscii(key) % vlen;␊
400 if ( op == op_find ) {␉␉␉// find␊
401␉if ( cases ) {␊
402␉ for ( n=(QAsciiBucket*)vec[index]; n;␊
403␉␉ n=(QAsciiBucket*)n->getNext() ) {␊
404␉␉if ( 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() ) {␊
410␉␉if ( qstricmp(n->getKey(),key) == 0 )␊
411␉␉ return n->getData();␉// item found␊
412␉ }␊
413␉}␊
414␉return 0;␉␉␉␉// not found␊
415 }␊
416 if ( op == op_replace ) {␉␉␉// replace␊
417␉if ( 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 )␊
425␉qWarning( "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␊
440␉for ( n=(QIntBucket*)vec[index]; n;␊
441␉ n=(QIntBucket*)n->getNext() ) {␊
442␉ if ( n->getKey() == key )␊
443␉␉return n->getData();␉␉// item found␊
444␉}␊
445␉return 0;␉␉␉␉// not found␊
446 }␊
447 if ( op == op_replace ) {␉␉␉// replace␊
448␉if ( 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 )␊
456␉qWarning( "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␊
471␉for ( n=(QPtrBucket*)vec[index]; n;␊
472␉ n=(QPtrBucket*)n->getNext() ) {␊
473␉ if ( n->getKey() == key )␊
474␉␉return n->getData();␉␉// item found␊
475␉}␊
476␉return 0;␉␉␉␉// not found␊
477 }␊
478 if ( op == op_replace ) {␉␉␉// replace␊
479␉if ( 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 )␊
487␉qWarning( "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++ ) {␊
516␉switch ( keytype ) {␊
517␉ case StringKey:␊
518␉␉{␊
519␉␉ QStringBucket *n=(QStringBucket *)old_vec[index];␊
520␉␉ while ( n ) {␊
521␉␉␉look_string( n->getKey(), n->getData(), op_insert );␊
522␉␉␉QStringBucket *t=(QStringBucket *)n->getNext();␊
523␉␉␉delete n;␊
524␉␉␉n = t;␊
525␉␉ }␊
526␉␉}␊
527␉␉break;␊
528␉ case AsciiKey:␊
529␉␉{␊
530␉␉ QAsciiBucket *n=(QAsciiBucket *)old_vec[index];␊
531␉␉ while ( n ) {␊
532␉␉␉look_ascii( n->getKey(), n->getData(), op_insert );␊
533␉␉␉QAsciiBucket *t=(QAsciiBucket *)n->getNext();␊
534␉␉␉delete n;␊
535␉␉␉n = t;␊
536␉␉ }␊
537␉␉}␊
538␉␉break;␊
539␉ case IntKey:␊
540␉␉{␊
541␉␉ QIntBucket *n=(QIntBucket *)old_vec[index];␊
542␉␉ while ( n ) {␊
543␉␉␉look_int( n->getKey(), n->getData(), op_insert );␊
544␉␉␉QIntBucket *t=(QIntBucket *)n->getNext();␊
545␉␉␉delete n;␊
546␉␉␉n = t;␊
547␉␉ }␊
548␉␉}␊
549␉␉break;␊
550␉ case PtrKey:␊
551␉␉{␊
552␉␉ QPtrBucket *n=(QPtrBucket *)old_vec[index];␊
553␉␉ while ( n ) {␊
554␉␉␉look_ptr( n->getKey(), n->getData(), op_insert );␊
555␉␉␉QPtrBucket *t=(QPtrBucket *)n->getNext();␊
556␉␉␉delete n;␊
557␉␉␉n = t;␊
558␉␉ }␊
559␉␉}␊
560␉␉break;␊
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() ) {␊
570␉QGDictIterator *i = iterators->first();␊
571␉while ( 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␊
587␉QGDictIterator *i = iterators->first();␊
588␉while ( i ) {␉␉␉␉// invalidate all iterators␊
589␉ if ( i->curNode == node )␉␉// referring to pending node␊
590␉␉i->operator++();␊
591␉ i = iterators->next();␊
592␉}␊
593 }␊
594 if ( prev )␉␉␉␉␉// unlink node␊
595␉prev->setNext( node->getNext() );␊
596 else␊
597␉vec[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␊
604␉return 0;␊
605 QStringBucket *n;␊
606 QStringBucket *prev = 0;␊
607 int index = hashKeyString(key) % vlen;␊
608 if ( cases ) {␊
609␉for ( n=(QStringBucket*)vec[index]; n;␊
610␉ n=(QStringBucket*)n->getNext() ) {␊
611␉ bool found = (key == n->getKey());␊
612␉ if ( found && d )␊
613␉␉found = (n->getData() == d);␊
614␉ if ( found ) {␊
615␉␉unlink_common(index,n,prev);␊
616␉␉return n;␊
617␉ }␊
618␉ prev = n;␊
619␉}␊
620 } else {␊
621␉QString k = key.lower();␊
622␉for ( n=(QStringBucket*)vec[index]; n;␊
623␉ n=(QStringBucket*)n->getNext() ) {␊
624␉ bool found = (k == n->getKey().lower());␊
625␉ if ( found && d )␊
626␉␉found = (n->getData() == d);␊
627␉ if ( found ) {␊
628␉␉unlink_common(index,n,prev);␊
629␉␉return 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␊
640␉return 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() ) {␊
645␉bool found = (cases ? qstrcmp(n->getKey(),key)␊
646␉␉ : qstricmp(n->getKey(),key)) == 0;␊
647␉if ( found && d )␊
648␉ found = (n->getData() == d);␊
649␉if ( found ) {␊
650␉ unlink_common(index,n,prev);␊
651␉ return n;␊
652␉}␊
653␉prev = n;␊
654 }␊
655 return 0;␊
656}␊
657␊
658QIntBucket *QGDict::unlink_int( long key, QCollection::Item d )␊
659{␊
660 if ( numItems == 0 )␉␉␉// nothing in dictionary␊
661␉return 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() ) {␊
666␉bool found = (n->getKey() == key);␊
667␉if ( found && d )␊
668␉ found = (n->getData() == d);␊
669␉if ( found ) {␊
670␉ unlink_common(index,n,prev);␊
671␉ return n;␊
672␉}␊
673␉prev = n;␊
674 }␊
675 return 0;␊
676}␊
677␊
678QPtrBucket *QGDict::unlink_ptr( void *key, QCollection::Item d )␊
679{␊
680 if ( numItems == 0 )␉␉␉// nothing in dictionary␊
681␉return 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() ) {␊
686␉bool found = (n->getKey() == key);␊
687␉if ( found && d )␊
688␉ found = (n->getData() == d);␊
689␉if ( found ) {␊
690␉ unlink_common(index,n,prev);␊
691␉ return n;␊
692␉}␊
693␉prev = 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 ) {␊
710␉deleteItem( n->getData() );␊
711␉delete n;␊
712␉return TRUE;␊
713 } else {␊
714␉return 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 ) {␊
725␉if ( copyk )␊
726␉ delete [] (char *)n->getKey();␊
727␉deleteItem( n->getData() );␊
728␉delete 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 ) {␊
740␉deleteItem( n->getData() );␊
741␉delete 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 ) {␊
753␉deleteItem( n->getData() );␊
754␉delete 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 ) {␊
767␉d = n->getData();␊
768␉delete n;␊
769 } else {␊
770␉d = 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 ) {␊
783␉if ( copyk )␊
784␉ delete [] (char *)n->getKey();␊
785␉d = n->getData();␊
786␉delete n;␊
787 } else {␊
788␉d = 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 ) {␊
801␉d = n->getData();␊
802␉delete n;␊
803 } else {␊
804␉d = 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 ) {␊
817␉d = n->getData();␊
818␉delete n;␊
819 } else {␊
820␉d = 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 )␊
834␉return;␊
835 numItems = 0;␉␉␉␉// disable remove() function␊
836 for ( uint j=0; j<vlen; j++ ) {␉␉// destroy hash table␊
837␉if ( vec[j] ) {␊
838␉ switch ( keytype ) {␊
839␉␉case StringKey:␊
840␉␉ {␊
841␉␉␉QStringBucket *n=(QStringBucket *)vec[j];␊
842␉␉␉while ( n ) {␊
843␉␉␉ QStringBucket *next = (QStringBucket*)n->getNext();␊
844␉␉␉ deleteItem( n->getData() );␊
845␉␉␉ delete n;␊
846␉␉␉ n = next;␊
847␉␉␉}␊
848␉␉ }␊
849␉␉ break;␊
850␉␉case AsciiKey:␊
851␉␉ {␊
852␉␉␉QAsciiBucket *n=(QAsciiBucket *)vec[j];␊
853␉␉␉while ( n ) {␊
854␉␉␉ QAsciiBucket *next = (QAsciiBucket*)n->getNext();␊
855␉␉␉ if ( copyk )␊
856␉␉␉␉delete [] (char *)n->getKey();␊
857␉␉␉ deleteItem( n->getData() );␊
858␉␉␉ delete n;␊
859␉␉␉ n = next;␊
860␉␉␉}␊
861␉␉ }␊
862␉␉ break;␊
863␉␉case IntKey:␊
864␉␉ {␊
865␉␉␉QIntBucket *n=(QIntBucket *)vec[j];␊
866␉␉␉while ( n ) {␊
867␉␉␉ QIntBucket *next = (QIntBucket*)n->getNext();␊
868␉␉␉ deleteItem( n->getData() );␊
869␉␉␉ delete n;␊
870␉␉␉ n = next;␊
871␉␉␉}␊
872␉␉ }␊
873␉␉ break;␊
874␉␉case PtrKey:␊
875␉␉ {␊
876␉␉␉QPtrBucket *n=(QPtrBucket *)vec[j];␊
877␉␉␉while ( 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␊
890␉QGDictIterator *i = iterators->first();␊
891␉while ( 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 ) {␊
913␉qDebug( "Empty!" );␊
914␉qDebug( "%s", line.ascii() );␊
915␉return;␊
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() ) {␊
921␉QBaseBucket *n = vec[i];␊
922␉int b = 0;␊
923␉while ( n ) {␉␉␉␉// count number of buckets␊
924␉ b++;␊
925␉ n = n->getNext();␊
926␉}␊
927␉real = real + (double)b * ((double)b+1.0)/2.0;␊
928␉char buf[80], *pbuf;␊
929␉if ( b > 78 )␊
930␉ b = 78;␊
931␉pbuf = buf;␊
932␉while ( b-- )␊
933␉ *pbuf++ = '*';␊
934␉*pbuf = '\0';␊
935␉qDebug( "%s", buf );␊
936␉i++;␊
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␊
977␉Item d;␊
978␉switch ( keytype ) {␊
979␉ case StringKey:␊
980␉␉{␊
981␉␉ QString k;␊
982␉␉ s >> k;␊
983␉␉ read( s, d );␊
984␉␉ look_string( k, d, op_insert );␊
985␉␉}␊
986␉␉break;␊
987␉ case AsciiKey:␊
988␉␉{␊
989␉␉ char *k;␊
990␉␉ s >> k;␊
991␉␉ read( s, d );␊
992␉␉ look_ascii( k, d, op_insert );␊
993␉␉ if ( copyk )␊
994␉␉␉delete [] k;␊
995␉␉}␊
996␉␉break;␊
997␉ case IntKey:␊
998␉␉{␊
999␉␉ Q_UINT32 k;␊
1000␉␉ s >> k;␊
1001␉␉ read( s, d );␊
1002␉␉ look_int( k, d, op_insert );␊
1003␉␉}␊
1004␉␉break;␊
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 )␊
1015␉␉␉look_ptr( (void *)k, d, op_insert );␊
1016␉␉}␊
1017␉␉break;␊
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() ) {␊
1033␉QBaseBucket *n = vec[i];␊
1034␉while ( n ) {␉␉␉␉// write all buckets␊
1035␉ switch ( keytype ) {␊
1036␉␉case StringKey:␊
1037␉␉ s << ((QStringBucket*)n)->getKey();␊
1038␉␉ break;␊
1039␉␉case AsciiKey:␊
1040␉␉ s << ((QAsciiBucket*)n)->getKey();␊
1041␉␉ break;␊
1042␉␉case IntKey:␊
1043␉␉ s << (Q_UINT32)((QIntBucket*)n)->getKey();␊
1044␉␉ break;␊
1045␉␉case 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␉}␊
1052␉i++;␊
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 ) {␊
1080␉dict->iterators = new QGDItList;␉// create iterator list␊
1081␉CHECK_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 )␊
1097␉dict->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␊
1109␉dict->iterators->removeRef( this );␊
1110 dict = it.dict;␊
1111 curNode = it.curNode;␊
1112 curIndex = it.curIndex;␊
1113 if ( dict )␊
1114␉dict->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␊
1126␉dict->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)␊
1139␉qWarning( "QGDictIterator::toFirst: Dictionary has been deleted" );␊
1140#endif␊
1141␉return 0;␊
1142 }␊
1143 if ( dict->count() == 0 ) {␉␉␉// empty dictionary␊
1144␉curNode = 0;␊
1145␉return 0;␊
1146 }␊
1147 register uint i = 0;␊
1148 register QBaseBucket **v = dict->vec;␊
1149 while ( !(*v++) )␊
1150␉i++;␊
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)␊
1166␉qWarning( "QGDictIterator::operator(): Dictionary has been deleted" );␊
1167#endif␊
1168␉return 0;␊
1169 }␊
1170 if ( !curNode )␊
1171␉return 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)␊
1186␉qWarning( "QGDictIterator::operator++: Dictionary has been deleted" );␊
1187#endif␊
1188␉return 0;␊
1189 }␊
1190 if ( !curNode )␊
1191␉return 0;␊
1192 curNode = curNode->getNext();␊
1193 if ( !curNode ) {␉␉␉␉// no next bucket␊
1194␉register uint i = curIndex + 1;␉␉// look from next vec element␊
1195␉register QBaseBucket **v = &dict->vec[i];␊
1196␉while ( i < dict->size() && !(*v++) )␊
1197␉ i++;␊
1198␉if ( i == dict->size() ) {␉␉// nothing found␊
1199␉ curNode = 0;␊
1200␉ return 0;␊
1201␉}␊
1202␉curNode = dict->vec[i];␊
1203␉curIndex = 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-- )␊
1216␉operator++();␊
1217 return curNode ? curNode->getData() : 0;␊
1218}␊
1219

Archive Download this file

Revision: 1322