qtools/qgdict.cpp

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