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
67Q_CORE_EXPORT int qGlobalQHashSeed();
68Q_CORE_EXPORT void qSetGlobalQHashSeed(int newSeed);
69
70namespace QHashPrivate {
71
72Q_DECL_CONST_FUNCTION constexpr size_t hash(size_t key, size_t seed) noexcept
73{
74 key ^= seed;
75 if constexpr (sizeof(size_t) == 4) {
76 key ^= key >> 16;
77 key *= UINT32_C(0x45d9f3b);
78 key ^= key >> 16;
79 key *= UINT32_C(0x45d9f3b);
80 key ^= key >> 16;
81 return key;
82 } else {
83 quint64 key64 = key;
84 key64 ^= key64 >> 32;
85 key64 *= UINT64_C(0xd6e8feb86659fd93);
86 key64 ^= key64 >> 32;
87 key64 *= UINT64_C(0xd6e8feb86659fd93);
88 key64 ^= key64 >> 32;
89 return size_t(key64);
90 }
91}
92
93}
94
95Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHashBits(const void *p, size_t size, size_t seed = 0) noexcept;
96
97// C++ builtin types
98Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(char key, size_t seed = 0) noexcept
99{ return QHashPrivate::hash(size_t(key), seed); }
100Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(uchar key, size_t seed = 0) noexcept
101{ return QHashPrivate::hash(size_t(key), seed); }
102Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(signed char key, size_t seed = 0) noexcept
103{ return QHashPrivate::hash(size_t(key), seed); }
104Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(ushort key, size_t seed = 0) noexcept
105{ return QHashPrivate::hash(size_t(key), seed); }
106Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(short key, size_t seed = 0) noexcept
107{ return QHashPrivate::hash(size_t(key), seed); }
108Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(uint key, size_t seed = 0) noexcept
109{ return QHashPrivate::hash(size_t(key), seed); }
110Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(int key, size_t seed = 0) noexcept
111{ return QHashPrivate::hash(size_t(key), seed); }
112Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(ulong key, size_t seed = 0) noexcept
113{ return QHashPrivate::hash(size_t(key), seed); }
114Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(long key, size_t seed = 0) noexcept
115{ return QHashPrivate::hash(size_t(key), seed); }
116Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(quint64 key, size_t seed = 0) noexcept
117{
118 if constexpr (sizeof(quint64) > sizeof(size_t))
119 key ^= (key >> 32);
120 return QHashPrivate::hash(size_t(key), seed);
121}
122Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(qint64 key, size_t seed = 0) noexcept { return qHash(quint64(key), seed); }
123Q_DECL_CONST_FUNCTION inline size_t qHash(float key, size_t seed = 0) noexcept
124{
125 // ensure -0 gets mapped to 0
126 key += 0.0f;
127 uint k;
128 memcpy(&k, &key, sizeof(float));
129 return QHashPrivate::hash(k, seed);
130}
131Q_CORE_EXPORT Q_DECL_CONST_FUNCTION size_t qHash(double key, size_t seed = 0) noexcept;
132#if !defined(Q_OS_DARWIN) || defined(Q_CLANG_QDOC)
133Q_CORE_EXPORT Q_DECL_CONST_FUNCTION size_t qHash(long double key, size_t seed = 0) noexcept;
134#endif
135Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(wchar_t key, size_t seed = 0) noexcept
136{ return QHashPrivate::hash(size_t(key), seed); }
137Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(char16_t key, size_t seed = 0) noexcept
138{ return QHashPrivate::hash(size_t(key), seed); }
139Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(char32_t key, size_t seed = 0) noexcept
140{ return QHashPrivate::hash(size_t(key), seed); }
141#ifdef __cpp_char8_t
142Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(char8_t key, size_t seed = 0) noexcept
143{ return QHashPrivate::hash(size_t(key), seed); }
144#endif
145template <class T> inline size_t qHash(const T *key, size_t seed = 0) noexcept
146{
147 return qHash(reinterpret_cast<quintptr>(key), seed);
148}
149Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(std::nullptr_t, size_t seed = 0) noexcept
150{
151 return seed;
152}
153
154// (some) Qt types
155Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(const QChar key, size_t seed = 0) noexcept { return qHash(key.unicode(), seed); }
156Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(const QByteArray &key, size_t seed = 0) noexcept;
157Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(const QByteArrayView &key, size_t seed = 0) noexcept;
158Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(QStringView key, size_t seed = 0) noexcept;
159#if QT_STRINGVIEW_LEVEL < 2
160inline Q_DECL_PURE_FUNCTION size_t qHash(const QString &key, size_t seed = 0) noexcept
161{ return qHash(QStringView{key}, seed); }
162#endif
163Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(const QBitArray &key, size_t seed = 0) noexcept;
164Q_CORE_EXPORT Q_DECL_PURE_FUNCTION size_t qHash(QLatin1String key, size_t seed = 0) noexcept;
165Q_DECL_CONST_FUNCTION constexpr inline size_t qHash(QKeyCombination key, size_t seed = 0) noexcept
166{ return qHash(key.toCombined(), seed); }
167Q_CORE_EXPORT Q_DECL_PURE_FUNCTION uint qt_hash(QStringView key, uint chained = 0) noexcept;
168
169template<typename T> inline size_t qHash(const T &t, size_t seed)
170 noexcept(noexcept(qHash(t)))
171{ return qHash(t) ^ seed; }
172
173namespace QtPrivate {
174
175struct QHashCombine
176{
177 typedef size_t result_type;
178 template <typename T>
179 constexpr result_type operator()(size_t seed, const T &t) const noexcept(noexcept(qHash(t)))
180 // combiner taken from N3876 / boost::hash_combine
181 { return seed ^ (qHash(t) + 0x9e3779b9 + (seed << 6) + (seed >> 2)) ; }
182};
183
184struct QHashCombineCommutative
185{
186 // QHashCombine is a good hash combiner, but is not commutative,
187 // ie. it depends on the order of the input elements. That is
188 // usually what we want: {0,1,3} should hash differently than
189 // {1,3,0}. Except when it isn't (e.g. for QSet and
190 // QHash). Therefore, provide a commutative combiner, too.
191 typedef size_t result_type;
192 template <typename T>
193 constexpr result_type operator()(size_t seed, const T &t) const noexcept(noexcept(qHash(t)))
194 { return seed + qHash(t); } // don't use xor!
195};
196
197template <typename... T>
198using QHashMultiReturnType = decltype(
199 std::declval< std::enable_if_t<(sizeof...(T) > 0)> >(),
200 (qHash(std::declval<const T &>()), ...),
201 size_t{}
202);
203
204// workaround for a MSVC ICE,
205// https://developercommunity.visualstudio.com/content/problem/996540/internal-compiler-error-on-msvc-1924-when-doing-sf.html
206template <typename T>
207inline constexpr bool QNothrowHashableHelper_v = noexcept(qHash(std::declval<const T &>()));
208
209template <typename T, typename Enable = void>
210struct QNothrowHashable : std::false_type {};
211
212template <typename T>
213struct QNothrowHashable<T, std::enable_if_t<QNothrowHashableHelper_v<T>>> : std::true_type {};
214
215} // namespace QtPrivate
216
217template <typename... T>
218constexpr
219#ifdef Q_QDOC
220size_t
221#else
222QtPrivate::QHashMultiReturnType<T...>
223#endif
224qHashMulti(size_t seed, const T &... args)
225 noexcept(std::conjunction_v<QtPrivate::QNothrowHashable<T>...>)
226{
227 QtPrivate::QHashCombine hash;
228 return ((seed = hash(seed, args)), ...), seed;
229}
230
231template <typename... T>
232constexpr
233#ifdef Q_QDOC
234size_t
235#else
236QtPrivate::QHashMultiReturnType<T...>
237#endif
238qHashMultiCommutative(size_t seed, const T &... args)
239 noexcept(std::conjunction_v<QtPrivate::QNothrowHashable<T>...>)
240{
241 QtPrivate::QHashCombineCommutative hash;
242 return ((seed = hash(seed, args)), ...), seed;
243}
244
245template <typename InputIterator>
246inline size_t qHashRange(InputIterator first, InputIterator last, size_t seed = 0)
247 noexcept(noexcept(qHash(*first))) // assume iterator operations don't throw
248{
249 return std::accumulate(first, last, seed, QtPrivate::QHashCombine());
250}
251
252template <typename InputIterator>
253inline size_t qHashRangeCommutative(InputIterator first, InputIterator last, size_t seed = 0)
254 noexcept(noexcept(qHash(*first))) // assume iterator operations don't throw
255{
256 return std::accumulate(first, last, seed, QtPrivate::QHashCombineCommutative());
257}
258
259template <typename T1, typename T2> inline size_t qHash(const std::pair<T1, T2> &key, size_t seed = 0)
260 noexcept(noexcept(qHash(key.first, seed)) && noexcept(qHash(key.second, seed)))
261{
262 return qHashMulti(seed, key.first, key.second);
263}
264
265#define QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH(Class, Arguments) \
266 QT_BEGIN_INCLUDE_NAMESPACE \
267 namespace std { \
268 template <> \
269 struct hash< QT_PREPEND_NAMESPACE(Class) > { \
270 using argument_type = QT_PREPEND_NAMESPACE(Class); \
271 using result_type = size_t; \
272 size_t operator()(Arguments s) const \
273 noexcept(noexcept(QT_PREPEND_NAMESPACE(qHash)(s))) \
274 { \
275 /* this seeds qHash with the result of */ \
276 /* std::hash applied to an int, to reap */ \
277 /* any protection against predictable hash */ \
278 /* values the std implementation may provide */ \
279 return QT_PREPEND_NAMESPACE(qHash)(s, \
280 QT_PREPEND_NAMESPACE(qHash)( \
281 std::hash<int>{}(0))); \
282 } \
283 }; \
284 } \
285 QT_END_INCLUDE_NAMESPACE \
286 /*end*/
287
288#define QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_CREF(Class) \
289 QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH(Class, const argument_type &)
290#define QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_VALUE(Class) \
291 QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH(Class, argument_type)
292
293QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_CREF(QString)
294QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_VALUE(QStringView)
295QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_VALUE(QLatin1String)
296QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_CREF(QByteArray)
297QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_CREF(QBitArray)
298
299QT_END_NAMESPACE
300
301#if defined(Q_CC_MSVC)
302#pragma warning( pop )
303#endif
304
305#endif // QHASHFUNCTIONS_H
306