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.h164
1 files changed, 54 insertions, 110 deletions
diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h
index a9ece12670..e367cc0068 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())
@@ -1003,6 +944,9 @@ 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
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-19 09:16:23 +0000