1/****************************************************************************
2**
3** Copyright (C) 2016 The Qt Company Ltd.
4** Copyright (C) 2015 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Marc Mutz <marc.mutz@kdab.com>
5** Contact: https://www.qt.io/licensing/
6**
7** This file is part of the QtCore module of the Qt Toolkit.
8**
9** $QT_BEGIN_LICENSE:LGPL$
10** Commercial License Usage
11** Licensees holding valid commercial Qt licenses may use this file in
12** accordance with the commercial license agreement provided with the
13** Software or, alternatively, in accordance with the terms contained in
14** a written agreement between you and The Qt Company. For licensing terms
15** and conditions see https://www.qt.io/terms-conditions. For further
16** information use the contact form at https://www.qt.io/contact-us.
17**
18** GNU Lesser General Public License Usage
19** Alternatively, this file may be used under the terms of the GNU Lesser
20** General Public License version 3 as published by the Free Software
21** Foundation and appearing in the file LICENSE.LGPL3 included in the
22** packaging of this file. Please review the following information to
23** ensure the GNU Lesser General Public License version 3 requirements
24** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
25**
26** GNU General Public License Usage
27** Alternatively, this file may be used under the terms of the GNU
28** General Public License version 2.0 or (at your option) the GNU General
29** Public license version 3 or any later version approved by the KDE Free
30** Qt Foundation. The licenses are as published by the Free Software
31** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
32** included in the packaging of this file. Please review the following
33** information to ensure the GNU General Public License requirements will
34** be met: https://www.gnu.org/licenses/gpl-2.0.html and
35** https://www.gnu.org/licenses/gpl-3.0.html.
36**
37** $QT_END_LICENSE$
38**
39****************************************************************************/
40
41#ifndef QHASHFUNCTIONS_H
42#define QHASHFUNCTIONS_H
43
44#include <QtCore/qstring.h>
45#include <QtCore/qpair.h>
46
47#include <numeric> // for std::accumulate
48#include <functional> // for std::hash
49
50#if 0
51#pragma qt_class(QHashFunctions)
52#endif
53
54#if defined(Q_CC_MSVC)
55#pragma warning( push )
56#pragma warning( disable : 4311 ) // disable pointer truncation warning
57#pragma warning( disable : 4127 ) // conditional expression is constant
58#endif
59
60QT_BEGIN_NAMESPACE
61
62class QBitArray;
63class QByteArray;
64class QString;
65class QLatin1String;
66
67#if QT_DEPRECATED_SINCE(6,6)
68QT_DEPRECATED_VERSION_X_6_6("Use QHashSeed instead")
69Q_CORE_EXPORT int qGlobalQHashSeed();
70QT_DEPRECATED_VERSION_X_6_6("Use QHashSeed instead")
71Q_CORE_EXPORT void qSetGlobalQHashSeed(int newSeed);
72#endif
73
74struct QHashSeed
75{
76 constexpr QHashSeed(size_t d = 0) : data(d) {}
77 constexpr operator size_t() const noexcept { return data; }
78
79 static Q_CORE_EXPORT QHashSeed globalSeed() noexcept Q_DECL_PURE_FUNCTION;
80 static Q_CORE_EXPORT void setDeterministicGlobalSeed();
81 static Q_CORE_EXPORT void resetRandomGlobalSeed();
82private:
83 size_t data;
84};
85
86namespace QHashPrivate {
87
88Q_DECL_CONST_FUNCTION constexpr size_t hash(size_t key, size_t seed) noexcept
89{
90 key ^= seed;
91 if constexpr (sizeof(size_t) == 4) {
92 key ^= key >> 16;
93 key *= UINT32_C(0x45d9f3b);
94 key ^= key >> 16;
95 key *= UINT32_C(0x45d9f3b);
96 key ^= key >> 16;
97 return key;
98 } else {
99 quint64 key64 = key;
100 key64 ^= key64 >> 32;
101 key64 *= UINT64_C(0xd6e8feb86659fd93);
102 key64 ^= key64 >> 32;
103 key64 *= UINT64_C(0xd6e8feb86659fd93);
104 key64 ^= key64 >> 32;
105 return size_t(key64);
106 }
107}
108
109template <typename T, typename = void>
110constexpr inline bool HasQHashSingleArgOverload = false;
111
112template <typename T>
113constexpr inline bool HasQHashSingleArgOverload<T, std::enable_if_t<
114 std::is_convertible_v<decltype(qHash(std::declval<const T &>())), size_t>
115>> = true;
116
117template <typename T1, typename T2> static constexpr bool noexceptPairHash();
118}
119
120Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHashBits(const void *p, size_t size, size_t seed = 0) noexcept;
121
122// implementation below qHashMulti
123template <typename T1, typename T2> inline size_t qHash(const std::pair<T1, T2> &key, size_t seed = 0)
124 noexcept(QHashPrivate::noexceptPairHash<T1, T2>());
125
126// C++ builtin types
127Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(char key, size_t seed = 0) noexcept
128{ return QHashPrivate::hash(size_t(key), seed); }
129Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(uchar key, size_t seed = 0) noexcept
130{ return QHashPrivate::hash(size_t(key), seed); }
131Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(signed char key, size_t seed = 0) noexcept
132{ return QHashPrivate::hash(size_t(key), seed); }
133Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(ushort key, size_t seed = 0) noexcept
134{ return QHashPrivate::hash(size_t(key), seed); }
135Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(short key, size_t seed = 0) noexcept
136{ return QHashPrivate::hash(size_t(key), seed); }
137Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(uint key, size_t seed = 0) noexcept
138{ return QHashPrivate::hash(size_t(key), seed); }
139Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(int key, size_t seed = 0) noexcept
140{ return QHashPrivate::hash(size_t(key), seed); }
141Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(ulong key, size_t seed = 0) noexcept
142{ return QHashPrivate::hash(size_t(key), seed); }
143Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(long key, size_t seed = 0) noexcept
144{ return QHashPrivate::hash(size_t(key), seed); }
145Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(quint64 key, size_t seed = 0) noexcept
146{
147 if constexpr (sizeof(quint64) > sizeof(size_t))
148 key ^= (key >> 32);
149 return QHashPrivate::hash(size_t(key), seed);
150}
151Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(qint64 key, size_t seed = 0) noexcept { return qHash(quint64(key), seed); }
152Q_DECL_CONST_FUNCTION inline size_t qHash(float key, size_t seed = 0) noexcept
153{
154 // ensure -0 gets mapped to 0
155 key += 0.0f;
156 uint k;
157 memcpy(&k, &key, sizeof(float));
158 return QHashPrivate::hash(k, seed);
159}
160Q_CORE_EXPORT Q_DECL_CONST_FUNCTION size_t qHash(double key, size_t seed = 0) noexcept;
161#if !defined(Q_OS_DARWIN) || defined(Q_CLANG_QDOC)
162Q_CORE_EXPORT Q_DECL_CONST_FUNCTION size_t qHash(long double key, size_t seed = 0) noexcept;
163#endif
164Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(wchar_t key, size_t seed = 0) noexcept
165{ return QHashPrivate::hash(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(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(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(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}
182
183// (some) Qt types
184Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(const QChar key, size_t seed = 0) noexcept { return qHash(key.unicode(), seed); }
185Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(const QByteArray &key, size_t seed = 0) noexcept;
186Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(const QByteArrayView &key, size_t seed = 0) noexcept;
187Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(QStringView key, size_t seed = 0) noexcept;
188#if QT_STRINGVIEW_LEVEL < 2
189inline Q_DECL_PURE_FUNCTION size_t qHash(const QString &key, size_t seed = 0) noexcept
190{ return qHash(QStringView{key}, seed); }
191#endif
192Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(const QBitArray &key, size_t seed = 0) noexcept;
193Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(QLatin1String key, size_t seed = 0) noexcept;
194Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(QKeyCombination key, size_t seed = 0) noexcept
195{ return qHash(key.toCombined(), seed); }
196Q_CORE_EXPORT Q_DECL_PURE_FUNCTION uint qt_hash(QStringView key, uint chained = 0) noexcept;
197
198template <typename Enum>
199Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(QFlags<Enum> flags, size_t seed = 0) noexcept
200{ return qHash(flags.toInt(), seed); }
201
202template <typename T, std::enable_if_t<QHashPrivate::HasQHashSingleArgOverload<T>, bool> = true>
203size_t qHash(const T &t, size_t seed) noexcept(noexcept(qHash(t)))
204{ return qHash(t) ^ seed; }
205
206template<typename T>
207bool qHashEquals(const T &a, const T &b)
208{
209 return a == b;
210}
211
212namespace QtPrivate {
213
214struct QHashCombine
215{
216 typedef size_t result_type;
217 template <typename T>
218 constexpr result_type operator()(size_t seed, const T &t) const noexcept(noexcept(qHash(t)))
219 // combiner taken from N3876 / boost::hash_combine
220 { return seed ^ (qHash(t) + 0x9e3779b9 + (seed << 6) + (seed >> 2)) ; }
221};
222
223struct QHashCombineCommutative
224{
225 // QHashCombine is a good hash combiner, but is not commutative,
226 // ie. it depends on the order of the input elements. That is
227 // usually what we want: {0,1,3} should hash differently than
228 // {1,3,0}. Except when it isn't (e.g. for QSet and
229 // QHash). Therefore, provide a commutative combiner, too.
230 typedef size_t result_type;
231 template <typename T>
232 constexpr result_type operator()(size_t seed, const T &t) const noexcept(noexcept(qHash(t)))
233 { return seed + qHash(t); } // don't use xor!
234};
235
236template <typename... T>
237using QHashMultiReturnType = decltype(
238 std::declval< std::enable_if_t<(sizeof...(T) > 0)> >(),
239 (qHash(std::declval<const T &>()), ...),
240 size_t{}
241);
242
243// workaround for a MSVC ICE,
244// https://developercommunity.visualstudio.com/content/problem/996540/internal-compiler-error-on-msvc-1924-when-doing-sf.html
245template <typename T>
246inline constexpr bool QNothrowHashableHelper_v = noexcept(qHash(std::declval<const T &>()));
247
248template <typename T, typename Enable = void>
249struct QNothrowHashable : std::false_type {};
250
251template <typename T>
252struct QNothrowHashable<T, std::enable_if_t<QNothrowHashableHelper_v<T>>> : std::true_type {};
253
254} // namespace QtPrivate
255
256template <typename... T>
257constexpr
258#ifdef Q_QDOC
259size_t
260#else
261QtPrivate::QHashMultiReturnType<T...>
262#endif
263qHashMulti(size_t seed, const T &... args)
264 noexcept(std::conjunction_v<QtPrivate::QNothrowHashable<T>...>)
265{
266 QtPrivate::QHashCombine hash;
267 return ((seed = hash(seed, args)), ...), seed;
268}
269
270template <typename... T>
271constexpr
272#ifdef Q_QDOC
273size_t
274#else
275QtPrivate::QHashMultiReturnType<T...>
276#endif
277qHashMultiCommutative(size_t seed, const T &... args)
278 noexcept(std::conjunction_v<QtPrivate::QNothrowHashable<T>...>)
279{
280 QtPrivate::QHashCombineCommutative hash;
281 return ((seed = hash(seed, args)), ...), seed;
282}
283
284template <typename InputIterator>
285inline size_t qHashRange(InputIterator first, InputIterator last, size_t seed = 0)
286 noexcept(noexcept(qHash(*first))) // assume iterator operations don't throw
287{
288 return std::accumulate(first, last, seed, QtPrivate::QHashCombine());
289}
290
291template <typename InputIterator>
292inline size_t qHashRangeCommutative(InputIterator first, InputIterator last, size_t seed = 0)
293 noexcept(noexcept(qHash(*first))) // assume iterator operations don't throw
294{
295 return std::accumulate(first, last, seed, QtPrivate::QHashCombineCommutative());
296}
297
298namespace QHashPrivate {
299template <typename T1, typename T2> static constexpr bool noexceptPairHash()
300{
301 size_t seed = 0;
302 return noexcept(qHash(std::declval<T1>(), seed)) && noexcept(qHash(std::declval<T2>(), seed));
303}
304} // QHashPrivate
305
306template <typename T1, typename T2> inline size_t qHash(const std::pair<T1, T2> &key, size_t seed)
307 noexcept(QHashPrivate::noexceptPairHash<T1, T2>())
308{
309 return qHashMulti(seed, key.first, key.second);
310}
311
312#define QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH(Class, Arguments) \
313 QT_BEGIN_INCLUDE_NAMESPACE \
314 namespace std { \
315 template <> \
316 struct hash< QT_PREPEND_NAMESPACE(Class) > { \
317 using argument_type = QT_PREPEND_NAMESPACE(Class); \
318 using result_type = size_t; \
319 size_t operator()(Arguments s) const \
320 noexcept(noexcept(QT_PREPEND_NAMESPACE(qHash)(s))) \
321 { \
322 /* this seeds qHash with the result of */ \
323 /* std::hash applied to an int, to reap */ \
324 /* any protection against predictable hash */ \
325 /* values the std implementation may provide */ \
326 return QT_PREPEND_NAMESPACE(qHash)(s, \
327 QT_PREPEND_NAMESPACE(qHash)( \
328 std::hash<int>{}(0))); \
329 } \
330 }; \
331 } \
332 QT_END_INCLUDE_NAMESPACE \
333 /*end*/
334
335#define QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_CREF(Class) \
336 QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH(Class, const argument_type &)
337#define QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_VALUE(Class) \
338 QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH(Class, argument_type)
339
340QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_CREF(QString)
341QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_VALUE(QStringView)
342QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_VALUE(QLatin1String)
343QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_CREF(QByteArray)
344QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_CREF(QBitArray)
345
346QT_END_NAMESPACE
347
348#if defined(Q_CC_MSVC)
349#pragma warning( pop )
350#endif
351
352#endif // QHASHFUNCTIONS_H
353

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