summaryrefslogtreecommitdiffstats
path: root/src/corelib/tools/qhash.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/corelib/tools/qhash.h')
-rw-r--r--src/corelib/tools/qhash.h123
1 files changed, 18 insertions, 105 deletions
diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h
index a9ece12670..2080a22e23 100644
--- a/src/corelib/tools/qhash.h
+++ b/src/corelib/tools/qhash.h
@@ -38,10 +38,9 @@
#include <QtCore/qchar.h>
#include <QtCore/qiterator.h>
#include <QtCore/qlist.h>
-#include <QtCore/qpair.h>
#include <QtCore/qrefcount.h>
+#include <QtCore/qhashfunctions.h>
-#include <numeric> // for std::accumulate
#ifdef Q_COMPILER_INITIALIZER_LISTS
#include <initializer_list>
#endif
@@ -54,101 +53,6 @@
QT_BEGIN_NAMESPACE
-class QBitArray;
-class QByteArray;
-class QString;
-class QStringRef;
-class QLatin1String;
-
-Q_CORE_EXPORT Q_DECL_PURE_FUNCTION uint qHashBits(const void *p, size_t size, uint seed = 0) Q_DECL_NOTHROW;
-
-Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qHash(char key, uint seed = 0) Q_DECL_NOTHROW { return uint(key) ^ seed; }
-Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qHash(uchar key, uint seed = 0) Q_DECL_NOTHROW { return uint(key) ^ seed; }
-Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qHash(signed char key, uint seed = 0) Q_DECL_NOTHROW { return uint(key) ^ seed; }
-Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qHash(ushort key, uint seed = 0) Q_DECL_NOTHROW { return uint(key) ^ seed; }
-Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qHash(short key, uint seed = 0) Q_DECL_NOTHROW { return uint(key) ^ seed; }
-Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qHash(uint key, uint seed = 0) Q_DECL_NOTHROW { return key ^ seed; }
-Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qHash(int key, uint seed = 0) Q_DECL_NOTHROW { return uint(key) ^ seed; }
-Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qHash(ulong key, uint seed = 0) Q_DECL_NOTHROW
-{
- return (sizeof(ulong) > sizeof(uint))
- ? (uint(((key >> (8 * sizeof(uint) - 1)) ^ key) & (~0U)) ^ seed)
- : (uint(key & (~0U)) ^ seed);
-}
-Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qHash(long key, uint seed = 0) Q_DECL_NOTHROW { return qHash(ulong(key), seed); }
-Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qHash(quint64 key, uint seed = 0) Q_DECL_NOTHROW
-{
- return uint(((key >> (8 * sizeof(uint) - 1)) ^ key) & (~0U)) ^ seed;
-}
-Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qHash(qint64 key, uint seed = 0) Q_DECL_NOTHROW { return qHash(quint64(key), seed); }
-Q_CORE_EXPORT Q_DECL_CONST_FUNCTION uint qHash(float key, uint seed = 0) Q_DECL_NOTHROW;
-Q_CORE_EXPORT Q_DECL_CONST_FUNCTION uint qHash(double key, uint seed = 0) Q_DECL_NOTHROW;
-#ifndef Q_OS_DARWIN
-Q_CORE_EXPORT Q_DECL_CONST_FUNCTION uint qHash(long double key, uint seed = 0) Q_DECL_NOTHROW;
-#endif
-Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qHash(const QChar key, uint seed = 0) Q_DECL_NOTHROW { return qHash(key.unicode(), seed); }
-Q_CORE_EXPORT Q_DECL_PURE_FUNCTION uint qHash(const QByteArray &key, uint seed = 0) Q_DECL_NOTHROW;
-Q_CORE_EXPORT Q_DECL_PURE_FUNCTION uint qHash(const QString &key, uint seed = 0) Q_DECL_NOTHROW;
-Q_CORE_EXPORT Q_DECL_PURE_FUNCTION uint qHash(const QStringRef &key, uint seed = 0) Q_DECL_NOTHROW;
-Q_CORE_EXPORT Q_DECL_PURE_FUNCTION uint qHash(const QBitArray &key, uint seed = 0) Q_DECL_NOTHROW;
-Q_CORE_EXPORT Q_DECL_PURE_FUNCTION uint qHash(QLatin1String key, uint seed = 0) Q_DECL_NOTHROW;
-Q_CORE_EXPORT Q_DECL_PURE_FUNCTION uint qt_hash(const QString &key) Q_DECL_NOTHROW;
-Q_CORE_EXPORT Q_DECL_PURE_FUNCTION uint qt_hash(const QStringRef &key) Q_DECL_NOTHROW;
-
-template <class T> inline uint qHash(const T *key, uint seed = 0) Q_DECL_NOTHROW
-{
- return qHash(reinterpret_cast<quintptr>(key), seed);
-}
-template<typename T> inline uint qHash(const T &t, uint seed)
- Q_DECL_NOEXCEPT_EXPR(noexcept(qHash(t)))
-{ return (qHash(t) ^ seed); }
-
-namespace QtPrivate {
-
-struct QHashCombine {
- typedef uint result_type;
- template <typename T>
- Q_DECL_CONSTEXPR result_type operator()(uint seed, const T &t) const Q_DECL_NOEXCEPT_EXPR(noexcept(qHash(t)))
- // combiner taken from N3876 / boost::hash_combine
- { return seed ^ (qHash(t) + 0x9e3779b9 + (seed << 6) + (seed >> 2)) ; }
-};
-
-struct QHashCombineCommutative {
- // QHashCombine is a good hash combiner, but is not commutative,
- // ie. it depends on the order of the input elements. That is
- // usually what we want: {0,1,3} should hash differently than
- // {1,3,0}. Except when it isn't (e.g. for QSet and
- // QHash). Therefore, provide a commutative combiner, too.
- typedef uint result_type;
- template <typename T>
- Q_DECL_CONSTEXPR result_type operator()(uint seed, const T &t) const Q_DECL_NOEXCEPT_EXPR(noexcept(qHash(t)))
- { return seed + qHash(t); } // don't use xor!
-};
-
-} // namespace QtPrivate
-
-template <typename InputIterator>
-inline uint qHashRange(InputIterator first, InputIterator last, uint seed = 0)
- Q_DECL_NOEXCEPT_EXPR(noexcept(qHash(*first))) // assume iterator operations don't throw
-{
- return std::accumulate(first, last, seed, QtPrivate::QHashCombine());
-}
-
-template <typename InputIterator>
-inline uint qHashRangeCommutative(InputIterator first, InputIterator last, uint seed = 0)
- Q_DECL_NOEXCEPT_EXPR(noexcept(qHash(*first))) // assume iterator operations don't throw
-{
- return std::accumulate(first, last, seed, QtPrivate::QHashCombineCommutative());
-}
-
-template <typename T1, typename T2> inline uint qHash(const QPair<T1, T2> &key, uint seed = 0)
- Q_DECL_NOEXCEPT_EXPR(noexcept(qHash(key.first, seed)) && noexcept(qHash(key.second, seed)))
-{
- uint h1 = qHash(key.first, seed);
- uint h2 = qHash(key.second, seed);
- return ((h1 << 16) | (h1 >> 16)) ^ h2 ^ seed;
-}
-
struct Q_CORE_EXPORT QHashData
{
struct Node {
@@ -449,6 +353,7 @@ public:
class const_iterator
{
friend class iterator;
+ friend class QSet<Key>;
QHashData::Node *i;
public:
@@ -547,6 +452,7 @@ private:
void detach_helper();
void freeData(QHashData *d);
Node **findNode(const Key &key, uint *hp = 0) const;
+ Node **findNode(const Key &key, uint h) const;
Node *createNode(uint h, const Key &key, const T &value, Node **nextNode);
void deleteNode(Node *node);
static void deleteNode2(QHashData::Node *node);
@@ -942,17 +848,10 @@ Q_INLINE_TEMPLATE bool QHash<Key, T>::contains(const Key &akey) const
}
template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::Node **QHash<Key, T>::findNode(const Key &akey,
- uint *ahp) const
+Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::Node **QHash<Key, T>::findNode(const Key &akey, uint h) const
{
Node **node;
- uint h = 0;
- if (d->numBuckets || ahp) {
- h = qHash(akey, d->seed);
- if (ahp)
- *ahp = h;
- }
if (d->numBuckets) {
node = reinterpret_cast<Node **>(&d->buckets[h % d->numBuckets]);
Q_ASSERT(*node == e || (*node)->next);
@@ -965,6 +864,20 @@ Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::Node **QHash<Key, T>::findNode(cons
}
template <class Key, class T>
+Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::Node **QHash<Key, T>::findNode(const Key &akey,
+ uint *ahp) const
+{
+ uint h = 0;
+
+ if (d->numBuckets || ahp) {
+ h = qHash(akey, d->seed);
+ if (ahp)
+ *ahp = h;
+ }
+ return findNode(akey, h);
+}
+
+template <class Key, class T>
Q_OUTOFLINE_TEMPLATE bool QHash<Key, T>::operator==(const QHash &other) const
{
if (size() != other.size())
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-30 21:25:35 +0000