1 /****************************************************************************
2 **
3 ** Copyright (C) 2015 The Qt Company Ltd.
4 ** Contact: http://www.qt.io/licensing/
5 **
6 ** This file is part of the test suite of the Qt Toolkit.
7 **
8 ** $QT_BEGIN_LICENSE:LGPL$
9 ** Commercial License Usage
10 ** Licensees holding valid commercial Qt licenses may use this file in
11 ** accordance with the commercial license agreement provided with the
12 ** Software or, alternatively, in accordance with the terms contained in
13 ** a written agreement between you and The Qt Company. For licensing terms
14 ** and conditions see http://www.qt.io/terms-conditions. For further
15 ** information use the contact form at http://www.qt.io/contact-us.
16 **
17 ** GNU Lesser General Public License Usage
18 ** Alternatively, this file may be used under the terms of the GNU Lesser
19 ** General Public License version 2.1 or version 3 as published by the Free
20 ** Software Foundation and appearing in the file LICENSE.LGPLv21 and
21 ** LICENSE.LGPLv3 included in the packaging of this file. Please review the
22 ** following information to ensure the GNU Lesser General Public License
23 ** requirements will be met: https://www.gnu.org/licenses/lgpl.html and
24 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
25 **
26 ** As a special exception, The Qt Company gives you certain additional
27 ** rights. These rights are described in The Qt Company LGPL Exception
28 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
29 **
30 ** GNU General Public License Usage
31 ** Alternatively, this file may be used under the terms of the GNU
32 ** General Public License version 3.0 as published by the Free Software
33 ** Foundation and appearing in the file LICENSE.GPL included in the
34 ** packaging of this file. Please review the following information to
35 ** ensure the GNU General Public License version 3.0 requirements will be
36 ** met: http://www.gnu.org/copyleft/gpl.html.
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();
~tst_QHash()56 virtual ~tst_QHash() {}
57
58 private slots:
59 void insert1();
60 void erase();
61 void key();
62
63 void swap();
64 void count(); // copied from tst_QMap
65 void clear(); // copied from tst_QMap
66 void empty(); // copied from tst_QMap
67 void find(); // copied from tst_QMap
68 void constFind(); // copied from tst_QMap
69 void contains(); // copied from tst_QMap
70 void take(); // copied from tst_QMap
71 void operator_eq(); // copied from tst_QMap
72 void rehash_isnt_quadratic();
73 void dont_need_default_constructor();
74 void qhash();
75 void qmultihash_specific();
76
77 void compare();
78 void compare2();
79 void iterators(); // sligthly modified from tst_QMap
80 void keys_values_uniqueKeys(); // slightly modified from tst_QMap
81 void noNeedlessRehashes();
82 };
83
84 struct Foo {
85 static int count;
FooFoo86 Foo():c(count) { ++count; }
FooFoo87 Foo(const Foo& o):c(o.c) { ++count; }
~FooFoo88 ~Foo() { --count; }
89 int c;
90 int data[8];
91 };
92
tst_QHash()93 tst_QHash::tst_QHash()
94 {}
95
96 int Foo::count = 0;
97
98 //copied from tst_QMap.cpp
99 class MyClass
100 {
101 public:
MyClass()102 MyClass() { ++count;
103 // qDebug("creating MyClass count=%d", count);
104 }
MyClass(const QString & c)105 MyClass( const QString& c) {
106 count++; str = c;
107 // qDebug("creating MyClass '%s' count = %d", str.latin1(), count);
108 }
~MyClass()109 ~MyClass() {
110 count--;
111 // qDebug("deleting MyClass '%s' count = %d", str.latin1(), count);
112 }
MyClass(const MyClass & c)113 MyClass( const MyClass& c ) {
114 count++; str = c.str;
115 // qDebug("creating MyClass '%s' count = %d", str.latin1(), count);
116 }
operator =(const MyClass & o)117 MyClass &operator =(const MyClass &o) {
118 // qDebug("copying MyClass '%s'", o.str.latin1());
119 str = o.str; return *this;
120 }
121
122 QString str;
123 static int count;
124 };
125
126 int MyClass::count = 0;
127
128 typedef QHash<QString, MyClass> MyMap;
129
130 //void tst_QMap::count()
count()131 void tst_QHash::count()
132 {
133 {
134 MyMap map;
135 MyMap map2( map );
136 QCOMPARE( map.count(), 0 );
137 QCOMPARE( map2.count(), 0 );
138 QCOMPARE( MyClass::count, 0 );
139 // detach
140 map2["Hallo"] = MyClass( "Fritz" );
141 QCOMPARE( map.count(), 0 );
142 QCOMPARE( map2.count(), 1 );
143 #ifndef Q_CC_SUN
144 QCOMPARE( MyClass::count, 1 );
145 #endif
146 }
147 QCOMPARE( MyClass::count, 0 );
148
149 {
150 typedef QHash<QString, MyClass> Map;
151 Map map;
152 QCOMPARE( map.count(), 0);
153 map.insert( "Torben", MyClass("Weis") );
154 QCOMPARE( map.count(), 1 );
155 map.insert( "Claudia", MyClass("Sorg") );
156 QCOMPARE( map.count(), 2 );
157 map.insert( "Lars", MyClass("Linzbach") );
158 map.insert( "Matthias", MyClass("Ettrich") );
159 map.insert( "Sue", MyClass("Paludo") );
160 map.insert( "Eirik", MyClass("Eng") );
161 map.insert( "Haavard", MyClass("Nord") );
162 map.insert( "Arnt", MyClass("Gulbrandsen") );
163 map.insert( "Paul", MyClass("Tvete") );
164 QCOMPARE( map.count(), 9 );
165 map.insert( "Paul", MyClass("Tvete 1") );
166 map.insert( "Paul", MyClass("Tvete 2") );
167 map.insert( "Paul", MyClass("Tvete 3") );
168 map.insert( "Paul", MyClass("Tvete 4") );
169 map.insert( "Paul", MyClass("Tvete 5") );
170 map.insert( "Paul", MyClass("Tvete 6") );
171
172 QCOMPARE( map.count(), 9 );
173 #ifndef Q_CC_SUN
174 QCOMPARE( MyClass::count, 9 );
175 #endif
176
177 Map map2( map );
178 QVERIFY( map2.count() == 9 );
179 #ifndef Q_CC_SUN
180 QCOMPARE( MyClass::count, 9 );
181 #endif
182
183 map2.insert( "Kay", MyClass("Roemer") );
184 QVERIFY( map2.count() == 10 );
185 QVERIFY( map.count() == 9 );
186 #ifndef Q_CC_SUN
187 QCOMPARE( MyClass::count, 19 );
188 #endif
189
190 map2 = map;
191 QVERIFY( map.count() == 9 );
192 QVERIFY( map2.count() == 9 );
193 #ifndef Q_CC_SUN
194 QCOMPARE( MyClass::count, 9 );
195 #endif
196
197 map2.insert( "Kay", MyClass("Roemer") );
198 QVERIFY( map2.count() == 10 );
199 #ifndef Q_CC_SUN
200 QCOMPARE( MyClass::count, 19 );
201 #endif
202
203 map2.clear();
204 QVERIFY( map.count() == 9 );
205 QVERIFY( map2.count() == 0 );
206 #ifndef Q_CC_SUN
207 QCOMPARE( MyClass::count, 9 );
208 #endif
209
210 map2 = map;
211 QVERIFY( map.count() == 9 );
212 QVERIFY( map2.count() == 9 );
213 #ifndef Q_CC_SUN
214 QCOMPARE( MyClass::count, 9 );
215 #endif
216
217 map2.clear();
218 QVERIFY( map.count() == 9 );
219 QVERIFY( map2.count() == 0 );
220 #ifndef Q_CC_SUN
221 QCOMPARE( MyClass::count, 9 );
222 #endif
223
224 map.remove( "Lars" );
225 QVERIFY( map.count() == 8 );
226 QVERIFY( map2.count() == 0 );
227 #ifndef Q_CC_SUN
228 QCOMPARE( MyClass::count, 8 );
229 #endif
230
231 map.remove( "Mist" );
232 QVERIFY( map.count() == 8 );
233 QVERIFY( map2.count() == 0 );
234 #ifndef Q_CC_SUN
235 QCOMPARE( MyClass::count, 8 );
236 #endif
237 }
238 QVERIFY( MyClass::count == 0 );
239
240 {
241 typedef QHash<QString,MyClass> Map;
242 Map map;
243 map["Torben"] = MyClass("Weis");
244 #ifndef Q_CC_SUN
245 QVERIFY( MyClass::count == 1 );
246 #endif
247 QVERIFY( map.count() == 1 );
248
249 (void)map["Torben"].str;
250 (void)map["Lars"].str;
251 #ifndef Q_CC_SUN
252 QVERIFY( MyClass::count == 2 );
253 #endif
254 QVERIFY( map.count() == 2 );
255
256 const Map& cmap = map;
257 (void)cmap["Depp"].str;
258 #ifndef Q_CC_SUN
259 QVERIFY( MyClass::count == 2 );
260 #endif
261 QVERIFY( map.count() == 2 );
262 QVERIFY( cmap.count() == 2 );
263 }
264 QCOMPARE( MyClass::count, 0 );
265 {
266 for ( int i = 0; i < 100; ++i )
267 {
268 QHash<int, MyClass> map;
269 for (int j = 0; j < i; ++j)
270 map.insert(j, MyClass(QString::number(j)));
271 }
272 QCOMPARE( MyClass::count, 0 );
273 }
274 QCOMPARE( MyClass::count, 0 );
275 }
insert1()276 void tst_QHash::insert1()
277 {
278 const char *hello = "hello";
279 const char *world = "world";
280 const char *allo = "allo";
281 const char *monde = "monde";
282
283 {
284 typedef QHash<QString, QString> Hash;
285 Hash hash;
286 QString key;
287 for (int i = 0; i < 10; ++i) {
288 key[0] = i + '0';
289 for (int j = 0; j < 10; ++j) {
290 key[1] = j + '0';
291 hash.insert(key, "V" + key);
292 }
293 }
294
295 for (int i = 0; i < 10; ++i) {
296 key[0] = i + '0';
297 for (int j = 0; j < 10; ++j) {
298 key[1] = j + '0';
299 hash.remove(key);
300 }
301 }
302 }
303
304 {
305 typedef QHash<int, const char *> Hash;
306 Hash hash;
307 hash.insert(1, hello);
308 hash.insert(2, world);
309
310 QVERIFY(hash.size() == 2);
311 QVERIFY(!hash.isEmpty());
312
313 {
314 Hash hash2 = hash;
315 hash2 = hash;
316 hash = hash2;
317 hash2 = hash2;
318 hash = hash;
319 hash2.clear();
320 hash2 = hash2;
321 QVERIFY(hash2.size() == 0);
322 QVERIFY(hash2.isEmpty());
323 }
324 QVERIFY(hash.size() == 2);
325
326 {
327 Hash hash2 = hash;
328 hash2[1] = allo;
329 hash2[2] = monde;
330
331 QVERIFY(hash2[1] == allo);
332 QVERIFY(hash2[2] == monde);
333 QVERIFY(hash[1] == hello);
334 QVERIFY(hash[2] == world);
335
336 hash2[1] = hash[1];
337 hash2[2] = hash[2];
338
339 QVERIFY(hash2[1] == hello);
340 QVERIFY(hash2[2] == world);
341
342 hash[1] = hash[1];
343 QVERIFY(hash[1] == hello);
344 }
345 {
346 Hash hash2 = hash;
347 hash2.detach();
348 hash2.remove(1);
349 QVERIFY(hash2.size() == 1);
350 hash2.remove(1);
351 QVERIFY(hash2.size() == 1);
352 hash2.remove(0);
353 QVERIFY(hash2.size() == 1);
354 hash2.remove(2);
355 QVERIFY(hash2.size() == 0);
356 QVERIFY(hash.size() == 2);
357 }
358
359 hash.detach();
360
361 {
362 Hash::iterator it1 = hash.find(1);
363 QVERIFY(it1 != hash.end());
364
365 Hash::iterator it2 = hash.find(0);
366 QVERIFY(it2 != hash.begin());
367 QVERIFY(it2 == hash.end());
368
369 *it1 = monde;
370 QVERIFY(*it1 == monde);
371 QVERIFY(hash[1] == monde);
372
373 *it1 = hello;
374 QVERIFY(*it1 == hello);
375 QVERIFY(hash[1] == hello);
376
377 hash[1] = monde;
378 QVERIFY(it1.key() == 1);
379 QVERIFY(it1.value() == monde);
380 QVERIFY(*it1 == monde);
381 QVERIFY(hash[1] == monde);
382
383 hash[1] = hello;
384 QVERIFY(*it1 == hello);
385 QVERIFY(hash[1] == hello);
386 }
387
388 {
389 const Hash hash2 = hash;
390
391 Hash::const_iterator it1 = hash2.find(1);
392 QVERIFY(it1 != hash2.end());
393 QVERIFY(it1.key() == 1);
394 QVERIFY(it1.value() == hello);
395 QVERIFY(*it1 == hello);
396
397 Hash::const_iterator it2 = hash2.find(2);
398 QVERIFY(it1 != it2);
399 QVERIFY(it1 != hash2.end());
400 QVERIFY(it2 != hash2.end());
401
402 int count = 0;
403 it1 = hash2.begin();
404 while (it1 != hash2.end()) {
405 count++;
406 ++it1;
407 }
408 QVERIFY(count == 2);
409
410 count = 0;
411 it1 = hash.begin();
412 while (it1 != hash.end()) {
413 count++;
414 ++it1;
415 }
416 QVERIFY(count == 2);
417 }
418
419 {
420 QVERIFY(hash.contains(1));
421 QVERIFY(hash.contains(2));
422 QVERIFY(!hash.contains(0));
423 QVERIFY(!hash.contains(3));
424 }
425
426 {
427 QVERIFY(hash.value(1) == hello);
428 QVERIFY(hash.value(2) == world);
429 QVERIFY(hash.value(3) == 0);
430 QVERIFY(hash.value(1, allo) == hello);
431 QVERIFY(hash.value(2, allo) == world);
432 QVERIFY(hash.value(3, allo) == allo);
433 QVERIFY(hash.value(0, monde) == monde);
434 }
435
436 {
437 QHash<int,Foo> hash;
438 for (int i = 0; i < 10; i++)
439 hash.insert(i, Foo());
440 QVERIFY(Foo::count == 10);
441 hash.remove(7);
442 QVERIFY(Foo::count == 9);
443
444 }
445 QVERIFY(Foo::count == 0);
446 {
447 QHash<int, int*> hash;
448 QVERIFY(((const QHash<int,int*>*) &hash)->operator[](7) == 0);
449 }
450 }
451 }
452
erase()453 void tst_QHash::erase()
454 {
455 QHash<int, int> h1;
456 h1.insert(1, 2);
457 h1.erase(h1.begin());
458 QVERIFY(h1.size() == 0);
459 QVERIFY(h1.begin() == h1.end());
460 h1.insert(3, 4);
461 QVERIFY(*h1.begin() == 4);
462 h1.insert(5, 6);
463 QVERIFY(h1.size() == 2);
464 QHash<int, int>::iterator it1 = h1.begin();
465 ++it1;
466 it1 = h1.erase(it1);
467 QVERIFY(it1 == h1.end());
468 h1.insert(7, 8);
469 h1.insert(9, 10);
470 it1 = h1.begin();
471 int n = 0;
472 while (it1 != h1.end()) {
473 it1 = h1.erase(it1);
474 ++n;
475 }
476 QVERIFY(n == 3);
477 QHash<int, int> h2;
478 h2.insertMulti(20, 41);
479 h2.insertMulti(20, 42);
480 QVERIFY(h2.size() == 2);
481 it1 = h2.erase(h2.begin());
482 it1 = h2.erase(h2.begin());
483 QVERIFY(it1 == h2.end());
484 }
485
key()486 void tst_QHash::key()
487 {
488 {
489 QString def("default value");
490
491 QHash<QString, int> hash1;
492 QCOMPARE(hash1.key(1), QString());
493 QCOMPARE(hash1.key(1, def), def);
494
495 hash1.insert("one", 1);
496 QCOMPARE(hash1.key(1), QString("one"));
497 QCOMPARE(hash1.key(1, def), QString("one"));
498 QCOMPARE(hash1.key(2), QString());
499 QCOMPARE(hash1.key(2, def), def);
500
501 hash1.insert("two", 2);
502 QCOMPARE(hash1.key(1), QString("one"));
503 QCOMPARE(hash1.key(1, def), QString("one"));
504 QCOMPARE(hash1.key(2), QString("two"));
505 QCOMPARE(hash1.key(2, def), QString("two"));
506 QCOMPARE(hash1.key(3), QString());
507 QCOMPARE(hash1.key(3, def), def);
508
509 hash1.insert("deux", 2);
510 QCOMPARE(hash1.key(1), QString("one"));
511 QCOMPARE(hash1.key(1, def), QString("one"));
512 QVERIFY(hash1.key(2) == "deux" || hash1.key(2) == "two");
513 QVERIFY(hash1.key(2, def) == "deux" || hash1.key(2, def) == "two");
514 QCOMPARE(hash1.key(3), QString());
515 QCOMPARE(hash1.key(3, def), def);
516 }
517
518 {
519 int def = 666;
520
521 QHash<int, QString> hash2;
522 QCOMPARE(hash2.key("one"), 0);
523 QCOMPARE(hash2.key("one", def), def);
524
525 hash2.insert(1, "one");
526 QCOMPARE(hash2.key("one"), 1);
527 QCOMPARE(hash2.key("one", def), 1);
528 QCOMPARE(hash2.key("two"), 0);
529 QCOMPARE(hash2.key("two", def), def);
530
531 hash2.insert(2, "two");
532 QCOMPARE(hash2.key("one"), 1);
533 QCOMPARE(hash2.key("one", def), 1);
534 QCOMPARE(hash2.key("two"), 2);
535 QCOMPARE(hash2.key("two", def), 2);
536 QCOMPARE(hash2.key("three"), 0);
537 QCOMPARE(hash2.key("three", def), def);
538
539 hash2.insert(3, "two");
540 QCOMPARE(hash2.key("one"), 1);
541 QCOMPARE(hash2.key("one", def), 1);
542 QCOMPARE(hash2.key("two"), 2);
543 QCOMPARE(hash2.key("two", def), 2);
544 QCOMPARE(hash2.key("three"), 0);
545 QCOMPARE(hash2.key("three", def), def);
546
547 hash2.insert(-1, "two");
548 QCOMPARE(hash2.key("two"), -1);
549 QCOMPARE(hash2.key("two", def), -1);
550
551 hash2.insert(0, "zero");
552 QCOMPARE(hash2.key("zero"), 0);
553 QCOMPARE(hash2.key("zero", def), 0);
554 }
555 }
556
swap()557 void tst_QHash::swap()
558 {
559 QHash<int,QString> h1, h2;
560 h1[0] = "h1[0]";
561 h2[1] = "h2[1]";
562 h1.swap(h2);
563 QCOMPARE(h1.value(1),QLatin1String("h2[1]"));
564 QCOMPARE(h2.value(0),QLatin1String("h1[0]"));
565 }
566
567 // copied from tst_QMap
clear()568 void tst_QHash::clear()
569 {
570 {
571 MyMap map;
572 map.clear();
573 QVERIFY( map.isEmpty() );
574 map.insert( "key", MyClass( "value" ) );
575 map.clear();
576 QVERIFY( map.isEmpty() );
577 map.insert( "key0", MyClass( "value0" ) );
578 map.insert( "key0", MyClass( "value1" ) );
579 map.insert( "key1", MyClass( "value2" ) );
580 map.clear();
581 QVERIFY( map.isEmpty() );
582 }
583 QCOMPARE( MyClass::count, int(0) );
584 }
585 //copied from tst_QMap
empty()586 void tst_QHash::empty()
587 {
588 QHash<int, QString> map1;
589
590 QVERIFY(map1.isEmpty());
591
592 map1.insert(1, "one");
593 QVERIFY(!map1.isEmpty());
594
595 map1.clear();
596 QVERIFY(map1.isEmpty());
597
598 }
599
600 //copied from tst_QMap
find()601 void tst_QHash::find()
602 {
603 QHash<int, QString> map1;
604 QString testString="Teststring %0";
605 QString compareString;
606 int i,count=0;
607
608 //QVERIFY(map1.find(1) == map1.end());
609
610 map1.insert(1,"Mensch");
611 map1.insert(1,"Mayer");
612 map1.insert(2,"Hej");
613
614 QVERIFY(map1.find(1).value() == "Mayer");
615 QVERIFY(map1.find(2).value() == "Hej");
616
617 for(i = 3; i < 10; ++i) {
618 compareString = testString.arg(i);
619 map1.insertMulti(4, compareString);
620 }
621
622 QHash<int, QString>::const_iterator it=map1.find(4);
623
624 for(i = 9; i > 2 && it != map1.end() && it.key() == 4; --i) {
625 compareString = testString.arg(i);
626 QVERIFY(it.value() == compareString);
627 ++it;
628 ++count;
629 }
630 QCOMPARE(count, 7);
631 }
632
633 // copied from tst_QMap
constFind()634 void tst_QHash::constFind()
635 {
636 QHash<int, QString> map1;
637 QString testString="Teststring %0";
638 QString compareString;
639 int i,count=0;
640
641 QVERIFY(map1.constFind(1) == map1.constEnd());
642
643 map1.insert(1,"Mensch");
644 map1.insert(1,"Mayer");
645 map1.insert(2,"Hej");
646
647 QVERIFY(map1.constFind(1).value() == "Mayer");
648 QVERIFY(map1.constFind(2).value() == "Hej");
649
650 for(i = 3; i < 10; ++i) {
651 compareString = testString.arg(i);
652 map1.insertMulti(4, compareString);
653 }
654
655 QHash<int, QString>::const_iterator it=map1.constFind(4);
656
657 for(i = 9; i > 2 && it != map1.constEnd() && it.key() == 4; --i) {
658 compareString = testString.arg(i);
659 QVERIFY(it.value() == compareString);
660 ++it;
661 ++count;
662 }
663 QCOMPARE(count, 7);
664 }
665
666 // copied from tst_QMap
contains()667 void tst_QHash::contains()
668 {
669 QHash<int, QString> map1;
670 int i;
671
672 map1.insert(1, "one");
673 QVERIFY(map1.contains(1));
674
675 for(i=2; i < 100; ++i)
676 map1.insert(i, "teststring");
677 for(i=99; i > 1; --i)
678 QVERIFY(map1.contains(i));
679
680 map1.remove(43);
681 QVERIFY(!map1.contains(43));
682 }
683
684 //copied from tst_QMap
take()685 void tst_QHash::take()
686 {
687 QHash<int, QString> map;
688
689 map.insert(2, "zwei");
690 map.insert(3, "drei");
691
692 QVERIFY(map.take(3) == "drei");
693 QVERIFY(!map.contains(3));
694 }
695
696 //copied from tst_QMap
operator_eq()697 void tst_QHash::operator_eq()
698 {
699 {
700 // compare for equality:
701 QHash<int, int> a;
702 QHash<int, int> b;
703
704 QVERIFY(a == b);
705 QVERIFY(!(a != b));
706
707 a.insert(1,1);
708 b.insert(1,1);
709 QVERIFY(a == b);
710 QVERIFY(!(a != b));
711
712 a.insert(0,1);
713 b.insert(0,1);
714 QVERIFY(a == b);
715 QVERIFY(!(a != b));
716
717 // compare for inequality:
718 a.insert(42,0);
719 QVERIFY(a != b);
720 QVERIFY(!(a == b));
721
722 a.insert(65, -1);
723 QVERIFY(a != b);
724 QVERIFY(!(a == b));
725
726 b.insert(-1, -1);
727 QVERIFY(a != b);
728 QVERIFY(!(a == b));
729 }
730
731 {
732 // a more complex map
733 QHash<QString, QString> a;
734 QHash<QString, QString> b;
735
736 QVERIFY(a == b);
737 QVERIFY(!(a != b));
738
739 a.insert("Hello", "World");
740 QVERIFY(a != b);
741 QVERIFY(!(a == b));
742
743 b.insert("Hello", "World");
744 QVERIFY(a == b);
745 QVERIFY(!(a != b));
746
747 a.insert("Goodbye", "cruel world");
748 QVERIFY(a != b);
749 QVERIFY(!(a == b));
750
751 b.insert("Goodbye", "cruel world");
752
753 // what happens if we insert nulls?
754 a.insert(QString(), QString());
755 QVERIFY(a != b);
756 QVERIFY(!(a == b));
757
758 // empty keys and null keys match:
759 b.insert(QString(""), QString());
760 QVERIFY(a == b);
761 QVERIFY(!(a != b));
762 }
763
764 {
765 // task 102658
766
767 QHash<QString, int> a;
768 QHash<QString, int> b;
769
770 a.insert("otto", 1);
771 b.insert("willy", 1);
772 QVERIFY(a != b);
773 QVERIFY(!(a == b));
774 }
775 }
776
compare()777 void tst_QHash::compare()
778 {
779 QHash<int, QString> hash1,hash2;
780 QString testString = "Teststring %1";
781 int i;
782
783 for(i = 0; i < 1000; ++i)
784 hash1.insert(i,testString.arg(i));
785
786 for(--i; i >= 0; --i)
787 hash2.insert(i,testString.arg(i));
788
789 hash1.squeeze();
790 hash2.squeeze();
791
792 QVERIFY(hash1 == hash2);
793 QVERIFY(!(hash1 != hash2));
794
795 hash1.take(234);
796 hash2.take(234);
797 QVERIFY(hash1 == hash2);
798 QVERIFY(!(hash1 != hash2));
799
800 hash2.take(261);
801 QVERIFY(!(hash1 == hash2));
802 QVERIFY(hash1 != hash2);
803 }
804
compare2()805 void tst_QHash::compare2()
806 {
807 QHash<int, int> a;
808 QHash<int, int> b;
809
810 a.insertMulti(17, 1);
811 a.insertMulti(17 * 2, 1);
812 b.insertMulti(17 * 2, 1);
813 b.insertMulti(17, 1);
814 QVERIFY(a == b);
815 QVERIFY(b == a);
816
817 a.insertMulti(17, 2);
818 a.insertMulti(17 * 2, 3);
819 b.insertMulti(17 * 2, 3);
820 b.insertMulti(17, 2);
821 QVERIFY(a == b);
822 QVERIFY(b == a);
823
824 a.insertMulti(17, 4);
825 a.insertMulti(17 * 2, 5);
826 b.insertMulti(17 * 2, 4);
827 b.insertMulti(17, 5);
828 QVERIFY(!(a == b));
829 QVERIFY(!(b == a));
830
831 a.clear();
832 b.clear();
833 a.insertMulti(1, 1);
834 a.insertMulti(1, 2);
835 a.insertMulti(1, 3);
836 b.insertMulti(1, 1);
837 b.insertMulti(1, 2);
838 b.insertMulti(1, 3);
839 b.insertMulti(1, 4);
840 QVERIFY(!(a == b));
841 QVERIFY(!(b == a));
842 }
843
844 //sligthly modified from tst_QMap
iterators()845 void tst_QHash::iterators()
846 {
847 QHash<int, QString> hash;
848 QMap<int, QString> testMap;
849 QString testString="Teststring %1";
850 QString testString1;
851 int i;
852
853 for(i = 1; i < 100; ++i)
854 hash.insert(i, testString.arg(i));
855
856 //to get some chaos in the hash
857 hash.squeeze();
858
859 //STL-Style iterators
860
861 QHash<int, QString>::iterator stlIt = hash.begin();
862 for(stlIt = hash.begin(), i = 1; stlIt != hash.end(), i < 100; ++stlIt, ++i) {
863 testMap.insert(i,stlIt.value());
864 //QVERIFY(stlIt.value() == hash.value(
865 }
866 stlIt = hash.begin();
867
868 QVERIFY(stlIt.value() == testMap.value(1));
869
870 stlIt+=5;
871 QVERIFY(stlIt.value() == testMap.value(6));
872
873 stlIt++;
874 QVERIFY(stlIt.value() == testMap.value(7));
875
876 stlIt-=3;
877 QVERIFY(stlIt.value() == testMap.value(4));
878
879 stlIt--;
880 QVERIFY(stlIt.value() == testMap.value(3));
881
882 testMap.clear();
883
884 //STL-Style const-iterators
885
886 QHash<int, QString>::const_iterator cstlIt = hash.constBegin();
887 for(cstlIt = hash.constBegin(), i = 1; cstlIt != hash.constEnd(), i < 100; ++cstlIt, ++i) {
888 testMap.insert(i,cstlIt.value());
889 //QVERIFY(stlIt.value() == hash.value(
890 }
891 cstlIt = hash.constBegin();
892
893 QVERIFY(cstlIt.value() == testMap.value(1));
894
895 cstlIt+=5;
896 QVERIFY(cstlIt.value() == testMap.value(6));
897
898 cstlIt++;
899 QVERIFY(cstlIt.value() == testMap.value(7));
900
901 cstlIt-=3;
902 QVERIFY(cstlIt.value() == testMap.value(4));
903
904 cstlIt--;
905 QVERIFY(cstlIt.value() == testMap.value(3));
906
907 testMap.clear();
908
909 //Java-Style iterators
910
911 QHashIterator<int, QString> javaIt(hash);
912
913 //walk through
914 i = 0;
915 while(javaIt.hasNext()) {
916 ++i;
917 javaIt.next();
918 testMap.insert(i,javaIt.value());
919 }
920 javaIt.toFront();
921 i = 0;
922 while(javaIt.hasNext()) {
923 ++i;
924 javaIt.next();
925 //qDebug(javaIt.value());
926 QVERIFY(javaIt.value() == testMap.value(i));
927 }
928
929 ++i;
930 while(javaIt.hasPrevious()) {
931 --i;
932 javaIt.previous();
933 QVERIFY(javaIt.value() == testMap.value(i));
934 }
935
936 /*
937 I've removed findNextKey() and findPreviousKey() from the API
938 for Qt 4.0 beta 1.
939 */
940
941 #if 0
942 //findPreviousKey() findNextKey()
943 for(i = 1; i < 100; ++i) {
944 if(javaIt.findNextKey(i))
945 QVERIFY(javaIt.value() == testString.arg(i));
946 else {
947 QVERIFY(!javaIt.hasNext());
948 QVERIFY(javaIt.findPreviousKey(i));
949 QVERIFY(javaIt.value() == testString.arg(i));
950 }
951
952 if(javaIt.findPreviousKey(i))
953 QVERIFY(javaIt.value() == testString.arg(i));
954 else {
955 QVERIFY(!javaIt.hasPrevious());
956 QVERIFY(javaIt.findNextKey(i));
957 QVERIFY(javaIt.value() == testString.arg(i));
958 }
959 }
960 #endif
961
962 //peekNext() peekPrevious()
963 javaIt.toFront();
964 javaIt.next();
965 while(javaIt.hasNext()) {
966 testString = javaIt.value();
967 testString1 = javaIt.peekNext().value();
968 javaIt.next();
969 //qDebug(testString + " " + testString1 + " " + javaIt.peekPrevious().value());
970 QVERIFY(javaIt.value() == testString1);
971 QCOMPARE(javaIt.peekPrevious().value(), testString1);
972 }
973 while(javaIt.hasPrevious()) {
974 testString = javaIt.value();
975 testString1 = javaIt.peekPrevious().value();
976 javaIt.previous();
977 QVERIFY(javaIt.value() == testString1);
978 //qDebug(testString + testString1 + javaIt.peekNext().value());
979 QCOMPARE(javaIt.peekNext().value(), testString1);
980 }
981 }
982
rehash_isnt_quadratic()983 void tst_QHash::rehash_isnt_quadratic()
984 {
985 // this test should be incredibly slow if rehash() is quadratic
986 for (int j = 0; j < 5; ++j) {
987 QHash<int, int> testHash;
988 #if defined(Q_OS_WINCE) || defined(Q_OS_SYMBIAN) // mobiles do not have infinite mem...
989 for (int i = 0; i < 50000; ++i)
990 #else
991 for (int i = 0; i < 500000; ++i)
992 #endif
993 testHash.insertMulti(1, 1);
994 }
995 }
996
997 class Bar
998 {
999 public:
Bar(int i)1000 Bar(int i) : j(i) {}
1001
1002 int j;
1003 };
1004
dont_need_default_constructor()1005 void tst_QHash::dont_need_default_constructor()
1006 {
1007 QHash<int, Bar> hash1;
1008 for (int i = 0; i < 100; ++i) {
1009 hash1.insert(i, Bar(2 * i));
1010 QVERIFY(hash1.value(i, Bar(-1)).j == 2 * i);
1011 QVERIFY(hash1.size() == i + 1);
1012 }
1013
1014 QHash<QString, Bar> hash2;
1015 for (int i = 0; i < 100; ++i) {
1016 hash2.insert(QString::number(i), Bar(2 * i));
1017 QVERIFY(hash2.value(QString::number(i), Bar(-1)).j == 2 * i);
1018 QVERIFY(hash2.size() == i + 1);
1019 }
1020 }
1021
qhash()1022 void tst_QHash::qhash()
1023 {
1024 {
1025 QBitArray a1;
1026 QBitArray a2;
1027 QVERIFY(qHash(a1) == 0);
1028
1029 a1.resize(1);
1030 a1.setBit(0, true);
1031
1032 a2.resize(1);
1033 a2.setBit(0, false);
1034
1035 uint h1 = qHash(a1);
1036 uint h2 = qHash(a2);
1037
1038 QVERIFY(h1 != h2);
1039
1040 a2.setBit(0, true);
1041 QVERIFY(h1 == qHash(a2));
1042
1043 a1.fill(true, 8);
1044 a1.resize(7);
1045
1046 h1 = qHash(a1);
1047
1048 a2.fill(true, 7);
1049 h2 = qHash(a2);
1050
1051 QVERIFY(h1 == h2);
1052
1053 a2.setBit(0, false);
1054 uint h3 = qHash(a2);
1055 QVERIFY(h2 != h3);
1056
1057 a2.setBit(0, true);
1058 QVERIFY(h2 == qHash(a2));
1059
1060 a2.setBit(6, false);
1061 uint h4 = qHash(a2);
1062 QVERIFY(h2 != h4);
1063
1064 a2.setBit(6, true);
1065 QVERIFY(h2 == qHash(a2));
1066
1067 QVERIFY(h3 != h4);
1068 }
1069
1070 {
1071 QPair<int, int> p12(1, 2);
1072 QPair<int, int> p21(2, 1);
1073
1074 QVERIFY(qHash(p12) == qHash(p12));
1075 QVERIFY(qHash(p21) == qHash(p21));
1076 QVERIFY(qHash(p12) != qHash(p21));
1077
1078 QPair<int, int> pA(0x12345678, 0x12345678);
1079 QPair<int, int> pB(0x12345675, 0x12345675);
1080
1081 QVERIFY(qHash(pA) != qHash(pB));
1082 }
1083 }
1084
qmultihash_specific()1085 void tst_QHash::qmultihash_specific()
1086 {
1087 QMultiHash<int, int> hash1;
1088 for (int i = 1; i <= 9; ++i) {
1089 for (int j = 1; j <= i; ++j) {
1090 int k = i * 10 + j;
1091 QVERIFY(!hash1.contains(i, k));
1092 hash1.insert(i, k);
1093 QVERIFY(hash1.contains(i, k));
1094 }
1095 }
1096
1097 for (int i = 1; i <= 9; ++i) {
1098 for (int j = 1; j <= i; ++j) {
1099 int k = i * 10 + j;
1100 QVERIFY(hash1.contains(i, k));
1101 }
1102 }
1103
1104 QVERIFY(hash1.contains(9, 99));
1105 QCOMPARE(hash1.count(), 45);
1106 hash1.remove(9, 99);
1107 QVERIFY(!hash1.contains(9, 99));
1108 QCOMPARE(hash1.count(), 44);
1109
1110 hash1.remove(9, 99);
1111 QVERIFY(!hash1.contains(9, 99));
1112 QCOMPARE(hash1.count(), 44);
1113
1114 hash1.remove(1, 99);
1115 QCOMPARE(hash1.count(), 44);
1116
1117 hash1.insert(1, 99);
1118 hash1.insert(1, 99);
1119
1120 QCOMPARE(hash1.count(), 46);
1121 hash1.remove(1, 99);
1122 QCOMPARE(hash1.count(), 44);
1123 hash1.remove(1, 99);
1124 QCOMPARE(hash1.count(), 44);
1125
1126 {
1127 QMultiHash<int, int>::const_iterator i = hash1.constFind(1, 11);
1128 QVERIFY(i.key() == 1);
1129 QVERIFY(i.value() == 11);
1130
1131 i = hash1.constFind(2, 22);
1132 QVERIFY(i.key() == 2);
1133 QVERIFY(i.value() == 22);
1134
1135 i = hash1.constFind(9, 98);
1136 QVERIFY(i.key() == 9);
1137 QVERIFY(i.value() == 98);
1138 }
1139
1140 {
1141 const QMultiHash<int, int> hash2(hash1);
1142 QMultiHash<int, int>::const_iterator i = hash2.find(1, 11);
1143 QVERIFY(i.key() == 1);
1144 QVERIFY(i.value() == 11);
1145
1146 i = hash2.find(2, 22);
1147 QVERIFY(i.key() == 2);
1148 QVERIFY(i.value() == 22);
1149
1150 i = hash2.find(9, 98);
1151 QVERIFY(i.key() == 9);
1152 QVERIFY(i.value() == 98);
1153 }
1154
1155 {
1156 QMultiHash<int, int>::iterator i = hash1.find(1, 11);
1157 QVERIFY(i.key() == 1);
1158 QVERIFY(i.value() == 11);
1159
1160 i = hash1.find(2, 22);
1161 QVERIFY(i.key() == 2);
1162 QVERIFY(i.value() == 22);
1163
1164 i = hash1.find(9, 98);
1165 QVERIFY(i.key() == 9);
1166 QVERIFY(i.value() == 98);
1167 }
1168
1169 {
1170 QMultiHash<int, int> map1;
1171 map1.insert(42, 1);
1172 map1.insert(10, 2);
1173 map1.insert(48, 3);
1174 QMultiHash<int, int> map2;
1175 map2.insert(8, 4);
1176 map2.insert(42, 5);
1177 map2.insert(95, 12);
1178
1179 map1+=map2;
1180 map2.insert(42, 1);
1181 map2.insert(10, 2);
1182 map2.insert(48, 3);
1183 QCOMPARE(map1.count(), map2.count());
1184 QVERIFY(map1.remove(42,5));
1185 QVERIFY(map2.remove(42,5));
1186 QVERIFY(map1 == map2);
1187 }
1188 }
1189
1190 template <typename T>
sorted(const QList<T> & list)1191 QList<T> sorted(const QList<T> &list)
1192 {
1193 QList<T> res = list;
1194 qSort(res);
1195 return res;
1196 }
1197
keys_values_uniqueKeys()1198 void tst_QHash::keys_values_uniqueKeys()
1199 {
1200 QHash<QString, int> hash;
1201 QVERIFY(hash.uniqueKeys().isEmpty());
1202 QVERIFY(hash.keys().isEmpty());
1203 QVERIFY(hash.values().isEmpty());
1204
1205 hash.insertMulti("alpha", 1);
1206 QVERIFY(sorted(hash.keys()) == (QList<QString>() << "alpha"));
1207 QVERIFY(hash.keys() == hash.uniqueKeys());
1208 QVERIFY(hash.values() == (QList<int>() << 1));
1209
1210 hash.insertMulti("beta", -2);
1211 QVERIFY(sorted(hash.keys()) == (QList<QString>() << "alpha" << "beta"));
1212 QVERIFY(hash.keys() == hash.uniqueKeys());
1213 QVERIFY(sorted(hash.values()) == sorted(QList<int>() << 1 << -2));
1214
1215 hash.insertMulti("alpha", 2);
1216 QVERIFY(sorted(hash.uniqueKeys()) == (QList<QString>() << "alpha" << "beta"));
1217 QVERIFY(sorted(hash.keys()) == (QList<QString>() << "alpha" << "alpha" << "beta"));
1218 QVERIFY(sorted(hash.values()) == sorted(QList<int>() << 2 << 1 << -2));
1219
1220 hash.insertMulti("beta", 4);
1221 QVERIFY(sorted(hash.uniqueKeys()) == (QList<QString>() << "alpha" << "beta"));
1222 QVERIFY(sorted(hash.keys()) == (QList<QString>() << "alpha" << "alpha" << "beta" << "beta"));
1223 QVERIFY(sorted(hash.values()) == sorted(QList<int>() << 2 << 1 << 4 << -2));
1224 }
1225
noNeedlessRehashes()1226 void tst_QHash::noNeedlessRehashes()
1227 {
1228 QHash<int, int> hash;
1229 for (int i = 0; i < 512; ++i) {
1230 int j = (i * 345) % 512;
1231 hash.insert(j, j);
1232 int oldCapacity = hash.capacity();
1233 hash[j] = j + 1;
1234 QCOMPARE(oldCapacity, hash.capacity());
1235 hash.insert(j, j + 1);
1236 QCOMPARE(oldCapacity, hash.capacity());
1237 }
1238 }
1239
1240 QTEST_APPLESS_MAIN(tst_QHash)
1241 #include "tst_qhash.moc"
1242