diff options
author | Marc Mutz <marc.mutz@kdab.com> | 2014-03-17 15:44:29 +0100 |
---|---|---|
committer | Marc Mutz <marc.mutz@kdab.com> | 2015-01-09 12:05:35 +0100 |
commit | 08373fb02d648544f091aa1aabfe5949ea83a0f8 (patch) | |
tree | 99a5705fbe45b2ae11fa3227ad8dde87ca2c2bd8 /src/corelib/tools/qhash.h | |
parent | 62b67092eadd97d739b05aeac68d556e02d22f85 (diff) | |
download | qtbase-08373fb02d648544f091aa1aabfe5949ea83a0f8.tar.gz |
Add qHashRange and qHashRangeCommutative
qHashRange() takes an (input iterator) range and hashes each element, combining
the hash values using the hash combiner from Boost/N1837 with the magic number
0x9e3779b9, as described here:
http://stackoverflow.com/questions/4948780/magic-number-in-boosthash-combine
qHashRangeCommutative() does the same but with a cummutative combiner (unsigned
addition) to create hash values that are order-independent, e.g. for hashed
containers. The obvious combiner, XOR, is a bad one because it eliminates
duplicate elements. Signed addition cannot be used, since signed overflow
leads to undefined behavior.
[ChangeLog][QtCore] Added qHashRange() and qHashRangeCommutative() functions to aid
implementing qHash() overloads for custom types.
Change-Id: I3c2bbc9ce4bd0455262a70e0cf248486525e534f
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
Diffstat (limited to 'src/corelib/tools/qhash.h')
-rw-r--r-- | src/corelib/tools/qhash.h | 40 |
1 files changed, 40 insertions, 0 deletions
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))) { |