summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/corelib/doc/snippets/code/src_corelib_tools_qhash.cpp14
-rw-r--r--src/corelib/tools/qhash.cpp85
-rw-r--r--src/corelib/tools/qhash.h40
-rw-r--r--tests/auto/corelib/tools/qhashfunctions/tst_qhashfunctions.cpp66
4 files changed, 205 insertions, 0 deletions
diff --git a/src/corelib/doc/snippets/code/src_corelib_tools_qhash.cpp b/src/corelib/doc/snippets/code/src_corelib_tools_qhash.cpp
index aa0473964c..0195b07b54 100644
--- a/src/corelib/doc/snippets/code/src_corelib_tools_qhash.cpp
+++ b/src/corelib/doc/snippets/code/src_corelib_tools_qhash.cpp
@@ -307,3 +307,17 @@ inline uint qHash(const std::vector<int> &key, uint seed = 0)
return qHashBits(&key.front(), key.size() * sizeof(int), seed);
}
//! [qhashbits]
+
+//! [qhashrange]
+inline uint qHash(const std::vector<int> &key, uint seed = 0)
+{
+ return qHashRange(key.begin(), key.end(), seed);
+}
+//! [qhashrange]
+
+//! [qhashrangecommutative]
+inline uint qHash(const std::unordered_set<int> &key, uint seed = 0)
+{
+ return qHashRangeCommutative(key.begin(), key.end(), seed);
+}
+//! [qhashrangecommutative]
diff --git a/src/corelib/tools/qhash.cpp b/src/corelib/tools/qhash.cpp
index 6a08576f7e..b9dafc36b2 100644
--- a/src/corelib/tools/qhash.cpp
+++ b/src/corelib/tools/qhash.cpp
@@ -665,6 +665,85 @@ void QHashData::checkSanity()
Types \c T1 and \c T2 must be supported by qHash().
*/
+/*! \fn uint qHashRange(InputIterator first, InputIterator last, uint seed = 0)
+ \relates QHash
+ \since 5.5
+
+ Returns the hash value for the range [\a{first},\a{last}), using \a seed
+ to seed the calculation, by successively applying qHash() to each
+ element and combining the hash values into a single one.
+
+ The return value of this function depends on the order of elements
+ in the range. That means that
+
+ \code
+ {0, 1, 2}
+ \endcode
+
+ and
+ \code
+ {1, 2, 0}
+ \endcode
+
+ hash to \b{different} values. If order does not matter, for example for hash
+ tables, use qHashRangeCommutative() instead. If you are hashing raw
+ memory, use qHashBits().
+
+ Use this function only to implement qHash() for your own custom
+ types. For example, here's how you could implement a qHash() overload for
+ std::vector<int>:
+
+ \snippet code/src_corelib_tools_qhash.cpp qhashrange
+
+ It bears repeating that the implementation of qHashRange() - like
+ the qHash() overloads offered by Qt - may change at any time. You
+ \b{must not} rely on the fact that qHashRange() will give the same
+ results (for the same inputs) across different Qt versions, even
+ if qHash() for the element type would.
+
+ \sa qHashBits(), qHashRangeCommutative()
+*/
+
+/*! \fn uint qHashRangeCommutative(InputIterator first, InputIterator last, uint seed = 0)
+ \relates QHash
+ \since 5.5
+
+ Returns the hash value for the range [\a{first},\a{last}), using \a seed
+ to seed the calculation, by successively applying qHash() to each
+ element and combining the hash values into a single one.
+
+ The return value of this function does not depend on the order of
+ elements in the range. That means that
+
+ \code
+ {0, 1, 2}
+ \endcode
+
+ and
+ \code
+ {1, 2, 0}
+ \endcode
+
+ hash to the \b{same} values. If order matters, for example, for vectors
+ and arrays, use qHashRange() instead. If you are hashing raw
+ memory, use qHashBits().
+
+ Use this function only to implement qHash() for your own custom
+ types. For example, here's how you could implement a qHash() overload for
+ std::unordered_set<int>:
+
+ \snippet code/src_corelib_tools_qhash.cpp qhashrangecommutative
+
+ It bears repeating that the implementation of
+ qHashRangeCommutative() - like the qHash() overloads offered by Qt
+ - may change at any time. You \b{must not} rely on the fact that
+ qHashRangeCommutative() will give the same results (for the same
+ inputs) across different Qt versions, even if qHash() for the
+ element type would.
+
+ \sa qHashBits(), qHashRange()
+*/
+
/*! \fn uint qHashBits(const void *p, size_t len, uint seed = 0)
\relates QHash
\since 5.4
@@ -678,10 +757,16 @@ void QHashData::checkSanity()
\snippet code/src_corelib_tools_qhash.cpp qhashbits
+ This takes advantage of the fact that std::vector lays out its data
+ contiguously. If that is not the case, or the contained type has
+ padding, you should use qHashRange() instead.
+
It bears repeating that the implementation of qHashBits() - like
the qHash() overloads offered by Qt - may change at any time. You
\b{must not} rely on the fact that qHashBits() will give the same
results (for the same inputs) across different Qt versions.
+
+ \sa qHashRange(), qHashRangeCommutative()
*/
/*! \fn uint qHash(char key, uint seed = 0)
diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h
index 325799d165..2a2c840c23 100644
--- a/src/corelib/tools/qhash.h
+++ b/src/corelib/tools/qhash.h
@@ -1,6 +1,7 @@
/****************************************************************************
**
** Copyright (C) 2014 Digia Plc and/or its subsidiary(-ies).
+** Copyright (C) 2015 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Marc Mutz <marc.mutz@kdab.com>
** Contact: http://www.qt-project.org/legal
**
** This file is part of the QtCore module of the Qt Toolkit.
@@ -40,6 +41,7 @@
#include <QtCore/qpair.h>
#include <QtCore/qrefcount.h>
+#include <numeric> // for std::accumulate
#ifdef Q_COMPILER_INITIALIZER_LISTS
#include <initializer_list>
#endif
@@ -101,6 +103,44 @@ 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)))
{
diff --git a/tests/auto/corelib/tools/qhashfunctions/tst_qhashfunctions.cpp b/tests/auto/corelib/tools/qhashfunctions/tst_qhashfunctions.cpp
index fb038dd37a..38d39d247c 100644
--- a/tests/auto/corelib/tools/qhashfunctions/tst_qhashfunctions.cpp
+++ b/tests/auto/corelib/tools/qhashfunctions/tst_qhashfunctions.cpp
@@ -42,6 +42,11 @@
#include <QtTest/QtTest>
#include <qhash.h>
+#include <qtypetraits.h>
+
+#include <iterator>
+#include <sstream>
+#include <algorithm>
class tst_QHashFunctions : public QObject
{
@@ -51,6 +56,8 @@ private Q_SLOTS:
void fp_qhash_of_zero_is_zero();
void qthash_data();
void qthash();
+ void range();
+ void rangeCommutative();
};
void tst_QHashFunctions::qhash()
@@ -149,5 +156,64 @@ void tst_QHashFunctions::qthash()
QTEST(result, "hash");
}
+namespace SomeNamespace {
+ struct Hashable { int i; };
+ inline uint qHash(Hashable h, uint seed = 0)
+ { return QT_PREPEND_NAMESPACE(qHash)(h.i, seed); }
+}
+
+void tst_QHashFunctions::range()
+{
+ static const int ints[] = {0, 1, 2, 3, 4, 5};
+ static const size_t numInts = sizeof ints / sizeof *ints;
+
+ // empty range just gives the seed:
+ QCOMPARE(qHashRange(ints, ints, 0xdeadbeefU), 0xdeadbeefU);
+ // verify that order matters:
+ QVERIFY(qHashRange(ints, ints + numInts) !=
+ qHashRange(std::reverse_iterator<const int*>(ints + numInts), std::reverse_iterator<const int*>(ints)));
+
+ {
+ // verify that the input iterator category suffices:
+ std::stringstream sstream;
+ Q_STATIC_ASSERT((QtPrivate::is_same<std::input_iterator_tag, std::istream_iterator<int>::iterator_category>::value));
+ std::copy(ints, ints + numInts, std::ostream_iterator<int>(sstream, " "));
+ sstream.seekg(0);
+ std::istream_iterator<int> it(sstream), end;
+ QCOMPARE(qHashRange(ints, ints + numInts), qHashRange(it, end));
+ }
+
+ SomeNamespace::Hashable hashables[] = {{0}, {1}, {2}, {3}, {4}, {5}};
+ static const size_t numHashables = sizeof hashables / sizeof *hashables;
+ // compile check: is qHash() found using ADL?
+ (void)qHashRange(hashables, hashables + numHashables);
+}
+
+void tst_QHashFunctions::rangeCommutative()
+{
+ int ints[] = {0, 1, 2, 3, 4, 5};
+ static const size_t numInts = sizeof ints / sizeof *ints;
+
+ // empty range just gives the seed:
+ QCOMPARE(qHashRangeCommutative(ints, ints, 0xdeadbeefU), 0xdeadbeefU);
+ // verify that order doesn't matter:
+ QCOMPARE(qHashRangeCommutative(ints, ints + numInts),
+ qHashRangeCommutative(std::reverse_iterator<int*>(ints + numInts), std::reverse_iterator<int*>(ints)));
+
+ {
+ // verify that the input iterator category suffices:
+ std::stringstream sstream;
+ std::copy(ints, ints + numInts, std::ostream_iterator<int>(sstream, " "));
+ sstream.seekg(0);
+ std::istream_iterator<int> it(sstream), end;
+ QCOMPARE(qHashRangeCommutative(ints, ints + numInts), qHashRangeCommutative(it, end));
+ }
+
+ SomeNamespace::Hashable hashables[] = {{0}, {1}, {2}, {3}, {4}, {5}};
+ static const size_t numHashables = sizeof hashables / sizeof *hashables;
+ // compile check: is qHash() found using ADL?
+ (void)qHashRangeCommutative(hashables, hashables + numHashables);
+}
+
QTEST_APPLESS_MAIN(tst_QHashFunctions)
#include "tst_qhashfunctions.moc"
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-24 00:55:39 +0000