1 /****************************************************************************

     2 **

     3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

     4 ** All rights reserved.

     5 ** Contact: Nokia Corporation (qt-info@nokia.com)

     6 **

     7 ** This file is part of the Qt3Support module of the Qt Toolkit.

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

    11 ** This file contains pre-release code and may not be distributed.

    12 ** You may use this file in accordance with the terms and conditions

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    15 **

    16 ** GNU Lesser General Public License Usage

    17 ** Alternatively, this file may be used under the terms of the GNU Lesser

    18 ** General Public License version 2.1 as published by the Free Software

    19 ** Foundation and appearing in the file LICENSE.LGPL included in the

    20 ** packaging of this file.  Please review the following information to

    21 ** ensure the GNU Lesser General Public License version 2.1 requirements

    22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

    23 **

    24 ** In addition, as a special exception, Nokia gives you certain additional

    25 ** rights.  These rights are described in the Nokia Qt LGPL Exception

    26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

    27 **

    28 ** If you have questions regarding the use of this file, please contact

    29 ** Nokia at qt-info@nokia.com.

    30 **

    31 **

    32 **

    33 **

    34 **

    35 **

    36 **

    37 **

    38 ** $QT_END_LICENSE$

    39 **

    40 ****************************************************************************/

    41 

    42 #include "q3gdict.h"

    43 #include "q3ptrlist.h"

    44 #include "qstring.h"

    45 #include "qdatastream.h"

    46 #include <ctype.h>

    47 

    48 QT_BEGIN_NAMESPACE

    49 

    50 /*!

    51   \class Q3GDict

    52   \reentrant

    53   \brief The Q3GDict class is an internal class for implementing QDict template classes.

    54 

    55   \internal

    56 

    57   Q3GDict is a strictly internal class that acts as a base class for the

    58   \link collection.html collection classes\endlink QDict and QIntDict.

    59 

    60   Q3GDict has some virtual functions that can be reimplemented to customize

    61   the subclasses.

    62   \list

    63   \i read() reads a collection/dictionary item from a QDataStream.

    64   \i write() writes a collection/dictionary item to a QDataStream.

    65   \endlist

    66   Normally, you do not have to reimplement any of these functions.

    67 */

    68 

    69 static const int op_find = 0;

    70 static const int op_insert = 1;

    71 static const int op_replace = 2;

    72 

    73 

    74 class Q3GDItList : public Q3PtrList<Q3GDictIterator>

    75 {

    76 public:

    77     Q3GDItList() : Q3PtrList<Q3GDictIterator>() {}

    78     Q3GDItList(const Q3GDItList &list) : Q3PtrList<Q3GDictIterator>(list) {}

    79     ~Q3GDItList() { clear(); }

    80     Q3GDItList &operator=(const Q3GDItList &list)

    81         { return (Q3GDItList&)Q3PtrList<Q3GDictIterator>::operator=(list); }

    82 };

    83 

    84 

    85 /*****************************************************************************

    86   Default implementation of special and virtual functions

    87  *****************************************************************************/

    88 

    89 /*!

    90   Returns the hash key for \a key, when key is a string.

    91 */

    92 

    93 int Q3GDict::hashKeyString(const QString &key)

    94 {

    95 #if defined(QT_CHECK_NULL)

    96     if (key.isNull())

    97         qWarning("Q3GDict::hashKeyString: Invalid null key");

    98 #endif

    99     int i;

   100     register uint h=0;

   101     uint g;

   102     const QChar *p = key.unicode();

   103     if (cases) {                                // case sensitive

   104         for (i=0; i<(int)key.length(); i++) {

   105             h = (h<<4) + p[i].cell();

   106             if ((g = h & 0xf0000000))

   107                 h ^= g >> 24;

   108             h &= ~g;

   109         }

   110     } else {                                    // case insensitive

   111         for (i=0; i<(int)key.length(); i++) {

   112             h = (h<<4) + p[i].lower().cell();

   113             if ((g = h & 0xf0000000))

   114                 h ^= g >> 24;

   115             h &= ~g;

   116         }

   117     }

   118     int index = h;

   119     if (index < 0)                              // adjust index to table size

   120         index = -index;

   121     return index;

   122 }

   123 

   124 /*!

   125   Returns the hash key for \a key, which is a C string.

   126 */

   127 

   128 int Q3GDict::hashKeyAscii(const char *key)

   129 {

   130 #if defined(QT_CHECK_NULL)

   131     if (key == 0)

   132         qWarning("Q3GDict::hashAsciiKey: Invalid null key");

   133 #endif

   134     register const char *k = key;

   135     register uint h=0;

   136     uint g;

   137     if (cases) {                                // case sensitive

   138         while (*k) {

   139             h = (h<<4) + *k++;

   140             if ((g = h & 0xf0000000))

   141                 h ^= g >> 24;

   142             h &= ~g;

   143         }

   144     } else {                                    // case insensitive

   145         while (*k) {

   146             h = (h<<4) + tolower((uchar) *k);

   147             if ((g = h & 0xf0000000))

   148                 h ^= g >> 24;

   149             h &= ~g;

   150             k++;

   151         }

   152     }

   153     int index = h;

   154     if (index < 0)                              // adjust index to table size

   155         index = -index;

   156     return index;

   157 }

   158 

   159 #ifndef QT_NO_DATASTREAM

   160 

   161 /*!

   162     \overload

   163   Reads a collection/dictionary item from the stream \a s and returns a

   164   reference to the stream.

   165 

   166   The default implementation sets \a item to 0.

   167 

   168   \sa write()

   169 */

   170 

   171 QDataStream& Q3GDict::read(QDataStream &s, Q3PtrCollection::Item &item)

   172 {

   173     item = 0;

   174     return s;

   175 }

   176 

   177 /*!

   178     \overload

   179   Writes a collection/dictionary item to the stream \a s and returns a

   180   reference to the stream.

   181 

   182   \sa read()

   183 */

   184 

   185 QDataStream& Q3GDict::write(QDataStream &s, Q3PtrCollection::Item) const

   186 {

   187     return s;

   188 }

   189 #endif //QT_NO_DATASTREAM

   190 

   191 /*****************************************************************************

   192   Q3GDict member functions

   193  *****************************************************************************/

   194 

   195 /*!

   196   Constructs a dictionary.

   197 

   198   \a len is the initial size of the dictionary.

   199   The key type is \a kt which may be \c StringKey, \c AsciiKey,

   200   \c IntKey or \c PtrKey. The case-sensitivity of lookups is set with

   201   \a caseSensitive. Keys are copied if \a copyKeys is true.

   202 */

   203 

   204 Q3GDict::Q3GDict(uint len, KeyType kt, bool caseSensitive, bool copyKeys)

   205 {

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

   207 }

   208 

   209 

   210 void Q3GDict::init(uint len, KeyType kt, bool caseSensitive, bool copyKeys)

   211 {

   212     vlen = len ? len : 17;

   213     vec = new Q3BaseBucket *[ vlen ];

   214 

   215     Q_CHECK_PTR(vec);

   216     memset((char*)vec, 0, vlen*sizeof(Q3BaseBucket*));

   217     numItems  = 0;

   218     iterators = 0;

   219     // The caseSensitive and copyKey options don't make sense for

   220     // all dict types.

   221     switch ((keytype = (uint)kt)) {

   222         case StringKey:

   223             cases = caseSensitive;

   224             copyk = false;

   225             break;

   226         case AsciiKey:

   227             cases = caseSensitive;

   228             copyk = copyKeys;

   229             break;

   230         default:

   231             cases = false;

   232             copyk = false;

   233             break;

   234     }

   235 }

   236 

   237 

   238 /*!

   239   Constructs a copy of \a dict.

   240 */

   241 

   242 Q3GDict::Q3GDict(const Q3GDict & dict)

   243     : Q3PtrCollection(dict)

   244 {

   245     init(dict.vlen, (KeyType)dict.keytype, dict.cases, dict.copyk);

   246     Q3GDictIterator it(dict);

   247     while (it.get()) {                  // copy from other dict

   248         switch (keytype) {

   249             case StringKey:

   250                 look_string(it.getKeyString(), it.get(), op_insert);

   251                 break;

   252             case AsciiKey:

   253                 look_ascii(it.getKeyAscii(), it.get(), op_insert);

   254                 break;

   255             case IntKey:

   256                 look_int(it.getKeyInt(), it.get(), op_insert);

   257                 break;

   258             case PtrKey:

   259                 look_ptr(it.getKeyPtr(), it.get(), op_insert);

   260                 break;

   261         }

   262         ++it;

   263     }

   264 }

   265 

   266 

   267 /*!

   268   Removes all items from the dictionary and destroys it.

   269 */

   270 

   271 Q3GDict::~Q3GDict()

   272 {

   273     clear();                                    // delete everything

   274     delete [] vec;

   275     if (!iterators)                             // no iterators for this dict

   276         return;

   277     Q3GDictIterator *i = iterators->first();

   278     while (i) {                         // notify all iterators that

   279         i->dict = 0;                            // this dict is deleted

   280         i = iterators->next();

   281     }

   282     delete iterators;

   283 }

   284 

   285 

   286 /*!

   287   Assigns \a dict to this dictionary.

   288 */

   289 

   290 Q3GDict &Q3GDict::operator=(const Q3GDict &dict)

   291 {

   292     if (&dict == this)

   293         return *this;

   294     clear();

   295     Q3GDictIterator it(dict);

   296     while (it.get()) {                  // copy from other dict

   297         switch (keytype) {

   298             case StringKey:

   299                 look_string(it.getKeyString(), it.get(), op_insert);

   300                 break;

   301             case AsciiKey:

   302                 look_ascii(it.getKeyAscii(), it.get(), op_insert);

   303                 break;

   304             case IntKey:

   305                 look_int(it.getKeyInt(), it.get(), op_insert);

   306                 break;

   307             case PtrKey:

   308                 look_ptr(it.getKeyPtr(), it.get(), op_insert);

   309                 break;

   310         }

   311         ++it;

   312     }

   313     return *this;

   314 }

   315 

   316 /*!

   317   \fn uint Q3GDict::count() const

   318 

   319   Returns the number of items in the dictionary.

   320 */

   321 

   322 /*!

   323   \fn uint Q3GDict::size() const

   324 

   325   Returns the size of the hash array.

   326 */

   327 

   328 /*!

   329   The do-it-all function; \a op is one of op_find, op_insert, op_replace.

   330   The key is \a key and the item is \a d.

   331 */

   332 

   333 Q3PtrCollection::Item Q3GDict::look_string(const QString &key, Q3PtrCollection::Item d,

   334                                        int op)

   335 {

   336     Q3StringBucket *n = 0;

   337     int index = hashKeyString(key) % vlen;

   338     if (op == op_find) {                        // find

   339         if (cases) {

   340             n = (Q3StringBucket*)vec[index];

   341             while(n != 0) {

   342                 if (key == n->getKey())

   343                     return n->getData();        // item found

   344                 n = (Q3StringBucket*)n->getNext();

   345             }

   346         } else {

   347             QString k = key.lower();

   348             n = (Q3StringBucket*)vec[index];

   349             while(n != 0) {

   350                 if (k == n->getKey().lower())

   351                     return n->getData();        // item found

   352                 n = (Q3StringBucket*)n->getNext();

   353             }

   354         }

   355         return 0;                               // not found

   356     }

   357     if (op == op_replace) {                     // replace

   358         if (vec[index] != 0)                    // maybe something there

   359             remove_string(key);

   360     }

   361     // op_insert or op_replace

   362     n = new Q3StringBucket(key,newItem(d),vec[index]);

   363     Q_CHECK_PTR(n);

   364 #if defined(QT_CHECK_NULL)

   365     if (n->getData() == 0)

   366         qWarning("QDict: Cannot insert null item");

   367 #endif

   368     vec[index] = n;

   369     numItems++;

   370     return n->getData();

   371 }

   372 

   373 Q3PtrCollection::Item Q3GDict::look_ascii(const char *key, Q3PtrCollection::Item d, int op)

   374 {

   375     Q3AsciiBucket *n;

   376     int index = hashKeyAscii(key) % vlen;

   377     if (op == op_find) {                        // find

   378         if (cases) {

   379             for (n=(Q3AsciiBucket*)vec[index]; n;

   380                   n=(Q3AsciiBucket*)n->getNext()) {

   381                 if (qstrcmp(n->getKey(),key) == 0)

   382                     return n->getData();        // item found

   383             }

   384         } else {

   385             for (n=(Q3AsciiBucket*)vec[index]; n;

   386                   n=(Q3AsciiBucket*)n->getNext()) {

   387                 if (qstricmp(n->getKey(),key) == 0)

   388                     return n->getData();        // item found

   389             }

   390         }

   391         return 0;                               // not found

   392     }

   393     if (op == op_replace) {                     // replace

   394         if (vec[index] != 0)                    // maybe something there

   395             remove_ascii(key);

   396     }

   397     // op_insert or op_replace

   398     n = new Q3AsciiBucket(copyk ? qstrdup(key) : key,newItem(d),vec[index]);

   399     Q_CHECK_PTR(n);

   400 #if defined(QT_CHECK_NULL)

   401     if (n->getData() == 0)

   402         qWarning("QAsciiDict: Cannot insert null item");

   403 #endif

   404     vec[index] = n;

   405     numItems++;

   406     return n->getData();

   407 }

   408 

   409 Q3PtrCollection::Item Q3GDict::look_int(long key, Q3PtrCollection::Item d, int op)

   410 {

   411     Q3IntBucket *n;

   412     int index = (int)((ulong)key % vlen);       // simple hash

   413     if (op == op_find) {                        // find

   414         for (n=(Q3IntBucket*)vec[index]; n;

   415               n=(Q3IntBucket*)n->getNext()) {

   416             if (n->getKey() == key)

   417                 return n->getData();            // item found

   418         }

   419         return 0;                               // not found

   420     }

   421     if (op == op_replace) {                     // replace

   422         if (vec[index] != 0)                    // maybe something there

   423             remove_int(key);

   424     }

   425     // op_insert or op_replace

   426     n = new Q3IntBucket(key,newItem(d),vec[index]);

   427     Q_CHECK_PTR(n);

   428 #if defined(QT_CHECK_NULL)

   429     if (n->getData() == 0)

   430         qWarning("QIntDict: Cannot insert null item");

   431 #endif

   432     vec[index] = n;

   433     numItems++;

   434     return n->getData();

   435 }

   436 

   437 Q3PtrCollection::Item Q3GDict::look_ptr(void *key, Q3PtrCollection::Item d, int op)

   438 {

   439     Q3PtrBucket *n;

   440     int index = (int)((ulong)key % vlen);       // simple hash

   441     if (op == op_find) {                        // find

   442         for (n=(Q3PtrBucket*)vec[index]; n;

   443               n=(Q3PtrBucket*)n->getNext()) {

   444             if (n->getKey() == key)

   445                 return n->getData();            // item found

   446         }

   447         return 0;                               // not found

   448     }

   449     if (op == op_replace) {                     // replace

   450         if (vec[index] != 0)                    // maybe something there

   451             remove_ptr(key);

   452     }

   453     // op_insert or op_replace

   454     n = new Q3PtrBucket(key,newItem(d),vec[index]);

   455     Q_CHECK_PTR(n);

   456 #if defined(QT_CHECK_NULL)

   457     if (n->getData() == 0)

   458         qWarning("Q3PtrDict: Cannot insert null item");

   459 #endif

   460     vec[index] = n;

   461     numItems++;

   462     return n->getData();

   463 }

   464 

   465 

   466 /*!

   467   Changes the size of the hashtable to \a newsize.

   468   The contents of the dictionary are preserved,

   469   but all iterators on the dictionary become invalid.

   470 */

   471 void Q3GDict::resize(uint newsize)

   472 {

   473     // Save old information

   474     Q3BaseBucket **old_vec = vec;

   475     uint old_vlen  = vlen;

   476     bool old_copyk = copyk;

   477 

   478     vec = new Q3BaseBucket *[vlen = newsize];

   479     Q_CHECK_PTR(vec);

   480     memset((char*)vec, 0, vlen*sizeof(Q3BaseBucket*));

   481     numItems = 0;

   482     copyk = false;

   483 

   484     // Reinsert every item from vec, deleting vec as we go

   485     for (uint index = 0; index < old_vlen; index++) {

   486         switch (keytype) {

   487             case StringKey:

   488                 {

   489                     Q3StringBucket *n=(Q3StringBucket *)old_vec[index];

   490                     while (n) {

   491                         look_string(n->getKey(), n->getData(), op_insert);

   492                         Q3StringBucket *t=(Q3StringBucket *)n->getNext();

   493                         delete n;

   494                         n = t;

   495                     }

   496                 }

   497                 break;

   498             case AsciiKey:

   499                 {

   500                     Q3AsciiBucket *n=(Q3AsciiBucket *)old_vec[index];

   501                     while (n) {

   502                         look_ascii(n->getKey(), n->getData(), op_insert);

   503                         Q3AsciiBucket *t=(Q3AsciiBucket *)n->getNext();

   504                         delete n;

   505                         n = t;

   506                     }

   507                 }

   508                 break;

   509             case IntKey:

   510                 {

   511                     Q3IntBucket *n=(Q3IntBucket *)old_vec[index];

   512                     while (n) {

   513                         look_int(n->getKey(), n->getData(), op_insert);

   514                         Q3IntBucket *t=(Q3IntBucket *)n->getNext();

   515                         delete n;

   516                         n = t;

   517                     }

   518                 }

   519                 break;

   520             case PtrKey:

   521                 {

   522                     Q3PtrBucket *n=(Q3PtrBucket *)old_vec[index];

   523                     while (n) {

   524                         look_ptr(n->getKey(), n->getData(), op_insert);

   525                         Q3PtrBucket *t=(Q3PtrBucket *)n->getNext();

   526                         delete n;

   527                         n = t;

   528                     }

   529                 }

   530                 break;

   531         }

   532     }

   533     delete [] old_vec;

   534 

   535     // Restore state

   536     copyk = old_copyk;

   537 

   538     // Invalidate all iterators, since order is lost

   539     if (iterators && iterators->count()) {

   540         Q3GDictIterator *i = iterators->first();

   541         while (i) {

   542             i->toFirst();

   543             i = iterators->next();

   544         }

   545     }

   546 }

   547 

   548 /*!

   549   Unlinks the bucket with the specified key (and specified data pointer,

   550   if it is set).

   551 */

   552 

   553 void Q3GDict::unlink_common(int index, Q3BaseBucket *node, Q3BaseBucket *prev)

   554 {

   555     if (iterators && iterators->count()) {      // update iterators

   556         Q3GDictIterator *i = iterators->first();

   557         while (i) {                             // invalidate all iterators

   558             if (i->curNode == node)             // referring to pending node

   559                 i->operator++();

   560             i = iterators->next();

   561         }

   562     }

   563     if (prev)                                   // unlink node

   564         prev->setNext(node->getNext());

   565     else

   566         vec[index] = node->getNext();

   567     numItems--;

   568 }

   569 

   570 Q3StringBucket *Q3GDict::unlink_string(const QString &key, Q3PtrCollection::Item d)

   571 {

   572     if (numItems == 0)                  // nothing in dictionary

   573         return 0;

   574     Q3StringBucket *n;

   575     Q3StringBucket *prev = 0;

   576     int index = hashKeyString(key) % vlen;

   577     if (cases) {

   578         for (n=(Q3StringBucket*)vec[index]; n;

   579               n=(Q3StringBucket*)n->getNext()) {

   580             bool found = (key == n->getKey());

   581             if (found && d)

   582                 found = (n->getData() == d);

   583             if (found) {

   584                 unlink_common(index,n,prev);

   585                 return n;

   586             }

   587             prev = n;

   588         }

   589     } else {

   590         QString k = key.lower();

   591         for (n=(Q3StringBucket*)vec[index]; n;

   592               n=(Q3StringBucket*)n->getNext()) {

   593             bool found = (k == n->getKey().lower());

   594             if (found && d)

   595                 found = (n->getData() == d);

   596             if (found) {

   597                 unlink_common(index,n,prev);

   598                 return n;

   599             }

   600             prev = n;

   601         }

   602     }

   603     return 0;

   604 }

   605 

   606 Q3AsciiBucket *Q3GDict::unlink_ascii(const char *key, Q3PtrCollection::Item d)

   607 {

   608     if (numItems == 0)                  // nothing in dictionary

   609         return 0;

   610     Q3AsciiBucket *n;

   611     Q3AsciiBucket *prev = 0;

   612     int index = hashKeyAscii(key) % vlen;

   613     for (n=(Q3AsciiBucket *)vec[index]; n; n=(Q3AsciiBucket *)n->getNext()) {

   614         bool found = (cases ? qstrcmp(n->getKey(),key)

   615                        : qstricmp(n->getKey(),key)) == 0;

   616         if (found && d)

   617             found = (n->getData() == d);

   618         if (found) {

   619             unlink_common(index,n,prev);

   620             return n;

   621         }

   622         prev = n;

   623     }

   624     return 0;

   625 }

   626 

   627 Q3IntBucket *Q3GDict::unlink_int(long key, Q3PtrCollection::Item d)

   628 {

   629     if (numItems == 0)                  // nothing in dictionary

   630         return 0;

   631     Q3IntBucket *n;

   632     Q3IntBucket *prev = 0;

   633     int index = (int)((ulong)key % vlen);

   634     for (n=(Q3IntBucket *)vec[index]; n; n=(Q3IntBucket *)n->getNext()) {

   635         bool found = (n->getKey() == key);

   636         if (found && d)

   637             found = (n->getData() == d);

   638         if (found) {

   639             unlink_common(index,n,prev);

   640             return n;

   641         }

   642         prev = n;

   643     }

   644     return 0;

   645 }

   646 

   647 Q3PtrBucket *Q3GDict::unlink_ptr(void *key, Q3PtrCollection::Item d)

   648 {

   649     if (numItems == 0)                  // nothing in dictionary

   650         return 0;

   651     Q3PtrBucket *n;

   652     Q3PtrBucket *prev = 0;

   653     int index = (int)((ulong)key % vlen);

   654     for (n=(Q3PtrBucket *)vec[index]; n; n=(Q3PtrBucket *)n->getNext()) {

   655         bool found = (n->getKey() == key);

   656         if (found && d)

   657             found = (n->getData() == d);

   658         if (found) {

   659             unlink_common(index,n,prev);

   660             return n;

   661         }

   662         prev = n;

   663     }

   664     return 0;

   665 }

   666 

   667 

   668 /*!

   669   Removes the item with the specified \a key.  If \a item is not null,

   670   the remove will match the \a item as well (used to remove an

   671   item when several items have the same key).

   672 */

   673 

   674 bool Q3GDict::remove_string(const QString &key, Q3PtrCollection::Item item)

   675 {

   676     Q3StringBucket *n = unlink_string(key, item);

   677     if (n) {

   678         deleteItem(n->getData());

   679         delete n;

   680         return true;

   681     } else {

   682         return false;

   683     }

   684 }

   685 

   686 bool Q3GDict::remove_ascii(const char *key, Q3PtrCollection::Item item)

   687 {

   688     Q3AsciiBucket *n = unlink_ascii(key, item);

   689     if (n) {

   690         if (copyk)

   691             delete [] (char *)n->getKey();

   692         deleteItem(n->getData());

   693         delete n;

   694     }

   695     return n != 0;

   696 }

   697 

   698 bool Q3GDict::remove_int(long key, Q3PtrCollection::Item item)

   699 {

   700     Q3IntBucket *n = unlink_int(key, item);

   701     if (n) {

   702         deleteItem(n->getData());

   703         delete n;

   704     }

   705     return n != 0;

   706 }

   707 

   708 bool Q3GDict::remove_ptr(void *key, Q3PtrCollection::Item item)

   709 {

   710     Q3PtrBucket *n = unlink_ptr(key, item);

   711     if (n) {

   712         deleteItem(n->getData());

   713         delete n;

   714     }

   715     return n != 0;

   716 }

   717 

   718 Q3PtrCollection::Item Q3GDict::take_string(const QString &key)

   719 {

   720     Q3StringBucket *n = unlink_string(key);

   721     Item d;

   722     if (n) {

   723         d = n->getData();

   724         delete n;

   725     } else {

   726         d = 0;

   727     }

   728     return d;

   729 }

   730 

   731 Q3PtrCollection::Item Q3GDict::take_ascii(const char *key)

   732 {

   733     Q3AsciiBucket *n = unlink_ascii(key);

   734     Item d;

   735     if (n) {

   736         if (copyk)

   737             delete [] (char *)n->getKey();

   738         d = n->getData();

   739         delete n;

   740     } else {

   741         d = 0;

   742     }

   743     return d;

   744 }

   745 

   746 Q3PtrCollection::Item Q3GDict::take_int(long key)

   747 {

   748     Q3IntBucket *n = unlink_int(key);

   749     Item d;

   750     if (n) {

   751         d = n->getData();

   752         delete n;

   753     } else {

   754         d = 0;

   755     }

   756     return d;

   757 }

   758 

   759 Q3PtrCollection::Item Q3GDict::take_ptr(void *key)

   760 {

   761     Q3PtrBucket *n = unlink_ptr(key);

   762     Item d;

   763     if (n) {

   764         d = n->getData();

   765         delete n;

   766     } else {

   767         d = 0;

   768     }

   769     return d;

   770 }

   771 

   772 /*!

   773   Removes all items from the dictionary.

   774 */

   775 void Q3GDict::clear()

   776 {

   777     if (!numItems)

   778         return;

   779     numItems = 0;                               // disable remove() function

   780     for (uint j=0; j<vlen; j++) {               // destroy hash table

   781         if (vec[j]) {

   782             switch (keytype) {

   783                 case StringKey:

   784                     {

   785                         Q3StringBucket *n=(Q3StringBucket *)vec[j];

   786                         while (n) {

   787                             Q3StringBucket *next = (Q3StringBucket*)n->getNext();

   788                             deleteItem(n->getData());

   789                             delete n;

   790                             n = next;

   791                         }

   792                     }

   793                     break;

   794                 case AsciiKey:

   795                     {

   796                         Q3AsciiBucket *n=(Q3AsciiBucket *)vec[j];

   797                         while (n) {

   798                             Q3AsciiBucket *next = (Q3AsciiBucket*)n->getNext();

   799                             if (copyk)

   800                                 delete [] (char *)n->getKey();

   801                             deleteItem(n->getData());

   802                             delete n;

   803                             n = next;

   804                         }

   805                     }

   806                     break;

   807                 case IntKey:

   808                     {

   809                         Q3IntBucket *n=(Q3IntBucket *)vec[j];

   810                         while (n) {

   811                             Q3IntBucket *next = (Q3IntBucket*)n->getNext();

   812                             deleteItem(n->getData());

   813                             delete n;

   814                             n = next;

   815                         }

   816                     }

   817                     break;

   818                 case PtrKey:

   819                     {

   820                         Q3PtrBucket *n=(Q3PtrBucket *)vec[j];

   821                         while (n) {

   822                             Q3PtrBucket *next = (Q3PtrBucket*)n->getNext();

   823                             deleteItem(n->getData());

   824                             delete n;

   825                             n = next;

   826                         }

   827                     }

   828                     break;

   829             }

   830             vec[j] = 0;                         // detach list of buckets

   831         }

   832     }

   833     if (iterators && iterators->count()) {      // invalidate all iterators

   834         Q3GDictIterator *i = iterators->first();

   835         while (i) {

   836             i->curNode = 0;

   837             i = iterators->next();

   838         }

   839     }

   840 }

   841 

   842 /*!

   843   Outputs debug statistics.

   844 */

   845 void Q3GDict::statistics() const

   846 {

   847 #if defined(QT_DEBUG)

   848     QString line;

   849     line.fill(QLatin1Char('-'), 60);

   850     double real, ideal;

   851     qDebug("%s", line.ascii());

   852     qDebug("DICTIONARY STATISTICS:");

   853     if (count() == 0) {

   854         qDebug("Empty!");

   855         qDebug("%s", line.ascii());

   856         return;

   857     }

   858     real = 0.0;

   859     ideal = (float)count()/(2.0*size())*(count()+2.0*size()-1);

   860     uint i = 0;

   861     while (i<size()) {

   862         Q3BaseBucket *n = vec[i];

   863         int b = 0;

   864         while (n) {                             // count number of buckets

   865             b++;

   866             n = n->getNext();

   867         }

   868         real = real + (double)b * ((double)b+1.0)/2.0;

   869         char buf[80], *pbuf;

   870         if (b > 78)

   871             b = 78;

   872         pbuf = buf;

   873         while (b--)

   874             *pbuf++ = '*';

   875         *pbuf = '\0';

   876         qDebug("%s", buf);

   877         i++;

   878     }

   879     qDebug("Array size = %d", size());

   880     qDebug("# items    = %d", count());

   881     qDebug("Real dist  = %g", real);

   882     qDebug("Rand dist  = %g", ideal);

   883     qDebug("Real/Rand  = %g", real/ideal);

   884     qDebug("%s", line.ascii());

   885 #endif // QT_DEBUG

   886 }

   887 

   888 

   889 /*****************************************************************************

   890   Q3GDict stream functions

   891  *****************************************************************************/

   892 #ifndef QT_NO_DATASTREAM

   893 QDataStream &operator>>(QDataStream &s, Q3GDict &dict)

   894 {

   895     return dict.read(s);

   896 }

   897 

   898 QDataStream &operator<<(QDataStream &s, const Q3GDict &dict)

   899 {

   900     return dict.write(s);

   901 }

   902 

   903 #if defined(Q_CC_DEC) && defined(__alpha) && (__DECCXX_VER-0 >= 50190001)

   904 #pragma message disable narrowptr

   905 #endif

   906 

   907 /*!

   908   Reads a dictionary from the stream \a s.

   909 */

   910 

   911 QDataStream &Q3GDict::read(QDataStream &s)

   912 {

   913     uint num;

   914     s >> num;                                   // read number of items

   915     clear();                                    // clear dict

   916     while (num--) {                             // read all items

   917         Item d;

   918         switch (keytype) {

   919             case StringKey:

   920                 {

   921                     QString k;

   922                     s >> k;

   923                     read(s, d);

   924                     look_string(k, d, op_insert);

   925                 }

   926                 break;

   927             case AsciiKey:

   928                 {

   929                     char *k;

   930                     s >> k;

   931                     read(s, d);

   932                     look_ascii(k, d, op_insert);

   933                     if (copyk)

   934                         delete [] k;

   935                 }

   936                 break;

   937             case IntKey:

   938                 {

   939                     Q_UINT32 k;

   940                     s >> k;

   941                     read(s, d);

   942                     look_int(k, d, op_insert);

   943                 }

   944                 break;

   945             case PtrKey:

   946                 {

   947                     Q_UINT32 k;

   948                     s >> k;

   949                     read(s, d);

   950                     // ### cannot insert 0 - this renders the thing

   951                     // useless since all pointers are written as 0,

   952                     // but hey, serializing pointers?  can it be done

   953                     // at all, ever?

   954                     if (k)

   955                         look_ptr((void *)(ulong)k, d, op_insert);

   956                 }

   957                 break;

   958         }

   959     }

   960     return s;

   961 }

   962 

   963 /*!

   964   Writes the dictionary to the stream \a s.

   965 */

   966 

   967 QDataStream& Q3GDict::write(QDataStream &s) const

   968 {

   969     s << count();                               // write number of items

   970     uint i = 0;

   971     while (i<size()) {

   972         Q3BaseBucket *n = vec[i];

   973         while (n) {                             // write all buckets

   974             switch (keytype) {

   975                 case StringKey:

   976                     s << ((Q3StringBucket*)n)->getKey();

   977                     break;

   978                 case AsciiKey:

   979                     s << ((Q3AsciiBucket*)n)->getKey();

   980                     break;

   981                 case IntKey:

   982                     s << (Q_UINT32)((Q3IntBucket*)n)->getKey();

   983                     break;

   984                 case PtrKey:

   985                     s << (Q_UINT32)0; // ### cannot serialize a pointer

   986                     break;

   987             }

   988             write(s, n->getData());             // write data

   989             n = n->getNext();

   990         }

   991         i++;

   992     }

   993     return s;

   994 }

   995 #endif //QT_NO_DATASTREAM

   996 

   997 /*****************************************************************************

   998   Q3GDictIterator member functions

   999  *****************************************************************************/

  1000 

  1001 /*!

  1002   \class Q3GDictIterator

  1003   \reentrant

  1004   \brief The Q3GDictIterator class is an internal class for implementing QDictIterator and QIntDictIterator.

  1005 

  1006   \internal

  1007 

  1008   Q3GDictIterator is a strictly internal class that does the heavy work for

  1009   QDictIterator and QIntDictIterator.

  1010 */

  1011 

  1012 /*!

  1013   Constructs an iterator that operates on the dictionary \a d.

  1014 */

  1015 

  1016 Q3GDictIterator::Q3GDictIterator(const Q3GDict &d)

  1017 {

  1018     dict = (Q3GDict *)&d;                       // get reference to dict

  1019     toFirst();                                  // set to first noe

  1020     if (!dict->iterators) {

  1021         dict->iterators = new Q3GDItList;       // create iterator list

  1022         Q_CHECK_PTR(dict->iterators);

  1023     }

  1024     dict->iterators->append(this);              // attach iterator to dict

  1025 }

  1026 

  1027 /*!

  1028   Constructs a copy of the iterator \a it.

  1029 */

  1030 

  1031 Q3GDictIterator::Q3GDictIterator(const Q3GDictIterator &it)

  1032 {

  1033     dict = it.dict;

  1034     curNode = it.curNode;

  1035     curIndex = it.curIndex;

  1036     if (dict)

  1037         dict->iterators->append(this);  // attach iterator to dict

  1038 }

  1039 

  1040 /*!

  1041   Assigns a copy of the iterator \a it and returns a reference to this

  1042   iterator.

  1043 */

  1044 

  1045 Q3GDictIterator &Q3GDictIterator::operator=(const Q3GDictIterator &it)

  1046 {

  1047     if (dict)                                   // detach from old dict

  1048         dict->iterators->removeRef(this);

  1049     dict = it.dict;

  1050     curNode = it.curNode;

  1051     curIndex = it.curIndex;

  1052     if (dict)

  1053         dict->iterators->append(this);  // attach to new list

  1054     return *this;

  1055 }

  1056 

  1057 /*!

  1058   Destroys the iterator.

  1059 */

  1060 

  1061 Q3GDictIterator::~Q3GDictIterator()

  1062 {

  1063     if (dict)                                   // detach iterator from dict

  1064         dict->iterators->removeRef(this);

  1065 }

  1066 

  1067 

  1068 /*!

  1069   Sets the iterator to point to the first item in the dictionary.

  1070 */

  1071 

  1072 Q3PtrCollection::Item Q3GDictIterator::toFirst()

  1073 {

  1074     if (!dict) {

  1075 #if defined(QT_CHECK_NULL)

  1076         qWarning("Q3GDictIterator::toFirst: Dictionary has been deleted");

  1077 #endif

  1078         return 0;

  1079     }

  1080     if (dict->count() == 0) {                   // empty dictionary

  1081         curNode = 0;

  1082         return 0;

  1083     }

  1084     register uint i = 0;

  1085     register Q3BaseBucket **v = dict->vec;

  1086     while (!(*v++))

  1087         i++;

  1088     curNode = dict->vec[i];

  1089     curIndex = i;

  1090     return curNode->getData();

  1091 }

  1092 

  1093 

  1094 /*!

  1095   Moves to the next item (postfix).

  1096 */

  1097 

  1098 Q3PtrCollection::Item Q3GDictIterator::operator()()

  1099 {

  1100     if (!dict) {

  1101 #if defined(QT_CHECK_NULL)

  1102         qWarning("Q3GDictIterator::operator(): Dictionary has been deleted");

  1103 #endif

  1104         return 0;

  1105     }

  1106     if (!curNode)

  1107         return 0;

  1108     Q3PtrCollection::Item d = curNode->getData();

  1109     this->operator++();

  1110     return d;

  1111 }

  1112 

  1113 /*!

  1114   Moves to the next item (prefix).

  1115 */

  1116 

  1117 Q3PtrCollection::Item Q3GDictIterator::operator++()

  1118 {

  1119     if (!dict) {

  1120 #if defined(QT_CHECK_NULL)

  1121         qWarning("Q3GDictIterator::operator++: Dictionary has been deleted");

  1122 #endif

  1123         return 0;

  1124     }

  1125     if (!curNode)

  1126         return 0;

  1127     curNode = curNode->getNext();

  1128     if (!curNode) {                             // no next bucket

  1129         register uint i = curIndex + 1;         // look from next vec element

  1130         register Q3BaseBucket **v = &dict->vec[i];

  1131         while (i < dict->size() && !(*v++))

  1132             i++;

  1133         if (i == dict->size()) {                // nothing found

  1134             curNode = 0;