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