diff options
| -rw-r--r-- | src/corelib/doc/snippets/code/src_corelib_tools_qhash.cpp | 10 | ||||
| -rw-r--r-- | src/corelib/tools/qhash.cpp | 40 | ||||
| -rw-r--r-- | src/corelib/tools/qhash.h | 46 | ||||
| -rw-r--r-- | tests/auto/corelib/tools/qhash/tst_qhash.cpp | 86 |
4 files changed, 170 insertions, 12 deletions
diff --git a/src/corelib/doc/snippets/code/src_corelib_tools_qhash.cpp b/src/corelib/doc/snippets/code/src_corelib_tools_qhash.cpp index 77981075a2..ee9f88fc65 100644 --- a/src/corelib/doc/snippets/code/src_corelib_tools_qhash.cpp +++ b/src/corelib/doc/snippets/code/src_corelib_tools_qhash.cpp @@ -350,3 +350,13 @@ size_t qHash(const K &key); size_t qHash(K key, size_t seed); size_t qHash(const K &key, size_t seed); //! [32] + +//! [33] +namespace std { +template <> struct hash<K> +{ + // seed is optional + size_t operator()(const K &key, size_t seed = 0) const; +}; +} +//! [33] diff --git a/src/corelib/tools/qhash.cpp b/src/corelib/tools/qhash.cpp index 112a492526..8a94695ec3 100644 --- a/src/corelib/tools/qhash.cpp +++ b/src/corelib/tools/qhash.cpp @@ -1194,22 +1194,26 @@ size_t qHash(long double key, size_t seed) noexcept instead, store a QWidget *. \target qHash - \section2 The qHash() hashing function + \section2 The hashing function A QHash's key type has additional requirements other than being an assignable data type: it must provide operator==(), and there must also be - a qHash() function in the type's namespace that returns a hash value for an - argument of the key's type. + a hashing function that returns a hash value for an argument of the + key's type. - The qHash() function computes a numeric value based on a key. It + The hashing function computes a numeric value based on a key. It can use any algorithm imaginable, as long as it always returns the same value if given the same argument. In other words, if - \c{e1 == e2}, then \c{qHash(e1) == qHash(e2)} must hold as well. - However, to obtain good performance, the qHash() function should + \c{e1 == e2}, then \c{hash(e1) == hash(e2)} must hold as well. + However, to obtain good performance, the hashing function should attempt to return different hash values for different keys to the largest extent possible. - For a key type \c{K}, the qHash function must have one of these signatures: + A hashing function for a key type \c{K} may be provided in two + different ways. + + The first way is by having an overload of \c{qHash()} in \c{K}'s + namespace. The \c{qHash()} function must have one of these signatures: \snippet code/src_corelib_tools_qhash.cpp 32 @@ -1220,6 +1224,20 @@ size_t qHash(long double key, size_t seed) noexcept the latter is used by QHash (note that you can simply define a two-arguments version, and use a default value for the seed parameter). + The second way to provide a hashing function is by specializing + the \c{std::hash} class for the key type \c{K}, and providing a + suitable function call operator for it: + + \snippet code/src_corelib_tools_qhash.cpp 33 + + The seed argument has the same meaning as for \c{qHash()}, + and may be left out. + + This second way allows to reuse the same hash function between + QHash and the C++ Standard Library unordered associative containers. + If both a \c{qHash()} overload and a \c{std::hash} specializations + are provided for a type, then the \c{qHash()} overload is preferred. + Here's a partial list of the C++ and Qt types that can serve as keys in a QHash: any integer type (char, unsigned long, etc.), any pointer type, QChar, QString, and QByteArray. For all of these, the \c <QHash> header @@ -1228,9 +1246,11 @@ size_t qHash(long double key, size_t seed) noexcept the documentation of each class. If you want to use other types as the key, make sure that you provide - operator==() and a qHash() implementation. The convenience qHashMulti() - function can be used to implement qHash() for a custom type, where - one usually wants to produce a hash value from multiple fields: + operator==() and a hash implementation. + + The convenience qHashMulti() function can be used to implement + qHash() for a custom type, where one usually wants to produce a + hash value from multiple fields: Example: \snippet code/src_corelib_tools_qhash.cpp 13 diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h index 5dc88943fc..8134f4402c 100644 --- a/src/corelib/tools/qhash.h +++ b/src/corelib/tools/qhash.h @@ -1,6 +1,7 @@ /**************************************************************************** ** ** Copyright (C) 2020 The Qt Company Ltd. +** Copyright (C) 2020 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Giuseppe D'Angelo <giuseppe.dangelo@kdab.com> ** Contact: https://www.qt.io/licensing/ ** ** This file is part of the QtCore module of the Qt Toolkit. @@ -48,6 +49,7 @@ #include <QtCore/qrefcount.h> #include <initializer_list> +#include <functional> // for std::hash QT_BEGIN_NAMESPACE @@ -58,6 +60,46 @@ struct QHashDummyValue namespace QHashPrivate { +template <typename T, typename = void> +constexpr inline bool HasQHashOverload = false; + +template <typename T> +constexpr inline bool HasQHashOverload<T, std::enable_if_t< + std::is_convertible_v<decltype(qHash(std::declval<const T &>(), std::declval<size_t>())), size_t> +>> = true; + +template <typename T, typename = void> +constexpr inline bool HasStdHashSpecializationWithSeed = false; + +template <typename T> +constexpr inline bool HasStdHashSpecializationWithSeed<T, std::enable_if_t< + std::is_convertible_v<decltype(std::hash<T>()(std::declval<const T &>(), std::declval<size_t>())), size_t> +>> = true; + +template <typename T, typename = void> +constexpr inline bool HasStdHashSpecializationWithoutSeed = false; + +template <typename T> +constexpr inline bool HasStdHashSpecializationWithoutSeed<T, std::enable_if_t< + std::is_convertible_v<decltype(std::hash<T>()(std::declval<const T &>())), size_t> +>> = true; + +template <typename T> +size_t calculateHash(const T &t, size_t seed) +{ + if constexpr (HasQHashOverload<T>) { + return qHash(t, seed); + } else if constexpr (HasStdHashSpecializationWithSeed<T>) { + return std::hash<T>()(t, seed); + } else if constexpr (HasStdHashSpecializationWithoutSeed<T>) { + Q_UNUSED(seed); + return std::hash<T>()(t); + } else { + static_assert(sizeof(T) == 0, "The key type must have a qHash overload or a std::hash specialization"); + return 0; + } +} + // QHash uses a power of two growth policy. namespace GrowthPolicy { inline constexpr size_t maxNumBuckets() noexcept @@ -545,7 +587,7 @@ struct Data iterator find(const Key &key) const noexcept { Q_ASSERT(numBuckets > 0); - size_t hash = qHash(key, seed); + size_t hash = QHashPrivate::calculateHash(key, seed); size_t bucket = GrowthPolicy::bucketForHash(numBuckets, hash); // loop over the buckets until we find the entry we search for // or an empty slot, in which case we know the entry doesn't exist @@ -614,7 +656,7 @@ struct Data size_t nextIndex = next & Span::LocalBucketMask; if (!spans[nextSpan].hasNode(nextIndex)) break; - size_t hash = qHash(spans[nextSpan].at(nextIndex).key, seed); + size_t hash = QHashPrivate::calculateHash(spans[nextSpan].at(nextIndex).key, seed); size_t newBucket = GrowthPolicy::bucketForHash(numBuckets, hash); while (true) { if (newBucket == next) { diff --git a/tests/auto/corelib/tools/qhash/tst_qhash.cpp b/tests/auto/corelib/tools/qhash/tst_qhash.cpp index f61dfda720..c6e26f24c0 100644 --- a/tests/auto/corelib/tools/qhash/tst_qhash.cpp +++ b/tests/auto/corelib/tools/qhash/tst_qhash.cpp @@ -33,6 +33,8 @@ #include <algorithm> #include <vector> +#include <unordered_set> +#include <string> class tst_QHash : public QObject { @@ -76,6 +78,8 @@ private slots: void badHashFunction(); void hashOfHash(); + + void stdHash(); }; struct IdentityTracker { @@ -1883,5 +1887,87 @@ void tst_QHash::hashOfHash() (void)qHash(multiHash); } +template <bool HasQHash_> +struct StdHashKeyType { + static inline constexpr bool HasQHash = HasQHash_; + static bool StdHashUsed; + + int i; + friend bool operator==(const StdHashKeyType &lhs, const StdHashKeyType &rhs) + { return lhs.i == rhs.i; } +}; + +template <bool HasQHash> +bool StdHashKeyType<HasQHash>::StdHashUsed = false; + +namespace std { +template <bool HasQHash> struct hash<StdHashKeyType<HasQHash>> +{ + size_t operator()(const StdHashKeyType<HasQHash> &s, size_t seed = 0) const { + StdHashKeyType<HasQHash>::StdHashUsed = true; + return hash<int>()(s.i) ^ seed; + } +}; +} + +template <bool HasQHash> +std::enable_if_t<HasQHash, size_t> +qHash(const StdHashKeyType<HasQHash> &s, size_t seed) +{ + return qHash(s.i, seed); +} + +template <typename T> +void stdHashImpl() +{ + QHash<T, int> hash; + for (int i = 0; i < 1000; ++i) + hash.insert(T{i}, i); + + QCOMPARE(hash.size(), 1000); + for (int i = 0; i < 1000; ++i) + QCOMPARE(hash.value(T{i}, -1), i); + + for (int i = 500; i < 1500; ++i) + hash.insert(T{i}, i); + + QCOMPARE(hash.size(), 1500); + for (int i = 0; i < 1500; ++i) + QCOMPARE(hash.value(T{i}, -1), i); + + qsizetype count = 0; + for (int i = -2000; i < 2000; ++i) { + if (hash.contains(T{i})) + ++count; + } + QCOMPARE(count, 1500); + QCOMPARE(T::StdHashUsed, !T::HasQHash); + + + std::unordered_set<T> set; + for (int i = 0; i < 1000; ++i) + set.insert(T{i}); + + for (int i = 500; i < 1500; ++i) + set.insert(T{i}); + + QCOMPARE(set.size(), size_t(1500)); + count = 0; + for (int i = -2000; i < 2000; ++i) + count += qsizetype(set.count(T{i})); + QCOMPARE(count, 1500); + QVERIFY(T::StdHashUsed); +} + +void tst_QHash::stdHash() +{ + stdHashImpl<StdHashKeyType<false>>(); + stdHashImpl<StdHashKeyType<true>>(); + + QSet<std::string> strings{ "a", "b", "c" }; + QVERIFY(strings.contains("a")); + QVERIFY(!strings.contains("z")); +} + QTEST_APPLESS_MAIN(tst_QHash) #include "tst_qhash.moc" |