QHash: add support for heterogeneous key lookups

This implements support in QHash and QMultiHash for lookups of
heterogeneous key types that produce the same hash value. This is
implemented by duplicating each of the following functions into an
overload on Key and one a template that is enable_if-constrained to a
key type that meets the requirement:
 * contains
 * count
 * equals_range
 * find
 * operator[] (const only)
 * remove
 * take
 * value
 * values (QMultiHash)

The non-const operator[] may insert into the hash, so it's not part of
this commit.

Change-Id: I664b9f014ffc48cbb49bfffd17b037852f0fd192
Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>

1 files changed, 263 insertions, 24 deletions

diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h
index 781ea1a157..0ce33759d0 100644
--- a/src/corelib/tools/qhash.h
+++ b/src/corelib/tools/qhash.h
@@ -677,8 +677,10 @@ struct Data
         return size >= (numBuckets >> 1);
     }
 
-    Bucket findBucket(const Key &key) const noexcept
+    template <typename K> Bucket findBucket(const K &key) const noexcept
     {
+        static_assert(std::is_same_v<std::remove_cv_t<Key>, K> ||
+                QHashHeterogeneousSearch<std::remove_cv_t<Key>, K>::value);
         Q_ASSERT(numBuckets > 0);
         size_t hash = QHashPrivate::calculateHash(key, seed);
         Bucket bucket(this, GrowthPolicy::bucketForHash(numBuckets, hash));
@@ -697,7 +699,7 @@ struct Data
         }
     }
 
-    Node *findNode(const Key &key) const noexcept
+    template <typename K> Node *findNode(const K &key) const noexcept
     {
         auto bucket = findBucket(key);
         if (bucket.isUnused())
@@ -955,6 +957,11 @@ public:
 
     bool remove(const Key &key)
     {
+        return removeImpl(key);
+    }
+private:
+    template <typename K> bool removeImpl(const K &key)
+    {
         if (isEmpty()) // prevents detaching shared null
             return false;
         auto it = d->findBucket(key);
@@ -967,13 +974,21 @@ public:
         d->erase(it);
         return true;
     }
+
+public:
     template <typename Predicate>
     qsizetype removeIf(Predicate pred)
     {
         return QtPrivate::associative_erase_if(*this, pred);
     }
+
     T take(const Key &key)
     {
+        return takeImpl(key);
+    }
+private:
+    template <typename K> T takeImpl(const K &key)
+    {
         if (isEmpty()) // prevents detaching shared null
             return T();
         auto it = d->findBucket(key);
@@ -988,6 +1003,7 @@ public:
         return value;
     }
 
+public:
     bool contains(const Key &key) const noexcept
     {
         if (!d)
@@ -1025,7 +1041,7 @@ public:
     }
 
 private:
-    template <typename Fn> T valueImpl(const Key &key, Fn &&defaultValue) const noexcept
+    template <typename K, typename Fn> T valueImpl(const K &key, Fn &&defaultValue) const noexcept
     {
         if (d) {
             Node *n = d->findNode(key);
@@ -1240,11 +1256,7 @@ private:
         return std::make_pair(first, second);
     }
 
-public:
-    typedef iterator Iterator;
-    typedef const_iterator ConstIterator;
-    inline qsizetype count() const noexcept { return d ? qsizetype(d->size) : 0; }
-    iterator find(const Key &key)
+    template <typename K> iterator findImpl(const K &key)
     {
         if (isEmpty()) // prevents detaching shared null
             return end();
@@ -1256,7 +1268,7 @@ public:
             return end();
         return iterator(it.toIterator(d));
     }
-    const_iterator find(const Key &key) const noexcept
+    template <typename K> const_iterator constFindImpl(const K &key) const noexcept
     {
         if (isEmpty())
             return end();
@@ -1265,6 +1277,19 @@ public:
             return end();
         return const_iterator({d, it.toBucketIndex(d)});
     }
+
+public:
+    typedef iterator Iterator;
+    typedef const_iterator ConstIterator;
+    inline qsizetype count() const noexcept { return d ? qsizetype(d->size) : 0; }
+    iterator find(const Key &key)
+    {
+        return findImpl(key);
+    }
+    const_iterator find(const Key &key) const noexcept
+    {
+        return constFindImpl(key);
+    }
     const_iterator constFind(const Key &key) const noexcept
     {
         return find(key);
@@ -1328,8 +1353,61 @@ private:
             result.it.node()->emplaceValue(std::forward<Args>(args)...);
         return iterator(result.it);
     }
-};
 
+public:
+#ifdef __cpp_concepts
+    bool remove(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key)
+    {
+        return removeImpl(key);
+    }
+    T take(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key)
+    {
+        return takeImpl(key);
+    }
+    bool contains(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key)
+    {
+        return d ? d->findNode(key) != nullptr : false;
+    }
+    qsizetype count(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key)
+    {
+        return contains(key) ? 1 : 0;
+    }
+    T value(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) const noexcept
+    {
+        return valueImpl(key, [] { return T(); });
+    }
+    T value(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key, const T &defaultValue) const noexcept
+    {
+        return valueImpl(key, [&] { return defaultValue; });
+    }
+    const T operator[](const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) const noexcept
+    {
+        return value(key);
+    }
+    std::pair<iterator, iterator>
+    equal_range(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key)
+    {
+        return equal_range_impl(*this, key);
+    }
+    std::pair<const_iterator, const_iterator>
+    equal_range(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) const noexcept
+    {
+        return equal_range_impl(*this, key);
+    }
+    iterator find(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key)
+    {
+        return findImpl(key);
+    }
+    const_iterator find(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) const noexcept
+    {
+        return constFindImpl(key);
+    }
+    const_iterator constFind(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) const noexcept
+    {
+        return find(key);
+    }
+#endif // __cpp_concepts
+};
 
 
 template <typename Key, typename T>
