From 08373fb02d648544f091aa1aabfe5949ea83a0f8 Mon Sep 17 00:00:00 2001 From: Marc Mutz Date: Mon, 17 Mar 2014 15:44:29 +0100 Subject: 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 --- src/corelib/tools/qhash.cpp | 85 +++++++++++++++++++++++++++++++++++++++++++++ src/corelib/tools/qhash.h | 40 +++++++++++++++++++++ 2 files changed, 125 insertions(+) (limited to 'src/corelib/tools') 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: + + \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: + + \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 ** Contact: http://www.qt-project.org/legal ** ** This file is part of the QtCore module of the Qt Toolkit. @@ -40,6 +41,7 @@ #include #include +#include // for std::accumulate #ifdef Q_COMPILER_INITIALIZER_LISTS #include #endif @@ -101,6 +103,44 @@ template 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 + 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 + 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 +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 +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 inline uint qHash(const QPair &key, uint seed = 0) Q_DECL_NOEXCEPT_EXPR(noexcept(qHash(key.first, seed)) && noexcept(qHash(key.second, seed))) { -- cgit v1.2.3