1// Copyright (C) 2016 The Qt Company Ltd.
2// Copyright (C) 2015 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Marc Mutz <marc.mutz@kdab.com>
3// Copyright (C) 2024 Intel Corporation.
4// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
5
6#ifndef QHASHFUNCTIONS_H
7#define QHASHFUNCTIONS_H
8
9#include <QtCore/qstring.h>
10#include <QtCore/qstringfwd.h>
11
12#include <numeric> // for std::accumulate
13#include <functional> // for std::hash
14#include <utility> // For std::pair
15
16#if 0
17#pragma qt_class(QHashFunctions)
18#endif
19
20#if defined(Q_CC_MSVC)
21#pragma warning( push )
22#pragma warning( disable : 4311 ) // disable pointer truncation warning
23#pragma warning( disable : 4127 ) // conditional expression is constant
24#endif
25
26QT_BEGIN_NAMESPACE
27
28class QBitArray;
29
30#if QT_DEPRECATED_SINCE(6,6)
31QT_DEPRECATED_VERSION_X_6_6("Use QHashSeed instead")
32Q_CORE_EXPORT int qGlobalQHashSeed();
33QT_DEPRECATED_VERSION_X_6_6("Use QHashSeed instead")
34Q_CORE_EXPORT void qSetGlobalQHashSeed(int newSeed);
35#endif
36
37struct QHashSeed
38{
39 constexpr QHashSeed(size_t d = 0) : data(d) {}
40 constexpr operator size_t() const noexcept { return data; }
41
42 static Q_CORE_EXPORT QHashSeed globalSeed() noexcept;
43 static Q_CORE_EXPORT void setDeterministicGlobalSeed();
44 static Q_CORE_EXPORT void resetRandomGlobalSeed();
45private:
46 size_t data;
47};
48
49// Whether, ∀ t of type T && ∀ seed, qHash(Key(t), seed) == qHash(t, seed)
50template <typename Key, typename T> struct QHashHeterogeneousSearch : std::false_type {};
51
52// Specializations
53template <> struct QHashHeterogeneousSearch<QString, QStringView> : std::true_type {};
54template <> struct QHashHeterogeneousSearch<QStringView, QString> : std::true_type {};
55template <> struct QHashHeterogeneousSearch<QByteArray, QByteArrayView> : std::true_type {};
56template <> struct QHashHeterogeneousSearch<QByteArrayView, QByteArray> : std::true_type {};
57#ifndef Q_PROCESSOR_ARM
58template <> struct QHashHeterogeneousSearch<QString, QLatin1StringView> : std::true_type {};
59template <> struct QHashHeterogeneousSearch<QStringView, QLatin1StringView> : std::true_type {};
60template <> struct QHashHeterogeneousSearch<QLatin1StringView, QString> : std::true_type {};
61template <> struct QHashHeterogeneousSearch<QLatin1StringView, QStringView> : std::true_type {};
62#endif
63
64namespace QHashPrivate {
65
66Q_DECL_CONST_FUNCTION constexpr size_t hash(size_t key, size_t seed) noexcept
67{
68 key ^= seed;
69 if constexpr (sizeof(size_t) == 4) {
70 key ^= key >> 16;
71 key *= UINT32_C(0x45d9f3b);
72 key ^= key >> 16;
73 key *= UINT32_C(0x45d9f3b);
74 key ^= key >> 16;
75 return key;
76 } else {
77 quint64 key64 = key;
78 key64 ^= key64 >> 32;
79 key64 *= UINT64_C(0xd6e8feb86659fd93);
80 key64 ^= key64 >> 32;
81 key64 *= UINT64_C(0xd6e8feb86659fd93);
82 key64 ^= key64 >> 32;
83 return size_t(key64);
84 }
85}
86
87template <typename T1, typename T2> static constexpr bool noexceptPairHash();
88}
89
90Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHashBits(const void *p, size_t size, size_t seed = 0) noexcept;
91
92// implementation below qHashMulti
93template <typename T1, typename T2> inline size_t qHash(const std::pair<T1, T2> &key, size_t seed = 0)
94 noexcept(QHashPrivate::noexceptPairHash<T1, T2>());
95
96// C++ builtin types
97Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(char key, size_t seed = 0) noexcept
98{ return QHashPrivate::hash(key: size_t(key), seed); }
99Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(uchar key, size_t seed = 0) noexcept
100{ return QHashPrivate::hash(key: size_t(key), seed); }
101Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(signed char key, size_t seed = 0) noexcept
102{ return QHashPrivate::hash(key: size_t(key), seed); }
103Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(ushort key, size_t seed = 0) noexcept
104{ return QHashPrivate::hash(key: size_t(key), seed); }
105Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(short key, size_t seed = 0) noexcept
106{ return QHashPrivate::hash(key: size_t(key), seed); }
107Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(uint key, size_t seed = 0) noexcept
108{ return QHashPrivate::hash(key: size_t(key), seed); }
109Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(int key, size_t seed = 0) noexcept
110{ return QHashPrivate::hash(key: size_t(key), seed); }
111Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(ulong key, size_t seed = 0) noexcept
112{ return QHashPrivate::hash(key: size_t(key), seed); }
113Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(long key, size_t seed = 0) noexcept
114{ return QHashPrivate::hash(key: size_t(key), seed); }
115Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(quint64 key, size_t seed = 0) noexcept
116{
117 if constexpr (sizeof(quint64) > sizeof(size_t))
118 key ^= (key >> 32);
119 return QHashPrivate::hash(key: size_t(key), seed);
120}
121Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(qint64 key, size_t seed = 0) noexcept
122{
123 if constexpr (sizeof(qint64) > sizeof(size_t)) {
124 // Avoid QTBUG-116080: we XOR the top half with its own sign bit:
125 // - if the qint64 is in range of qint32, then signmask ^ high == 0
126 // (for Qt 7 only)
127 // - if the qint64 is in range of quint32, then signmask == 0 and we
128 // do the same as the quint64 overload above
129 quint32 high = quint32(quint64(key) >> 32);
130 quint32 low = quint32(quint64(key));
131 quint32 signmask = qint32(high) >> 31; // all zeroes or all ones
132 signmask = QT_VERSION_MAJOR > 6 ? signmask : 0;
133 low ^= signmask ^ high;
134 return qHash(key: low, seed);
135 }
136 return qHash(key: quint64(key), seed);
137}
138#ifdef QT_SUPPORTS_INT128
139constexpr size_t qHash(quint128 key, size_t seed = 0) noexcept
140{
141 return qHash(key: quint64(key + (key >> 64)), seed);
142}
143constexpr size_t qHash(qint128 key, size_t seed = 0) noexcept
144{
145 // Avoid QTBUG-116080: same as above, but with double the sizes and without
146 // the need for compatibility
147 quint64 high = quint64(quint128(key) >> 64);
148 quint64 low = quint64(quint128(key));
149 quint64 signmask = qint64(high) >> 63; // all zeroes or all ones
150 low += signmask ^ high;
151 return qHash(key: low, seed);
152}
153#endif // QT_SUPPORTS_INT128
154Q_DECL_CONST_FUNCTION inline size_t qHash(float key, size_t seed = 0) noexcept
155{
156 // ensure -0 gets mapped to 0
157 key += 0.0f;
158 uint k;
159 memcpy(dest: &k, src: &key, n: sizeof(float));
160 return QHashPrivate::hash(key: k, seed);
161}
162Q_CORE_EXPORT Q_DECL_CONST_FUNCTION size_t qHash(double key, size_t seed = 0) noexcept;
163Q_CORE_EXPORT Q_DECL_CONST_FUNCTION size_t qHash(long double key, size_t seed = 0) noexcept;
164Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(wchar_t key, size_t seed = 0) noexcept
165{ return QHashPrivate::hash(key: size_t(key), seed); }
166Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(char16_t key, size_t seed = 0) noexcept
167{ return QHashPrivate::hash(key: size_t(key), seed); }
168Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(char32_t key, size_t seed = 0) noexcept
169{ return QHashPrivate::hash(key: size_t(key), seed); }
170#ifdef __cpp_char8_t
171Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(char8_t key, size_t seed = 0) noexcept
172{ return QHashPrivate::hash(size_t(key), seed); }
173#endif
174template <class T> inline size_t qHash(const T *key, size_t seed = 0) noexcept
175{
176 return qHash(key: reinterpret_cast<quintptr>(key), seed);
177}
178Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(std::nullptr_t, size_t seed = 0) noexcept
179{
180 return seed;
181}
182template <class Enum, std::enable_if_t<std::is_enum_v<Enum>, bool> = true>
183Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(Enum e, size_t seed = 0) noexcept
184{ return QHashPrivate::hash(key: qToUnderlying(e), seed); }
185
186// (some) Qt types
187Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(const QChar key, size_t seed = 0) noexcept { return qHash(key: key.unicode(), seed); }
188
189#if QT_CORE_REMOVED_SINCE(6, 4)
190Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(const QByteArray &key, size_t seed = 0) noexcept;
191Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(const QByteArrayView &key, size_t seed = 0) noexcept;
192#else
193Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(QByteArrayView key, size_t seed = 0) noexcept;
194inline Q_DECL_PURE_FUNCTION size_t qHash(const QByteArray &key, size_t seed = 0
195 QT6_DECL_NEW_OVERLOAD_TAIL) noexcept
196{ return qHash(key: qToByteArrayViewIgnoringNull(b: key), seed); }
197#endif
198
199Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(QStringView key, size_t seed = 0) noexcept;
200inline Q_DECL_PURE_FUNCTION size_t qHash(const QString &key, size_t seed = 0) noexcept
201{ return qHash(key: QStringView{key}, seed); }
202#ifndef QT_BOOTSTRAPPED
203Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(const QBitArray &key, size_t seed = 0) noexcept;
204#endif
205Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(QLatin1StringView key, size_t seed = 0) noexcept;
206Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(QKeyCombination key, size_t seed = 0) noexcept
207{ return qHash(key: key.toCombined(), seed); }
208Q_CORE_EXPORT Q_DECL_PURE_FUNCTION uint qt_hash(QStringView key, uint chained = 0) noexcept;
209
210template <typename Enum>
211Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(QFlags<Enum> flags, size_t seed = 0) noexcept
212{ return qHash(flags.toInt(), seed); }
213
214// ### Qt 7: remove this "catch-all" overload logic, and require users
215// to provide the two-argument version of qHash.
216#if (QT_VERSION < QT_VERSION_CHECK(7, 0, 0))
217// Beware of moving this code from here. It needs to see all the
218// declarations of qHash overloads for C++ fundamental types *before*
219// its own declaration.
220namespace QHashPrivate {
221template <typename T, typename = void>
222constexpr inline bool HasQHashSingleArgOverload = false;
223
224template <typename T>
225constexpr inline bool HasQHashSingleArgOverload<T, std::enable_if_t<
226 std::is_convertible_v<decltype(qHash(std::declval<const T &>())), size_t>
227>> = true;
228}
229
230// Add Args... to make this overload consistently a worse match than
231// original 2-arg qHash overloads (QTBUG-126659)
232template <typename T, typename...Args, std::enable_if_t<QHashPrivate::HasQHashSingleArgOverload<T> && sizeof...(Args) == 0 && !std::is_enum_v<T>, bool> = true>
233size_t qHash(const T &t, size_t seed, Args&&...) noexcept(noexcept(qHash(t)))
234{ return qHash(t) ^ seed; }
235#endif // < Qt 7
236
237namespace QHashPrivate {
238
239namespace detail {
240// approximates std::equality_comparable_with
241template <typename T, typename U, typename = void>
242struct is_equality_comparable_with : std::false_type {};
243
244template <typename T, typename U>
245struct is_equality_comparable_with<T, U,
246 std::void_t<
247 decltype(bool(std::declval<T>() == std::declval<U>())),
248 decltype(bool(std::declval<U>() == std::declval<T>())),
249 decltype(bool(std::declval<T>() != std::declval<U>())),
250 decltype(bool(std::declval<U>() != std::declval<T>()))
251 >>
252 : std::true_type {};
253}
254
255template <typename Key, typename T> struct HeterogeneouslySearchableWithHelper
256 : std::conjunction<
257 // if Key and T are not the same (member already exists)
258 std::negation<std::is_same<Key, T>>,
259 // but are comparable amongst each other
260 detail::is_equality_comparable_with<Key, T>,
261 // and supports heteregenous hashing
262 QHashHeterogeneousSearch<Key, T>
263 > {};
264
265template <typename Key, typename T>
266using HeterogeneouslySearchableWith = HeterogeneouslySearchableWithHelper<
267 q20::remove_cvref_t<Key>,
268 q20::remove_cvref_t<T>
269>;
270
271template <typename Key, typename K>
272using if_heterogeneously_searchable_with = std::enable_if_t<
273 QHashPrivate::HeterogeneouslySearchableWith<Key, K>::value,
274 bool>;
275
276}
277
278template<typename T>
279bool qHashEquals(const T &a, const T &b)
280{
281 return a == b;
282}
283
284template <typename T1, typename T2, QHashPrivate::if_heterogeneously_searchable_with<T1, T2> = true>
285bool qHashEquals(const T1 &a, const T2 &b)
286{
287 return a == b;
288}
289
290namespace QtPrivate {
291
292struct QHashCombine
293{
294 typedef size_t result_type;
295 template <typename T>
296 constexpr result_type operator()(size_t seed, const T &t) const noexcept(noexcept(qHash(t)))
297 // combiner taken from N3876 / boost::hash_combine
298 { return seed ^ (qHash(t) + 0x9e3779b9 + (seed << 6) + (seed >> 2)) ; }
299};
300
301struct QHashCombineCommutative
302{
303 // QHashCombine is a good hash combiner, but is not commutative,
304 // ie. it depends on the order of the input elements. That is
305 // usually what we want: {0,1,3} should hash differently than
306 // {1,3,0}. Except when it isn't (e.g. for QSet and
307 // QHash). Therefore, provide a commutative combiner, too.
308 typedef size_t result_type;
309 template <typename T>
310 constexpr result_type operator()(size_t seed, const T &t) const noexcept(noexcept(qHash(t)))
311 { return seed + qHash(t); } // don't use xor!
312};
313
314template <typename... T>
315using QHashMultiReturnType = decltype(
316 std::declval< std::enable_if_t<(sizeof...(T) > 0)> >(),
317 (qHash(std::declval<const T &>()), ...),
318 size_t{}
319);
320
321// workaround for a MSVC ICE,
322// https://developercommunity.visualstudio.com/content/problem/996540/internal-compiler-error-on-msvc-1924-when-doing-sf.html
323template <typename T>
324inline constexpr bool QNothrowHashableHelper_v = noexcept(qHash(std::declval<const T &>()));
325
326template <typename T, typename Enable = void>
327struct QNothrowHashable : std::false_type {};
328
329template <typename T>
330struct QNothrowHashable<T, std::enable_if_t<QNothrowHashableHelper_v<T>>> : std::true_type {};
331
332template <typename T>
333constexpr inline bool QNothrowHashable_v = QNothrowHashable<T>::value;
334
335} // namespace QtPrivate
336
337template <typename... T>
338constexpr
339#ifdef Q_QDOC
340size_t
341#else
342QtPrivate::QHashMultiReturnType<T...>
343#endif
344qHashMulti(size_t seed, const T &... args)
345 noexcept(std::conjunction_v<QtPrivate::QNothrowHashable<T>...>)
346{
347 QtPrivate::QHashCombine hash;
348 return ((seed = hash(seed, args)), ...), seed;
349}
350
351template <typename... T>
352constexpr
353#ifdef Q_QDOC
354size_t
355#else
356QtPrivate::QHashMultiReturnType<T...>
357#endif
358qHashMultiCommutative(size_t seed, const T &... args)
359 noexcept(std::conjunction_v<QtPrivate::QNothrowHashable<T>...>)
360{
361 QtPrivate::QHashCombineCommutative hash;
362 return ((seed = hash(seed, args)), ...), seed;
363}
364
365template <typename InputIterator>
366inline size_t qHashRange(InputIterator first, InputIterator last, size_t seed = 0)
367 noexcept(noexcept(qHash(*first))) // assume iterator operations don't throw
368{
369 return std::accumulate(first, last, seed, QtPrivate::QHashCombine());
370}
371
372template <typename InputIterator>
373inline size_t qHashRangeCommutative(InputIterator first, InputIterator last, size_t seed = 0)
374 noexcept(noexcept(qHash(*first))) // assume iterator operations don't throw
375{
376 return std::accumulate(first, last, seed, QtPrivate::QHashCombineCommutative());
377}
378
379namespace QHashPrivate {
380template <typename T1, typename T2> static constexpr bool noexceptPairHash()
381{
382 size_t seed = 0;
383 return noexcept(qHash(std::declval<T1>(), seed)) && noexcept(qHash(std::declval<T2>(), seed));
384}
385} // QHashPrivate
386
387template <typename T1, typename T2> inline size_t qHash(const std::pair<T1, T2> &key, size_t seed)
388 noexcept(QHashPrivate::noexceptPairHash<T1, T2>())
389{
390 return qHashMulti(seed, key.first, key.second);
391}
392
393#define QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH(Class, Arguments) \
394 QT_BEGIN_INCLUDE_NAMESPACE \
395 namespace std { \
396 template <> \
397 struct hash< QT_PREPEND_NAMESPACE(Class) > { \
398 using argument_type = QT_PREPEND_NAMESPACE(Class); \
399 using result_type = size_t; \
400 size_t operator()(Arguments s) const \
401 noexcept(QT_PREPEND_NAMESPACE( \
402 QtPrivate::QNothrowHashable_v)<argument_type>) \
403 { \
404 /* this seeds qHash with the result of */ \
405 /* std::hash applied to an int, to reap */ \
406 /* any protection against predictable hash */ \
407 /* values the std implementation may provide */ \
408 using QT_PREPEND_NAMESPACE(qHash); \
409 return qHash(s, qHash(std::hash<int>{}(0))); \
410 } \
411 }; \
412 } \
413 QT_END_INCLUDE_NAMESPACE \
414 /*end*/
415
416#define QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_CREF(Class) \
417 QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH(Class, const argument_type &)
418#define QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_VALUE(Class) \
419 QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH(Class, argument_type)
420
421QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_CREF(QString)
422QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_VALUE(QStringView)
423QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_VALUE(QLatin1StringView)
424QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_VALUE(QByteArrayView)
425QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_CREF(QByteArray)
426#ifndef QT_BOOTSTRAPPED
427QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_CREF(QBitArray)
428#endif
429
430QT_END_NAMESPACE
431
432#if defined(Q_CC_MSVC)
433#pragma warning( pop )
434#endif
435
436#endif // QHASHFUNCTIONS_H
437

source code of qtbase/src/corelib/tools/qhashfunctions.h