Chameleon

Chameleon Svn Source Tree

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

Source at commit 1406 created 12 years 10 months ago.
By meklort, Revert drivers.c so that kexts are only loaded when OSBundleRequired is set and that value is not safe mode. Added some comments about it too.
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: 1406