@@ -1507,6 +1585,11 @@ public:
 
     qsizetype remove(const Key &key)
     {
+        return removeImpl(key);
+    }
+private:
+    template <typename K> qsizetype removeImpl(const K &key)
+    {
         if (isEmpty()) // prevents detaching shared null
             return 0;
         auto it = d->findBucket(key);
@@ -1522,13 +1605,21 @@ public:
         d->erase(it);
         return n;
     }
+
+public:
     template <typename Predicate>
     qsizetype removeIf(Predicate pred)
     {
         return QtPrivate::associative_erase_if(*this, pred);
     }
+
     T take(const Key &key)
     {
+        return takeImpl(key);
+    }
+private:
+    template <typename K> T takeImpl(const K &key)
+    {
         if (isEmpty()) // prevents detaching shared null
             return T();
         auto it = d->findBucket(key);
@@ -1553,6 +1644,7 @@ public:
         return t;
     }
 
+public:
     bool contains(const Key &key) const noexcept
     {
         if (!d)
@@ -1586,7 +1678,7 @@ public:
     }
 
 private:
-    template <typename Fn> T valueImpl(const Key &key, Fn &&defaultValue) const noexcept
+    template <typename K, typename Fn> T valueImpl(const K &key, Fn &&defaultValue) const noexcept
     {
         if (d) {
             Node *n = d->findNode(key);
@@ -1650,9 +1742,15 @@ public:
         }
         return res;
     }
