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 test suite 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 <QtTest/QtTest>

    43 

    44 #include <qhash.h>

    45 #include <qmap.h>

    46 

    47 //TESTED_CLASS=

    48 //TESTED_FILES=

    49 

    50 class tst_QHash : public QObject

    51 {

    52     Q_OBJECT

    53 

    54 public:

    55     tst_QHash();

    56     virtual ~tst_QHash() {}

    57 

    58 private slots:

    59     void insert1();

    60     void erase();

    61     void key();

    62 

    63     void count(); // copied from tst_QMap

    64     void clear(); // copied from tst_QMap

    65     void empty(); // copied from tst_QMap

    66     void find(); // copied from tst_QMap

    67     void constFind(); // copied from tst_QMap

    68     void contains(); // copied from tst_QMap

    69     void take(); // copied from tst_QMap

    70     void operator_eq(); // copied from tst_QMap

    71     void rehash_isnt_quadratic();

    72     void dont_need_default_constructor();

    73     void qhash();

    74     void qmultihash_specific();

    75 

    76     void compare();

    77     void compare2();

    78     void iterators(); // sligthly modified from tst_QMap

    79     void keys_values_uniqueKeys(); // slightly modified from tst_QMap

    80     void noNeedlessRehashes();

    81 };

    82 

    83 struct Foo {

    84     static int count;

    85     Foo():c(count) { ++count; }

    86     Foo(const Foo& o):c(o.c) { ++count; }

    87     ~Foo() { --count; }

    88     int c;

    89     int data[8];

    90 };

    91 

    92 tst_QHash::tst_QHash()

    93 {}

    94 

    95 int Foo::count = 0;

    96 

    97 //copied from tst_QMap.cpp

    98 class MyClass

    99 {

   100 public:

   101     MyClass() { ++count;

   102 //     qDebug("creating MyClass count=%d", count);

   103     }

   104     MyClass( const QString& c) {

   105 	count++; str = c;

   106 // 	qDebug("creating MyClass '%s' count = %d", str.latin1(), count);

   107     }

   108     ~MyClass() {

   109 	count--;

   110 // 	qDebug("deleting MyClass '%s' count = %d", str.latin1(), count);

   111     }

   112     MyClass( const MyClass& c ) {

   113 	count++; str = c.str;

   114 // 	qDebug("creating MyClass '%s' count = %d", str.latin1(), count);

   115     }

   116     MyClass &operator =(const MyClass &o) {

   117 // 	qDebug("copying MyClass '%s'", o.str.latin1());

   118 	str = o.str; return *this;

   119     }

   120 

   121     QString str;

   122     static int count;

   123 };

   124 

   125 int MyClass::count = 0;

   126 

   127 typedef QHash<QString, MyClass> MyMap;

   128 

   129 //void tst_QMap::count()

   130 void tst_QHash::count()

   131 {

   132     {

   133 	MyMap map;

   134 	MyMap map2( map );

   135 	QCOMPARE( map.count(), 0 );

   136 	QCOMPARE( map2.count(), 0 );

   137 	QCOMPARE( MyClass::count, 0 );

   138 	// detach

   139 	map2["Hallo"] = MyClass( "Fritz" );

   140 	QCOMPARE( map.count(), 0 );

   141         QCOMPARE( map2.count(), 1 );

   142 #ifndef Q_CC_SUN

   143 	QCOMPARE( MyClass::count, 1 );

   144 #endif

   145     }

   146     QCOMPARE( MyClass::count, 0 );

   147 

   148     {

   149 	typedef QHash<QString, MyClass> Map;

   150 	Map map;

   151 	QCOMPARE( map.count(), 0);

   152 	map.insert( "Torben", MyClass("Weis") );

   153 	QCOMPARE( map.count(), 1 );

   154 	map.insert( "Claudia", MyClass("Sorg") );

   155 	QCOMPARE( map.count(), 2 );

   156 	map.insert( "Lars", MyClass("Linzbach") );

   157 	map.insert( "Matthias", MyClass("Ettrich") );

   158 	map.insert( "Sue", MyClass("Paludo") );

   159 	map.insert( "Eirik", MyClass("Eng") );

   160 	map.insert( "Haavard", MyClass("Nord") );

   161 	map.insert( "Arnt", MyClass("Gulbrandsen") );

   162 	map.insert( "Paul", MyClass("Tvete") );

   163 	QCOMPARE( map.count(), 9 );

   164 	map.insert( "Paul", MyClass("Tvete 1") );

   165 	map.insert( "Paul", MyClass("Tvete 2") );

   166 	map.insert( "Paul", MyClass("Tvete 3") );

   167 	map.insert( "Paul", MyClass("Tvete 4") );

   168 	map.insert( "Paul", MyClass("Tvete 5") );

   169 	map.insert( "Paul", MyClass("Tvete 6") );

   170 

   171 	QCOMPARE( map.count(), 9 );

   172 #ifndef Q_CC_SUN

   173 	QCOMPARE( MyClass::count, 9 );

   174 #endif

   175 

   176 	Map map2( map );

   177 	QVERIFY( map2.count() == 9 );

   178 #ifndef Q_CC_SUN

   179 	QCOMPARE( MyClass::count, 9 );

   180 #endif

   181 

   182 	map2.insert( "Kay", MyClass("Roemer") );

   183 	QVERIFY( map2.count() == 10 );

   184 	QVERIFY( map.count() == 9 );

   185 #ifndef Q_CC_SUN

   186 	QCOMPARE( MyClass::count, 19 );

   187 #endif

   188 

   189 	map2 = map;

   190 	QVERIFY( map.count() == 9 );

   191 	QVERIFY( map2.count() == 9 );

   192 #ifndef Q_CC_SUN

   193 	QCOMPARE( MyClass::count, 9 );

   194 #endif

   195 

   196 	map2.insert( "Kay", MyClass("Roemer") );

   197 	QVERIFY( map2.count() == 10 );

   198 #ifndef Q_CC_SUN

   199 	QCOMPARE( MyClass::count, 19 );

   200 #endif

   201 

   202 	map2.clear();

   203 	QVERIFY( map.count() == 9 );

   204 	QVERIFY( map2.count() == 0 );

   205 #ifndef Q_CC_SUN

   206 	QCOMPARE( MyClass::count, 9 );

   207 #endif

   208 

   209 	map2 = map;

   210 	QVERIFY( map.count() == 9 );

   211 	QVERIFY( map2.count() == 9 );

   212 #ifndef Q_CC_SUN

   213 	QCOMPARE( MyClass::count, 9 );

   214 #endif

   215 

   216 	map2.clear();

   217 	QVERIFY( map.count() == 9 );

   218 	QVERIFY( map2.count() == 0 );

   219 #ifndef Q_CC_SUN

   220 	QCOMPARE( MyClass::count, 9 );

   221 #endif

   222 

   223 	map.remove( "Lars" );

   224 	QVERIFY( map.count() == 8 );

   225 	QVERIFY( map2.count() == 0 );

   226 #ifndef Q_CC_SUN

   227 	QCOMPARE( MyClass::count, 8 );

   228 #endif

   229 

   230 	map.remove( "Mist" );

   231 	QVERIFY( map.count() == 8 );

   232 	QVERIFY( map2.count() == 0 );

   233 #ifndef Q_CC_SUN

   234 	QCOMPARE( MyClass::count, 8 );

   235 #endif

   236     }

   237     QVERIFY( MyClass::count == 0 );

   238 

   239     {

   240 	typedef QHash<QString,MyClass> Map;

   241 	Map map;

   242 	map["Torben"] = MyClass("Weis");

   243 #ifndef Q_CC_SUN

   244 	QVERIFY( MyClass::count == 1 );

   245 #endif

   246 	QVERIFY( map.count() == 1 );

   247 

   248 	(void)map["Torben"].str;

   249 	(void)map["Lars"].str;

   250 #ifndef Q_CC_SUN

   251 	QVERIFY( MyClass::count == 2 );

   252 #endif

   253 	QVERIFY( map.count() == 2 );

   254 

   255 	const Map& cmap = map;

   256 	(void)cmap["Depp"].str;

   257 #ifndef Q_CC_SUN

   258 	QVERIFY( MyClass::count == 2 );

   259 #endif

   260 	QVERIFY( map.count() == 2 );

   261 	QVERIFY( cmap.count() == 2 );

   262     }

   263     QCOMPARE( MyClass::count, 0 );

   264     {

   265 	for ( int i = 0; i < 100; ++i )

   266 	{

   267 	    QHash<int, MyClass> map;

   268 	    for (int j = 0; j < i; ++j)

   269 		map.insert(j, MyClass(QString::number(j)));

   270 	}

   271 	QCOMPARE( MyClass::count, 0 );

   272     }

   273     QCOMPARE( MyClass::count, 0 );

   274 }

   275 void tst_QHash::insert1()

   276 {

   277     const char *hello = "hello";

   278     const char *world = "world";

   279     const char *allo = "allo";

   280     const char *monde = "monde";

   281 

   282     {

   283         typedef QHash<QString, QString> Hash;

   284         Hash hash;

   285         QString key;

   286         for (int i = 0; i < 10; ++i) {

   287             key[0] = i + '0';

   288             for (int j = 0; j < 10; ++j) {

   289                 key[1] = j + '0';

   290                 hash.insert(key, "V" + key);

   291             }

   292         }

   293 

   294         for (int i = 0; i < 10; ++i) {

   295             key[0] = i + '0';

   296             for (int j = 0; j < 10; ++j) {

   297                 key[1] = j + '0';

   298                 hash.remove(key);

   299             }

   300         }

   301     }

   302 

   303     {

   304         typedef QHash<int, const char *> Hash;

   305         Hash hash;

   306         hash.insert(1, hello);

   307         hash.insert(2, world);

   308 

   309         QVERIFY(hash.size() == 2);

   310         QVERIFY(!hash.isEmpty());

   311 

   312         {

   313             Hash hash2 = hash;

   314             hash2 = hash;

   315             hash = hash2;

   316             hash2 = hash2;

   317             hash = hash;

   318             hash2.clear();

   319             hash2 = hash2;

   320             QVERIFY(hash2.size() == 0);

   321             QVERIFY(hash2.isEmpty());

   322         }

   323         QVERIFY(hash.size() == 2);

   324 

   325         {

   326             Hash hash2 = hash;

   327             hash2[1] = allo;

   328             hash2[2] = monde;

   329 

   330             QVERIFY(hash2[1] == allo);

   331             QVERIFY(hash2[2] == monde);

   332             QVERIFY(hash[1] == hello);

   333             QVERIFY(hash[2] == world);

   334 

   335             hash2[1] = hash[1];

   336             hash2[2] = hash[2];

   337 

   338             QVERIFY(hash2[1] == hello);

   339             QVERIFY(hash2[2] == world);

   340 

   341             hash[1] = hash[1];

   342 	    QVERIFY(hash[1] == hello);

   343 	}

   344 	        {

   345             Hash hash2 = hash;

   346             hash2.detach();

   347             hash2.remove(1);

   348             QVERIFY(hash2.size() == 1);

   349             hash2.remove(1);

   350             QVERIFY(hash2.size() == 1);

   351             hash2.remove(0);

   352             QVERIFY(hash2.size() == 1);

   353             hash2.remove(2);

   354             QVERIFY(hash2.size() == 0);

   355             QVERIFY(hash.size() == 2);

   356         }

   357 

   358         hash.detach();

   359 

   360         {

   361             Hash::iterator it1 = hash.find(1);

   362             QVERIFY(it1 != hash.end());

   363 

   364             Hash::iterator it2 = hash.find(0);

   365             QVERIFY(it2 != hash.begin());

   366             QVERIFY(it2 == hash.end());

   367 

   368             *it1 = monde;

   369             QVERIFY(*it1 == monde);

   370             QVERIFY(hash[1] == monde);

   371 

   372             *it1 = hello;

   373             QVERIFY(*it1 == hello);

   374             QVERIFY(hash[1] == hello);

   375 

   376             hash[1] = monde;

   377             QVERIFY(it1.key() == 1);

   378             QVERIFY(it1.value() == monde);

   379             QVERIFY(*it1 == monde);

   380             QVERIFY(hash[1] == monde);

   381 

   382             hash[1] = hello;

   383             QVERIFY(*it1 == hello);

   384             QVERIFY(hash[1] == hello);

   385         }

   386 

   387         {

   388             const Hash hash2 = hash;

   389 

   390             Hash::const_iterator it1 = hash2.find(1);

   391             QVERIFY(it1 != hash2.end());

   392             QVERIFY(it1.key() == 1);

   393             QVERIFY(it1.value() == hello);

   394             QVERIFY(*it1 == hello);

   395 

   396             Hash::const_iterator it2 = hash2.find(2);

   397             QVERIFY(it1 != it2);

   398             QVERIFY(it1 != hash2.end());

   399             QVERIFY(it2 != hash2.end());

   400 

   401             int count = 0;

   402             it1 = hash2.begin();

   403             while (it1 != hash2.end()) {

   404                 count++;

   405                 ++it1;

   406             }

   407             QVERIFY(count == 2);

   408 

   409             count = 0;

   410             it1 = hash.begin();

   411             while (it1 != hash.end()) {

   412                 count++;

   413                 ++it1;

   414             }

   415             QVERIFY(count == 2);

   416         }

   417 

   418         {

   419             QVERIFY(hash.contains(1));

   420             QVERIFY(hash.contains(2));

   421             QVERIFY(!hash.contains(0));

   422             QVERIFY(!hash.contains(3));

   423         }

   424 

   425         {

   426             QVERIFY(hash.value(1) == hello);

   427             QVERIFY(hash.value(2) == world);

   428             QVERIFY(hash.value(3) == 0);

   429             QVERIFY(hash.value(1, allo) == hello);

   430             QVERIFY(hash.value(2, allo) == world);

   431             QVERIFY(hash.value(3, allo) == allo);

   432             QVERIFY(hash.value(0, monde) == monde);

   433         }

   434 

   435         {

   436             QHash<int,Foo> hash;

   437             for (int i = 0; i < 10; i++)

   438                 hash.insert(i, Foo());

   439             QVERIFY(Foo::count == 10);

   440             hash.remove(7);

   441             QVERIFY(Foo::count == 9);

   442 

   443         }

   444         QVERIFY(Foo::count == 0);

   445         {

   446             QHash<int, int*> hash;

   447             QVERIFY(((const QHash<int,int*>*) &hash)->operator[](7) == 0);

   448         }

   449     }

   450 }

   451 

   452 void tst_QHash::erase()

   453 {

   454     QHash<int, int> h1;

   455     h1.insert(1, 2);

   456     h1.erase(h1.begin());

   457     QVERIFY(h1.size() == 0);

   458     QVERIFY(h1.begin() == h1.end());

   459     h1.insert(3, 4);

   460     QVERIFY(*h1.begin() == 4);

   461     h1.insert(5, 6);

   462     QVERIFY(h1.size() == 2);

   463     QHash<int, int>::iterator it1 = h1.begin();

   464     ++it1;

   465     it1 = h1.erase(it1);

   466     QVERIFY(it1 == h1.end());

   467     h1.insert(7, 8);

   468     h1.insert(9, 10);

   469     it1 = h1.begin();

   470     int n = 0;

   471     while (it1 != h1.end()) {

   472 	it1 = h1.erase(it1);

   473 	++n;

   474     }

   475     QVERIFY(n == 3);

   476     QHash<int, int> h2;

   477     h2.insertMulti(20, 41);

   478     h2.insertMulti(20, 42);

   479     QVERIFY(h2.size() == 2);

   480     it1 = h2.erase(h2.begin());

   481     it1 = h2.erase(h2.begin());

   482     QVERIFY(it1 == h2.end());

   483 }

   484 

   485 void tst_QHash::key()

   486 {

   487     {

   488         QString def("default value");

   489 

   490         QHash<QString, int> hash1;

   491         QCOMPARE(hash1.key(1), QString());

   492         QCOMPARE(hash1.key(1, def), def);

   493 

   494         hash1.insert("one", 1);

   495         QCOMPARE(hash1.key(1), QString("one"));

   496         QCOMPARE(hash1.key(1, def), QString("one"));

   497         QCOMPARE(hash1.key(2), QString());

   498         QCOMPARE(hash1.key(2, def), def);

   499 

   500         hash1.insert("two", 2);

   501         QCOMPARE(hash1.key(1), QString("one"));

   502         QCOMPARE(hash1.key(1, def), QString("one"));

   503         QCOMPARE(hash1.key(2), QString("two"));

   504         QCOMPARE(hash1.key(2, def), QString("two"));

   505         QCOMPARE(hash1.key(3), QString());

   506         QCOMPARE(hash1.key(3, def), def);

   507 

   508         hash1.insert("deux", 2);

   509         QCOMPARE(hash1.key(1), QString("one"));

   510         QCOMPARE(hash1.key(1, def), QString("one"));

   511         QVERIFY(hash1.key(2) == "deux" || hash1.key(2) == "two");

   512         QVERIFY(hash1.key(2, def) == "deux" || hash1.key(2, def) == "two");

   513         QCOMPARE(hash1.key(3), QString());

   514         QCOMPARE(hash1.key(3, def), def);

   515     }

   516 

   517     {

   518         int def = 666;

   519 

   520         QHash<int, QString> hash2;

   521         QCOMPARE(hash2.key("one"), 0);

   522         QCOMPARE(hash2.key("one", def), def);

   523 

   524         hash2.insert(1, "one");

   525         QCOMPARE(hash2.key("one"), 1);

   526         QCOMPARE(hash2.key("one", def), 1);

   527         QCOMPARE(hash2.key("two"), 0);

   528         QCOMPARE(hash2.key("two", def), def);

   529 

   530         hash2.insert(2, "two");

   531         QCOMPARE(hash2.key("one"), 1);

   532         QCOMPARE(hash2.key("one", def), 1);

   533         QCOMPARE(hash2.key("two"), 2);

   534         QCOMPARE(hash2.key("two", def), 2);

   535         QCOMPARE(hash2.key("three"), 0);

   536         QCOMPARE(hash2.key("three", def), def);

   537 

   538         hash2.insert(3, "two");

   539         QCOMPARE(hash2.key("one"), 1);

   540         QCOMPARE(hash2.key("one", def), 1);

   541         QCOMPARE(hash2.key("two"), 2);

   542         QCOMPARE(hash2.key("two", def), 2);

   543         QCOMPARE(hash2.key("three"), 0);

   544         QCOMPARE(hash2.key("three", def), def);

   545 

   546         hash2.insert(-1, "two");

   547         QCOMPARE(hash2.key("two"), -1);

   548         QCOMPARE(hash2.key("two", def), -1);

   549 

   550         hash2.insert(0, "zero");

   551         QCOMPARE(hash2.key("zero"), 0);

   552         QCOMPARE(hash2.key("zero", def), 0);

   553     }

   554 }

   555 

   556 // copied from tst_QMap

   557 void tst_QHash::clear()

   558 {

   559     {

   560 	MyMap map;

   561 	map.clear();

   562 	QVERIFY( map.isEmpty() );

   563 	map.insert( "key", MyClass( "value" ) );

   564 	map.clear();

   565 	QVERIFY( map.isEmpty() );

   566 	map.insert( "key0", MyClass( "value0" ) );

   567 	map.insert( "key0", MyClass( "value1" ) );

   568 	map.insert( "key1", MyClass( "value2" ) );

   569 	map.clear();

   570 	QVERIFY( map.isEmpty() );

   571     }

   572     QCOMPARE( MyClass::count, int(0) );

   573 }

   574 //copied from tst_QMap

   575 void tst_QHash::empty()

   576 {

   577     QHash<int, QString> map1;

   578 

   579     QVERIFY(map1.isEmpty());

   580 

   581     map1.insert(1, "one");

   582     QVERIFY(!map1.isEmpty());

   583 

   584     map1.clear();

   585     QVERIFY(map1.isEmpty());

   586 

   587 }

   588 

   589 //copied from tst_QMap

   590 void tst_QHash::find()

   591 {

   592     QHash<int, QString> map1;

   593     QString testString="Teststring %0";

   594     QString compareString;

   595     int i,count=0;

   596 

   597     //QVERIFY(map1.find(1) == map1.end());

   598 

   599     map1.insert(1,"Mensch");

   600     map1.insert(1,"Mayer");

   601     map1.insert(2,"Hej");

   602 

   603     QVERIFY(map1.find(1).value() == "Mayer");

   604     QVERIFY(map1.find(2).value() == "Hej");

   605 

   606     for(i = 3; i < 10; ++i) {

   607         compareString = testString.arg(i);

   608         map1.insertMulti(4, compareString);

   609     }

   610 

   611     QHash<int, QString>::const_iterator it=map1.find(4);

   612 

   613     for(i = 9; i > 2 && it != map1.end() && it.key() == 4; --i) {

   614         compareString = testString.arg(i);

   615         QVERIFY(it.value() == compareString);

   616         ++it;

   617         ++count;

   618     }

   619     QCOMPARE(count, 7);

   620 }

   621 

   622 // copied from tst_QMap

   623 void tst_QHash::constFind()

   624 {

   625     QHash<int, QString> map1;

   626     QString testString="Teststring %0";

   627     QString compareString;

   628     int i,count=0;

   629 

   630     QVERIFY(map1.constFind(1) == map1.constEnd());

   631 

   632     map1.insert(1,"Mensch");

   633     map1.insert(1,"Mayer");

   634     map1.insert(2,"Hej");

   635 

   636     QVERIFY(map1.constFind(1).value() == "Mayer");

   637     QVERIFY(map1.constFind(2).value() == "Hej");

   638 

   639     for(i = 3; i < 10; ++i) {

   640         compareString = testString.arg(i);

   641         map1.insertMulti(4, compareString);

   642     }

   643 

   644     QHash<int, QString>::const_iterator it=map1.constFind(4);

   645 

   646     for(i = 9; i > 2 && it != map1.constEnd() && it.key() == 4; --i) {

   647         compareString = testString.arg(i);

   648         QVERIFY(it.value() == compareString);

   649         ++it;

   650         ++count;

   651     }

   652     QCOMPARE(count, 7);

   653 }

   654 

   655 // copied from tst_QMap

   656 void tst_QHash::contains()

   657 {

   658     QHash<int, QString> map1;

   659     int i;

   660 

   661     map1.insert(1, "one");

   662     QVERIFY(map1.contains(1));

   663 

   664     for(i=2; i < 100; ++i)

   665         map1.insert(i, "teststring");

   666     for(i=99; i > 1; --i)

   667         QVERIFY(map1.contains(i));

   668 

   669     map1.remove(43);

   670     QVERIFY(!map1.contains(43));

   671 }

   672 

   673 //copied from tst_QMap

   674 void tst_QHash::take()

   675 {

   676     QHash<int, QString> map;

   677 

   678     map.insert(2, "zwei");

   679     map.insert(3, "drei");

   680 

   681     QVERIFY(map.take(3) == "drei");

   682     QVERIFY(!map.contains(3));

   683 }

   684 

   685 //copied from tst_QMap

   686 void tst_QHash::operator_eq()

   687 {

   688     {

   689         // compare for equality:

   690         QHash<int, int> a;

   691         QHash<int, int> b;

   692 

   693         QVERIFY(a == b);

   694         QVERIFY(!(a != b));

   695 

   696         a.insert(1,1);

   697         b.insert(1,1);

   698         QVERIFY(a == b);

   699         QVERIFY(!(a != b));

   700 

   701         a.insert(0,1);

   702         b.insert(0,1);

   703         QVERIFY(a == b);

   704         QVERIFY(!(a != b));

   705 

   706         // compare for inequality:

   707         a.insert(42,0);

   708         QVERIFY(a != b);

   709         QVERIFY(!(a == b));

   710 

   711         a.insert(65, -1);

   712         QVERIFY(a != b);

   713         QVERIFY(!(a == b));

   714 

   715         b.insert(-1, -1);

   716         QVERIFY(a != b);

   717         QVERIFY(!(a == b));

   718     }

   719 

   720     {

   721         // a more complex map

   722         QHash<QString, QString> a;

   723         QHash<QString, QString> b;

   724 

   725         QVERIFY(a == b);

   726         QVERIFY(!(a != b));

   727 

   728         a.insert("Hello", "World");

   729         QVERIFY(a != b);

   730         QVERIFY(!(a == b));

   731 

   732         b.insert("Hello", "World");

   733         QVERIFY(a == b);

   734         QVERIFY(!(a != b));

   735 

   736         a.insert("Goodbye", "cruel world");

   737         QVERIFY(a != b);

   738         QVERIFY(!(a == b));

   739 

   740         b.insert("Goodbye", "cruel world");

   741 

   742         // what happens if we insert nulls?

   743         a.insert(QString(), QString());

   744         QVERIFY(a != b);

   745         QVERIFY(!(a == b));

   746 

   747         // empty keys and null keys match:

   748         b.insert(QString(""), QString());

   749         QVERIFY(a == b);

   750         QVERIFY(!(a != b));

   751     }

   752 

   753     {

   754         // task 102658

   755 

   756         QHash<QString, int> a;

   757         QHash<QString, int> b;

   758 

   759         a.insert("otto", 1);

   760         b.insert("willy", 1);

   761         QVERIFY(a != b);

   762         QVERIFY(!(a == b));

   763     }

   764 }

   765 

   766 void tst_QHash::compare()

   767 {

   768     QHash<int, QString> hash1,hash2;

   769     QString testString = "Teststring %1";

   770     int i;

   771 

   772     for(i = 0; i < 1000; ++i)

   773         hash1.insert(i,testString.arg(i));

   774 

   775     for(--i; i >= 0; --i)

   776         hash2.insert(i,testString.arg(i));

   777 

   778     hash1.squeeze();

   779     hash2.squeeze();

   780 

   781     QVERIFY(hash1 == hash2);

   782     QVERIFY(!(hash1 != hash2));

   783 

   784     hash1.take(234);

   785     hash2.take(234);

   786     QVERIFY(hash1 == hash2);

   787     QVERIFY(!(hash1 != hash2));

   788 

   789     hash2.take(261);

   790     QVERIFY(!(hash1 == hash2));

   791     QVERIFY(hash1 != hash2);

   792 }

   793 

   794 void tst_QHash::compare2()

   795 {

   796     QHash<int, int> a;

   797     QHash<int, int> b;

   798 

   799     a.insertMulti(17, 1);

   800     a.insertMulti(17 * 2, 1);

   801     b.insertMulti(17 * 2, 1);

   802     b.insertMulti(17, 1);

   803     QVERIFY(a == b);

   804     QVERIFY(b == a);

   805 

   806     a.insertMulti(17, 2);

   807     a.insertMulti(17 * 2, 3);

   808     b.insertMulti(17 * 2, 3);

   809     b.insertMulti(17, 2);

   810     QVERIFY(a == b);

   811     QVERIFY(b == a);

   812 

   813     a.insertMulti(17, 4);

   814     a.insertMulti(17 * 2, 5);

   815     b.insertMulti(17 * 2, 4);

   816     b.insertMulti(17, 5);

   817     QVERIFY(!(a == b));

   818     QVERIFY(!(b == a));

   819 

   820     a.clear();

   821     b.clear();

   822     a.insertMulti(1, 1);

   823     a.insertMulti(1, 2);

   824     a.insertMulti(1, 3);

   825     b.insertMulti(1, 1);

   826     b.insertMulti(1, 2);

   827     b.insertMulti(1, 3);

   828     b.insertMulti(1, 4);

   829     QVERIFY(!(a == b));

   830     QVERIFY(!(b == a));

   831 }

   832 

   833 //sligthly modified from tst_QMap

   834 void tst_QHash::iterators()

   835 {

   836     QHash<int, QString> hash;

   837     QMap<int, QString> testMap;

   838     QString testString="Teststring %1";

   839     QString testString1;

   840     int i;

   841 

   842     for(i = 1; i < 100; ++i)

   843         hash.insert(i, testString.arg(i));

   844 

   845     //to get some chaos in the hash

   846     hash.squeeze();

   847 

   848     //STL-Style iterators

   849 

   850     QHash<int, QString>::iterator stlIt = hash.begin();

   851     for(stlIt = hash.begin(), i = 1; stlIt != hash.end(), i < 100; ++stlIt, ++i) {

   852             testMap.insert(i,stlIt.value());

   853             //QVERIFY(stlIt.value() == hash.value(

   854     }

   855     stlIt = hash.begin();

   856 

   857     QVERIFY(stlIt.value() == testMap.value(1));

   858 

   859     stlIt+=5;

   860     QVERIFY(stlIt.value() == testMap.value(6));

   861 

   862     stlIt++;

   863     QVERIFY(stlIt.value() == testMap.value(7));

   864 

   865     stlIt-=3;

   866     QVERIFY(stlIt.value() == testMap.value(4));

   867 

   868     stlIt--;

   869     QVERIFY(stlIt.value() == testMap.value(3));

   870 

   871     testMap.clear();

   872 

   873     //STL-Style const-iterators

   874 

   875     QHash<int, QString>::const_iterator cstlIt = hash.constBegin();

   876     for(cstlIt = hash.constBegin(), i = 1; cstlIt != hash.constEnd(), i < 100; ++cstlIt, ++i) {

   877             testMap.insert(i,cstlIt.value());

   878             //QVERIFY(stlIt.value() == hash.value(

   879     }

   880     cstlIt = hash.constBegin();

   881 

   882     QVERIFY(cstlIt.value() == testMap.value(1));

   883 

   884     cstlIt+=5;

   885     QVERIFY(cstlIt.value() == testMap.value(6));

   886 

   887     cstlIt++;

   888     QVERIFY(cstlIt.value() == testMap.value(7));

   889 

   890     cstlIt-=3;

   891     QVERIFY(cstlIt.value() == testMap.value(4));

   892 

   893     cstlIt--;

   894     QVERIFY(cstlIt.value() == testMap.value(3));

   895 

   896     testMap.clear();

   897 

   898     //Java-Style iterators

   899 

   900     QHashIterator<int, QString> javaIt(hash);

   901 

   902     //walk through

   903     i = 0;

   904     while(javaIt.hasNext()) {

   905         ++i;

   906         javaIt.next();

   907         testMap.insert(i,javaIt.value());

   908     }

   909     javaIt.toFront();

   910     i = 0;

   911     while(javaIt.hasNext()) {

   912         ++i;

   913         javaIt.next();

   914         //qDebug(javaIt.value());

   915         QVERIFY(javaIt.value() == testMap.value(i));

   916     }

   917 

   918     ++i;

   919     while(javaIt.hasPrevious()) {

   920         --i;

   921         javaIt.previous();

   922         QVERIFY(javaIt.value() == testMap.value(i));

   923     }

   924 

   925     /*

   926         I've removed findNextKey() and findPreviousKey() from the API

   927         for Qt 4.0 beta 1.

   928     */

   929 

   930 #if 0

   931     //findPreviousKey()  findNextKey()

   932     for(i = 1; i < 100; ++i) {

   933         if(javaIt.findNextKey(i))

   934             QVERIFY(javaIt.value() == testString.arg(i));

   935         else {

   936             QVERIFY(!javaIt.hasNext());

   937             QVERIFY(javaIt.findPreviousKey(i));

   938             QVERIFY(javaIt.value() == testString.arg(i));

   939         }

   940 

   941         if(javaIt.findPreviousKey(i))

   942             QVERIFY(javaIt.value() == testString.arg(i));

   943         else {

   944             QVERIFY(!javaIt.hasPrevious());

   945             QVERIFY(javaIt.findNextKey(i));

   946             QVERIFY(javaIt.value() == testString.arg(i));

   947         }

   948     }

   949 #endif

   950 

   951     //peekNext()  peekPrevious()

   952     javaIt.toFront();

   953     javaIt.next();

   954     while(javaIt.hasNext()) {

   955         testString = javaIt.value();

   956         testString1 = javaIt.peekNext().value();

   957         javaIt.next();

   958         //qDebug(testString + "  " + testString1 + "    " + javaIt.peekPrevious().value());

   959         QVERIFY(javaIt.value() == testString1);

   960         QCOMPARE(javaIt.peekPrevious().value(), testString1);

   961     }

   962     while(javaIt.hasPrevious()) {

   963         testString = javaIt.value();

   964         testString1 = javaIt.peekPrevious().value();

   965         javaIt.previous();

   966         QVERIFY(javaIt.value() == testString1);

   967         //qDebug(testString + testString1 + javaIt.peekNext().value());

   968         QCOMPARE(javaIt.peekNext().value(), testString1);

   969     }

   970 }

   971 

   972 void tst_QHash::rehash_isnt_quadratic()

   973 {

   974     // this test should be incredibly slow if rehash() is quadratic

   975     for (int j = 0; j < 5; ++j) {

   976         QHash<int, int> testHash;

   977 #if defined(Q_OS_WINCE) || defined(Q_OS_SYMBIAN) // mobiles do not have infinite mem...

   978         for (int i = 0; i < 50000; ++i)

   979 #else

   980         for (int i = 0; i < 500000; ++i)

   981 #endif

   982             testHash.insertMulti(1, 1);

   983     }

   984 }

   985 

   986 class Bar

   987 {

   988 public:

   989     Bar(int i) : j(i) {}

   990 

   991     int j;

   992 };

   993 

   994 void tst_QHash::dont_need_default_constructor()

   995 {

   996     QHash<int, Bar> hash1;

   997     for (int i = 0; i < 100; ++i) {

   998         hash1.insert(i, Bar(2 * i));

   999         QVERIFY(hash1.value(i, Bar(-1)).j == 2 * i);

  1000         QVERIFY(hash1.size() == i + 1);

  1001     }

  1002 

  1003     QHash<QString, Bar> hash2;

  1004     for (int i = 0; i < 100; ++i) {

  1005         hash2.insert(QString::number(i), Bar(2 * i));

  1006         QVERIFY(hash2.value(QString::number(i), Bar(-1)).j == 2 * i);

  1007         QVERIFY(hash2.size() == i + 1);

  1008     }

  1009 }

  1010 

  1011 void tst_QHash::qhash()

  1012 {

  1013     {

  1014         QBitArray a1;

  1015         QBitArray a2;

  1016         QVERIFY(qHash(a1) == 0);

  1017 

  1018         a1.resize(1);

  1019         a1.setBit(0, true);

  1020 

  1021         a2.resize(1);

  1022         a2.setBit(0, false);

  1023 

  1024         uint h1 = qHash(a1);

  1025         uint h2 = qHash(a2);

  1026 

  1027         QVERIFY(h1 != h2);

  1028 

  1029         a2.setBit(0, true);

  1030         QVERIFY(h1 == qHash(a2));

  1031 

  1032         a1.fill(true, 8);

  1033         a1.resize(7);

  1034 

  1035         h1 = qHash(a1);

  1036 

  1037         a2.fill(true, 7);

  1038         h2 = qHash(a2);

  1039 

  1040         QVERIFY(h1 == h2);

  1041 

  1042         a2.setBit(0, false);

  1043         uint h3 = qHash(a2);

  1044         QVERIFY(h2 != h3);

  1045 

  1046         a2.setBit(0, true);

  1047         QVERIFY(h2 == qHash(a2));

  1048 

  1049         a2.setBit(6, false);

  1050         uint h4 = qHash(a2);

  1051         QVERIFY(h2 != h4);

  1052 

  1053         a2.setBit(6, true);

  1054         QVERIFY(h2 == qHash(a2));

  1055 

  1056         QVERIFY(h3 != h4);

  1057     }

  1058 

  1059     {

  1060         QPair<int, int> p12(1, 2);

  1061         QPair<int, int> p21(2, 1);

  1062 

  1063         QVERIFY(qHash(p12) == qHash(p12));

  1064         QVERIFY(qHash(p21) == qHash(p21));

  1065         QVERIFY(qHash(p12) != qHash(p21));

  1066 

  1067         QPair<int, int> pA(0x12345678, 0x12345678);

  1068         QPair<int, int> pB(0x12345675, 0x12345675);

  1069 

  1070         QVERIFY(qHash(pA) != qHash(pB));

  1071     }

  1072 }

  1073 

  1074 void tst_QHash::qmultihash_specific()

  1075 {

  1076     QMultiHash<int, int> hash1;

  1077     for (int i = 1; i <= 9; ++i) {

  1078         for (int j = 1; j <= i; ++j) {

  1079             int k = i * 10 + j;

  1080             QVERIFY(!hash1.contains(i, k));

  1081             hash1.insert(i, k);

  1082             QVERIFY(hash1.contains(i, k));

  1083         }

  1084     }

  1085 

  1086     for (int i = 1; i <= 9; ++i) {

  1087         for (int j = 1; j <= i; ++j) {

  1088             int k = i * 10 + j;

  1089             QVERIFY(hash1.contains(i, k));

  1090         }

  1091     }

  1092 

  1093     QVERIFY(hash1.contains(9, 99));

  1094     QCOMPARE(hash1.count(), 45);

  1095     hash1.remove(9, 99);

  1096     QVERIFY(!hash1.contains(9, 99));

  1097     QCOMPARE(hash1.count(), 44);

  1098 

  1099     hash1.remove(9, 99);

  1100     QVERIFY(!hash1.contains(9, 99));

  1101     QCOMPARE(hash1.count(), 44);

  1102 

  1103     hash1.remove(1, 99);

  1104     QCOMPARE(hash1.count(), 44);

  1105 

  1106     hash1.insert(1, 99);

  1107     hash1.insert(1, 99);

  1108 

  1109     QCOMPARE(hash1.count(), 46);

  1110     hash1.remove(1, 99);

  1111     QCOMPARE(hash1.count(), 44);

  1112     hash1.remove(1, 99);

  1113     QCOMPARE(hash1.count(), 44);

  1114 

  1115     {

  1116     QMultiHash<int, int>::const_iterator i = hash1.constFind(1, 11);

  1117     QVERIFY(i.key() == 1);

  1118     QVERIFY(i.value() == 11);

  1119 

  1120     i = hash1.constFind(2, 22);

  1121     QVERIFY(i.key() == 2);

  1122     QVERIFY(i.value() == 22);

  1123 

  1124     i = hash1.constFind(9, 98);

  1125     QVERIFY(i.key() == 9);

  1126     QVERIFY(i.value() == 98);

  1127     }

  1128 

  1129     {

  1130     const QMultiHash<int, int> hash2(hash1);

  1131     QMultiHash<int, int>::const_iterator i = hash2.find(1, 11);

  1132     QVERIFY(i.key() == 1);

  1133     QVERIFY(i.value() == 11);

  1134