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 "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( "%s",line.ascii() );
 911     qDebug( "DICTIONARY STATISTICS:" );
 912     if ( count() == 0 ) {
 913         qDebug( "Empty!" );
 914         qDebug( "%s", line.ascii() );
 915         return;
 916     }
 917     real = 0.0;
 918     ideal = (float)count()/(2.0*size())*(count()+2.0*size()-1);
 919     uint i = 0;
 920     while ( i<size() ) {
 921         QBaseBucket *n = vec[i];
 922         int b = 0;
 923         while ( n ) {                           // count number of buckets
 924             b++;
 925             n = n->getNext();
 926         }
 927         real = real + (double)b * ((double)b+1.0)/2.0;
 928         char buf[80], *pbuf;
 929         if ( b > 78 )
 930             b = 78;
 931         pbuf = buf;
 932         while ( b-- )
 933             *pbuf++ = '*';
 934         *pbuf = '\0';
 935         qDebug( "%s", buf );
 936         i++;
 937     }
 938     qDebug( "Array size = %d", size() );
 939     qDebug( "# items    = %d", count() );
 940     qDebug( "Real dist  = %g", real );
 941     qDebug( "Rand dist  = %g", ideal );
 942     qDebug( "Real/Rand  = %g", real/ideal );
 943     qDebug( "%s",line.ascii() );
 944 #endif // DEBUG
 945 }
 946
 947
 948 /*****************************************************************************
 949   QGDict stream functions
 950  *****************************************************************************/
 951 #ifndef QT_NO_DATASTREAM
 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                     unsigned long k;
1000                     s >> k;
1001                     read( s, d );
1002                     look_int( (long)k, d, op_insert );
1003                 }
1004                 break;
1005             case PtrKey:
1006                 {
1007                     unsigned long 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()
1136 {
1137     if ( !dict ) {
1138 #if defined(CHECK_NULL)
1139         qWarning( "QGDictIterator::toFirst: Dictionary has been deleted" );
1140 #endif
1141         return 0;
1142     }
1143     if ( dict->count() == 0 ) {                 // empty dictionary
1144         curNode = 0;
1145         return 0;
1146     }
1147     register uint i = 0;
1148     register QBaseBucket **v = dict->vec;
1149     while ( !(*v++) )
1150         i++;
1151     curNode = dict->vec[i];
1152     curIndex = i;
1153     return curNode->getData();
1154 }
1155
1156
1157 /*!
1158   \internal
1159   Moves to the next item (postfix).
1160 */
1161
1162 QCollection::Item QGDictIterator::operator()()
1163 {
1164     if ( !dict ) {
1165 #if defined(CHECK_NULL)
1166         qWarning( "QGDictIterator::operator(): Dictionary has been deleted" );
1167 #endif
1168         return 0;
1169     }
1170     if ( !curNode )
1171         return 0;
1172     QCollection::Item d = curNode->getData();
1173     this->operator++();
1174     return d;
1175 }
1176
1177 /*!
1178   \internal
1179   Moves to the next item (prefix).
1180 */
1181
1182 QCollection::Item QGDictIterator::operator++()
1183 {
1184     if ( !dict ) {
1185 #if defined(CHECK_NULL)
1186         qWarning( "QGDictIterator::operator++: Dictionary has been deleted" );
1187 #endif
1188         return 0;
1189     }
1190     if ( !curNode )
1191         return 0;
1192     curNode = curNode->getNext();
1193     if ( !curNode ) {                           // no next bucket
1194         register uint i = curIndex + 1;         // look from next vec element
1195         register QBaseBucket **v = &dict->vec[i];
1196         while ( i < dict->size() && !(*v++) )
1197             i++;
1198         if ( i == dict->size() ) {              // nothing found
1199             curNode = 0;
1200             return 0;
1201         }
1202         curNode = dict->vec[i];
1203         curIndex = i;
1204     }
1205     return curNode->getData();
1206 }
1207
1208 /*!
1209   \internal
1210   Moves \e jumps positions forward.
1211 */
1212
1213 QCollection::Item QGDictIterator::operator+=( uint jumps )
1214 {
1215     while ( curNode && jumps-- )
1216         operator++();
1217     return curNode ? curNode->getData() : 0;
1218 }