+
     QList<T> values() const { return QList<T>(begin(), end()); }
     QList<T> values(const Key &key) const
     {
+        return valuesImpl(key);
+    }
+private:
+    template <typename K> QList<T> valuesImpl(const K &key) const
+    {
         QList<T> values;
         if (d) {
             Node *n = d->findNode(key);
@@ -1667,6 +1765,7 @@ public:
         return values;
     }
 
+public:
     class const_iterator;
 
     class iterator
@@ -1878,7 +1977,9 @@ public:
     typedef iterator Iterator;
     typedef const_iterator ConstIterator;
     inline qsizetype count() const noexcept { return size(); }
-    iterator find(const Key &key)
+
+private:
+    template <typename K> iterator findImpl(const K &key)
     {
         if (isEmpty())
             return end();
@@ -1891,11 +1992,7 @@ public:
             return end();
         return iterator(it.toIterator(d));
     }
-    const_iterator find(const Key &key) const noexcept
-    {
-        return constFind(key);
-    }
-    const_iterator constFind(const Key &key) const noexcept
+    template <typename K> const_iterator constFindImpl(const K &key) const noexcept
     {
         if (isEmpty())
             return end();
@@ -1904,6 +2001,20 @@ public:
             return constEnd();
         return const_iterator(it.toIterator(d));
     }
+public:
+    iterator find(const Key &key)
+    {
+        return findImpl(key);
+    }
+    const_iterator constFind(const Key &key) const noexcept
+    {
+        return constFindImpl(key);
+    }
+    const_iterator find(const Key &key) const noexcept
+    {
+        return constFindImpl(key);
+    }
+
     iterator insert(const Key &key, const T &value)
     {
         return emplace(key, value);
@@ -1969,6 +2080,11 @@ public:
 
     bool contains(const Key &key, const T &value) const noexcept
     {
+        return containsImpl(key, value);
+    }
+private:
+    template <typename K> bool containsImpl(const K &key, const T &value) const noexcept
+    {
         if (isEmpty())
             return false;
         auto n = d->findNode(key);
@@ -1977,8 +2093,14 @@ public:
         return n->value->contains(value);
     }
 
+public:
     qsizetype remove(const Key &key, const T &value)
     {
+        return removeImpl(key, value);
+    }
+private:
+    template <typename K> qsizetype removeImpl(const K &key, const T &value)
+    {
         if (isEmpty()) // prevents detaching shared null
             return 0;
         auto it = d->findBucket(key);
@@ -2007,8 +2129,14 @@ public:
         return n;
     }
 
+public:
     qsizetype count(const Key &key) const noexcept
     {
+        return countImpl(key);
+    }
+private:
+    template <typename K> qsizetype countImpl(const K &key) const noexcept
+    {
         if (!d)
             return 0;
         auto it = d->findBucket(key);
@@ -2024,8 +2152,14 @@ public:
         return n;
     }
 
+public:
     qsizetype count(const Key &key, const T &value) const noexcept
     {
+        return countImpl(key, value);
+    }
+private:
+    template <typename K> qsizetype countImpl(const K &key, const T &value) const noexcept
+    {
         if (!d)
             return 0;
         auto it = d->findBucket(key);
@@ -2042,7 +2176,7 @@ public:
         return n;
     }
 
-    iterator find(const Key &key, const T &value)
+    template <typename K> iterator findImpl(const K &key, const T &value)
     {
         if (isEmpty())
             return end();
@@ -2051,11 +2185,7 @@ public:
         auto it = constFind(key, value);
         return iterator(it.i, it.e);
     }
-    const_iterator find(const Key &key, const T &value) const noexcept
-    {
-        return constFind(key, value);
-    }
-    const_iterator constFind(const Key &key, const T &value) const noexcept
+    template <typename K> const_iterator constFindImpl(const K &key, const T &value) const noexcept
     {
         const_iterator i(constFind(key));
         const_iterator end(constEnd());
@@ -2067,6 +2197,21 @@ public:
         return end;
     }
 
+public:
+    iterator find(const Key &key, const T &value)
+    {
+        return findImpl(key, value);
+    }
+
+    const_iterator constFind(const Key &key, const T &value) const noexcept
+    {
+        return constFindImpl(key, value);
+    }
+    const_iterator find(const Key &key, const T &value) const noexcept
+    {
+        return constFind(key, value);
+    }
+
     QMultiHash &unite(const QMultiHash &other)
     {
         if (isEmpty()) {
@@ -2104,14 +2249,25 @@ public:
 
     std::pair<iterator, iterator> equal_range(const Key &key)
     {
+        return equal_range_impl(key);
+    }
+private:
+    template <typename K> std::pair<iterator, iterator> equal_range_impl(const K &key)
+    {
         const auto copy = isDetached() ? QMultiHash() : *this; // keep 'key' alive across the detach
         detach();
         auto pair = std::as_const(*this).equal_range(key);
         return {iterator(pair.first.i), iterator(pair.second.i)};
     }
 
+public:
     std::pair<const_iterator, const_iterator> equal_range(const Key &key) const noexcept
     {
+        return equal_range_impl(key);
+    }
+private:
+    template <typename K> std::pair<const_iterator, const_iterator> equal_range_impl(const K &key) const noexcept
+    {
         if (!d)
             return {end(), end()};
 
@@ -2124,7 +2280,6 @@ public:
         return {const_iterator(it), const_iterator(end)};
     }
 
-private:
     void detach_helper()
     {
         if (!d) {
@@ -2161,6 +2316,90 @@ private:
         }
         return iterator(result.it);
     }
+
+public:
+#ifdef __cpp_concepts
+    qsizetype remove(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key)
+    {
+        return removeImpl(key);
+    }
+    T take(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key)
+    {
+        return takeImpl(key);
+    }
+    bool contains(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) const noexcept
+    {
+        if (!d)
+            return false;
+        return d->findNode(key) != nullptr;
+    }
+    T value(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) const noexcept
+    {
+        return valueImpl(key, [] { return T(); });
+    }
+    T value(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key, const T &defaultValue) const noexcept
+    {
+        return valueImpl(key, [&] { return defaultValue; });
+    }
+    const T operator[](const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) const noexcept
+    {
+        return value(key);
+    }
+    QList<T> values(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key)
+    {
+        return valuesImpl(key);
+    }
+    iterator find(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key)
+    {
+        return findImpl(key);
+    }
+    const_iterator constFind(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) const noexcept
+    {
+        return constFindImpl(key);
+    }
+    const_iterator find(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) const noexcept
+    {
+        return constFindImpl(key);
+    }
+    bool contains(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key, const T &value) const noexcept
+    {
+        return containsImpl(key, value);
+    }
+    qsizetype remove(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key, const T &value)
+    {
+        return removeImpl(key, value);
+    }
+    qsizetype count(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) const noexcept
+    {
+        return countImpl(key);
+    }
+    qsizetype count(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key, const T &value) const noexcept
+    {
+        return countImpl(key, value);
+    }
+    iterator find(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key, const T &value)
+    {
+        return findImpl(key, value);
+    }
+    const_iterator constFind(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key, const T &value) const noexcept
+    {
+        return constFindImpl(key, value);
+    }
+    const_iterator find(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key, const T &value) const noexcept
+    {
+        return constFind(key, value);
+    }
+    std::pair<iterator, iterator>
+    equal_range(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key)
+    {
+        return equal_range_impl(key);
+    }
+    std::pair<const_iterator, const_iterator>
+    equal_range(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) const noexcept
+    {
+        return equal_range_impl(key);
+    }
+#endif // __cpp_concepts
 };
 
 Q_DECLARE_ASSOCIATIVE_FORWARD_ITERATOR(Hash)