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
97#define QT_MK_QHASH_COMPAT(X) \
98 template <typename T, std::enable_if_t<std::is_same_v<T, X>, bool> = true> \
99 constexpr size_t qHash(T key, size_t seed = 0) noexcept \
100 /* QHashPrivate::hash() xors before mixing, while 1-to-2-arg adapter xors after */ \
101 { return QHashPrivate::hash(size_t(key), 0 QT7_ONLY(+ seed)) QT6_ONLY(^ seed); } \
102 /* end */
103QT_MK_QHASH_COMPAT(bool) // QTBUG-126674
104Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(char key, size_t seed = 0) noexcept
105{ return QHashPrivate::hash(key: size_t(key), seed); }
106Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(uchar key, size_t seed = 0) noexcept
107{ return QHashPrivate::hash(key: size_t(key), seed); }
108Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(signed char key, size_t seed = 0) noexcept
109{ return QHashPrivate::hash(key: size_t(key), seed); }
110Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(ushort key, size_t seed = 0) noexcept
111{ return QHashPrivate::hash(key: size_t(key), seed); }
112Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(short key, size_t seed = 0) noexcept
113{ return QHashPrivate::hash(key: size_t(key), seed); }
114Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(uint key, size_t seed = 0) noexcept
115{ return QHashPrivate::hash(key: size_t(key), seed); }
116Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(int key, size_t seed = 0) noexcept
117{ return QHashPrivate::hash(key: size_t(key), seed); }
118Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(ulong key, size_t seed = 0) noexcept
119{ return QHashPrivate::hash(key: size_t(key), seed); }
120Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(long key, size_t seed = 0) noexcept
121{ return QHashPrivate::hash(key: size_t(key), seed); }
122#undef QT_MK_QHASH_COMPAT
123Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(quint64 key, size_t seed = 0) noexcept
124{
125 if constexpr (sizeof(quint64) > sizeof(size_t))
126 key ^= (key >> 32);
127 return QHashPrivate::hash(key: size_t(key), seed);
128}
129Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(qint64 key, size_t seed = 0) noexcept
130{
131 if constexpr (sizeof(qint64) > sizeof(size_t)) {
132 // Avoid QTBUG-116080: we XOR the top half with its own sign bit:
133 // - if the qint64 is in range of qint32, then signmask ^ high == 0
134 // (for Qt 7 only)
135 // - if the qint64 is in range of quint32, then signmask == 0 and we
136 // do the same as the quint64 overload above
137 quint32 high = quint32(quint64(key) >> 32);
138 quint32 low = quint32(quint64(key));
139 quint32 signmask = qint32(high) >> 31; // all zeroes or all ones
140 signmask = QT_VERSION_MAJOR > 6 ? signmask : 0;
141 low ^= signmask ^ high;
142 return qHash(key: low, seed);
143 }
144 return qHash(key: quint64(key), seed);
145}
146#ifdef QT_SUPPORTS_INT128
147constexpr size_t qHash(quint128 key, size_t seed = 0) noexcept
148{
149 return qHash(key: quint64(key + (key >> 64)), seed);
150}
151constexpr size_t qHash(qint128 key, size_t seed = 0) noexcept
152{
153 // Avoid QTBUG-116080: same as above, but with double the sizes and without
154 // the need for compatibility
155 quint64 high = quint64(quint128(key) >> 64);
156 quint64 low = quint64(quint128(key));
157 quint64 signmask = qint64(high) >> 63; // all zeroes or all ones
158 low += signmask ^ high;
159 return qHash(key: low, seed);
160}
161#endif // QT_SUPPORTS_INT128
162Q_DECL_CONST_FUNCTION inline size_t qHash(float key, size_t seed = 0) noexcept
163{
164 // ensure -0 gets mapped to 0
165 key += 0.0f;
166 uint k;
167 memcpy(dest: &k, src: &key, n: sizeof(float));
168 return QHashPrivate::hash(key: k, seed);
169}
170Q_CORE_EXPORT Q_DECL_CONST_FUNCTION size_t qHash(double key, size_t seed = 0) noexcept;
171Q_CORE_EXPORT Q_DECL_CONST_FUNCTION size_t qHash(long double key, size_t seed = 0) noexcept;
172Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(wchar_t key, size_t seed = 0) noexcept
173{ return QHashPrivate::hash(key: size_t(key), seed); }
174Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(char16_t key, size_t seed = 0) noexcept
175{ return QHashPrivate::hash(key: size_t(key), seed); }
176Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(char32_t key, size_t seed = 0) noexcept
177{ return QHashPrivate::hash(key: size_t(key), seed); }
178#ifdef __cpp_char8_t
179Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(char8_t key, size_t seed = 0) noexcept
180{ return QHashPrivate::hash(size_t(key), seed); }
181#endif
182template <class T> inline size_t qHash(const T *key, size_t seed = 0) noexcept
183{
184 return qHash(key: reinterpret_cast<quintptr>(key), seed);
185}
186Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(std::nullptr_t, size_t seed = 0) noexcept
187{
188 return seed;
189}
190template <class Enum, std::enable_if_t<std::is_enum_v<Enum>, bool> = true>
191Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(Enum e, size_t seed = 0) noexcept
192{ return QHashPrivate::hash(key: qToUnderlying(e), seed); }
193
194// (some) Qt types
195Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(const QChar key, size_t seed = 0) noexcept { return qHash(key: key.unicode(), seed); }
196
197#if QT_CORE_REMOVED_SINCE(6, 4)
198Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(const QByteArray &key, size_t seed = 0) noexcept;
199Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(const QByteArrayView &key, size_t seed = 0) noexcept;
200#else
201Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(QByteArrayView key, size_t seed = 0) noexcept;
202inline Q_DECL_PURE_FUNCTION size_t qHash(const QByteArray &key, size_t seed = 0
203 QT6_DECL_NEW_OVERLOAD_TAIL) noexcept
204{ return qHash(key: qToByteArrayViewIgnoringNull(b: key), seed); }
205#endif
206
207Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(QStringView key, size_t seed = 0) noexcept;
208inline Q_DECL_PURE_FUNCTION size_t qHash(const QString &key, size_t seed = 0) noexcept
209{ return qHash(key: QStringView{key}, seed); }
210#ifndef QT_BOOTSTRAPPED
211Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(const QBitArray &key, size_t seed = 0) noexcept;
212#endif
213Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(QLatin1StringView key, size_t seed = 0) noexcept;
214Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(QKeyCombination key, size_t seed = 0) noexcept
215{ return qHash(key: key.toCombined(), seed); }
216Q_CORE_EXPORT Q_DECL_PURE_FUNCTION uint qt_hash(QStringView key, uint chained = 0) noexcept;
217
218template <typename Enum>
219Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(QFlags<Enum> flags, size_t seed = 0) noexcept
220{ return qHash(flags.toInt(), seed); }
221
222// ### Qt 7: remove this "catch-all" overload logic, and require users
223// to provide the two-argument version of qHash.
224#if (QT_VERSION < QT_VERSION_CHECK(7, 0, 0))
225// Beware of moving this code from here. It needs to see all the
226// declarations of qHash overloads for C++ fundamental types *before*
227// its own declaration.
228namespace QHashPrivate {
229template <typename T, typename = void>
230constexpr inline bool HasQHashSingleArgOverload = false;
231
232template <typename T>
233constexpr inline bool HasQHashSingleArgOverload<T, std::enable_if_t<
234 std::is_convertible_v<decltype(qHash(key: std::declval<const T &>())), size_t>
235>> = true;
236}
237
238// Add Args... to make this overload consistently a worse match than
239// original 2-arg qHash overloads (QTBUG-126659)
240template <typename T, typename...Args,
241 std::enable_if_t<QHashPrivate::HasQHashSingleArgOverload<T>
242 && sizeof...(Args) == 0 && !std::is_enum_v<T>, bool> = true>
243constexpr size_t qHash(const T &t, size_t seed, Args&&...) noexcept(noexcept(qHash(t)))
244{ return qHash(t) ^ seed; }
245#endif // < Qt 7
246
247namespace QHashPrivate {
248
249namespace detail {
250// approximates std::equality_comparable_with
251template <typename T, typename U, typename = void>
252struct is_equality_comparable_with : std::false_type {};
253
254template <typename T, typename U>
255struct is_equality_comparable_with<T, U,
256 std::void_t<
257 decltype(bool(std::declval<T>() == std::declval<U>())),
258 decltype(bool(std::declval<U>() == std::declval<T>())),
259 decltype(bool(std::declval<T>() != std::declval<U>())),
260 decltype(bool(std::declval<U>() != std::declval<T>()))
261 >>
262 : std::true_type {};
263}
264
265template <typename Key, typename T> struct HeterogeneouslySearchableWithHelper
266 : std::conjunction<
267 // if Key and T are not the same (member already exists)
268 std::negation<std::is_same<Key, T>>,
269 // but are comparable amongst each other
270 detail::is_equality_comparable_with<Key, T>,
271 // and supports heteregenous hashing
272 QHashHeterogeneousSearch<Key, T>
273 > {};
274
275template <typename Key, typename T>
276using HeterogeneouslySearchableWith = HeterogeneouslySearchableWithHelper<
277 q20::remove_cvref_t<Key>,
278 q20::remove_cvref_t<T>
279>;
280
281template <typename Key, typename K>
282using if_heterogeneously_searchable_with = std::enable_if_t<
283 QHashPrivate::HeterogeneouslySearchableWith<Key, K>::value,
284 bool>;
285
286}
287
288template<typename T>
289bool qHashEquals(const T &a, const T &b)
290{
291 return a == b;
292}
293
294template <typename T1, typename T2, QHashPrivate::if_heterogeneously_searchable_with<T1, T2> = true>
295bool qHashEquals(const T1 &a, const T2 &b)
296{
297 return a == b;
298}
299
300namespace QtPrivate {
301template <typename Mixer> struct QHashCombinerWithSeed : private Mixer
302{
303 using result_type = typename Mixer::result_type;
304 size_t seed;
305 constexpr QHashCombinerWithSeed(result_type s) noexcept : seed(s) {}
306
307 template <typename T>
308 constexpr result_type operator()(result_type result, const T &t) const
309 noexcept(noexcept(qHash(t, seed)))
310 {
311 return Mixer::operator()(result, qHash(t, seed));
312 }
313};
314
315#if QT_VERSION < QT_VERSION_CHECK(7, 0, 0) || defined(QT_BOOTSTRAPPED)
316// Earlier Qt 6.x versions of qHashMulti() failed to pass the seed as the seed
317// argument of qHash(), so this class exists for compatibility with user and
318// inline code that relies on the old behavior. For Qt 7, we'll replace with
319// the above version, except for the bootstrapped tools (which have no seed).
320template <typename Mixer> struct QHashCombiner : private Mixer
321{
322 using result_type = typename Mixer::result_type;
323
324 static constexpr size_t seed = 0;
325 constexpr QHashCombiner(result_type) noexcept {}
326 Q_DECL_DEPRECATED_X("pass the seed argument") constexpr QHashCombiner() noexcept {}
327
328 template <typename T>
329 constexpr result_type operator()(result_type result, const T &t) const
330 noexcept(noexcept(qHash(t, seed)))
331 {
332 return Mixer::operator()(result, qHash(t, seed));
333 }
334};
335#else
336template <typename Mixer> using QHashCombiner = QHashCombinerWithSeed<Mixer>;
337#endif
338
339struct QHashCombineMixer
340{
341 typedef size_t result_type;
342 constexpr result_type operator()(result_type result, result_type hash) const noexcept
343 {
344 // combiner taken from N3876 / boost::hash_combine
345 return result ^ (hash + 0x9e3779b9 + (result << 6) + (result >> 2));
346 }
347};
348using QHashCombine = QHashCombiner<QHashCombineMixer>;
349using QHashCombineWithSeed = QHashCombinerWithSeed<QHashCombineMixer>;
350
351struct QHashCombineCommutativeMixer : std::plus<size_t>
352{
353 // QHashCombine is a good hash combiner, but is not commutative,
354 // ie. it depends on the order of the input elements. That is
355 // usually what we want: {0,1,3} should hash differently than
356 // {1,3,0}. Except when it isn't (e.g. for QSet and
357 // QHash). Therefore, provide a commutative combiner, too.
358 typedef size_t result_type;
359};
360using QHashCombineCommutative = QHashCombiner<QHashCombineCommutativeMixer>;
361using QHashCombineCommutativeWithSeed = QHashCombinerWithSeed<QHashCombineCommutativeMixer>;
362
363template <typename... T>
364using QHashMultiReturnType = decltype(
365 std::declval< std::enable_if_t<(sizeof...(T) > 0)> >(),
366 (qHash(std::declval<const T &>(), size_t(0)), ...),
367 size_t{}
368);
369
370// workaround for a MSVC ICE,
371// https://developercommunity.visualstudio.com/content/problem/996540/internal-compiler-error-on-msvc-1924-when-doing-sf.html
372template <typename T>
373inline constexpr bool QNothrowHashableHelper_v = noexcept(qHash(std::declval<const T &>(), size_t(0)));
374
375template <typename T, typename Enable = void>
376struct QNothrowHashable : std::false_type {};
377
378template <typename T>
379struct QNothrowHashable<T, std::enable_if_t<QNothrowHashableHelper_v<T>>> : std::true_type {};
380
381template <typename T>
382constexpr inline bool QNothrowHashable_v = QNothrowHashable<T>::value;
383
384} // namespace QtPrivate
385
386template <typename... T>
387constexpr
388#ifdef Q_QDOC
389size_t
390#else
391QtPrivate::QHashMultiReturnType<T...>
392#endif
393qHashMulti(size_t seed, const T &... args)
394 noexcept(std::conjunction_v<QtPrivate::QNothrowHashable<T>...>)
395{
396 QtPrivate::QHashCombine hash(seed);
397 return ((seed = hash(seed, args)), ...), seed;
398}
399
400template <typename... T>
401constexpr
402#ifdef Q_QDOC
403size_t
404#else
405QtPrivate::QHashMultiReturnType<T...>
406#endif
407qHashMultiCommutative(size_t seed, const T &... args)
408 noexcept(std::conjunction_v<QtPrivate::QNothrowHashable<T>...>)
409{
410 QtPrivate::QHashCombineCommutative hash(seed);
411 return ((seed = hash(seed, args)), ...), seed;
412}
413
414template <typename InputIterator>
415inline size_t qHashRange(InputIterator first, InputIterator last, size_t seed = 0)
416 noexcept(noexcept(qHash(*first))) // assume iterator operations don't throw
417{
418 return std::accumulate(first, last, seed, QtPrivate::QHashCombine(seed));
419}
420
421template <typename InputIterator>
422inline size_t qHashRangeCommutative(InputIterator first, InputIterator last, size_t seed = 0)
423 noexcept(noexcept(qHash(*first))) // assume iterator operations don't throw
424{
425 return std::accumulate(first, last, seed, QtPrivate::QHashCombineCommutative(seed));
426}
427
428namespace QHashPrivate {
429template <typename T1, typename T2> static constexpr bool noexceptPairHash()
430{
431 size_t seed = 0;
432 return noexcept(qHash(std::declval<T1>(), seed)) && noexcept(qHash(std::declval<T2>(), seed));
433}
434} // QHashPrivate
435
436template <typename T1, typename T2> inline size_t qHash(const std::pair<T1, T2> &key, size_t seed)
437 noexcept(QHashPrivate::noexceptPairHash<T1, T2>())
438{
439 return qHashMulti(seed, key.first, key.second);
440}
441
442#define QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH(Class, Arguments) \
443 QT_BEGIN_INCLUDE_NAMESPACE \
444 namespace std { \
445 template <> \
446 struct hash< QT_PREPEND_NAMESPACE(Class) > { \
447 using argument_type = QT_PREPEND_NAMESPACE(Class); \
448 using result_type = size_t; \
449 size_t operator()(Arguments s) const \
450 noexcept(QT_PREPEND_NAMESPACE( \
451 QtPrivate::QNothrowHashable_v)<argument_type>) \
452 { \
453 /* this seeds qHash with the result of */ \
454 /* std::hash applied to an int, to reap */ \
455 /* any protection against predictable hash */ \
456 /* values the std implementation may provide */ \
457 using QT_PREPEND_NAMESPACE(qHash); \
458 return qHash(s, qHash(std::hash<int>{}(0))); \
459 } \
460 }; \
461 } \
462 QT_END_INCLUDE_NAMESPACE \
463 /*end*/
464
465#define QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_CREF(Class) \
466 QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH(Class, const argument_type &)
467#define QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_VALUE(Class) \
468 QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH(Class, argument_type)
469
470QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_CREF(QString)
471QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_VALUE(QStringView)
472QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_VALUE(QLatin1StringView)
473QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_VALUE(QByteArrayView)
474QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_CREF(QByteArray)
475#ifndef QT_BOOTSTRAPPED
476QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_CREF(QBitArray)
477#endif
478
479QT_END_NAMESPACE
480
481#if defined(Q_CC_MSVC)
482#pragma warning( pop )
483#endif
484
485#endif // QHASHFUNCTIONS_H
486

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