tst_QHash: check which of several equal keys is inserted

Add a test that checks that QHash keeps the first of the keys
that compare equal. This may or may not be documented, but is
inconsistent with the values in a QHash, where the last element
with equal key is kept.

Document this as a test. That way, we'll be informed when the
behavior changes (e.g. by a port to std::unordered_map).

Do the equivalent checks in tst_QMap, too. There, of course,
instead of equal keys, check equivalent ones.

Change-Id: I2c5f04f8e8a6bbc7dbaadadd878a4c876e4df042
Reviewed-by: Olivier Goffart <ogoffart@woboq.com>

2 files changed, 67 insertions, 0 deletions

diff --git a/tests/auto/corelib/tools/qhash/tst_qhash.cpp b/tests/auto/corelib/tools/qhash/tst_qhash.cpp
index 77baed87c2..7e8fc234de 100644
--- a/tests/auto/corelib/tools/qhash/tst_qhash.cpp
+++ b/tests/auto/corelib/tools/qhash/tst_qhash.cpp
@@ -84,6 +84,14 @@ private slots:
     void eraseValidIteratorOnSharedHash();
 };
 
+struct IdentityTracker {
+    int value, id;
+};
+
+inline uint qHash(IdentityTracker key) { return qHash(key.value); }
+inline bool operator==(IdentityTracker lhs, IdentityTracker rhs) { return lhs.value == rhs.value; }
+
+
 struct Foo {
     static int count;
     Foo():c(count) { ++count; }
@@ -443,6 +451,32 @@ void tst_QHash::insert1()
             QVERIFY(((const QHash<int,int*>*) &hash)->operator[](7) == 0);
         }
     }
+    {
+        QHash<IdentityTracker, int> hash;
+        QCOMPARE(hash.size(), 0);
+        const int dummy = -1;
+        IdentityTracker id00 = {0, 0}, id01 = {0, 1}, searchKey = {0, dummy};
+        QCOMPARE(hash.insert(id00, id00.id).key().id, id00.id);
+        QCOMPARE(hash.size(), 1);
+        QCOMPARE(hash.insert(id01, id01.id).key().id, id00.id); // first key inserted is kept
+        QCOMPARE(hash.size(), 1);
+        QCOMPARE(hash.find(searchKey).value(), id01.id);  // last-inserted value
+        QCOMPARE(hash.find(searchKey).key().id, id00.id); // but first-inserted key
+    }
+    {
+        QMultiHash<IdentityTracker, int> hash;
+        QCOMPARE(hash.size(), 0);
+        const int dummy = -1;
+        IdentityTracker id00 = {0, 0}, id01 = {0, 1}, searchKey = {0, dummy};
+        QCOMPARE(hash.insert(id00, id00.id).key().id, id00.id);
+        QCOMPARE(hash.size(), 1);
+        QCOMPARE(hash.insert(id01, id01.id).key().id, id01.id);
+        QCOMPARE(hash.size(), 2);
+        QMultiHash<IdentityTracker, int>::const_iterator pos = hash.constFind(searchKey);
+        QCOMPARE(pos.value(), pos.key().id); // key fits to value it was inserted with
+        ++pos;
+        QCOMPARE(pos.value(), pos.key().id); // key fits to value it was inserted with
+    }
 }
 
 void tst_QHash::erase()
diff --git a/tests/auto/corelib/tools/qmap/tst_qmap.cpp b/tests/auto/corelib/tools/qmap/tst_qmap.cpp
index 3daab73cc2..108dc35907 100644
--- a/tests/auto/corelib/tools/qmap/tst_qmap.cpp
+++ b/tests/auto/corelib/tools/qmap/tst_qmap.cpp
@@ -89,6 +89,12 @@ private slots:
     void eraseValidIteratorOnSharedMap();
 };
 
+struct IdentityTracker {
+    int value, id;
+};
+
+inline bool operator<(IdentityTracker lhs, IdentityTracker rhs) { return lhs.value < rhs.value; }
+
 typedef QMap<QString, QString> StringMap;
 
 class MyClass
@@ -1122,6 +1128,33 @@ void tst_QMap::insert()
         QCOMPARE(intMap.size(), 1000);
         QCOMPARE(intMap.value(i), -1);
     }
+
+    {
+        QMap<IdentityTracker, int> map;
+        QCOMPARE(map.size(), 0);
+        const int dummy = -1;
+        IdentityTracker id00 = {0, 0}, id01 = {0, 1}, searchKey = {0, dummy};
+        QCOMPARE(map.insert(id00, id00.id).key().id, id00.id);
+        QCOMPARE(map.size(), 1);
+        QCOMPARE(map.insert(id01, id01.id).key().id, id00.id); // first key inserted is kept
+        QCOMPARE(map.size(), 1);
+        QCOMPARE(map.find(searchKey).value(), id01.id);  // last-inserted value
+        QCOMPARE(map.find(searchKey).key().id, id00.id); // but first-inserted key
+    }
+    {
+        QMultiMap<IdentityTracker, int> map;
+        QCOMPARE(map.size(), 0);
+        const int dummy = -1;
+        IdentityTracker id00 = {0, 0}, id01 = {0, 1}, searchKey = {0, dummy};
+        QCOMPARE(map.insert(id00, id00.id).key().id, id00.id);
+        QCOMPARE(map.size(), 1);
+        QCOMPARE(map.insert(id01, id01.id).key().id, id01.id);
+        QCOMPARE(map.size(), 2);
+        QMultiMap<IdentityTracker, int>::const_iterator pos = map.constFind(searchKey);
+        QCOMPARE(pos.value(), pos.key().id); // key fits to value it was inserted with
+        ++pos;
+        QCOMPARE(pos.value(), pos.key().id); // key fits to value it was inserted with
+    }
 }
 
 void tst_QMap::checkMostLeftNode()