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.h92
1 files changed, 57 insertions, 35 deletions
diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h
index 59a5251c50..e0387d4644 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)))
{
@@ -288,7 +328,7 @@ class QHash
static inline int alignOfNode() { return qMax<int>(sizeof(void*), Q_ALIGNOF(Node)); }
public:
- inline QHash() : d(const_cast<QHashData *>(&QHashData::shared_null)) { }
+ inline QHash() Q_DECL_NOTHROW : d(const_cast<QHashData *>(&QHashData::shared_null)) { }
#ifdef Q_COMPILER_INITIALIZER_LISTS
inline QHash(std::initializer_list<std::pair<Key,T> > list)
: d(const_cast<QHashData *>(&QHashData::shared_null))
@@ -298,19 +338,19 @@ public:
insert(it->first, it->second);
}
#endif
- inline QHash(const QHash<Key, T> &other) : d(other.d) { d->ref.ref(); if (!d->sharable) detach(); }
- inline ~QHash() { if (!d->ref.deref()) freeData(d); }
+ QHash(const QHash &other) : d(other.d) { d->ref.ref(); if (!d->sharable) detach(); }
+ ~QHash() { if (!d->ref.deref()) freeData(d); }
- QHash<Key, T> &operator=(const QHash<Key, T> &other);
+ QHash &operator=(const QHash &other);
#ifdef Q_COMPILER_RVALUE_REFS
- inline QHash(QHash<Key, T> &&other) : d(other.d) { other.d = const_cast<QHashData *>(&QHashData::shared_null); }
- inline QHash<Key, T> &operator=(QHash<Key, T> &&other)
+ QHash(QHash &&other) Q_DECL_NOTHROW : d(other.d) { other.d = const_cast<QHashData *>(&QHashData::shared_null); }
+ QHash &operator=(QHash &&other) Q_DECL_NOTHROW
{ qSwap(d, other.d); return *this; }
#endif
- inline void swap(QHash<Key, T> &other) { qSwap(d, other.d); }
+ void swap(QHash &other) Q_DECL_NOTHROW { qSwap(d, other.d); }
- bool operator==(const QHash<Key, T> &other) const;
- inline bool operator!=(const QHash<Key, T> &other) const { return !(*this == other); }
+ bool operator==(const QHash &other) const;
+ bool operator!=(const QHash &other) const { return !(*this == other); }
inline int size() const { return d->size; }
@@ -325,7 +365,7 @@ public:
#if QT_SUPPORTS(UNSHARABLE_CONTAINERS)
inline void setSharable(bool sharable) { if (!sharable) detach(); if (d != &QHashData::shared_null) d->sharable = sharable; }
#endif
- inline bool isSharedWith(const QHash<Key, T> &other) const { return d == other.d; }
+ bool isSharedWith(const QHash &other) const { return d == other.d; }
void clear();
@@ -488,7 +528,7 @@ public:
const_iterator constFind(const Key &key) const;
iterator insert(const Key &key, const T &value);
iterator insertMulti(const Key &key, const T &value);
- QHash<Key, T> &unite(const QHash<Key, T> &other);
+ QHash &unite(const QHash &other);
// STL compatibility
typedef T mapped_type;
@@ -564,9 +604,9 @@ QHash<Key, T>::createNode(uint ah, const Key &akey, const T &avalue, Node **anex
}
template <class Key, class T>
-Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::unite(const QHash<Key, T> &other)
+Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::unite(const QHash &other)
{
- QHash<Key, T> copy(other);
+ QHash copy(other);
const_iterator it = copy.constEnd();
while (it != copy.constBegin()) {
--it;
@@ -584,7 +624,7 @@ Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::freeData(QHashData *x)
template <class Key, class T>
Q_INLINE_TEMPLATE void QHash<Key, T>::clear()
{
- *this = QHash<Key,T>();
+ *this = QHash();
}
template <class Key, class T>
@@ -597,7 +637,7 @@ Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::detach_helper()
}
template <class Key, class T>
-Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::operator=(const QHash<Key, T> &other)
+Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::operator=(const QHash &other)
{
if (d != other.d) {
QHashData *o = other.d;
@@ -925,7 +965,7 @@ Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::Node **QHash<Key, T>::findNode(cons
}
template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE bool QHash<Key, T>::operator==(const QHash<Key, T> &other) const
+Q_OUTOFLINE_TEMPLATE bool QHash<Key, T>::operator==(const QHash &other) const
{
if (size() != other.size())
return false;
@@ -964,7 +1004,7 @@ public:
}
#endif
QMultiHash(const QHash<Key, T> &other) : QHash<Key, T>(other) {}
- inline void swap(QMultiHash<Key, T> &other) { QHash<Key, T>::swap(other); } // prevent QMultiHash<->QHash swaps
+ void swap(QMultiHash &other) { QHash<Key, T>::swap(other); } // prevent QMultiHash<->QHash swaps
inline typename QHash<Key, T>::iterator replace(const Key &key, const T &value)
{ return QHash<Key, T>::insert(key, value); }
@@ -977,29 +1017,11 @@ public:
inline QMultiHash operator+(const QMultiHash &other) const
{ QMultiHash result = *this; result += other; return result; }
-#if !defined(Q_NO_USING_KEYWORD) && !defined(Q_CC_RVCT)
- // RVCT compiler doesn't handle using-keyword right when used functions are overloaded in child class
using QHash<Key, T>::contains;
using QHash<Key, T>::remove;
using QHash<Key, T>::count;
using QHash<Key, T>::find;
using QHash<Key, T>::constFind;
-#else
- inline bool contains(const Key &key) const
- { return QHash<Key, T>::contains(key); }
- inline int remove(const Key &key)
- { return QHash<Key, T>::remove(key); }
- inline int count(const Key &key) const
- { return QHash<Key, T>::count(key); }
- inline int count() const
- { return QHash<Key, T>::count(); }
- inline typename QHash<Key, T>::iterator find(const Key &key)
- { return QHash<Key, T>::find(key); }
- inline typename QHash<Key, T>::const_iterator find(const Key &key) const
- { return QHash<Key, T>::find(key); }
- inline typename QHash<Key, T>::const_iterator constFind(const Key &key) const
- { return QHash<Key, T>::constFind(key); }
-#endif
bool contains(const Key &key, const T &value) const;
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-05 04:15:25 +0000