diff options
Diffstat (limited to 'src/corelib/tools/qhash.h')
-rw-r--r-- | src/corelib/tools/qhash.h | 174 |
1 files changed, 62 insertions, 112 deletions
diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h index a9ece12670..a18dd74706 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 { @@ -345,7 +249,7 @@ public: #ifdef Q_COMPILER_RVALUE_REFS 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; } + { QHash moved(std::move(other)); swap(moved); return *this; } #endif void swap(QHash &other) Q_DECL_NOTHROW { qSwap(d, other.d); } @@ -402,7 +306,7 @@ public: typedef T *pointer; typedef T &reference; - inline iterator() : i(0) { } + inline iterator() : i(Q_NULLPTR) { } explicit inline iterator(void *node) : i(reinterpret_cast<QHashData::Node *>(node)) { } inline const Key &key() const { return concrete(i)->key; } @@ -449,6 +353,7 @@ public: class const_iterator { friend class iterator; + friend class QSet<Key>; QHashData::Node *i; public: @@ -458,7 +363,7 @@ public: typedef const T *pointer; typedef const T &reference; - inline const_iterator() : i(0) { } + inline const_iterator() : i(Q_NULLPTR) { } explicit inline const_iterator(void *node) : i(reinterpret_cast<QHashData::Node *>(node)) { } #ifdef QT_STRICT_ITERATORS @@ -508,6 +413,31 @@ public: }; friend class const_iterator; + class key_iterator + { + const_iterator i; + + public: + typedef typename const_iterator::iterator_category iterator_category; + typedef typename const_iterator::difference_type difference_type; + typedef Key value_type; + typedef const Key *pointer; + typedef const Key &reference; + + explicit key_iterator(const_iterator o) : i(o) { } + + const Key &operator*() const { return i.key(); } + const Key *operator->() const { return &i.key(); } + bool operator==(key_iterator o) const { return i == o.i; } + bool operator!=(key_iterator o) const { return i != o.i; } + + inline key_iterator &operator++() { ++i; return *this; } + inline key_iterator operator++(int) { return key_iterator(i++);} + inline key_iterator &operator--() { --i; return *this; } + inline key_iterator operator--(int) { return key_iterator(i--); } + const_iterator base() const { return i; } + }; + // STL style inline iterator begin() { detach(); return iterator(d->firstNode()); } inline const_iterator begin() const { return const_iterator(d->firstNode()); } @@ -517,6 +447,9 @@ public: inline const_iterator end() const { return const_iterator(e); } inline const_iterator cend() const { return const_iterator(e); } inline const_iterator constEnd() const { return const_iterator(e); } + inline key_iterator keyBegin() const { return key_iterator(begin()); } + inline key_iterator keyEnd() const { return key_iterator(end()); } + iterator erase(iterator it); // more Qt @@ -546,7 +479,8 @@ public: private: void detach_helper(); void freeData(QHashData *d); - Node **findNode(const Key &key, uint *hp = 0) const; + Node **findNode(const Key &key, uint *hp = Q_NULLPTR) 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); @@ -590,7 +524,7 @@ template <class Key, class T> Q_INLINE_TEMPLATE void QHash<Key, T>::duplicateNode(QHashData::Node *node, void *newNode) { Node *concreteNode = concrete(node); - new (newNode) Node(concreteNode->key, concreteNode->value, concreteNode->h, 0); + new (newNode) Node(concreteNode->key, concreteNode->value, concreteNode->h, Q_NULLPTR); } template <class Key, class T> @@ -942,17 +876,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 +892,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()) @@ -994,7 +935,7 @@ template <class Key, class T> class QMultiHash : public QHash<Key, T> { public: - QMultiHash() {} + QMultiHash() Q_DECL_NOTHROW {} #ifdef Q_COMPILER_INITIALIZER_LISTS inline QMultiHash(std::initializer_list<std::pair<Key,T> > list) { @@ -1003,8 +944,14 @@ public: insert(it->first, it->second); } #endif + // compiler-generated copy/move ctors/assignment operators are fine! + // compiler-generated destructor is fine! + QMultiHash(const QHash<Key, T> &other) : QHash<Key, T>(other) {} - void swap(QMultiHash &other) { QHash<Key, T>::swap(other); } // prevent QMultiHash<->QHash swaps +#ifdef Q_COMPILER_RVALUE_REFS + QMultiHash(QHash<Key, T> &&other) Q_DECL_NOTHROW : QHash<Key, T>(std::move(other)) {} +#endif + void swap(QMultiHash &other) Q_DECL_NOTHROW { 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); } @@ -1093,6 +1040,9 @@ Q_INLINE_TEMPLATE int QMultiHash<Key, T>::count(const Key &key, const T &value) return n; } +Q_CORE_EXPORT int qGlobalQHashSeed(); +Q_CORE_EXPORT void qSetGlobalQHashSeed(int newSeed); + Q_DECLARE_ASSOCIATIVE_ITERATOR(Hash) Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Hash) |