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// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
4
5#ifndef QHASHFUNCTIONS_H
6#define QHASHFUNCTIONS_H
7
8#include <QtCore/qstring.h>
9#include <QtCore/qstringfwd.h>
10#include <QtCore/qpair.h>
11
12#include <numeric> // for std::accumulate
13#include <functional> // for std::hash
14
15#if 0
16#pragma qt_class(QHashFunctions)
17#endif
18
19#if defined(Q_CC_MSVC)
20#pragma warning( push )
21#pragma warning( disable : 4311 ) // disable pointer truncation warning
22#pragma warning( disable : 4127 ) // conditional expression is constant
23#endif
24
25QT_BEGIN_NAMESPACE
26
27class QBitArray;
28
29#if QT_DEPRECATED_SINCE(6,6)
30QT_DEPRECATED_VERSION_X_6_6("Use QHashSeed instead")
31Q_CORE_EXPORT int qGlobalQHashSeed();
32QT_DEPRECATED_VERSION_X_6_6("Use QHashSeed instead")
33Q_CORE_EXPORT void qSetGlobalQHashSeed(int newSeed);
34#endif
35
36struct QHashSeed
37{
38 constexpr QHashSeed(size_t d = 0) : data(d) {}
39 constexpr operator size_t() const noexcept { return data; }
40
41 static Q_CORE_EXPORT QHashSeed globalSeed() noexcept;
42 static Q_CORE_EXPORT void setDeterministicGlobalSeed();
43 static Q_CORE_EXPORT void resetRandomGlobalSeed();
44private:
45 size_t data;
46};
47
48namespace QHashPrivate {
49
50Q_DECL_CONST_FUNCTION constexpr size_t hash(size_t key, size_t seed) noexcept
51{
52 key ^= seed;
53 if constexpr (sizeof(size_t) == 4) {
54 key ^= key >> 16;
55 key *= UINT32_C(0x45d9f3b);
56 key ^= key >> 16;
57 key *= UINT32_C(0x45d9f3b);
58 key ^= key >> 16;
59 return key;
60 } else {
61 quint64 key64 = key;
62 key64 ^= key64 >> 32;
63 key64 *= UINT64_C(0xd6e8feb86659fd93);
64 key64 ^= key64 >> 32;
65 key64 *= UINT64_C(0xd6e8feb86659fd93);
66 key64 ^= key64 >> 32;
67 return size_t(key64);
68 }
69}
70
71template <typename T1, typename T2> static constexpr bool noexceptPairHash();
72}
73
74Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHashBits(const void *p, size_t size, size_t seed = 0) noexcept;
75
76// implementation below qHashMulti
77template <typename T1, typename T2> inline size_t qHash(const std::pair<T1, T2> &key, size_t seed = 0)
78 noexcept(QHashPrivate::noexceptPairHash<T1, T2>());
79
80// C++ builtin types
81Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(char key, size_t seed = 0) noexcept
82{ return QHashPrivate::hash(key: size_t(key), seed); }
83Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(uchar key, size_t seed = 0) noexcept
84{ return QHashPrivate::hash(key: size_t(key), seed); }
85Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(signed char key, size_t seed = 0) noexcept
86{ return QHashPrivate::hash(key: size_t(key), seed); }
87Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(ushort key, size_t seed = 0) noexcept
88{ return QHashPrivate::hash(key: size_t(key), seed); }
89Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(short key, size_t seed = 0) noexcept
90{ return QHashPrivate::hash(key: size_t(key), seed); }
91Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(uint key, size_t seed = 0) noexcept
92{ return QHashPrivate::hash(key: size_t(key), seed); }
93Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(int key, size_t seed = 0) noexcept
94{ return QHashPrivate::hash(key: size_t(key), seed); }
95Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(ulong key, size_t seed = 0) noexcept
96{ return QHashPrivate::hash(key: size_t(key), seed); }
97Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(long key, size_t seed = 0) noexcept
98{ return QHashPrivate::hash(key: size_t(key), seed); }
99Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(quint64 key, size_t seed = 0) noexcept
100{
101 if constexpr (sizeof(quint64) > sizeof(size_t))
102 key ^= (key >> 32);
103 return QHashPrivate::hash(key: size_t(key), seed);
104}
105Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(qint64 key, size_t seed = 0) noexcept { return qHash(key: quint64(key), seed); }
106Q_DECL_CONST_FUNCTION inline size_t qHash(float key, size_t seed = 0) noexcept
107{
108 // ensure -0 gets mapped to 0
109 key += 0.0f;
110 uint k;
111 memcpy(dest: &k, src: &key, n: sizeof(float));
112 return QHashPrivate::hash(key: k, seed);
113}
114Q_CORE_EXPORT Q_DECL_CONST_FUNCTION size_t qHash(double key, size_t seed = 0) noexcept;
115#if !defined(Q_OS_DARWIN) || defined(Q_QDOC)
116Q_CORE_EXPORT Q_DECL_CONST_FUNCTION size_t qHash(long double key, size_t seed = 0) noexcept;
117#endif
118Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(wchar_t key, size_t seed = 0) noexcept
119{ return QHashPrivate::hash(key: size_t(key), seed); }
120Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(char16_t key, size_t seed = 0) noexcept
121{ return QHashPrivate::hash(key: size_t(key), seed); }
122Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(char32_t key, size_t seed = 0) noexcept
123{ return QHashPrivate::hash(key: size_t(key), seed); }
124#ifdef __cpp_char8_t
125Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(char8_t key, size_t seed = 0) noexcept
126{ return QHashPrivate::hash(size_t(key), seed); }
127#endif
128template <class T> inline size_t qHash(const T *key, size_t seed = 0) noexcept
129{
130 return qHash(key: reinterpret_cast<quintptr>(key), seed);
131}
132Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(std::nullptr_t, size_t seed = 0) noexcept
133{
134 return seed;
135}
136template <class Enum, std::enable_if_t<std::is_enum_v<Enum>, bool> = true>
137Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(Enum e, size_t seed = 0) noexcept
138{ return QHashPrivate::hash(key: qToUnderlying(e), seed); }
139
140// (some) Qt types
141Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(const QChar key, size_t seed = 0) noexcept { return qHash(key: key.unicode(), seed); }
142
143#if QT_CORE_REMOVED_SINCE(6, 4)
144Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(const QByteArray &key, size_t seed = 0) noexcept;
145Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(const QByteArrayView &key, size_t seed = 0) noexcept;
146#else
147Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(QByteArrayView key, size_t seed = 0) noexcept;
148inline Q_DECL_PURE_FUNCTION size_t qHash(const QByteArray &key, size_t seed = 0
149 QT6_DECL_NEW_OVERLOAD_TAIL) noexcept
150{ return qHash(key: qToByteArrayViewIgnoringNull(b: key), seed); }
151#endif
152
153Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(QStringView key, size_t seed = 0) noexcept;
154inline Q_DECL_PURE_FUNCTION size_t qHash(const QString &key, size_t seed = 0) noexcept
155{ return qHash(key: QStringView{key}, seed); }
156Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(const QBitArray &key, size_t seed = 0) noexcept;
157Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(QLatin1StringView key, size_t seed = 0) noexcept;
158Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(QKeyCombination key, size_t seed = 0) noexcept
159{ return qHash(key: key.toCombined(), seed); }
160Q_CORE_EXPORT Q_DECL_PURE_FUNCTION uint qt_hash(QStringView key, uint chained = 0) noexcept;
161
162template <typename Enum>
163Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(QFlags<Enum> flags, size_t seed = 0) noexcept
164{ return qHash(flags.toInt(), seed); }
165
166// ### Qt 7: remove this "catch-all" overload logic, and require users
167// to provide the two-argument version of qHash.
168#if (QT_VERSION < QT_VERSION_CHECK(7, 0, 0))
169// Beware of moving this code from here. It needs to see all the
170// declarations of qHash overloads for C++ fundamental types *before*
171// its own declaration.
172namespace QHashPrivate {
173template <typename T, typename = void>
174constexpr inline bool HasQHashSingleArgOverload = false;
175
176template <typename T>
177constexpr inline bool HasQHashSingleArgOverload<T, std::enable_if_t<
178 std::is_convertible_v<decltype(qHash(std::declval<const T &>())), size_t>
179>> = true;
180}
181
182template <typename T, std::enable_if_t<QHashPrivate::HasQHashSingleArgOverload<T> && !std::is_enum_v<T>, bool> = true>
183size_t qHash(const T &t, size_t seed) noexcept(noexcept(qHash(t)))
184{ return qHash(t) ^ seed; }
185#endif // < Qt 7
186
187template<typename T>
188bool qHashEquals(const T &a, const T &b)
189{
190 return a == b;
191}
192
193namespace QtPrivate {
194
195struct QHashCombine
196{
197 typedef size_t result_type;
198 template <typename T>
199 constexpr result_type operator()(size_t seed, const T &t) const noexcept(noexcept(qHash(t)))
200 // combiner taken from N3876 / boost::hash_combine
201 { return seed ^ (qHash(t) + 0x9e3779b9 + (seed << 6) + (seed >> 2)) ; }
202};
203
204struct QHashCombineCommutative
205{
206 // QHashCombine is a good hash combiner, but is not commutative,
207 // ie. it depends on the order of the input elements. That is
208 // usually what we want: {0,1,3} should hash differently than
209 // {1,3,0}. Except when it isn't (e.g. for QSet and
210 // QHash). Therefore, provide a commutative combiner, too.
211 typedef size_t result_type;
212 template <typename T>
213 constexpr result_type operator()(size_t seed, const T &t) const noexcept(noexcept(qHash(t)))
214 { return seed + qHash(t); } // don't use xor!
215};
216
217template <typename... T>
218using QHashMultiReturnType = decltype(
219 std::declval< std::enable_if_t<(sizeof...(T) > 0)> >(),
220 (qHash(std::declval<const T &>()), ...),
221 size_t{}
222);
223
224// workaround for a MSVC ICE,
225// https://developercommunity.visualstudio.com/content/problem/996540/internal-compiler-error-on-msvc-1924-when-doing-sf.html
226template <typename T>
227inline constexpr bool QNothrowHashableHelper_v = noexcept(qHash(std::declval<const T &>()));
228
229template <typename T, typename Enable = void>
230struct QNothrowHashable : std::false_type {};
231
232template <typename T>
233struct QNothrowHashable<T, std::enable_if_t<QNothrowHashableHelper_v<T>>> : std::true_type {};
234
235template <typename T>
236constexpr inline bool QNothrowHashable_v = QNothrowHashable<T>::value;
237
238} // namespace QtPrivate
239
240template <typename... T>
241constexpr
242#ifdef Q_QDOC
243size_t
244#else
245QtPrivate::QHashMultiReturnType<T...>
246#endif
247qHashMulti(size_t seed, const T &... args)
248 noexcept(std::conjunction_v<QtPrivate::QNothrowHashable<T>...>)
249{
250 QtPrivate::QHashCombine hash;
251 return ((seed = hash(seed, args)), ...), seed;
252}
253
254template <typename... T>
255constexpr
256#ifdef Q_QDOC
257size_t
258#else
259QtPrivate::QHashMultiReturnType<T...>
260#endif
261qHashMultiCommutative(size_t seed, const T &... args)
262 noexcept(std::conjunction_v<QtPrivate::QNothrowHashable<T>...>)
263{
264 QtPrivate::QHashCombineCommutative hash;
265 return ((seed = hash(seed, args)), ...), seed;
266}
267
268template <typename InputIterator>
269inline size_t qHashRange(InputIterator first, InputIterator last, size_t seed = 0)
270 noexcept(noexcept(qHash(*first))) // assume iterator operations don't throw
271{
272 return std::accumulate(first, last, seed, QtPrivate::QHashCombine());
273}
274
275template <typename InputIterator>
276inline size_t qHashRangeCommutative(InputIterator first, InputIterator last, size_t seed = 0)
277 noexcept(noexcept(qHash(*first))) // assume iterator operations don't throw
278{
279 return std::accumulate(first, last, seed, QtPrivate::QHashCombineCommutative());
280}
281
282namespace QHashPrivate {
283template <typename T1, typename T2> static constexpr bool noexceptPairHash()
284{
285 size_t seed = 0;
286 return noexcept(qHash(std::declval<T1>(), seed)) && noexcept(qHash(std::declval<T2>(), seed));
287}
288} // QHashPrivate
289
290template <typename T1, typename T2> inline size_t qHash(const std::pair<T1, T2> &key, size_t seed)
291 noexcept(QHashPrivate::noexceptPairHash<T1, T2>())
292{
293 return qHashMulti(seed, key.first, key.second);
294}
295
296#define QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH(Class, Arguments) \
297 QT_BEGIN_INCLUDE_NAMESPACE \
298 namespace std { \
299 template <> \
300 struct hash< QT_PREPEND_NAMESPACE(Class) > { \
301 using argument_type = QT_PREPEND_NAMESPACE(Class); \
302 using result_type = size_t; \
303 size_t operator()(Arguments s) const \
304 noexcept(QT_PREPEND_NAMESPACE( \
305 QtPrivate::QNothrowHashable_v)<argument_type>) \
306 { \
307 /* this seeds qHash with the result of */ \
308 /* std::hash applied to an int, to reap */ \
309 /* any protection against predictable hash */ \
310 /* values the std implementation may provide */ \
311 using QT_PREPEND_NAMESPACE(qHash); \
312 return qHash(s, qHash(std::hash<int>{}(0))); \
313 } \
314 }; \
315 } \
316 QT_END_INCLUDE_NAMESPACE \
317 /*end*/
318
319#define QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_CREF(Class) \
320 QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH(Class, const argument_type &)
321#define QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_VALUE(Class) \
322 QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH(Class, argument_type)
323
324QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_CREF(QString)
325QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_VALUE(QStringView)
326QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_VALUE(QLatin1StringView)
327QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_VALUE(QByteArrayView)
328QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_CREF(QByteArray)
329QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_CREF(QBitArray)
330
331QT_END_NAMESPACE
332
333#if defined(Q_CC_MSVC)
334#pragma warning( pop )
335#endif
336
337#endif // QHASHFUNCTIONS_H
338

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