Back to home page

EIC code displayed by LXR

 
 

    


File indexing completed on 2025-10-14 09:03:02

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 // Copyright (C) 2024 Intel Corporation.
0004 // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
0005 
0006 #ifndef QHASHFUNCTIONS_H
0007 #define QHASHFUNCTIONS_H
0008 
0009 #include <QtCore/qstring.h>
0010 #include <QtCore/qstringfwd.h>
0011 
0012 #include <numeric> // for std::accumulate
0013 #include <functional> // for std::hash
0014 #include <utility> // For std::pair
0015 
0016 #if 0
0017 #pragma qt_class(QHashFunctions)
0018 #endif
0019 
0020 #if defined(Q_CC_MSVC)
0021 #pragma warning( push )
0022 #pragma warning( disable : 4311 ) // disable pointer truncation warning
0023 #pragma warning( disable : 4127 ) // conditional expression is constant
0024 #endif
0025 
0026 QT_BEGIN_NAMESPACE
0027 
0028 class QBitArray;
0029 
0030 #if QT_DEPRECATED_SINCE(6,6)
0031 QT_DEPRECATED_VERSION_X_6_6("Use QHashSeed instead")
0032 Q_CORE_EXPORT int qGlobalQHashSeed();
0033 QT_DEPRECATED_VERSION_X_6_6("Use QHashSeed instead")
0034 Q_CORE_EXPORT void qSetGlobalQHashSeed(int newSeed);
0035 #endif
0036 
0037 struct QHashSeed
0038 {
0039     constexpr QHashSeed(size_t d = 0) : data(d) {}
0040     constexpr operator size_t() const noexcept { return data; }
0041 
0042     static Q_CORE_EXPORT QHashSeed globalSeed() noexcept;
0043     static Q_CORE_EXPORT void setDeterministicGlobalSeed();
0044     static Q_CORE_EXPORT void resetRandomGlobalSeed();
0045 private:
0046     size_t data;
0047 };
0048 
0049 // Whether, ∀ t of type T && ∀ seed, qHash(Key(t), seed) == qHash(t, seed)
0050 template <typename Key, typename T> struct QHashHeterogeneousSearch : std::false_type {};
0051 
0052 // Specializations
0053 template <> struct QHashHeterogeneousSearch<QString, QStringView> : std::true_type {};
0054 template <> struct QHashHeterogeneousSearch<QStringView, QString> : std::true_type {};
0055 template <> struct QHashHeterogeneousSearch<QByteArray, QByteArrayView> : std::true_type {};
0056 template <> struct QHashHeterogeneousSearch<QByteArrayView, QByteArray> : std::true_type {};
0057 #ifndef Q_PROCESSOR_ARM
0058 template <> struct QHashHeterogeneousSearch<QString, QLatin1StringView> : std::true_type {};
0059 template <> struct QHashHeterogeneousSearch<QStringView, QLatin1StringView> : std::true_type {};
0060 template <> struct QHashHeterogeneousSearch<QLatin1StringView, QString> : std::true_type {};
0061 template <> struct QHashHeterogeneousSearch<QLatin1StringView, QStringView> : std::true_type {};
0062 #endif
0063 
0064 namespace QHashPrivate {
0065 
0066 Q_DECL_CONST_FUNCTION constexpr size_t hash(size_t key, size_t seed) noexcept
0067 {
0068     key ^= seed;
0069     if constexpr (sizeof(size_t) == 4) {
0070         key ^= key >> 16;
0071         key *= UINT32_C(0x45d9f3b);
0072         key ^= key >> 16;
0073         key *= UINT32_C(0x45d9f3b);
0074         key ^= key >> 16;
0075         return key;
0076     } else {
0077         quint64 key64 = key;
0078         key64 ^= key64 >> 32;
0079         key64 *= UINT64_C(0xd6e8feb86659fd93);
0080         key64 ^= key64 >> 32;
0081         key64 *= UINT64_C(0xd6e8feb86659fd93);
0082         key64 ^= key64 >> 32;
0083         return size_t(key64);
0084     }
0085 }
0086 
0087 template <typename T1, typename T2> static constexpr bool noexceptPairHash();
0088 }
0089 
0090 Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHashBits(const void *p, size_t size, size_t seed = 0) noexcept;
0091 
0092 // implementation below qHashMulti
0093 template <typename T1, typename T2> inline size_t qHash(const std::pair<T1, T2> &key, size_t seed = 0)
0094     noexcept(QHashPrivate::noexceptPairHash<T1, T2>());
0095 
0096 // C++ builtin types
0097 #define QT_MK_QHASH_COMPAT(X) \
0098     template <typename T, std::enable_if_t<std::is_same_v<T, X>, bool> = true> \
0099     constexpr size_t qHash(T key, size_t seed = 0) noexcept \
0100     /* QHashPrivate::hash() xors before mixing, while 1-to-2-arg adapter xors after */ \
0101     { return QHashPrivate::hash(size_t(key), 0 QT7_ONLY(+ seed)) QT6_ONLY(^ seed); } \
0102     /* end */
0103 QT_MK_QHASH_COMPAT(bool) // QTBUG-126674
0104 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(char key, size_t seed = 0) noexcept
0105 { return QHashPrivate::hash(size_t(key), seed); }
0106 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(uchar key, size_t seed = 0) noexcept
0107 { return QHashPrivate::hash(size_t(key), seed); }
0108 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(signed char key, size_t seed = 0) noexcept
0109 { return QHashPrivate::hash(size_t(key), seed); }
0110 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(ushort key, size_t seed = 0) noexcept
0111 { return QHashPrivate::hash(size_t(key), seed); }
0112 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(short key, size_t seed = 0) noexcept
0113 { return QHashPrivate::hash(size_t(key), seed); }
0114 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(uint key, size_t seed = 0) noexcept
0115 { return QHashPrivate::hash(size_t(key), seed); }
0116 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(int key, size_t seed = 0) noexcept
0117 { return QHashPrivate::hash(size_t(key), seed); }
0118 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(ulong key, size_t seed = 0) noexcept
0119 { return QHashPrivate::hash(size_t(key), seed); }
0120 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(long key, size_t seed = 0) noexcept
0121 { return QHashPrivate::hash(size_t(key), seed); }
0122 #undef QT_MK_QHASH_COMPAT
0123 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(quint64 key, size_t seed = 0) noexcept
0124 {
0125     if constexpr (sizeof(quint64) > sizeof(size_t))
0126         key ^= (key >> 32);
0127     return QHashPrivate::hash(size_t(key), seed);
0128 }
0129 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(qint64 key, size_t seed = 0) noexcept
0130 {
0131     if constexpr (sizeof(qint64) > sizeof(size_t)) {
0132         // Avoid QTBUG-116080: we XOR the top half with its own sign bit:
0133         // - if the qint64 is in range of qint32, then signmask ^ high == 0
0134         //   (for Qt 7 only)
0135         // - if the qint64 is in range of quint32, then signmask == 0 and we
0136         //   do the same as the quint64 overload above
0137         quint32 high = quint32(quint64(key) >> 32);
0138         quint32 low = quint32(quint64(key));
0139         quint32 signmask = qint32(high) >> 31;  // all zeroes or all ones
0140         signmask = QT_VERSION_MAJOR > 6 ? signmask : 0;
0141         low ^= signmask ^ high;
0142         return qHash(low, seed);
0143     }
0144     return qHash(quint64(key), seed);
0145 }
0146 #ifdef QT_SUPPORTS_INT128
0147 constexpr size_t qHash(quint128 key, size_t seed = 0) noexcept
0148 {
0149     return qHash(quint64(key + (key >> 64)), seed);
0150 }
0151 constexpr size_t qHash(qint128 key, size_t seed = 0) noexcept
0152 {
0153     // Avoid QTBUG-116080: same as above, but with double the sizes and without
0154     // the need for compatibility
0155     quint64 high = quint64(quint128(key) >> 64);
0156     quint64 low = quint64(quint128(key));
0157     quint64 signmask = qint64(high) >> 63; // all zeroes or all ones
0158     low += signmask ^ high;
0159     return qHash(low, seed);
0160 }
0161 #endif // QT_SUPPORTS_INT128
0162 Q_DECL_CONST_FUNCTION inline size_t qHash(float key, size_t seed = 0) noexcept
0163 {
0164     // ensure -0 gets mapped to 0
0165     key += 0.0f;
0166     uint k;
0167     memcpy(&k, &key, sizeof(float));
0168     return QHashPrivate::hash(k, seed);
0169 }
0170 Q_CORE_EXPORT Q_DECL_CONST_FUNCTION size_t qHash(double key, size_t seed = 0) noexcept;
0171 Q_CORE_EXPORT Q_DECL_CONST_FUNCTION size_t qHash(long double key, size_t seed = 0) noexcept;
0172 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(wchar_t key, size_t seed = 0) noexcept
0173 { return QHashPrivate::hash(size_t(key), seed); }
0174 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(char16_t key, size_t seed = 0) noexcept
0175 { return QHashPrivate::hash(size_t(key), seed); }
0176 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(char32_t key, size_t seed = 0) noexcept
0177 { return QHashPrivate::hash(size_t(key), seed); }
0178 #ifdef __cpp_char8_t
0179 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(char8_t key, size_t seed = 0) noexcept
0180 { return QHashPrivate::hash(size_t(key), seed); }
0181 #endif
0182 template <class T> inline size_t qHash(const T *key, size_t seed = 0) noexcept
0183 {
0184     return qHash(reinterpret_cast<quintptr>(key), seed);
0185 }
0186 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(std::nullptr_t, size_t seed = 0) noexcept
0187 {
0188     return seed;
0189 }
0190 template <class Enum, std::enable_if_t<std::is_enum_v<Enum>, bool> = true>
0191 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(Enum e, size_t seed = 0) noexcept
0192 { return QHashPrivate::hash(qToUnderlying(e), seed); }
0193 
0194 // (some) Qt types
0195 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(const QChar key, size_t seed = 0) noexcept { return qHash(key.unicode(), seed); }
0196 
0197 #if QT_CORE_REMOVED_SINCE(6, 4)
0198 Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(const QByteArray &key, size_t seed = 0) noexcept;
0199 Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(const QByteArrayView &key, size_t seed = 0) noexcept;
0200 #else
0201 Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(QByteArrayView key, size_t seed = 0) noexcept;
0202 inline Q_DECL_PURE_FUNCTION size_t qHash(const QByteArray &key, size_t seed = 0
0203         QT6_DECL_NEW_OVERLOAD_TAIL) noexcept
0204 { return qHash(qToByteArrayViewIgnoringNull(key), seed); }
0205 #endif
0206 
0207 Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(QStringView key, size_t seed = 0) noexcept;
0208 inline Q_DECL_PURE_FUNCTION size_t qHash(const QString &key, size_t seed = 0) noexcept
0209 { return qHash(QStringView{key}, seed); }
0210 #ifndef QT_BOOTSTRAPPED
0211 Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(const QBitArray &key, size_t seed = 0) noexcept;
0212 #endif
0213 Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(QLatin1StringView key, size_t seed = 0) noexcept;
0214 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(QKeyCombination key, size_t seed = 0) noexcept
0215 { return qHash(key.toCombined(), seed); }
0216 Q_CORE_EXPORT Q_DECL_PURE_FUNCTION uint qt_hash(QStringView key, uint chained = 0) noexcept;
0217 
0218 template <typename Enum>
0219 Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(QFlags<Enum> flags, size_t seed = 0) noexcept
0220 { return qHash(flags.toInt(), seed); }
0221 
0222 // ### Qt 7: remove this "catch-all" overload logic, and require users
0223 // to provide the two-argument version of qHash.
0224 #if (QT_VERSION < QT_VERSION_CHECK(7, 0, 0))
0225 // Beware of moving this code from here. It needs to see all the
0226 // declarations of qHash overloads for C++ fundamental types *before*
0227 // its own declaration.
0228 namespace QHashPrivate {
0229 template <typename T, typename = void>
0230 constexpr inline bool HasQHashSingleArgOverload = false;
0231 
0232 template <typename T>
0233 constexpr inline bool HasQHashSingleArgOverload<T, std::enable_if_t<
0234     std::is_convertible_v<decltype(qHash(std::declval<const T &>())), size_t>
0235 >> = true;
0236 }
0237 
0238 // Add Args... to make this overload consistently a worse match than
0239 // original 2-arg qHash overloads (QTBUG-126659)
0240 template <typename T, typename...Args,
0241           std::enable_if_t<QHashPrivate::HasQHashSingleArgOverload<T>
0242                            && sizeof...(Args) == 0 && !std::is_enum_v<T>, bool> = true>
0243 constexpr size_t qHash(const T &t, size_t seed, Args&&...) noexcept(noexcept(qHash(t)))
0244 { return qHash(t) ^ seed; }
0245 #endif // < Qt 7
0246 
0247 namespace QHashPrivate {
0248 
0249 namespace detail {
0250 // approximates std::equality_comparable_with
0251 template <typename T, typename U, typename = void>
0252 struct is_equality_comparable_with : std::false_type {};
0253 
0254 template <typename T, typename U>
0255 struct is_equality_comparable_with<T, U,
0256     std::void_t<
0257         decltype(bool(std::declval<T>() == std::declval<U>())),
0258         decltype(bool(std::declval<U>() == std::declval<T>())),
0259         decltype(bool(std::declval<T>() != std::declval<U>())),
0260         decltype(bool(std::declval<U>() != std::declval<T>()))
0261     >>
0262     : std::true_type {};
0263 }
0264 
0265 template <typename Key, typename T> struct HeterogeneouslySearchableWithHelper
0266     : std::conjunction<
0267         // if Key and T are not the same (member already exists)
0268         std::negation<std::is_same<Key, T>>,
0269         // but are comparable amongst each other
0270         detail::is_equality_comparable_with<Key, T>,
0271         // and supports heteregenous hashing
0272         QHashHeterogeneousSearch<Key, T>
0273     > {};
0274 
0275 template <typename Key, typename T>
0276 using HeterogeneouslySearchableWith = HeterogeneouslySearchableWithHelper<
0277         q20::remove_cvref_t<Key>,
0278         q20::remove_cvref_t<T>
0279 >;
0280 
0281 template <typename Key, typename K>
0282 using if_heterogeneously_searchable_with = std::enable_if_t<
0283         QHashPrivate::HeterogeneouslySearchableWith<Key, K>::value,
0284     bool>;
0285 
0286 }
0287 
0288 template<typename T>
0289 bool qHashEquals(const T &a, const T &b)
0290 {
0291     return a == b;
0292 }
0293 
0294 template <typename T1, typename T2, QHashPrivate::if_heterogeneously_searchable_with<T1, T2> = true>
0295 bool qHashEquals(const T1 &a, const T2 &b)
0296 {
0297     return a == b;
0298 }
0299 
0300 namespace QtPrivate {
0301 
0302 struct QHashCombine
0303 {
0304     typedef size_t result_type;
0305     template <typename T>
0306     constexpr result_type operator()(size_t seed, const T &t) const noexcept(noexcept(qHash(t)))
0307     // combiner taken from N3876 / boost::hash_combine
0308     { return seed ^ (qHash(t) + 0x9e3779b9 + (seed << 6) + (seed >> 2)) ; }
0309 };
0310 
0311 struct QHashCombineCommutative
0312 {
0313     // QHashCombine is a good hash combiner, but is not commutative,
0314     // ie. it depends on the order of the input elements. That is
0315     // usually what we want: {0,1,3} should hash differently than
0316     // {1,3,0}. Except when it isn't (e.g. for QSet and
0317     // QHash). Therefore, provide a commutative combiner, too.
0318     typedef size_t result_type;
0319     template <typename T>
0320     constexpr result_type operator()(size_t seed, const T &t) const noexcept(noexcept(qHash(t)))
0321     { return seed + qHash(t); } // don't use xor!
0322 };
0323 
0324 template <typename... T>
0325 using QHashMultiReturnType = decltype(
0326     std::declval< std::enable_if_t<(sizeof...(T) > 0)> >(),
0327     (qHash(std::declval<const T &>()), ...),
0328     size_t{}
0329 );
0330 
0331 // workaround for a MSVC ICE,
0332 // https://developercommunity.visualstudio.com/content/problem/996540/internal-compiler-error-on-msvc-1924-when-doing-sf.html
0333 template <typename T>
0334 inline constexpr bool QNothrowHashableHelper_v = noexcept(qHash(std::declval<const T &>()));
0335 
0336 template <typename T, typename Enable = void>
0337 struct QNothrowHashable : std::false_type {};
0338 
0339 template <typename T>
0340 struct QNothrowHashable<T, std::enable_if_t<QNothrowHashableHelper_v<T>>> : std::true_type {};
0341 
0342 template <typename T>
0343 constexpr inline bool QNothrowHashable_v = QNothrowHashable<T>::value;
0344 
0345 } // namespace QtPrivate
0346 
0347 template <typename... T>
0348 constexpr
0349 #ifdef Q_QDOC
0350 size_t
0351 #else
0352 QtPrivate::QHashMultiReturnType<T...>
0353 #endif
0354 qHashMulti(size_t seed, const T &... args)
0355     noexcept(std::conjunction_v<QtPrivate::QNothrowHashable<T>...>)
0356 {
0357     QtPrivate::QHashCombine hash;
0358     return ((seed = hash(seed, args)), ...), seed;
0359 }
0360 
0361 template <typename... T>
0362 constexpr
0363 #ifdef Q_QDOC
0364 size_t
0365 #else
0366 QtPrivate::QHashMultiReturnType<T...>
0367 #endif
0368 qHashMultiCommutative(size_t seed, const T &... args)
0369     noexcept(std::conjunction_v<QtPrivate::QNothrowHashable<T>...>)
0370 {
0371     QtPrivate::QHashCombineCommutative hash;
0372     return ((seed = hash(seed, args)), ...), seed;
0373 }
0374 
0375 template <typename InputIterator>
0376 inline size_t qHashRange(InputIterator first, InputIterator last, size_t seed = 0)
0377     noexcept(noexcept(qHash(*first))) // assume iterator operations don't throw
0378 {
0379     return std::accumulate(first, last, seed, QtPrivate::QHashCombine());
0380 }
0381 
0382 template <typename InputIterator>
0383 inline size_t qHashRangeCommutative(InputIterator first, InputIterator last, size_t seed = 0)
0384     noexcept(noexcept(qHash(*first))) // assume iterator operations don't throw
0385 {
0386     return std::accumulate(first, last, seed, QtPrivate::QHashCombineCommutative());
0387 }
0388 
0389 namespace QHashPrivate {
0390 template <typename T1, typename T2> static constexpr bool noexceptPairHash()
0391 {
0392     size_t seed = 0;
0393     return noexcept(qHash(std::declval<T1>(), seed)) && noexcept(qHash(std::declval<T2>(), seed));
0394 }
0395 } // QHashPrivate
0396 
0397 template <typename T1, typename T2> inline size_t qHash(const std::pair<T1, T2> &key, size_t seed)
0398     noexcept(QHashPrivate::noexceptPairHash<T1, T2>())
0399 {
0400     return qHashMulti(seed, key.first, key.second);
0401 }
0402 
0403 #define QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH(Class, Arguments)      \
0404     QT_BEGIN_INCLUDE_NAMESPACE                                      \
0405     namespace std {                                                 \
0406         template <>                                                 \
0407         struct hash< QT_PREPEND_NAMESPACE(Class) > {                \
0408             using argument_type = QT_PREPEND_NAMESPACE(Class);      \
0409             using result_type = size_t;                             \
0410             size_t operator()(Arguments s) const                    \
0411               noexcept(QT_PREPEND_NAMESPACE(                        \
0412                      QtPrivate::QNothrowHashable_v)<argument_type>) \
0413             {                                                       \
0414                 /* this seeds qHash with the result of */           \
0415                 /* std::hash applied to an int, to reap */          \
0416                 /* any protection against predictable hash */       \
0417                 /* values the std implementation may provide */     \
0418                 using QT_PREPEND_NAMESPACE(qHash);                  \
0419                 return qHash(s, qHash(std::hash<int>{}(0)));        \
0420             }                                                       \
0421         };                                                          \
0422     }                                                               \
0423     QT_END_INCLUDE_NAMESPACE                                        \
0424     /*end*/
0425 
0426 #define QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_CREF(Class) \
0427     QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH(Class, const argument_type &)
0428 #define QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_VALUE(Class) \
0429     QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH(Class, argument_type)
0430 
0431 QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_CREF(QString)
0432 QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_VALUE(QStringView)
0433 QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_VALUE(QLatin1StringView)
0434 QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_VALUE(QByteArrayView)
0435 QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_CREF(QByteArray)
0436 #ifndef QT_BOOTSTRAPPED
0437 QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_CREF(QBitArray)
0438 #endif
0439 
0440 QT_END_NAMESPACE
0441 
0442 #if defined(Q_CC_MSVC)
0443 #pragma warning( pop )
0444 #endif
0445 
0446 #endif // QHASHFUNCTIONS_H