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 

    61 static const int op_find    = 0;

    62 static const int op_insert  = 1;

    63 static const int op_replace = 2;

    64 

    65 

    66 class QGDItList : public QList<QGDictIterator>

    67 {

    68 public:

    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 

    86 int 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 

   123 int 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 

   168 QDataStream& 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 

   181 QDataStream& 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 

   196 QGDict::QGDict( uint len, KeyType kt, bool caseSensitive, bool copyKeys )

   197 {

   198     init( len, kt, caseSensitive, copyKeys );

   199 }

   200 

   201 

   202 void 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 

   233 QGDict::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 

   263 QGDict::~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 

   283 QGDict &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 

   356 QCollection::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 

   396 QCollection::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 

   435 QCollection::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 

   466 QCollection::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 */

   501 void 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 

   584 void 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 

   601 QStringBucket *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 

   637 QAsciiBucket *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 

   658 QIntBucket *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 

   678 QPtrBucket *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 

   706 bool 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 

   721 bool 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 

   736 bool 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 

   749 bool 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 

   762 QCollection::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 

   778 QCollection::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 

   796 QCollection::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 

   812 QCollection::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 

   831 void 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 

   904 void QGDict::statistics() const

   905 {

   906 #if defined(DEBUG)

   907     QString line;

   908     line.fill( '-', 60 );

   909     double real, ideal;

   910     qDebug( line.ascii() );

   911     qDebug( "DICTIONARY STATISTICS:" );

   912     if ( count() == 0 ) {

   913 	qDebug( "Empty!" );

   914 	qDebug( 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( 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( line.ascii() );

   944 #endif // DEBUG

   945 }

   946 

   947 

   948 /*****************************************************************************

   949   QGDict stream functions

   950  *****************************************************************************/

   951 #ifndef QT_NO_DATASTREAM

   952 QDataStream &operator>>( QDataStream &s, QGDict &dict )

   953 {

   954     return dict.read( s );

   955 }

   956 

   957 QDataStream &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 

   971 QDataStream &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 

  1028 QDataStream& 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 

  1075 QGDictIterator::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 

  1091 QGDictIterator::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 

  1106 QGDictIterator &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 

  1123 QGDictIterator::~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 

  1135 QCollection::Item QGDictIterator::toFirst()