include/QtCore/qhashfunctions.h

0001 // Copyright (C) 2016 The Qt Company Ltd.
0002 // Copyright (C) 2015 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Marc Mutz <marc.mutz@kdab.com>
0003 // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
0004
0005 #ifndef QHASHFUNCTIONS_H
0006 #define QHASHFUNCTIONS_H
0007
0008 #include <QtCore/qstring.h>
0009 #include <QtCore/qstringfwd.h>
0010
0011 #include <numeric> // for std::accumulate
0012 #include <functional> // for std::hash
0013 #include <utility> // For std::pair
0014
0015 #if 0
0016 #pragma qt_class(QHashFunctions)
0017 #endif
0018
0019 #if defined(Q_CC_MSVC)
0020 #pragma warning( push )
0021 #pragma warning( disable : 4311 ) // disable pointer truncation warning
0022 #pragma warning( disable : 4127 ) // conditional expression is constant
0023 #endif
0024
0025 QT_BEGIN_NAMESPACE
0026
0027 class QBitArray;
0028
0029 #if QT_DEPRECATED_SINCE(6,6)
0030 QT_DEPRECATED_VERSION_X_6_6("Use QHashSeed instead")
0031 Q_CORE_EXPORT int qGlobalQHashSeed();
0032 QT_DEPRECATED_VERSION_X_6_6("Use QHashSeed instead")
0033 Q_CORE_EXPORT void qSetGlobalQHashSeed(int newSeed);
0034 #endif
0035
0036 struct QHashSeed
0037 {
0038     constexpr QHashSeed(size_t d = 0) : data(d) {}
0039     constexpr operator size_t() const noexcept { return data; }
0040
0041     static Q_CORE_EXPORT QHashSeed globalSeed() noexcept;
0042     static Q_CORE_EXPORT void setDeterministicGlobalSeed();
0043     static Q_CORE_EXPORT void resetRandomGlobalSeed();
0044 private:
0045     size_t data;
0046 };
0047
0048 namespace QHashPrivate {
0049
0050 Q_DECL_CONST_FUNCTION constexpr size_t hash(size_t key, size_t seed) noexcept
0051 {
0052     key ^= seed;
0053     if constexpr (sizeof(size_t) == 4) {
0054         key ^= key >> 16;
0055         key *= UINT32_C(0x45d9f3b);
0056         key ^= key >> 16;
0057         key *= UINT32_C(0x45d9f3b);
0058         key ^= key >> 16;
0059         return key;
0060     } else {
0061         quint64 key64 = key;
0062         key64 ^= key64 >> 32;
0063         key64 *= UINT64_C(0xd6e8feb86659fd93);
0064         key64 ^= key64 >> 32;
0065         key64 *= UINT64_C(0xd6e8feb86659fd93);
0066         key64 ^= key64 >> 32;
0067         return size_t(key64);
0068     }
0069 }
0070
0071 template <typename T1, typename T2> static constexpr bool noexceptPairHash();
0072 }
0073
0074 Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHashBits(const void *p, size_t size, size_t seed = 0) noexcept;
0075
0076 // implementation below qHashMulti
0077 template <typename T1, typename T2> inline size_t qHash(const std::pair<T1, T2> &key, size_t seed = 0)
0078     noexcept(QHashPrivate::noexceptPairHash<T1, T2>());
0079
0080 // C++ builtin types
0081 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(char key, size_t seed = 0) noexcept
0082 { return QHashPrivate::hash(size_t(key), seed); }
0083 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(uchar key, size_t seed = 0) noexcept
0084 { return QHashPrivate::hash(size_t(key), seed); }
0085 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(signed char key, size_t seed = 0) noexcept
0086 { return QHashPrivate::hash(size_t(key), seed); }
0087 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(ushort key, size_t seed = 0) noexcept
0088 { return QHashPrivate::hash(size_t(key), seed); }
0089 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(short key, size_t seed = 0) noexcept
0090 { return QHashPrivate::hash(size_t(key), seed); }
0091 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(uint key, size_t seed = 0) noexcept
0092 { return QHashPrivate::hash(size_t(key), seed); }
0093 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(int key, size_t seed = 0) noexcept
0094 { return QHashPrivate::hash(size_t(key), seed); }
0095 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(ulong key, size_t seed = 0) noexcept
0096 { return QHashPrivate::hash(size_t(key), seed); }
0097 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(long key, size_t seed = 0) noexcept
0098 { return QHashPrivate::hash(size_t(key), seed); }
0099 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(quint64 key, size_t seed = 0) noexcept
0100 {
0101     if constexpr (sizeof(quint64) > sizeof(size_t))
0102         key ^= (key >> 32);
0103     return QHashPrivate::hash(size_t(key), seed);
0104 }
0105 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(qint64 key, size_t seed = 0) noexcept { return qHash(quint64(key), seed); }
0106 Q_DECL_CONST_FUNCTION inline size_t qHash(float key, size_t seed = 0) noexcept
0107 {
0108     // ensure -0 gets mapped to 0
0109     key += 0.0f;
0110     uint k;
0111     memcpy(&k, &key, sizeof(float));
0112     return QHashPrivate::hash(k, seed);
0113 }
0114 Q_CORE_EXPORT Q_DECL_CONST_FUNCTION size_t qHash(double key, size_t seed = 0) noexcept;
0115 Q_CORE_EXPORT Q_DECL_CONST_FUNCTION size_t qHash(long double key, size_t seed = 0) noexcept;
0116 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(wchar_t key, size_t seed = 0) noexcept
0117 { return QHashPrivate::hash(size_t(key), seed); }
0118 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(char16_t key, size_t seed = 0) noexcept
0119 { return QHashPrivate::hash(size_t(key), seed); }
0120 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(char32_t key, size_t seed = 0) noexcept
0121 { return QHashPrivate::hash(size_t(key), seed); }
0122 #ifdef __cpp_char8_t
0123 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(char8_t key, size_t seed = 0) noexcept
0124 { return QHashPrivate::hash(size_t(key), seed); }
0125 #endif
0126 template <class T> inline size_t qHash(const T *key, size_t seed = 0) noexcept
0127 {
0128     return qHash(reinterpret_cast<quintptr>(key), seed);
0129 }
0130 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(std::nullptr_t, size_t seed = 0) noexcept
0131 {
0132     return seed;
0133 }
0134 template <class Enum, std::enable_if_t<std::is_enum_v<Enum>, bool> = true>
0135 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(Enum e, size_t seed = 0) noexcept
0136 { return QHashPrivate::hash(qToUnderlying(e), seed); }
0137
0138 // (some) Qt types
0139 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(const QChar key, size_t seed = 0) noexcept { return qHash(key.unicode(), seed); }
0140
0141 #if QT_CORE_REMOVED_SINCE(6, 4)
0142 Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(const QByteArray &key, size_t seed = 0) noexcept;
0143 Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(const QByteArrayView &key, size_t seed = 0) noexcept;
0144 #else
0145 Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(QByteArrayView key, size_t seed = 0) noexcept;
0146 inline Q_DECL_PURE_FUNCTION size_t qHash(const QByteArray &key, size_t seed = 0
0147         QT6_DECL_NEW_OVERLOAD_TAIL) noexcept
0148 { return qHash(qToByteArrayViewIgnoringNull(key), seed); }
0149 #endif
0150
0151 Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(QStringView key, size_t seed = 0) noexcept;
0152 inline Q_DECL_PURE_FUNCTION size_t qHash(const QString &key, size_t seed = 0) noexcept
0153 { return qHash(QStringView{key}, seed); }
0154 #ifndef QT_BOOTSTRAPPED
0155 Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(const QBitArray &key, size_t seed = 0) noexcept;
0156 #endif
0157 Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(QLatin1StringView key, size_t seed = 0) noexcept;
0158 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(QKeyCombination key, size_t seed = 0) noexcept
0159 { return qHash(key.toCombined(), seed); }
0160 Q_CORE_EXPORT Q_DECL_PURE_FUNCTION uint qt_hash(QStringView key, uint chained = 0) noexcept;
0161
0162 template <typename Enum>
0163 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(QFlags<Enum> flags, size_t seed = 0) noexcept
0164 { return qHash(flags.toInt(), seed); }
0165
0166 // ### Qt 7: remove this "catch-all" overload logic, and require users
0167 // to provide the two-argument version of qHash.
0168 #if (QT_VERSION < QT_VERSION_CHECK(7, 0, 0))
0169 // Beware of moving this code from here. It needs to see all the
0170 // declarations of qHash overloads for C++ fundamental types *before*
0171 // its own declaration.
0172 namespace QHashPrivate {
0173 template <typename T, typename = void>
0174 constexpr inline bool HasQHashSingleArgOverload = false;
0175
0176 template <typename T>
0177 constexpr inline bool HasQHashSingleArgOverload<T, std::enable_if_t<
0178     std::is_convertible_v<decltype(qHash(std::declval<const T &>())), size_t>
0179 >> = true;
0180 }
0181
0182 template <typename T, std::enable_if_t<QHashPrivate::HasQHashSingleArgOverload<T> && !std::is_enum_v<T>, bool> = true>
0183 size_t qHash(const T &t, size_t seed) noexcept(noexcept(qHash(t)))
0184 { return qHash(t) ^ seed; }
0185 #endif // < Qt 7
0186
0187 template<typename T>
0188 bool qHashEquals(const T &a, const T &b)
0189 {
0190     return a == b;
0191 }
0192
0193 namespace QtPrivate {
0194
0195 struct QHashCombine
0196 {
0197     typedef size_t result_type;
0198     template <typename T>
0199     constexpr result_type operator()(size_t seed, const T &t) const noexcept(noexcept(qHash(t)))
0200     // combiner taken from N3876 / boost::hash_combine
0201     { return seed ^ (qHash(t) + 0x9e3779b9 + (seed << 6) + (seed >> 2)) ; }
0202 };
0203
0204 struct QHashCombineCommutative
0205 {
0206     // QHashCombine is a good hash combiner, but is not commutative,
0207     // ie. it depends on the order of the input elements. That is
0208     // usually what we want: {0,1,3} should hash differently than
0209     // {1,3,0}. Except when it isn't (e.g. for QSet and
0210     // QHash). Therefore, provide a commutative combiner, too.
0211     typedef size_t result_type;
0212     template <typename T>
0213     constexpr result_type operator()(size_t seed, const T &t) const noexcept(noexcept(qHash(t)))
0214     { return seed + qHash(t); } // don't use xor!
0215 };
0216
0217 template <typename... T>
0218 using QHashMultiReturnType = decltype(
0219     std::declval< std::enable_if_t<(sizeof...(T) > 0)> >(),
0220     (qHash(std::declval<const T &>()), ...),
0221     size_t{}
0222 );
0223
0224 // workaround for a MSVC ICE,
0225 // https://developercommunity.visualstudio.com/content/problem/996540/internal-compiler-error-on-msvc-1924-when-doing-sf.html
0226 template <typename T>
0227 inline constexpr bool QNothrowHashableHelper_v = noexcept(qHash(std::declval<const T &>()));
0228
0229 template <typename T, typename Enable = void>
0230 struct QNothrowHashable : std::false_type {};
0231
0232 template <typename T>
0233 struct QNothrowHashable<T, std::enable_if_t<QNothrowHashableHelper_v<T>>> : std::true_type {};
0234
0235 template <typename T>
0236 constexpr inline bool QNothrowHashable_v = QNothrowHashable<T>::value;
0237
0238 } // namespace QtPrivate
0239
0240 template <typename... T>
0241 constexpr
0242 #ifdef Q_QDOC
0243 size_t
0244 #else
0245 QtPrivate::QHashMultiReturnType<T...>
0246 #endif
0247 qHashMulti(size_t seed, const T &... args)
0248     noexcept(std::conjunction_v<QtPrivate::QNothrowHashable<T>...>)
0249 {
0250     QtPrivate::QHashCombine hash;
0251     return ((seed = hash(seed, args)), ...), seed;
0252 }
0253
0254 template <typename... T>
0255 constexpr
0256 #ifdef Q_QDOC
0257 size_t
0258 #else
0259 QtPrivate::QHashMultiReturnType<T...>
0260 #endif
0261 qHashMultiCommutative(size_t seed, const T &... args)
0262     noexcept(std::conjunction_v<QtPrivate::QNothrowHashable<T>...>)
0263 {
0264     QtPrivate::QHashCombineCommutative hash;
0265     return ((seed = hash(seed, args)), ...), seed;
0266 }
0267
0268 template <typename InputIterator>
0269 inline size_t qHashRange(InputIterator first, InputIterator last, size_t seed = 0)
0270     noexcept(noexcept(qHash(*first))) // assume iterator operations don't throw
0271 {
0272     return std::accumulate(first, last, seed, QtPrivate::QHashCombine());
0273 }
0274
0275 template <typename InputIterator>
0276 inline size_t qHashRangeCommutative(InputIterator first, InputIterator last, size_t seed = 0)
0277     noexcept(noexcept(qHash(*first))) // assume iterator operations don't throw
0278 {
0279     return std::accumulate(first, last, seed, QtPrivate::QHashCombineCommutative());
0280 }
0281
0282 namespace QHashPrivate {
0283 template <typename T1, typename T2> static constexpr bool noexceptPairHash()
0284 {
0285     size_t seed = 0;
0286     return noexcept(qHash(std::declval<T1>(), seed)) && noexcept(qHash(std::declval<T2>(), seed));
0287 }
0288 } // QHashPrivate
0289
0290 template <typename T1, typename T2> inline size_t qHash(const std::pair<T1, T2> &key, size_t seed)
0291     noexcept(QHashPrivate::noexceptPairHash<T1, T2>())
0292 {
0293     return qHashMulti(seed, key.first, key.second);
0294 }
0295
0296 #define QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH(Class, Arguments)      \
0297     QT_BEGIN_INCLUDE_NAMESPACE                                      \
0298     namespace std {                                                 \
0299         template <>                                                 \
0300         struct hash< QT_PREPEND_NAMESPACE(Class) > {                \
0301             using argument_type = QT_PREPEND_NAMESPACE(Class);      \
0302             using result_type = size_t;                             \
0303             size_t operator()(Arguments s) const                    \
0304               noexcept(QT_PREPEND_NAMESPACE(                        \
0305                      QtPrivate::QNothrowHashable_v)<argument_type>) \
0306             {                                                       \
0307                 /* this seeds qHash with the result of */           \
0308                 /* std::hash applied to an int, to reap */          \
0309                 /* any protection against predictable hash */       \
0310                 /* values the std implementation may provide */     \
0311                 using QT_PREPEND_NAMESPACE(qHash);                  \
0312                 return qHash(s, qHash(std::hash<int>{}(0)));        \
0313             }                                                       \
0314         };                                                          \
0315     }                                                               \
0316     QT_END_INCLUDE_NAMESPACE                                        \
0317     /*end*/
0318
0319 #define QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_CREF(Class) \
0320     QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH(Class, const argument_type &)
0321 #define QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_VALUE(Class) \
0322     QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH(Class, argument_type)
0323
0324 QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_CREF(QString)
0325 QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_VALUE(QStringView)
0326 QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_VALUE(QLatin1StringView)
0327 QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_VALUE(QByteArrayView)
0328 QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_CREF(QByteArray)
0329 #ifndef QT_BOOTSTRAPPED
0330 QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_CREF(QBitArray)
0331 #endif
0332
0333 QT_END_NAMESPACE
0334
0335 #if defined(Q_CC_MSVC)
0336 #pragma warning( pop )
0337 #endif
0338
0339 #endif // QHASHFUNCTIONS_H